Line data Source code
1 : /**
2 : Copyright (c) 2021-2022 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : #ifndef STAPPLER_CORE_UTILS_SPHASHTABLE_H_
25 : #define STAPPLER_CORE_UTILS_SPHASHTABLE_H_
26 :
27 : #include "SPLog.h"
28 : #include "SPRef.h"
29 :
30 : namespace STAPPLER_VERSIONIZED stappler {
31 :
32 : class NamedRef : public RefBase<memory::StandartInterface> {
33 : public:
34 2102031 : virtual ~NamedRef() { }
35 : virtual StringView getName() const = 0;
36 : };
37 :
38 : struct NamedMem : memory::AllocPool {
39 1120800 : virtual ~NamedMem() { }
40 :
41 : StringView key;
42 : };
43 :
44 : using HashFunc = uint32_t (*)(const char *key, size_t *klen);
45 :
46 : template <typename Value>
47 : class HashTable;
48 :
49 : template <typename Value>
50 : struct HashTraits;
51 :
52 : template <>
53 : struct HashTraits<NamedRef *> {
54 : static uint32_t hash(uint32_t salt, const NamedRef *value) {
55 : auto name = value->getName();
56 : return hash::hash32(name.data(), name.size(), salt);
57 : }
58 :
59 : static bool equal(const NamedRef *l, const NamedRef *r) {
60 : return l == r;
61 : }
62 : };
63 :
64 : template <>
65 : struct HashTraits<Rc<NamedRef>> {
66 1725 : static uint32_t hash(uint32_t salt, const NamedRef *value) {
67 1725 : auto name = value->getName();
68 3450 : return hash::hash32(name.data(), name.size(), salt);
69 : }
70 :
71 1525 : static uint32_t hash(uint32_t salt, StringView value) {
72 1525 : return hash::hash32(value.data(), value.size(), salt);
73 : }
74 :
75 0 : static bool equal(const NamedRef *l, const NamedRef *r) {
76 0 : return l == r;
77 : }
78 :
79 1525 : static bool equal(const NamedRef *l, StringView value) {
80 1525 : return l->getName() == value;
81 : }
82 : };
83 :
84 : template <>
85 : struct HashTraits<NamedMem *> {
86 4128 : static uint32_t hash(uint32_t salt, const NamedMem *value) {
87 4128 : return hash::hash32(value->key.data(), value->key.size(), salt);
88 : }
89 :
90 130582 : static uint32_t hash(uint32_t salt, StringView value) {
91 130582 : return hash::hash32(value.data(), value.size(), salt);
92 : }
93 :
94 0 : static bool equal(const NamedMem *l, const NamedMem *r) {
95 0 : return l->key == r->key;
96 : }
97 :
98 11174 : static bool equal(const NamedMem *l, StringView value) {
99 11174 : return l->key == value;
100 : }
101 : };
102 :
103 : template <typename Value>
104 : struct HashTraitDiscovery;
105 :
106 : template <typename Value>
107 : struct HashTraitDiscovery<Rc<Value>> {
108 : using type = typename std::conditional<
109 : std::is_base_of<NamedRef, Value>::value,
110 : HashTraits<Rc<NamedRef>>,
111 : typename HashTraitDiscovery<Value *>::type>::type;
112 : };
113 :
114 : template <typename Value>
115 : struct HashTraitDiscovery<Value *> {
116 : using type = typename std::conditional<
117 : std::is_base_of<NamedMem, Value>::value,
118 : HashTraits<NamedMem *>,
119 : HashTraits<Value *>>::type;
120 : };
121 :
122 : template <typename Value>
123 : struct HashEntry {
124 : using Type = typename std::remove_cv<typename std::remove_reference<Value>::type>::type;
125 : using Traits = typename HashTraitDiscovery<Value>::type;
126 :
127 : template <typename ... Args>
128 295851 : static uint32_t getHash(uint32_t salt, Args && ... args) {
129 295851 : return Traits::hash(salt, std::forward<Args>(args)...);
130 : }
131 :
132 : template <typename ... Args>
133 85796 : static bool isEqual(const Value &l, Args && ... args) {
134 85796 : return Traits::equal(l, std::forward<Args>(args)...);
135 : }
136 :
137 : HashEntry *next;
138 : uint32_t hash;
139 : std::array<uint8_t, sizeof(Value)> data;
140 :
141 295093 : Value *get() { return (Value *)data.data(); }
142 2483288 : const Value *get() const { return (const Value *)data.data(); }
143 : };
144 :
145 : template <typename Value>
146 : struct HashIndex {
147 : using Type = typename std::remove_cv<typename std::remove_reference<Value>::type>::type;
148 :
149 : HashTable<Value> *ht;
150 : HashEntry<Type> **_bucket;
151 : HashEntry<Type> *_self;
152 : HashEntry<Type> *_next;
153 : uint32_t index;
154 :
155 124284 : HashIndex * next() {
156 124284 : if (_self) {
157 96910 : _bucket = &_self->next;
158 : }
159 124284 : _self = _next;
160 541098 : while (!_self) {
161 438743 : if (index > ht->max) {
162 21929 : _self = _next = nullptr;
163 21929 : _bucket = nullptr;
164 21929 : return nullptr;
165 : }
166 416814 : _self = ht->array[index];
167 416814 : _bucket = &ht->array[index];
168 416814 : ++ index;
169 : }
170 102355 : _next = _self->next;
171 102355 : return this;
172 : }
173 :
174 9427 : bool operator==(const HashIndex &l) const { return l.ht == ht && l._self == _self && l._next == _next && l.index == index; }
175 270549 : bool operator!=(const HashIndex &l) const { return l.ht != ht || l._self != _self || l._next != _next || l.index != index; }
176 :
177 96910 : HashIndex& operator++() { this->next(); return *this; }
178 : HashIndex operator++(int) { auto tmp = *this; this->next(); return tmp; }
179 :
180 122839 : Type & operator*() const { return *_self->get(); }
181 58751 : Type * operator->() const { return _self->get(); }
182 : };
183 :
184 : template <typename Value>
185 : struct ConstHashIndex {
186 : using Type = typename std::remove_cv<typename std::remove_reference<Value>::type>::type;
187 :
188 : const HashTable<Value> *ht;
189 : const HashEntry<Type> * const*_bucket;
190 : const HashEntry<Type> *_self;
191 : const HashEntry<Type> *_next;
192 : uint32_t index;
193 :
194 3069207 : ConstHashIndex * next() {
195 3069207 : if (_self) {
196 2430981 : _bucket = &_self->next;
197 : }
198 3069207 : _self = _next;
199 13344496 : while (!_self) {
200 10863135 : if (index > ht->max) {
201 587846 : _self = _next = nullptr;
202 587846 : return nullptr;
203 : }
204 10275289 : _self = ht->array[index];
205 10275289 : _bucket = &ht->array[index];
206 10275289 : ++ index;
207 : }
208 2481361 : _next = _self->next;
209 2481361 : return this;
210 : }
211 :
212 : bool operator==(const ConstHashIndex &l) const { return l.ht == ht && l._self == _self && l._next == _next && l.index == index; }
213 3022088 : bool operator!=(const ConstHashIndex &l) const { return l.ht != ht || l._self != _self || l._next != _next || l.index != index; }
214 :
215 2430981 : ConstHashIndex& operator++() { this->next(); return *this; }
216 : ConstHashIndex operator++(int) { auto tmp = *this; this->next(); return tmp; }
217 :
218 2483124 : const Type & operator*() const { return *_self->get(); }
219 167 : const Type * operator->() const { return _self->get(); }
220 : };
221 :
222 : template <typename Value>
223 : class HashTable {
224 : public:
225 : using Pool = memory::pool_t;
226 : using ValueType = HashEntry<Value>;
227 :
228 : using merge_fn = void *(*)(Pool *p, const void *key, size_t klen, const void *h1_val, const void *h2_val, const void *data);
229 : using foreach_fn = bool (*)(void *rec, const void *key, size_t klen, const void *value);
230 :
231 : static constexpr auto INITIAL_MAX = 15; /* tunable == 2^n - 1 */
232 :
233 : using iterator = HashIndex<Value>;
234 : using const_iterator = ConstHashIndex<Value>;
235 :
236 2240 : HashTable(Pool *p = nullptr) {
237 2240 : if (!p) {
238 2194 : p = memory::pool::acquire();
239 : }
240 :
241 2240 : SPASSERT(p, "Pool should be defined");
242 :
243 2240 : auto now = Time::now().toMicros();
244 2240 : this->pool = p;
245 2240 : this->free = nullptr;
246 2240 : this->count = 0;
247 2240 : this->max = INITIAL_MAX;
248 2240 : this->seed = (unsigned int)((now >> 32) ^ now ^ (uintptr_t)pool ^ (uintptr_t)this ^ (uintptr_t)&now) - 1;
249 2240 : this->array = alloc_array(this->pool, max);
250 2240 : }
251 :
252 50 : HashTable(const HashTable ©, Pool *p = nullptr) {
253 50 : if (!p) {
254 50 : p = memory::pool::acquire();
255 : }
256 :
257 50 : SPASSERT(p, "Pool should be defined");
258 :
259 50 : this->pool = p;
260 50 : this->free = nullptr;
261 50 : this->count = copy.count;
262 50 : this->max = copy.max;
263 50 : this->seed = copy.seed;
264 50 : this->array = this->do_copy(copy.array, copy.max);
265 50 : }
266 :
267 25 : HashTable(HashTable &©, Pool *p = nullptr) {
268 25 : if (!p) {
269 25 : p = memory::pool::acquire();
270 : }
271 :
272 25 : SPASSERT(p, "Pool should be defined");
273 :
274 25 : this->pool = p;
275 25 : this->free = nullptr;
276 25 : this->count = copy.count;
277 25 : this->max = copy.max;
278 25 : this->seed = copy.seed;
279 :
280 25 : if (p == copy.pool) {
281 25 : this->array = this->do_copy(copy.array, copy.max);
282 : } else {
283 0 : this->free = copy.free; copy.free = nullptr;
284 0 : this->array = copy.array; copy.array = nullptr;
285 : }
286 25 : }
287 :
288 1419 : ~HashTable() {
289 1419 : if (count) {
290 598 : clear();
291 : }
292 :
293 1419 : if (array) {
294 1419 : memory::pool::free(pool, array, (max + 1) * sizeof(ValueType));
295 1419 : array = nullptr;
296 : }
297 1419 : }
298 :
299 : HashTable &operator=(const HashTable &other) {
300 : clear();
301 :
302 : if (array) {
303 : memory::pool::free(pool, array, (max + 1) * sizeof(ValueType));
304 : array = nullptr;
305 : }
306 :
307 : this->free = nullptr;
308 : this->count = other.count;
309 : this->max = other.max;
310 : this->seed = other.seed;
311 : this->array = this->do_copy(other.array, other.max);
312 :
313 : return *this;
314 : }
315 :
316 : HashTable &operator=(HashTable &&other) {
317 : clear();
318 :
319 : if (array) {
320 : memory::pool::free(pool, array, (max + 1) * sizeof(ValueType));
321 : array = nullptr;
322 : }
323 :
324 : this->free = nullptr;
325 : this->count = other.count;
326 : this->max = other.max;
327 : this->seed = other.seed;
328 :
329 : if (this->pool == other.pool) {
330 : this->array = this->do_copy(other.array, other.max);
331 : } else {
332 : this->free = other.free; other.free = nullptr;
333 : this->array = other.array; other.array = nullptr;
334 : }
335 :
336 : return *this;
337 : }
338 :
339 : template <typename ... Args>
340 200 : Pair<iterator, bool> assign(Args && ... args) {
341 200 : ValueType **hep = nullptr;
342 : iterator iter;
343 200 : auto ret = set_value(true, &hep, std::forward<Args>(args)...);
344 200 : iter._bucket = hep;
345 200 : iter._self = ret.first;
346 200 : iter._next = ret.first->next;
347 200 : iter.index = (ret.first->hash & this->max);
348 200 : iter.ht = this;
349 400 : return pair(iter, ret.second);
350 : }
351 :
352 : template <typename ... Args>
353 11858 : Pair<iterator, bool> emplace(Args && ... args) {
354 11858 : ValueType **hep = nullptr;
355 : iterator iter;
356 11858 : auto ret = set_value(false, &hep, std::forward<Args>(args)...);
357 11858 : iter._bucket = hep;
358 11858 : iter._self = ret.first;
359 11858 : iter._next = ret.first->next;
360 11858 : iter.index = (ret.first->hash & this->max);
361 11858 : iter.ht = this;
362 23716 : return pair(iter, ret.second);
363 : }
364 :
365 : template <typename ... Args>
366 25 : bool contains(Args && ... args) const {
367 25 : if (auto ret = get_value(nullptr, std::forward<Args>(args)...)) {
368 25 : return true;
369 : }
370 0 : return false;
371 : }
372 :
373 : template <typename ... Args>
374 157567 : iterator find(Args && ... args) {
375 157567 : ValueType **hep = nullptr;
376 157567 : if (auto ret = get_value(&hep, std::forward<Args>(args)...)) {
377 : iterator iter;
378 76573 : iter._bucket = hep;
379 76573 : iter._self = ret;
380 76573 : iter._next = ret->next;
381 76573 : iter.index = (ret->hash & this->max);
382 76573 : iter.ht = this;
383 76573 : return iter;
384 : }
385 80994 : return end();
386 : }
387 :
388 : template <typename ... Args>
389 3240 : const_iterator find(Args && ... args) const {
390 3240 : ValueType **hep = nullptr;
391 3240 : if (auto ret = get_value(&hep, std::forward<Args>(args)...)) {
392 : const_iterator iter;
393 1901 : iter._bucket = hep;
394 1901 : iter._self = ret;
395 1901 : iter._next = ret->next;
396 1901 : iter.index = (ret->hash & this->max);
397 1901 : iter.ht = this;
398 1901 : return iter;
399 : }
400 1339 : return end();
401 : }
402 :
403 : template <typename ... Args>
404 122145 : const typename ValueType::Type get(Args && ... args) const {
405 122145 : if (auto ret = get_value(nullptr, std::forward<Args>(args)...)) {
406 6897 : return *ret->get();
407 : }
408 115248 : return nullptr;
409 : }
410 :
411 6647 : iterator erase(iterator iter) {
412 6647 : if (this->count == 0) {
413 0 : return end();
414 : }
415 6647 : ValueType *old = *iter._bucket;
416 6647 : *iter._bucket = (*iter._bucket)->next;
417 6647 : old->next = this->free;
418 6647 : old->get()->~Value();
419 6647 : this->free = old;
420 6647 : --this->count;
421 :
422 : // bucket already points to next, try to offset _self quickly
423 6647 : iter._self = iter._next;
424 6647 : if (iter._self) {
425 1052 : iter._next = iter._self->next;
426 : } else {
427 : // or search for next hash bucket
428 5595 : iter.next();
429 : }
430 :
431 6647 : if (this->count == 0) {
432 105 : return end();
433 : }
434 6542 : return iter;
435 : }
436 :
437 : template <typename ... Args>
438 416 : iterator erase(Args && ... args) {
439 : ValueType **hep, *he;
440 416 : const auto hash = ValueType::getHash(seed, std::forward<Args>(args)...);
441 416 : const auto idx = hash & this->max;
442 :
443 : /* scan linked list */
444 536 : for (hep = &this->array[idx], he = *hep; he; hep = &he->next, he = *hep) {
445 520 : if (he->hash == hash && ValueType::isEqual(*he->get(), std::forward<Args>(args)...)) {
446 400 : break;
447 : }
448 : }
449 :
450 416 : if (he) {
451 : // make iterator for current cell
452 : iterator iter;
453 400 : iter._bucket = hep;
454 400 : iter._self = he;
455 400 : iter._next = he->next;
456 400 : iter.index = (he->hash & this->max);
457 400 : iter.ht = this;
458 :
459 400 : return erase(iter);
460 : } else {
461 16 : return end();
462 : }
463 : }
464 :
465 132972 : size_t size() const { return count; }
466 9986 : bool empty() const { return count == 0; }
467 :
468 25 : void reserve(size_t c) {
469 25 : if (!this->array) {
470 : if constexpr (sizeof(size_t) == 8) {
471 0 : do_allocate_array(math::npot(uint64_t(c)) - 1);
472 : } else {
473 : do_allocate_array(math::npot(uint32_t(c)) - 1);
474 : }
475 0 : return;
476 : }
477 :
478 25 : if (c <= this->count) {
479 0 : return;
480 : }
481 :
482 25 : if (c > this->max) {
483 25 : expand_array(this, c);
484 : }
485 :
486 25 : auto mem = (ValueType *)memory::pool::palloc(this->pool, sizeof(ValueType) * (c - this->count));
487 :
488 775 : for (size_t i = this->count; i < c; ++ i) {
489 750 : mem->next = free;
490 750 : free = mem;
491 750 : ++ mem;
492 : }
493 : }
494 :
495 924 : void clear() {
496 924 : if (!array) {
497 0 : return;
498 : }
499 :
500 21900 : for (size_t i = 0; i <= max; ++ i) {
501 20976 : auto v = array[i];
502 25306 : while (v) {
503 4330 : auto tmp = v;
504 4330 : v = v->next;
505 :
506 4330 : tmp->next = free;
507 4330 : free = tmp;
508 4330 : tmp->get()->~Value();
509 : }
510 20976 : array[i] = nullptr;
511 : }
512 :
513 924 : count = 0;
514 : }
515 :
516 21779 : iterator begin() {
517 21779 : if (!array) {
518 0 : return end();
519 : }
520 :
521 : HashIndex<Value> hi;
522 21779 : hi.ht = this;
523 21779 : hi.index = 0;
524 21779 : hi._bucket = nullptr;
525 21779 : hi._self = nullptr;
526 21779 : hi._next = nullptr;
527 21779 : hi.next();
528 21779 : return hi;
529 : }
530 349787 : iterator end() {
531 : HashIndex<Value> hi;
532 349787 : hi.ht = this;
533 349787 : hi.index = this->max + 1;
534 349787 : hi._bucket = nullptr;
535 349787 : hi._self = nullptr;
536 349787 : hi._next = nullptr;
537 349787 : return hi;
538 : }
539 :
540 638255 : const_iterator begin() const {
541 638255 : if (!array) {
542 0 : return end();
543 : }
544 :
545 : ConstHashIndex<Value> hi;
546 638255 : hi.ht = this;
547 638255 : hi.index = 0;
548 638255 : hi._bucket = nullptr;
549 638255 : hi._self = nullptr;
550 638255 : hi._next = nullptr;
551 638255 : hi.next();
552 638259 : return hi;
553 : }
554 :
555 592446 : const_iterator end() const {
556 : ConstHashIndex<Value> hi;
557 592446 : hi.ht = this;
558 592446 : hi.index = this->max + 1;
559 592446 : hi._bucket = nullptr;
560 592446 : hi._self = nullptr;
561 592446 : hi._next = nullptr;
562 592446 : return hi;
563 : }
564 :
565 50 : size_t get_cell_count() const {
566 50 : if (!array) {
567 0 : return 0;
568 : }
569 :
570 50 : size_t count = 0;
571 1250 : for (size_t i = 0; i <= max; ++ i) {
572 1200 : if (array[i]) {
573 533 : ++ count;
574 : }
575 : }
576 50 : return count;
577 : }
578 :
579 50 : size_t get_free_count() const {
580 50 : size_t count = 0;
581 50 : auto f = free;
582 800 : while (f) {
583 750 : f = f->next;
584 750 : ++ count;
585 : }
586 50 : return count;
587 : }
588 :
589 : uint32_t get_seed() const { return seed; }
590 :
591 : private:
592 : friend struct HashIndex<Value>;
593 : friend struct ConstHashIndex<Value>;
594 :
595 7190 : ValueType *allocate_value() {
596 7190 : return (ValueType *)memory::pool::palloc(this->pool, sizeof(ValueType));
597 : }
598 :
599 2485 : static HashEntry<Value> **alloc_array(memory::pool_t *p, uint32_t max) {
600 2485 : return (ValueType **)memory::pool::calloc(p, max + 1, sizeof(ValueType));
601 : }
602 :
603 170 : static void expand_array(HashTable *ht, uint32_t new_max = 0) {
604 : HashEntry<Value> **new_array;
605 :
606 170 : if (!new_max) {
607 145 : new_max = ht->max * 2 + 1;
608 : } else {
609 25 : new_max = math::npot(new_max) - 1;
610 25 : if (new_max <= ht->max) {
611 0 : return;
612 : }
613 : }
614 :
615 170 : new_array = alloc_array(ht->pool, new_max);
616 :
617 170 : auto end = ht->end();
618 170 : auto hi = ht->begin();
619 3946 : while (hi != end) {
620 3776 : uint32_t i = hi._self->hash & new_max;
621 3776 : hi._self->next = new_array[i];
622 3776 : new_array[i] = hi._self;
623 3776 : ++ hi;
624 : }
625 :
626 170 : memory::pool::free(ht->pool, ht->array, (ht->max + 1) * sizeof(ValueType));
627 :
628 170 : ht->array = new_array;
629 170 : ht->max = new_max;
630 : }
631 :
632 : template <typename ... Args>
633 283373 : ValueType * get_value(ValueType ***bucket, Args && ... args) const {
634 283373 : if (!this->array) {
635 0 : return nullptr;
636 : }
637 :
638 : ValueType **hep, *he;
639 283373 : const auto hash = ValueType::getHash(seed, std::forward<Args>(args)...);
640 283373 : const auto idx = hash & this->max;
641 :
642 : /* scan linked list */
643 449616 : for (hep = &this->array[idx], he = *hep; he; hep = &he->next, he = *hep) {
644 251639 : if (he->hash == hash && ValueType::isEqual(*he->get(), std::forward<Args>(args)...)) {
645 85396 : break;
646 : }
647 : }
648 :
649 283373 : if (bucket) {
650 161195 : *bucket = hep;
651 : }
652 283373 : return he;
653 : }
654 :
655 : template <typename ... Args>
656 12058 : Pair<ValueType *, bool> set_value(bool replace, ValueType ***bucket, Args && ... args) {
657 12058 : if (!this->array) {
658 0 : do_allocate_array(INITIAL_MAX);
659 : }
660 :
661 : ValueType **hep, *he;
662 12058 : const auto hash = ValueType::getHash(seed, std::forward<Args>(args)...);
663 12058 : const auto idx = hash & this->max;
664 :
665 : /* scan linked list */
666 18387 : for (hep = &this->array[idx], he = *hep; he; hep = &he->next, he = *hep) {
667 6329 : if (he->hash == hash && ValueType::isEqual(*he->get(), std::forward<Args>(args)...)) {
668 0 : break;
669 : }
670 : }
671 :
672 12058 : if (he) {
673 0 : if (replace) {
674 0 : he->get()->~Value();
675 0 : new (he->data.data()) Value(std::forward<Args>(args)...);
676 : }
677 0 : if (bucket) {
678 0 : *bucket = hep;
679 : }
680 0 : return pair(he, false);
681 : } else {
682 : /* add a new entry for non-NULL values */
683 12058 : if ((he = this->free) != NULL) {
684 4868 : this->free = he->next;
685 : } else {
686 7190 : he = allocate_value();
687 : }
688 :
689 12058 : this->count++;
690 12058 : he->next = NULL;
691 12058 : he->hash = hash;
692 12058 : new (he->data.data()) Value(std::forward<Args>(args)...);
693 :
694 12058 : *hep = he;
695 :
696 : /* check that the collision rate isn't too high */
697 12058 : if (this->count > this->max) {
698 145 : expand_array(this);
699 : }
700 12058 : if (bucket) {
701 12058 : *bucket = hep;
702 : }
703 12058 : return pair(he, true);
704 : }
705 : }
706 :
707 75 : HashEntry<Value> ** do_copy(HashEntry<Value> **copy_array, uint32_t copy_max) {
708 75 : auto new_array = alloc_array(this->pool, copy_max);
709 75 : auto new_vals = (HashEntry<Value> *)memory::pool::palloc(this->pool, sizeof(ValueType) * this->count);
710 :
711 75 : size_t j = 0;
712 1275 : for (size_t i = 0; i <= copy_max; i++) {
713 1200 : auto target = &new_array[i];
714 1200 : auto orig_entry = copy_array[i];
715 1975 : while (orig_entry) {
716 775 : auto new_entry = &new_vals[j++];
717 775 : new_entry->next = nullptr;
718 775 : new_entry->hash = orig_entry->hash;
719 775 : new (new_entry->data.data()) Value(*orig_entry->get());
720 775 : *target = new_entry;
721 775 : target = &new_entry->next;
722 775 : orig_entry = orig_entry->next;
723 : }
724 : }
725 75 : return new_array;
726 : }
727 :
728 0 : void do_allocate_array(uint32_t max) {
729 0 : auto now = Time::now().toMicros();
730 0 : this->count = 0;
731 0 : this->max = max;
732 0 : this->seed = (unsigned int)((now >> 32) ^ now ^ (uintptr_t)pool ^ (uintptr_t)this ^ (uintptr_t)&now) - 1;
733 0 : this->array = alloc_array(this->pool, this->max);
734 0 : }
735 :
736 : Pool *pool = nullptr;
737 : HashEntry<Value> **array;
738 : uint32_t count, max, seed;
739 : HashEntry<Value> *free = nullptr; /* List of recycled entries */
740 : };
741 :
742 : }
743 :
744 : #endif /* STAPPLER_CORE_UTILS_SPHASHTABLE_H_ */
|
