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 263