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