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 14 #include "src/__support/CPP/iterator.h" 15 16 namespace LIBC_NAMESPACE { 17 18 // A fixed size data store backed by an underlying cpp::array data structure. It 19 // supports vector like API but is not resizable like a vector. 20 template <typename T, size_t CAPACITY> class FixedVector { 21 cpp::array<T, CAPACITY> store; 22 size_t item_count = 0; 23 24 public: 25 constexpr FixedVector() = default; 26 27 using iterator = typename cpp::array<T, CAPACITY>::iterator; FixedVector(iterator begin,iterator end)28 constexpr FixedVector(iterator begin, iterator end) { 29 for (; begin != end; ++begin) 30 push_back(*begin); 31 } 32 FixedVector(size_t count,const T & value)33 constexpr FixedVector(size_t count, const T &value) { 34 for (size_t i = 0; i < count; ++i) 35 push_back(value); 36 } 37 push_back(const T & obj)38 bool push_back(const T &obj) { 39 if (item_count == CAPACITY) 40 return false; 41 store[item_count] = obj; 42 ++item_count; 43 return true; 44 } 45 back()46 const T &back() const { return store[item_count - 1]; } 47 back()48 T &back() { return store[item_count - 1]; } 49 pop_back()50 bool pop_back() { 51 if (item_count == 0) 52 return false; 53 --item_count; 54 return true; 55 } 56 57 T &operator[](size_t idx) { return store[idx]; } 58 59 const T &operator[](size_t idx) const { return store[idx]; } 60 empty()61 bool empty() const { return item_count == 0; } 62 size()63 size_t size() const { return item_count; } 64 65 // Empties the store for all practical purposes. reset()66 void reset() { item_count = 0; } 67 68 // This static method does not free up the resources held by |store|, 69 // say by calling `free` or something similar. It just does the equivalent 70 // of the `reset` method. Considering that FixedVector is of fixed storage, 71 // a `destroy` method like this should not be required. However, FixedVector 72 // is used in a few places as an alternate for data structures which use 73 // dynamically allocated storate. So, the `destroy` method like this 74 // matches the `destroy` API of those other data structures so that users 75 // can easily swap one data structure for the other. destroy(FixedVector<T,CAPACITY> * store)76 static void destroy(FixedVector<T, CAPACITY> *store) { store->reset(); } 77 78 using reverse_iterator = typename cpp::array<T, CAPACITY>::reverse_iterator; rbegin()79 LIBC_INLINE constexpr reverse_iterator rbegin() { 80 return reverse_iterator{&store[item_count]}; 81 } rend()82 LIBC_INLINE constexpr reverse_iterator rend() { return store.rend(); } 83 begin()84 LIBC_INLINE constexpr iterator begin() { return store.begin(); } end()85 LIBC_INLINE constexpr iterator end() { return iterator{&store[item_count]}; } 86 }; 87 88 } // namespace LIBC_NAMESPACE 89 90 #endif // LLVM_LIBC_SRC___SUPPORT_FIXEDVECTOR_H 91