libc/src/__support/fixedvector.h

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