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_SUPPORT_BLOCKSTORE_H
  10 #define LLVM_LIBC_SUPPORT_BLOCKSTORE_H
  11
  12 #include <src/__support/CPP/new.h>
  13 #include <src/__support/libc_assert.h>
  14
  15 #include <stddef.h>
  16 #include <stdint.h>
  17
  18 namespace __llvm_libc {
  19 namespace cpp {
  20
  21 // The difference between BlockStore a traditional vector types is that,
  22 // when more capacity is desired, a new block is added instead of allocating
  23 // a larger sized array and copying over existing items to the new allocation.
  24 // Also, the initial block does not need heap allocation. Hence, a BlockStore is
  25 // suitable for global objects as it does not require explicit construction.
  26 // Also, the destructor of this class does nothing, which eliminates the need
  27 // for an atexit global object destruction. But, it also means that the global
  28 // object should be explicitly cleaned up at the appropriate time.
  29 //
  30 // If REVERSE_ORDER is true, the iteration of elements will in the reverse
  31 // order. Also, since REVERSE_ORDER is a constexpr, conditionals branching
  32 // on its value will be optimized out in the code below.
  33 template <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER = false>
  34 class BlockStore {
  35 protected:
  36   struct Block {
  37     alignas(T) uint8_t data[BLOCK_SIZE * sizeof(T)] = {0};
  38     Block *next = nullptr;
  39   };
  40
  41   Block first;
  42   Block *current = &first;
  43   size_t fill_count = 0;
  44
  45   struct Pair {
  46     Block *first, *second;
  47   };
  48   Pair getLastBlocks() {
  49     if (REVERSE_ORDER)
  50       return {current, current->next};
  51     Block *prev = nullptr;
  52     Block *curr = &first;
  53     for (; curr->next; prev = curr, curr = curr->next)
  54       ;
  55     LIBC_ASSERT(curr == current);
  56     return {curr, prev};
  57   }
  58
  59   Block *getLastBlock() { return getLastBlocks().first; }
  60
  61 public:
  62   constexpr BlockStore() = default;
  63   ~BlockStore() = default;
  64
  65   class iterator {
  66     Block *block;
  67     size_t index;
  68
  69   public:
  70     constexpr iterator(Block *b, size_t i) : block(b), index(i) {}
  71
  72     iterator &operator++() {
  73       if (REVERSE_ORDER) {
  74         if (index == 0)
  75           return *this;
  76
  77         --index;
  78         if (index == 0 && block->next != nullptr) {
  79           index = BLOCK_SIZE;
  80           block = block->next;
  81         }
  82       } else {
  83         if (index == BLOCK_SIZE)
  84           return *this;
  85
  86         ++index;
  87         if (index == BLOCK_SIZE && block->next != nullptr) {
  88           index = 0;
  89           block = block->next;
  90         }
  91       }
  92
  93       return *this;
  94     }
  95
  96     T &operator*() {
  97       size_t true_index = REVERSE_ORDER ? index - 1 : index;
  98       return *reinterpret_cast<T *>(block->data + sizeof(T) * true_index);
  99     }
 100
 101     bool operator==(const iterator &rhs) const {
 102       return block == rhs.block && index == rhs.index;
 103     }
 104
 105     bool operator!=(const iterator &rhs) const {
 106       return block != rhs.block || index != rhs.index;
 107     }
 108   };
 109
 110   static void destroy(BlockStore<T, BLOCK_SIZE, REVERSE_ORDER> *block_store);
 111
 112   T *new_obj() {
 113     if (fill_count == BLOCK_SIZE) {
 114       AllocChecker ac;
 115       auto new_block = new (ac) Block();
 116       if (!ac)
 117         return nullptr;
 118       if (REVERSE_ORDER) {
 119         new_block->next = current;
 120       } else {
 121         new_block->next = nullptr;
 122         current->next = new_block;
 123       }
 124       current = new_block;
 125       fill_count = 0;
 126     }
 127     T *obj = reinterpret_cast<T *>(current->data + fill_count * sizeof(T));
 128     ++fill_count;
 129     return obj;
 130   }
 131
 132   [[nodiscard]] bool push_back(const T &value) {
 133     T *ptr = new_obj();
 134     if (ptr == nullptr)
 135       return false;
 136     *ptr = value;
 137     return true;
 138   }
 139
 140   T &back() {
 141     return *reinterpret_cast<T *>(getLastBlock()->data +
 142                                   sizeof(T) * (fill_count - 1));
 143   }
 144
 145   void pop_back() {
 146     fill_count--;
 147     if (fill_count || current == &first)
 148       return;
 149     auto [last, prev] = getLastBlocks();
 150     if (REVERSE_ORDER) {
 151       LIBC_ASSERT(last == current);
 152       current = current->next;
 153     } else {
 154       LIBC_ASSERT(prev->next == last);
 155       current = prev;
 156       current->next = nullptr;
 157     }
 158     if (last != &first)
 159       delete last;
 160     fill_count = BLOCK_SIZE;
 161   }
 162
 163   bool empty() const { return current == &first && !fill_count; }
 164
 165   iterator begin() {
 166     if (REVERSE_ORDER)
 167       return iterator(current, fill_count);
 168     else
 169       return iterator(&first, 0);
 170   }
 171
 172   iterator end() {
 173     if (REVERSE_ORDER)
 174       return iterator(&first, 0);
 175     else
 176       return iterator(current, fill_count);
 177   }
 178 };
 179
 180 template <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER>
 181 void BlockStore<T, BLOCK_SIZE, REVERSE_ORDER>::destroy(
 182     BlockStore<T, BLOCK_SIZE, REVERSE_ORDER> *block_store) {
 183   if (REVERSE_ORDER) {
 184     auto current = block_store->current;
 185     while (current->next != nullptr) {
 186       auto temp = current;
 187       current = current->next;
 188       delete temp;
 189     }
 190   } else {
 191     auto current = block_store->first.next;
 192     while (current != nullptr) {
 193       auto temp = current;
 194       current = current->next;
 195       delete temp;
 196     }
 197   }
 198   block_store->current = nullptr;
 199   block_store->fill_count = 0;
 200 }
 201
 202 // A convenience type for reverse order block stores.
 203 template <typename T, size_t BLOCK_SIZE>
 204 using ReverseOrderBlockStore = BlockStore<T, BLOCK_SIZE, true>;
 205
 206 } // namespace cpp
 207 } // namespace __llvm_libc
 208
 209 #endif // LLVM_LIBC_SUPPORT_BLOCKSTORE_H