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
18namespace 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.
32template <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER = false>
33class BlockStore {
34protected:
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 };
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
58 Block *get_last_block() { return get_last_blocks().first; }
59
60public:
61 constexpr BlockStore() = default;
62 ~BlockStore() = default;
63
64 class Iterator {
65 Block *block;
66 size_t index;
67
68 public:
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
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
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
139 T &back() {
140 return *reinterpret_cast<T *>(get_last_block()->data +
141 sizeof(T) * (fill_count - 1));
142 }
143
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
162 bool empty() const { return current == &first && !fill_count; }
163
164 Iterator begin() {
165 if (REVERSE_ORDER)
166 return Iterator(current, fill_count);
167 else
168 return Iterator(&first, 0);
169 }
170
171 Iterator end() {
172 if (REVERSE_ORDER)
173 return Iterator(&first, 0);
174 else
175 return Iterator(current, fill_count);
176 }
177};
178
179template <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER>
180void 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.
202template <typename T, size_t BLOCK_SIZE>
203using ReverseOrderBlockStore = BlockStore<T, BLOCK_SIZE, true>;
204
205} // namespace LIBC_NAMESPACE
206
207#endif // LLVM_LIBC_SRC___SUPPORT_BLOCKSTORE_H
208

source code of libc/src/__support/blockstore.h