libc/src/__support/blockstore.h

   1 //===-- A data structure which stores data in blocks  -----------*- 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_BLOCKSTORE_H
  10 #define LLVM_LIBC_SRC___SUPPORT_BLOCKSTORE_H
  11
  12 #include "src/__support/CPP/array.h"
  13 #include "src/__support/CPP/new.h"
  14 #include "src/__support/CPP/type_traits.h"
  15 #include "src/__support/libc_assert.h"
  16 #include "src/__support/macros/config.h"
  17
  18 #include <stddef.h>
  19 #include <stdint.h>
  20
  21 namespace LIBC_NAMESPACE_DECL {
  22
  23 // The difference between BlockStore a traditional vector types is that,
  24 // when more capacity is desired, a new block is added instead of allocating
  25 // a larger sized array and copying over existing items to the new allocation.
  26 // Also, the initial block does not need heap allocation. Hence, a BlockStore is
  27 // suitable for global objects as it does not require explicit construction.
  28 // Also, the destructor of this class does nothing, which eliminates the need
  29 // for an atexit global object destruction. But, it also means that the global
  30 // object should be explicitly cleaned up at the appropriate time.
  31 //
  32 // If REVERSE_ORDER is true, the iteration of elements will in the reverse
  33 // order. Also, since REVERSE_ORDER is a constexpr, conditionals branching
  34 // on its value will be optimized out in the code below.
  35 template <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER = false>
  36 class BlockStore {
  37 protected:
  38   struct Block {
  39     alignas(T) uint8_t data[BLOCK_SIZE * sizeof(T)] = {0};
  40     Block *next = nullptr;
  41   };
  42
  43   Block first;
  44   Block *current = &first;
  45   size_t fill_count = 0;
  46
  47   struct Pair {
  48     Block *first, *second;
  49   };
  50   LIBC_INLINE Pair get_last_blocks() {
  51     if (REVERSE_ORDER)
  52       return {current, current->next};
  53     Block *prev = nullptr;
  54     Block *curr = &first;
  55     for (; curr->next; prev = curr, curr = curr->next)
  56       ;
  57     LIBC_ASSERT(curr == current);
  58     return {curr, prev};
  59   }
  60
  61   LIBC_INLINE Block *get_last_block() { return get_last_blocks().first; }
  62
  63 public:
  64   LIBC_INLINE constexpr BlockStore() = default;
  65   LIBC_INLINE ~BlockStore() = default;
  66
  67   class Iterator {
  68     Block *block;
  69     size_t index;
  70
  71   public:
  72     LIBC_INLINE constexpr Iterator(Block *b, size_t i) : block(b), index(i) {}
  73
  74     LIBC_INLINE Iterator &operator++() {
  75       if (REVERSE_ORDER) {
  76         if (index == 0)
  77           return *this;
  78
  79         --index;
  80         if (index == 0 && block->next != nullptr) {
  81           index = BLOCK_SIZE;
  82           block = block->next;
  83         }
  84       } else {
  85         if (index == BLOCK_SIZE)
  86           return *this;
  87
  88         ++index;
  89         if (index == BLOCK_SIZE && block->next != nullptr) {
  90           index = 0;
  91           block = block->next;
  92         }
  93       }
  94
  95       return *this;
  96     }
  97
  98     LIBC_INLINE T &operator*() {
  99       size_t true_index = REVERSE_ORDER ? index - 1 : index;
 100       return *reinterpret_cast<T *>(block->data + sizeof(T) * true_index);
 101     }
 102
 103     LIBC_INLINE Iterator operator+(int i) {
 104       LIBC_ASSERT(i >= 0 &&
 105                   "BlockStore iterators only support incrementation.");
 106       auto other = *this;
 107       for (int j = 0; j < i; ++j)
 108         ++other;
 109
 110       return other;
 111     }
 112
 113     LIBC_INLINE bool operator==(const Iterator &rhs) const {
 114       return block == rhs.block && index == rhs.index;
 115     }
 116
 117     LIBC_INLINE bool operator!=(const Iterator &rhs) const {
 118       return block != rhs.block || index != rhs.index;
 119     }
 120   };
 121
 122   LIBC_INLINE static void
 123   destroy(BlockStore<T, BLOCK_SIZE, REVERSE_ORDER> *block_store);
 124
 125   LIBC_INLINE T *new_obj() {
 126     if (fill_count == BLOCK_SIZE) {
 127       AllocChecker ac;
 128       auto new_block = new (ac) Block();
 129       if (!ac)
 130         return nullptr;
 131       if (REVERSE_ORDER) {
 132         new_block->next = current;
 133       } else {
 134         new_block->next = nullptr;
 135         current->next = new_block;
 136       }
 137       current = new_block;
 138       fill_count = 0;
 139     }
 140     T *obj = reinterpret_cast<T *>(current->data + fill_count * sizeof(T));
 141     ++fill_count;
 142     return obj;
 143   }
 144
 145   [[nodiscard]] LIBC_INLINE bool push_back(const T &value) {
 146     T *ptr = new_obj();
 147     if (ptr == nullptr)
 148       return false;
 149     *ptr = value;
 150     return true;
 151   }
 152
 153   LIBC_INLINE T &back() {
 154     return *reinterpret_cast<T *>(get_last_block()->data +
 155                                   sizeof(T) * (fill_count - 1));
 156   }
 157
 158   LIBC_INLINE void pop_back() {
 159     fill_count--;
 160     if (fill_count || current == &first)
 161       return;
 162     auto [last, prev] = get_last_blocks();
 163     if (REVERSE_ORDER) {
 164       LIBC_ASSERT(last == current);
 165       current = current->next;
 166     } else {
 167       LIBC_ASSERT(prev->next == last);
 168       current = prev;
 169       current->next = nullptr;
 170     }
 171     if (last != &first)
 172       delete last;
 173     fill_count = BLOCK_SIZE;
 174   }
 175
 176   LIBC_INLINE bool empty() const { return current == &first && !fill_count; }
 177
 178   LIBC_INLINE Iterator begin() {
 179     if (REVERSE_ORDER)
 180       return Iterator(current, fill_count);
 181     else
 182       return Iterator(&first, 0);
 183   }
 184
 185   LIBC_INLINE Iterator end() {
 186     if (REVERSE_ORDER)
 187       return Iterator(&first, 0);
 188     else
 189       return Iterator(current, fill_count);
 190   }
 191
 192   // Removes the element at pos, then moves all the objects after back by one to
 193   // fill the hole. It's assumed that pos is a valid iterator to somewhere in
 194   // this block_store.
 195   LIBC_INLINE void erase(Iterator pos) {
 196     const Iterator last_item = Iterator(current, fill_count);
 197     if (pos == last_item) {
 198       pop_back();
 199       return;
 200     }
 201
 202     if constexpr (REVERSE_ORDER) {
 203       // REVERSE: Iterate from begin to pos
 204       const Iterator range_end = pos;
 205       Iterator cur = begin();
 206       T prev_val = *cur;
 207       ++cur;
 208       T cur_val = *cur;
 209
 210       for (; cur != range_end; ++cur) {
 211         cur_val = *cur;
 212         *cur = prev_val;
 213         prev_val = cur_val;
 214       }
 215       // As long as this isn't the end we will always need to move at least one
 216       // item (since we know that pos isn't the last item due to the check
 217       // above).
 218       if (range_end != end())
 219         *cur = prev_val;
 220     } else {
 221       // FORWARD: Iterate from pos to end
 222       const Iterator range_end = end();
 223       Iterator cur = pos;
 224       Iterator prev = cur;
 225       ++cur;
 226
 227       for (; cur != range_end; prev = cur, ++cur)
 228         *prev = *cur;
 229     }
 230     pop_back();
 231   }
 232 };
 233
 234 template <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER>
 235 LIBC_INLINE void BlockStore<T, BLOCK_SIZE, REVERSE_ORDER>::destroy(
 236     BlockStore<T, BLOCK_SIZE, REVERSE_ORDER> *block_store) {
 237   if (REVERSE_ORDER) {
 238     auto current = block_store->current;
 239     while (current->next != nullptr) {
 240       auto temp = current;
 241       current = current->next;
 242       delete temp;
 243     }
 244   } else {
 245     auto current = block_store->first.next;
 246     while (current != nullptr) {
 247       auto temp = current;
 248       current = current->next;
 249       delete temp;
 250     }
 251   }
 252   block_store->current = nullptr;
 253   block_store->fill_count = 0;
 254 }
 255
 256 // A convenience type for reverse order block stores.
 257 template <typename T, size_t BLOCK_SIZE>
 258 using ReverseOrderBlockStore = BlockStore<T, BLOCK_SIZE, true>;
 259
 260 } // namespace LIBC_NAMESPACE_DECL
 261
 262 #endif // LLVM_LIBC_SRC___SUPPORT_BLOCKSTORE_H