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 };
get_last_blocks()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
get_last_block()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:
Iterator(Block * b,size_t i)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
new_obj()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
push_back(const T & value)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
back()153 LIBC_INLINE T &back() {
154 return *reinterpret_cast<T *>(get_last_block()->data +
155 sizeof(T) * (fill_count - 1));
156 }
157
pop_back()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
empty()176 LIBC_INLINE bool empty() const { return current == &first && !fill_count; }
177
begin()178 LIBC_INLINE Iterator begin() {
179 if (REVERSE_ORDER)
180 return Iterator(current, fill_count);
181 else
182 return Iterator(&first, 0);
183 }
184
end()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.
erase(Iterator pos)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>
destroy(BlockStore<T,BLOCK_SIZE,REVERSE_ORDER> * block_store)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