263 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_BLOCKSTORE_H10#define LLVM_LIBC_SRC___SUPPORT_BLOCKSTORE_H11 12#include "hdr/stdint_proxy.h"13#include "src/__support/CPP/array.h"14#include "src/__support/CPP/new.h"15#include "src/__support/CPP/type_traits.h"16#include "src/__support/libc_assert.h"17#include "src/__support/macros/config.h"18 19#include <stddef.h>20 21namespace 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 allocating25// 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 is27// suitable for global objects as it does not require explicit construction.28// Also, the destructor of this class does nothing, which eliminates the need29// for an atexit global object destruction. But, it also means that the global30// object should be explicitly cleaned up at the appropriate time.31//32// If REVERSE_ORDER is true, the iteration of elements will in the reverse33// order. Also, since REVERSE_ORDER is a constexpr, conditionals branching34// on its value will be optimized out in the code below.35template <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER = false>36class BlockStore {37protected: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 63public: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 void123 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 else182 return Iterator(&first, 0);183 }184 185 LIBC_INLINE Iterator end() {186 if (REVERSE_ORDER)187 return Iterator(&first, 0);188 else189 return Iterator(current, fill_count);190 }191 192 // Removes the element at pos, then moves all the objects after back by one to193 // fill the hole. It's assumed that pos is a valid iterator to somewhere in194 // 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 pos204 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 one216 // item (since we know that pos isn't the last item due to the check217 // above).218 if (range_end != end())219 *cur = prev_val;220 } else {221 // FORWARD: Iterate from pos to end222 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 234template <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER>235LIBC_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.257template <typename T, size_t BLOCK_SIZE>258using ReverseOrderBlockStore = BlockStore<T, BLOCK_SIZE, true>;259 260} // namespace LIBC_NAMESPACE_DECL261 262#endif // LLVM_LIBC_SRC___SUPPORT_BLOCKSTORE_H263