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)
|
18 | int __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 |
|
28 | using std::size_t;
|
29 | namespace 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 | */
|
36 | template <class T>
|
37 | class RandomInsertPiggyList {
|
38 | public:
|
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 |
|
142 | template <class T>
|
143 | class PiggyList {
|
144 | public:
|
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
|