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