OILS / vendor / souffle / datastructure / PiggyList.h View on Github | oilshell.org

336 lines, 185 significant
1#pragma once
2
3#include "souffle/utility/ParallelUtil.h"
4#include <array>
5#include <atomic>
6#include <cassert>
7#include <cstring>
8#include <iostream>
9#include <iterator>
10
11#ifdef _WIN32
12#include <intrin.h>
13/**
14 * Some versions of MSVC do not provide a builtin for counting leading zeroes
15 * like gcc, so we have to implement it ourselves.
16 */
17#if defined(_MSC_VER)
18int __inline __builtin_clzll(unsigned long long value) {
19#if _WIN64
20 return static_cast<int>(__lzcnt64(value));
21#else
22 return static_cast<int>(__lzcnt(value));
23#endif
24}
25#endif // _MSC_VER
26#endif // _WIN32
27
28using std::size_t;
29namespace souffle {
30
31/**
32 * A PiggyList that allows insertAt functionality.
33 * This means we can't append, as we don't know the next available element.
34 * insertAt is dangerous. You must be careful not to call it for the same index twice!
35 */
36template <class T>
37class RandomInsertPiggyList {
38public:
39 RandomInsertPiggyList() = default;
40 // an instance where the initial size is not 65k, and instead is user settable (to a power of
41 // initialbitsize)
42 RandomInsertPiggyList(std::size_t initialbitsize) : BLOCKBITS(initialbitsize) {}
43
44 /** copy constructor */
45 RandomInsertPiggyList(const RandomInsertPiggyList& other) : BLOCKBITS(other.BLOCKBITS) {
46 this->numElements.store(other.numElements.load());
47
48 // copy blocks from the old lookup table to this one
49 for (std::size_t i = 0; i < maxContainers; ++i) {
50 if (other.blockLookupTable[i].load() != nullptr) {
51 // calculate the size of that block
52 const std::size_t blockSize = INITIALBLOCKSIZE << i;
53
54 // allocate that in the new container
55 this->blockLookupTable[i].store(new T[blockSize]);
56
57 // then copy the stuff over
58 std::memcpy(this->blockLookupTable[i].load(), other.blockLookupTable[i].load(),
59 blockSize * sizeof(T));
60 }
61 }
62 }
63
64 // move ctr
65 RandomInsertPiggyList(RandomInsertPiggyList&& other) = delete;
66 // copy assign ctor
67 RandomInsertPiggyList& operator=(RandomInsertPiggyList& other) = delete;
68 // move assign ctor
69 RandomInsertPiggyList& operator=(RandomInsertPiggyList&& other) = delete;
70
71 ~RandomInsertPiggyList() {
72 freeList();
73 }
74
75 inline std::size_t size() const {
76 return numElements.load();
77 }
78
79 inline T* getBlock(std::size_t blockNum) const {
80 return blockLookupTable[blockNum];
81 }
82
83 inline T& get(std::size_t index) const {
84 std::size_t nindex = index + INITIALBLOCKSIZE;
85 std::size_t blockNum = (63 - __builtin_clzll(nindex));
86 std::size_t blockInd = (nindex) & ((1 << blockNum) - 1);
87 return this->getBlock(blockNum - BLOCKBITS)[blockInd];
88 }
89
90 void insertAt(std::size_t index, T value) {
91 // starting with an initial blocksize requires some shifting to transform into a nice powers of two
92 // series
93 std::size_t blockNum = (63 - __builtin_clzll(index + INITIALBLOCKSIZE)) - BLOCKBITS;
94
95 // allocate the block if not allocated
96 if (blockLookupTable[blockNum].load() == nullptr) {
97 slock.lock();
98 if (blockLookupTable[blockNum].load() == nullptr) {
99 blockLookupTable[blockNum].store(new T[INITIALBLOCKSIZE << blockNum]);
100 }
101 slock.unlock();
102 }
103
104 this->get(index) = value;
105 // we ALWAYS increment size, even if there was something there before (its impossible to tell!)
106 // the onus is up to the user to not call this for an index twice
107 ++numElements;
108 }
109
110 void clear() {
111 freeList();
112 numElements.store(0);
113 }
114 const std::size_t BLOCKBITS = 16ul;
115 const std::size_t INITIALBLOCKSIZE = (((std::size_t)1ul) << BLOCKBITS);
116
117 // number of elements currently stored within
118 std::atomic<std::size_t> numElements{0};
119
120 // 2^64 - 1 elements can be stored (default initialised to nullptrs)
121 static constexpr std::size_t maxContainers = 64;
122 std::array<std::atomic<T*>, maxContainers> blockLookupTable = {};
123
124 // for parallel node insertions
125 mutable SpinLock slock;
126
127 /**
128 * Free the arrays allocated within the linked list nodes
129 */
130 void freeList() {
131 slock.lock();
132 // delete all - deleting a nullptr is a no-op
133 for (std::size_t i = 0; i < maxContainers; ++i) {
134 delete[] blockLookupTable[i].load();
135 // reset the container within to be empty.
136 blockLookupTable[i].store(nullptr);
137 }
138 slock.unlock();
139 }
140};
141
142template <class T>
143class PiggyList {
144public:
145 PiggyList() : num_containers(0), container_size(0), m_size(0) {}
146 PiggyList(std::size_t initialbitsize)
147 : BLOCKBITS(initialbitsize), num_containers(0), container_size(0), m_size(0) {}
148
149 /** copy constructor */
150 PiggyList(const PiggyList& other) : BLOCKBITS(other.BLOCKBITS) {
151 num_containers.store(other.num_containers.load());
152 container_size.store(other.container_size.load());
153 m_size.store(other.m_size.load());
154 // copy each chunk from other into this
155 // the size of the next container to allocate
156 std::size_t cSize = BLOCKSIZE;
157 for (std::size_t i = 0; i < other.num_containers; ++i) {
158 this->blockLookupTable[i] = new T[cSize];
159 std::memcpy(this->blockLookupTable[i], other.blockLookupTable[i], cSize * sizeof(T));
160 cSize <<= 1;
161 }
162 // if this isn't the case, uhh
163 assert((cSize >> 1) == container_size.load());
164 }
165
166 /** move constructor */
167 PiggyList(PiggyList&& other) = delete;
168 /** copy assign ctor **/
169 PiggyList& operator=(const PiggyList& other) = delete;
170
171 ~PiggyList() {
172 freeList();
173 }
174
175 /**
176 * Well, returns the number of nodes exist within the list + number of nodes queued to be inserted
177 * The reason for this, is that there may be many nodes queued up
178 * that haven't had time to had containers created and updated
179 * @return the number of nodes exist within the list + number of nodes queued to be inserted
180 */
181 inline std::size_t size() const {
182 return m_size.load();
183 };
184
185 inline T* getBlock(std::size_t blocknum) const {
186 return this->blockLookupTable[blocknum];
187 }
188
189 std::size_t append(T element) {
190 std::size_t new_index = m_size.fetch_add(1, std::memory_order_acquire);
191
192 // will this not fit?
193 if (container_size < new_index + 1) {
194 sl.lock();
195 // check and add as many containers as required
196 while (container_size < new_index + 1) {
197 blockLookupTable[num_containers] = new T[allocsize];
198 num_containers += 1;
199 container_size += allocsize;
200 // double the number elements that will be allocated next time
201 allocsize <<= 1;
202 }
203 sl.unlock();
204 }
205
206 this->get(new_index) = element;
207 return new_index;
208 }
209
210 std::size_t createNode() {
211 std::size_t new_index = m_size.fetch_add(1, std::memory_order_acquire);
212
213 // will this not fit?
214 if (container_size < new_index + 1) {
215 sl.lock();
216 // check and add as many containers as required
217 while (container_size < new_index + 1) {
218 blockLookupTable[num_containers] = new T[allocsize];
219 num_containers += 1;
220 container_size += allocsize;
221 // double the number elements that will be allocated next time
222 allocsize <<= 1;
223 }
224 sl.unlock();
225 }
226
227 return new_index;
228 }
229
230 /**
231 * Retrieve a reference to the stored value at index
232 * @param index position to search
233 * @return the value at index
234 */
235 inline T& get(std::size_t index) const {
236 // supa fast 2^16 size first block
237 std::size_t nindex = index + BLOCKSIZE;
238 std::size_t blockNum = (63 - __builtin_clzll(nindex));
239 std::size_t blockInd = (nindex) & ((1 << blockNum) - 1);
240 return this->getBlock(blockNum - BLOCKBITS)[blockInd];
241 }
242
243 /**
244 * Clear all elements from the PiggyList
245 */
246 void clear() {
247 freeList();
248 m_size = 0;
249 num_containers = 0;
250
251 allocsize = BLOCKSIZE;
252 container_size = 0;
253 }
254
255 class iterator {
256 std::size_t cIndex = 0;
257 PiggyList* bl;
258
259 public:
260 using iterator_category = std::forward_iterator_tag;
261 using value_type = T;
262 using difference_type = void;
263 using pointer = T*;
264 using reference = T&;
265
266 // default ctor, to silence
267 iterator() = default;
268
269 /* begin iterator for iterating over all elements */
270 iterator(PiggyList* bl) : bl(bl){};
271 /* ender iterator for marking the end of the iteration */
272 iterator(PiggyList* bl, std::size_t beginInd) : cIndex(beginInd), bl(bl){};
273
274 T operator*() {
275 return bl->get(cIndex);
276 };
277 const T operator*() const {
278 return bl->get(cIndex);
279 };
280
281 iterator& operator++(int) {
282 ++cIndex;
283 return *this;
284 };
285
286 iterator operator++() {
287 iterator ret(*this);
288 ++cIndex;
289 return ret;
290 };
291
292 bool operator==(const iterator& x) const {
293 return x.cIndex == this->cIndex && x.bl == this->bl;
294 };
295
296 bool operator!=(const iterator& x) const {
297 return !(x == *this);
298 };
299 };
300
301 iterator begin() {
302 return iterator(this);
303 }
304 iterator end() {
305 return iterator(this, size());
306 }
307 const std::size_t BLOCKBITS = 16ul;
308 const std::size_t BLOCKSIZE = (((std::size_t)1ul) << BLOCKBITS);
309
310 // number of inserted
311 std::atomic<std::size_t> num_containers = 0;
312 std::size_t allocsize = BLOCKSIZE;
313 std::atomic<std::size_t> container_size = 0;
314 std::atomic<std::size_t> m_size = 0;
315
316 // > 2^64 elements can be stored (default initialise to nullptrs)
317 static constexpr std::size_t max_conts = 64;
318 std::array<T*, max_conts> blockLookupTable = {};
319
320 // for parallel node insertions
321 mutable SpinLock sl;
322
323 /**
324 * Free the arrays allocated within the linked list nodes
325 */
326 void freeList() {
327 sl.lock();
328 // we don't know which ones are taken up!
329 for (std::size_t i = 0; i < num_containers; ++i) {
330 delete[] blockLookupTable[i];
331 }
332 sl.unlock();
333 }
334};
335
336} // namespace souffle