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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_LIBC_SRC___SUPPORT_FIXEDVECTOR_H 10 #define LLVM_LIBC_SRC___SUPPORT_FIXEDVECTOR_H 11 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 18 namespace LIBC_NAMESPACE_DECL { 19 20 // A fixed size data store backed by an underlying cpp::array data structure. It 21 // supports vector like API but is not resizable like a vector. 22 template <typename T, size_t CAPACITY> class FixedVector { 23 cpp::array<T, CAPACITY> store; 24 size_t item_count = 0; 25 26 public: 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 equivalent 100 // of the `reset` method. Considering that FixedVector is of fixed storage, 101 // a `destroy` method like this should not be required. However, FixedVector 102 // is used in a few places as an alternate for data structures which use 103 // dynamically allocated storate. So, the `destroy` method like this 104 // matches the `destroy` API of those other data structures so that users 105 // 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_DECL 126 127 #endif // LLVM_LIBC_SRC___SUPPORT_FIXEDVECTOR_H 128