128 lines · c
1//===-- A data structure for a fixed capacity data store --------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_FIXEDVECTOR_H10#define LLVM_LIBC_SRC___SUPPORT_FIXEDVECTOR_H11 12#include "src/__support/CPP/array.h"13#include "src/__support/CPP/iterator.h"14#include "src/__support/libc_assert.h"15#include "src/__support/macros/config.h"16#include "src/string/memory_utils/inline_memset.h"17 18namespace LIBC_NAMESPACE_DECL {19 20// A fixed size data store backed by an underlying cpp::array data structure. It21// supports vector like API but is not resizable like a vector.22template <typename T, size_t CAPACITY> class FixedVector {23 cpp::array<T, CAPACITY> store;24 size_t item_count = 0;25 26public:27 LIBC_INLINE constexpr FixedVector() = default;28 29 using iterator = typename cpp::array<T, CAPACITY>::iterator;30 LIBC_INLINE constexpr FixedVector(iterator begin, iterator end)31 : store{}, item_count{} {32 LIBC_ASSERT(begin + CAPACITY >= end);33 for (; begin != end; ++begin)34 push_back(*begin);35 }36 37 using const_iterator = typename cpp::array<T, CAPACITY>::const_iterator;38 LIBC_INLINE constexpr FixedVector(const_iterator begin, const_iterator end)39 : store{}, item_count{} {40 LIBC_ASSERT(begin + CAPACITY >= end);41 for (; begin != end; ++begin)42 push_back(*begin);43 }44 45 LIBC_INLINE constexpr FixedVector(size_t count, const T &value)46 : store{}, item_count{} {47 LIBC_ASSERT(count <= CAPACITY);48 for (size_t i = 0; i < count; ++i)49 push_back(value);50 }51 52 LIBC_INLINE constexpr bool push_back(const T &obj) {53 if (item_count == CAPACITY)54 return false;55 store[item_count] = obj;56 ++item_count;57 return true;58 }59 60 LIBC_INLINE constexpr const T &back() const {61 LIBC_ASSERT(!empty());62 return store[item_count - 1];63 }64 65 LIBC_INLINE constexpr T &back() {66 LIBC_ASSERT(!empty());67 return store[item_count - 1];68 }69 70 LIBC_INLINE constexpr bool pop_back() {71 if (item_count == 0)72 return false;73 inline_memset(&store[item_count - 1], 0, sizeof(T));74 --item_count;75 return true;76 }77 78 LIBC_INLINE constexpr T &operator[](size_t idx) {79 LIBC_ASSERT(idx < item_count);80 return store[idx];81 }82 83 LIBC_INLINE constexpr const T &operator[](size_t idx) const {84 LIBC_ASSERT(idx < item_count);85 return store[idx];86 }87 88 LIBC_INLINE constexpr bool empty() const { return item_count == 0; }89 90 LIBC_INLINE constexpr size_t size() const { return item_count; }91 92 // Empties the store for all practical purposes.93 LIBC_INLINE constexpr void reset() {94 inline_memset(store.data(), 0, sizeof(T) * item_count);95 item_count = 0;96 }97 98 // This static method does not free up the resources held by |store|,99 // say by calling `free` or something similar. It just does the equivalent100 // of the `reset` method. Considering that FixedVector is of fixed storage,101 // a `destroy` method like this should not be required. However, FixedVector102 // is used in a few places as an alternate for data structures which use103 // dynamically allocated storate. So, the `destroy` method like this104 // matches the `destroy` API of those other data structures so that users105 // can easily swap one data structure for the other.106 LIBC_INLINE static void destroy(FixedVector<T, CAPACITY> *store) {107 store->reset();108 }109 110 using reverse_iterator = typename cpp::array<T, CAPACITY>::reverse_iterator;111 LIBC_INLINE constexpr reverse_iterator rbegin() {112 return reverse_iterator{&store[item_count]};113 }114 LIBC_INLINE constexpr reverse_iterator rend() { return store.rend(); }115 116 LIBC_INLINE constexpr iterator begin() { return store.begin(); }117 LIBC_INLINE constexpr iterator end() { return iterator{&store[item_count]}; }118 119 LIBC_INLINE constexpr const_iterator begin() const { return store.begin(); }120 LIBC_INLINE constexpr const_iterator end() const {121 return const_iterator{&store[item_count]};122 }123};124 125} // namespace LIBC_NAMESPACE_DECL126 127#endif // LLVM_LIBC_SRC___SUPPORT_FIXEDVECTOR_H128