Blender V5.3
BLI_ghash.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
11
12#include <algorithm>
13#include <climits>
14#include <cstdarg>
15#include <cstdlib>
16
17#include "MEM_guardedalloc.h"
18
19#include "BLI_math_base_c.hh"
20#include "BLI_mempool.hh"
21#include "BLI_sys_types.hh" /* for intptr_t support */
22#include "BLI_utildefines.hh"
23
24#define GHASH_INTERNAL_API
25#include "BLI_ghash.hh" /* own include */
26
27#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
28
29namespace blender {
30
31/* -------------------------------------------------------------------- */
34
35#define GHASH_USE_MODULO_BUCKETS
36
40static const uint hashsizes[] = {
41 5, 11, 17, 37, 67, 131, 257, 521, 1031,
42 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309,
43 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
44};
45
46#ifdef GHASH_USE_MODULO_BUCKETS
47# define GHASH_MAX_SIZE 27
48BLI_STATIC_ASSERT(ARRAY_SIZE(hashsizes) == GHASH_MAX_SIZE, "Invalid 'hashsizes' size");
49#else
50# define GHASH_BUCKET_BIT_MIN 2
51# define GHASH_BUCKET_BIT_MAX 28 /* About 268M of buckets... */
52#endif
53
62#define GHASH_LIMIT_GROW(_nbkt) (((_nbkt) * 3) / 4)
63#define GHASH_LIMIT_SHRINK(_nbkt) (((_nbkt) * 3) / 16)
64
65/* WARNING! Keep in sync with ugly _gh_Entry in header!!! */
66struct Entry {
68
69 void *key;
70};
71
72struct GHashEntry {
74
75 void *val;
76};
77
79
80#define GHASH_ENTRY_SIZE(_is_gset) ((_is_gset) ? sizeof(GSetEntry) : sizeof(GHashEntry))
81
82struct GHash {
85
90#ifdef GHASH_USE_MODULO_BUCKETS
92#else
93 uint bucket_mask, bucket_bit, bucket_bit_min;
94#endif
95
98};
99
101
102/* -------------------------------------------------------------------- */
105
107 Entry *dst,
108 const GHash *gh_src,
109 const Entry *src,
110 GHashKeyCopyFP keycopyfp,
111 GHashValCopyFP valcopyfp)
112{
113 dst->key = (keycopyfp) ? keycopyfp(src->key) : src->key;
114
115 if ((gh_dst->flag & GHASH_FLAG_IS_GSET) == 0) {
116 if ((gh_src->flag & GHASH_FLAG_IS_GSET) == 0) {
117 (reinterpret_cast<GHashEntry *>(dst))->val =
118 (valcopyfp) ?
119 valcopyfp((reinterpret_cast<GHashEntry *>(const_cast<Entry *>(src)))->val) :
120 (reinterpret_cast<GHashEntry *>(const_cast<Entry *>(src)))->val;
121 }
122 else {
123 (reinterpret_cast<GHashEntry *>(dst))->val = nullptr;
124 }
125 }
126}
127
131BLI_INLINE uint ghash_keyhash(const GHash *gh, const void *key)
132{
133 return gh->hashfp(key);
134}
135
140{
141 return gh->hashfp(e->key);
142}
143
148{
149#ifdef GHASH_USE_MODULO_BUCKETS
150 return hash % gh->nbuckets;
151#else
152 return hash & gh->bucket_mask;
153#endif
154}
155
160{
161 if (curr_bucket >= gh->nbuckets) {
162 curr_bucket = 0;
163 }
164 if (gh->buckets[curr_bucket]) {
165 return curr_bucket;
166 }
167 for (; curr_bucket < gh->nbuckets; curr_bucket++) {
168 if (gh->buckets[curr_bucket]) {
169 return curr_bucket;
170 }
171 }
172 for (curr_bucket = 0; curr_bucket < gh->nbuckets; curr_bucket++) {
173 if (gh->buckets[curr_bucket]) {
174 return curr_bucket;
175 }
176 }
178 return 0;
179}
180
184static void ghash_buckets_resize(GHash *gh, const uint nbuckets)
185{
186 Entry **buckets_old = gh->buckets;
187 Entry **buckets_new;
188 const uint nbuckets_old = gh->nbuckets;
189 uint i;
190
191 BLI_assert((gh->nbuckets != nbuckets) || !gh->buckets);
192 // printf("%s: %d -> %d\n", __func__, nbuckets_old, nbuckets);
193
194 gh->nbuckets = nbuckets;
195#ifdef GHASH_USE_MODULO_BUCKETS
196#else
197 gh->bucket_mask = nbuckets - 1;
198#endif
199
200 buckets_new = MEM_new_array_zeroed<Entry *>(gh->nbuckets, __func__);
201
202 if (buckets_old) {
203 if (nbuckets > nbuckets_old) {
204 for (i = 0; i < nbuckets_old; i++) {
205 for (Entry *e = buckets_old[i], *e_next; e; e = e_next) {
206 const uint hash = ghash_entryhash(gh, e);
207 const uint bucket_index = ghash_bucket_index(gh, hash);
208 e_next = e->next;
209 e->next = buckets_new[bucket_index];
210 buckets_new[bucket_index] = e;
211 }
212 }
213 }
214 else {
215 for (i = 0; i < nbuckets_old; i++) {
216#ifdef GHASH_USE_MODULO_BUCKETS
217 for (Entry *e = buckets_old[i], *e_next; e; e = e_next) {
218 const uint hash = ghash_entryhash(gh, e);
219 const uint bucket_index = ghash_bucket_index(gh, hash);
220 e_next = e->next;
221 e->next = buckets_new[bucket_index];
222 buckets_new[bucket_index] = e;
223 }
224#else
225 /* No need to recompute hashes in this case, since our mask is just smaller,
226 * all items in old bucket 'i' will go in same new bucket (i & new_mask)! */
227 const uint bucket_index = ghash_bucket_index(gh, i);
228 BLI_assert(!buckets_old[i] ||
229 (bucket_index == ghash_bucket_index(gh, ghash_entryhash(gh, buckets_old[i]))));
230 Entry *e;
231 for (e = buckets_old[i]; e && e->next; e = e->next) {
232 /* pass */
233 }
234 if (e) {
235 e->next = buckets_new[bucket_index];
236 buckets_new[bucket_index] = buckets_old[i];
237 }
238#endif
239 }
240 }
241 }
242
243 gh->buckets = buckets_new;
244 if (buckets_old) {
245 MEM_delete(buckets_old);
246 }
247}
248
253static void ghash_buckets_expand(GHash *gh, const uint nentries, const bool user_defined)
254{
255 uint new_nbuckets;
256
257 if (gh->buckets && (nentries < gh->limit_grow)) [[likely]] {
258 return;
259 }
260
261 new_nbuckets = gh->nbuckets;
262
263#ifdef GHASH_USE_MODULO_BUCKETS
264 while ((nentries > gh->limit_grow) && (gh->cursize < GHASH_MAX_SIZE - 1)) {
265 new_nbuckets = hashsizes[++gh->cursize];
266 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
267 }
268#else
269 while ((nentries > gh->limit_grow) && (gh->bucket_bit < GHASH_BUCKET_BIT_MAX)) {
270 new_nbuckets = 1u << ++gh->bucket_bit;
271 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
272 }
273#endif
274
275 if (user_defined) {
276#ifdef GHASH_USE_MODULO_BUCKETS
277 gh->size_min = gh->cursize;
278#else
279 gh->bucket_bit_min = gh->bucket_bit;
280#endif
281 }
282
283 if ((new_nbuckets == gh->nbuckets) && gh->buckets) {
284 return;
285 }
286
287 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
288 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
289 ghash_buckets_resize(gh, new_nbuckets);
290}
291
293 const uint nentries,
294 const bool user_defined,
295 const bool force_shrink)
296{
297 uint new_nbuckets;
298
299 if (!(force_shrink || (gh->flag & GHASH_FLAG_ALLOW_SHRINK))) {
300 return;
301 }
302
303 if (gh->buckets && (nentries > gh->limit_shrink)) [[likely]] {
304 return;
305 }
306
307 new_nbuckets = gh->nbuckets;
308
309#ifdef GHASH_USE_MODULO_BUCKETS
310 while ((nentries < gh->limit_shrink) && (gh->cursize > gh->size_min)) {
311 new_nbuckets = hashsizes[--gh->cursize];
312 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
313 }
314#else
315 while ((nentries < gh->limit_shrink) && (gh->bucket_bit > gh->bucket_bit_min)) {
316 new_nbuckets = 1u << --gh->bucket_bit;
317 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
318 }
319#endif
320
321 if (user_defined) {
322#ifdef GHASH_USE_MODULO_BUCKETS
323 gh->size_min = gh->cursize;
324#else
325 gh->bucket_bit_min = gh->bucket_bit;
326#endif
327 }
328
329 if ((new_nbuckets == gh->nbuckets) && gh->buckets) {
330 return;
331 }
332
333 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
334 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
335 ghash_buckets_resize(gh, new_nbuckets);
336}
337
341BLI_INLINE void ghash_buckets_reset(GHash *gh, const uint nentries)
342{
343 MEM_SAFE_DELETE(gh->buckets);
344
345#ifdef GHASH_USE_MODULO_BUCKETS
346 gh->cursize = 0;
347 gh->size_min = 0;
348 gh->nbuckets = hashsizes[gh->cursize];
349#else
350 gh->bucket_bit = GHASH_BUCKET_BIT_MIN;
351 gh->bucket_bit_min = GHASH_BUCKET_BIT_MIN;
352 gh->nbuckets = 1u << gh->bucket_bit;
353 gh->bucket_mask = gh->nbuckets - 1;
354#endif
355
358
359 gh->nentries = 0;
360
361 ghash_buckets_expand(gh, nentries, (nentries != 0));
362}
363
369BLI_INLINE Entry *ghash_lookup_entry_ex(const GHash *gh, const void *key, const uint bucket_index)
370{
371 Entry *e;
372 /* If we do not store GHash, not worth computing it for each entry here!
373 * Typically, comparison function will be quicker, and since it's needed in the end anyway... */
374 for (e = gh->buckets[bucket_index]; e; e = e->next) {
375 if (gh->cmpfp(key, e->key) == false) [[unlikely]] {
376 return e;
377 }
378 }
379
380 return nullptr;
381}
382
390 const void *key,
391 Entry **r_e_prev,
392 const uint bucket_index)
393{
394 /* If we do not store GHash, not worth computing it for each entry here!
395 * Typically, comparison function will be quicker, and since it's needed in the end anyway... */
396 for (Entry *e_prev = nullptr, *e = gh->buckets[bucket_index]; e; e_prev = e, e = e->next) {
397 if (gh->cmpfp(key, e->key) == false) [[unlikely]] {
398 *r_e_prev = e_prev;
399 return e;
400 }
401 }
402
403 *r_e_prev = nullptr;
404 return nullptr;
405}
406
410BLI_INLINE Entry *ghash_lookup_entry(const GHash *gh, const void *key)
411{
412 const uint hash = ghash_keyhash(gh, key);
413 const uint bucket_index = ghash_bucket_index(gh, hash);
414 return ghash_lookup_entry_ex(gh, key, bucket_index);
415}
416
418 GHashCmpFP cmpfp,
419 const char *info,
420 const uint nentries_reserve,
421 const uint flag)
422{
423 GHash *gh = MEM_new_zeroed<GHash>(info);
424
425 gh->hashfp = hashfp;
426 gh->cmpfp = cmpfp;
427
428 gh->buckets = nullptr;
429 gh->flag = flag;
430
431 ghash_buckets_reset(gh, nentries_reserve);
433 GHASH_ENTRY_SIZE(flag & GHASH_FLAG_IS_GSET), 64, 64, BLI_MEMPOOL_NOP);
434
435 return gh;
436}
437
443BLI_INLINE void ghash_insert_ex(GHash *gh, void *key, void *val, const uint bucket_index)
444{
446
447 BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
448 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
449
450 e->e.next = gh->buckets[bucket_index];
451 e->e.key = key;
452 e->val = val;
453 gh->buckets[bucket_index] = reinterpret_cast<Entry *>(e);
454
455 ghash_buckets_expand(gh, ++gh->nentries, false);
456}
457
462 void *key,
463 const uint bucket_index,
464 Entry *e)
465{
466 BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
467
468 e->next = gh->buckets[bucket_index];
469 e->key = key;
470 gh->buckets[bucket_index] = e;
471
472 ghash_buckets_expand(gh, ++gh->nentries, false);
473}
474
478BLI_INLINE void ghash_insert_ex_keyonly(GHash *gh, void *key, const uint bucket_index)
479{
481
482 BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
483 BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0);
484
485 e->next = gh->buckets[bucket_index];
486 e->key = key;
487 gh->buckets[bucket_index] = e;
488
489 ghash_buckets_expand(gh, ++gh->nentries, false);
490}
491
492BLI_INLINE void ghash_insert(GHash *gh, void *key, void *val)
493{
494 const uint hash = ghash_keyhash(gh, key);
495 const uint bucket_index = ghash_bucket_index(gh, hash);
496
497 ghash_insert_ex(gh, key, val, bucket_index);
498}
499
501 void *key,
502 void *val,
503 const bool override,
504 GHashKeyFreeFP keyfreefp,
505 GHashValFreeFP valfreefp)
506{
507 const uint hash = ghash_keyhash(gh, key);
508 const uint bucket_index = ghash_bucket_index(gh, hash);
509 GHashEntry *e = reinterpret_cast<GHashEntry *>(ghash_lookup_entry_ex(gh, key, bucket_index));
510
511 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
512
513 if (e) {
514 if (override) {
515 if (keyfreefp) {
516 keyfreefp(e->e.key);
517 }
518 if (valfreefp) {
519 valfreefp(e->val);
520 }
521 e->e.key = key;
522 e->val = val;
523 }
524 return false;
525 }
526 ghash_insert_ex(gh, key, val, bucket_index);
527 return true;
528}
529
531 void *key,
532 const bool override,
533 GHashKeyFreeFP keyfreefp)
534{
535 const uint hash = ghash_keyhash(gh, key);
536 const uint bucket_index = ghash_bucket_index(gh, hash);
537 Entry *e = ghash_lookup_entry_ex(gh, key, bucket_index);
538
539 BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0);
540
541 if (e) {
542 if (override) {
543 if (keyfreefp) {
544 keyfreefp(e->key);
545 }
546 e->key = key;
547 }
548 return false;
549 }
550 ghash_insert_ex_keyonly(gh, key, bucket_index);
551 return true;
552}
553
558 const void *key,
559 GHashKeyFreeFP keyfreefp,
560 GHashValFreeFP valfreefp,
561 const uint bucket_index)
562{
563 Entry *e_prev;
564 Entry *e = ghash_lookup_entry_prev_ex(gh, key, &e_prev, bucket_index);
565
566 BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET));
567
568 if (e) {
569 if (keyfreefp) {
570 keyfreefp(e->key);
571 }
572 if (valfreefp) {
573 valfreefp((reinterpret_cast<GHashEntry *>(e))->val);
574 }
575
576 if (e_prev) {
577 e_prev->next = e->next;
578 }
579 else {
580 gh->buckets[bucket_index] = e->next;
581 }
582
583 ghash_buckets_contract(gh, --gh->nentries, false, false);
584 }
585
586 return e;
587}
588
593{
594 uint curr_bucket = state->curr_bucket;
595 if (gh->nentries == 0) {
596 return nullptr;
597 }
598
599 /* NOTE: using first_bucket_index here allows us to avoid potential
600 * huge number of loops over buckets,
601 * in case we are popping from a large ghash with few items in it... */
602 curr_bucket = ghash_find_next_bucket_index(gh, curr_bucket);
603
604 Entry *e = gh->buckets[curr_bucket];
605 BLI_assert(e);
606
607 ghash_remove_ex(gh, e->key, nullptr, nullptr, curr_bucket);
608
609 state->curr_bucket = curr_bucket;
610 return e;
611}
612
616static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
617{
618 uint i;
619
620 BLI_assert(keyfreefp || valfreefp);
621 BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET));
622
623 for (i = 0; i < gh->nbuckets; i++) {
624 Entry *e;
625
626 for (e = gh->buckets[i]; e; e = e->next) {
627 if (keyfreefp) {
628 keyfreefp(e->key);
629 }
630 if (valfreefp) {
631 valfreefp((reinterpret_cast<GHashEntry *>(e))->val);
632 }
633 }
634 }
635}
636
640static GHash *ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
641{
642 GHash *gh_new;
643 uint i;
644 /* This allows us to be sure to get the same number of buckets in gh_new as in ghash. */
645 const uint reserve_nentries_new = std::max(GHASH_LIMIT_GROW(gh->nbuckets) - 1, gh->nentries);
646
647 BLI_assert(!valcopyfp || !(gh->flag & GHASH_FLAG_IS_GSET));
648
649 gh_new = ghash_new(gh->hashfp, gh->cmpfp, __func__, 0, gh->flag);
650 ghash_buckets_expand(gh_new, reserve_nentries_new, false);
651
652 BLI_assert(gh_new->nbuckets == gh->nbuckets);
653
654 for (i = 0; i < gh->nbuckets; i++) {
655 Entry *e;
656
657 for (e = gh->buckets[i]; e; e = e->next) {
658 Entry *e_new = BLI_mempool_alloc<Entry>(gh_new->entrypool);
659 ghash_entry_copy(gh_new, e_new, gh, e, keycopyfp, valcopyfp);
660
661 /* Warning!
662 * This means entries in buckets in new copy will be in reversed order!
663 * This shall not be an issue though, since order should never be assumed in ghash. */
664
665 /* NOTE: We can use 'i' here, since we are sure that
666 * 'gh' and 'gh_new' have the same number of buckets! */
667 e_new->next = gh_new->buckets[i];
668 gh_new->buckets[i] = e_new;
669 }
670 }
671 gh_new->nentries = gh->nentries;
672
673 return gh_new;
674}
675
677
678/* -------------------------------------------------------------------- */
681
683 GHashCmpFP cmpfp,
684 const char *info,
685 const uint nentries_reserve)
686{
687 return ghash_new(hashfp, cmpfp, info, nentries_reserve, 0);
688}
689
690GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
691{
692 return BLI_ghash_new_ex(hashfp, cmpfp, info, 0);
693}
694
695GHash *BLI_ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
696{
697 return ghash_copy(gh, keycopyfp, valcopyfp);
698}
699
700void BLI_ghash_reserve(GHash *gh, const uint nentries_reserve)
701{
702 ghash_buckets_expand(gh, nentries_reserve, true);
703 ghash_buckets_contract(gh, nentries_reserve, true, false);
704}
705
707{
708 return gh->nentries;
709}
710
711void BLI_ghash_insert(GHash *gh, void *key, void *val)
712{
713 ghash_insert(gh, key, val);
714}
715
717 GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
718{
719 return ghash_insert_safe(gh, key, val, true, keyfreefp, valfreefp);
720}
721
722void *BLI_ghash_replace_key(GHash *gh, void *key)
723{
724 const uint hash = ghash_keyhash(gh, key);
725 const uint bucket_index = ghash_bucket_index(gh, hash);
726 GHashEntry *e = reinterpret_cast<GHashEntry *>(ghash_lookup_entry_ex(gh, key, bucket_index));
727 if (e != nullptr) {
728 void *key_prev = e->e.key;
729 e->e.key = key;
730 return key_prev;
731 }
732 return nullptr;
733}
734
735void *BLI_ghash_lookup(const GHash *gh, const void *key)
736{
737 GHashEntry *e = reinterpret_cast<GHashEntry *>(ghash_lookup_entry(gh, key));
738 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
739 return e ? e->val : nullptr;
740}
741
742void *BLI_ghash_lookup_default(const GHash *gh, const void *key, void *val_default)
743{
744 GHashEntry *e = reinterpret_cast<GHashEntry *>(ghash_lookup_entry(gh, key));
745 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
746 return e ? e->val : val_default;
747}
748
749void **BLI_ghash_lookup_p(GHash *gh, const void *key)
750{
751 GHashEntry *e = reinterpret_cast<GHashEntry *>(ghash_lookup_entry(gh, key));
752 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
753 return e ? &e->val : nullptr;
754}
755
756bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val)
757{
758 const uint hash = ghash_keyhash(gh, key);
759 const uint bucket_index = ghash_bucket_index(gh, hash);
760 GHashEntry *e = reinterpret_cast<GHashEntry *>(ghash_lookup_entry_ex(gh, key, bucket_index));
761 const bool haskey = (e != nullptr);
762
763 if (!haskey) {
765 ghash_insert_ex_keyonly_entry(gh, key, bucket_index, reinterpret_cast<Entry *>(e));
766 }
767
768 *r_val = &e->val;
769 return haskey;
770}
771
772bool BLI_ghash_ensure_p_ex(GHash *gh, const void *key, void ***r_key, void ***r_val)
773{
774 const uint hash = ghash_keyhash(gh, key);
775 const uint bucket_index = ghash_bucket_index(gh, hash);
776 GHashEntry *e = reinterpret_cast<GHashEntry *>(ghash_lookup_entry_ex(gh, key, bucket_index));
777 const bool haskey = (e != nullptr);
778
779 if (!haskey) {
780 /* Pass 'key' in case we resize. */
783 gh, const_cast<void *>(key), bucket_index, reinterpret_cast<Entry *>(e));
784 e->e.key = nullptr; /* caller must re-assign */
785 }
786
787 *r_key = &e->e.key;
788 *r_val = &e->val;
789 return haskey;
790}
791
793 const void *key,
794 GHashKeyFreeFP keyfreefp,
795 GHashValFreeFP valfreefp)
796{
797 const uint hash = ghash_keyhash(gh, key);
798 const uint bucket_index = ghash_bucket_index(gh, hash);
799 Entry *e = ghash_remove_ex(gh, key, keyfreefp, valfreefp, bucket_index);
800 if (e) {
802 return true;
803 }
804 return false;
805}
806
807void *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp)
808{
809 /* Same as #BLI_ghash_remove but return the value,
810 * no free value argument since it will be returned. */
811
812 const uint hash = ghash_keyhash(gh, key);
813 const uint bucket_index = ghash_bucket_index(gh, hash);
814 GHashEntry *e = reinterpret_cast<GHashEntry *>(
815 ghash_remove_ex(gh, key, keyfreefp, nullptr, bucket_index));
816 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
817 if (e) {
818 void *val = e->val;
820 return val;
821 }
822 return nullptr;
823}
824
825bool BLI_ghash_haskey(const GHash *gh, const void *key)
826{
827 return (ghash_lookup_entry(gh, key) != nullptr);
828}
829
830bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val)
831{
832 GHashEntry *e = reinterpret_cast<GHashEntry *>(ghash_pop(gh, state));
833
834 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
835
836 if (e) {
837 *r_key = e->e.key;
838 *r_val = e->val;
839
841 return true;
842 }
843
844 *r_key = *r_val = nullptr;
845 return false;
846}
847
849 GHashKeyFreeFP keyfreefp,
850 GHashValFreeFP valfreefp,
851 const uint nentries_reserve)
852{
853 if (keyfreefp || valfreefp) {
854 ghash_free_cb(gh, keyfreefp, valfreefp);
855 }
856
857 ghash_buckets_reset(gh, nentries_reserve);
858 BLI_mempool_clear_ex(gh->entrypool, nentries_reserve ? int(nentries_reserve) : -1);
859}
860
861void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
862{
863 BLI_ghash_clear_ex(gh, keyfreefp, valfreefp, 0);
864}
865
866void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
867{
869 if (keyfreefp || valfreefp) {
870 ghash_free_cb(gh, keyfreefp, valfreefp);
871 }
872
873 MEM_delete(gh->buckets);
875 MEM_delete(gh);
876}
877
879{
880 gh->flag |= flag;
881}
882
884{
885 gh->flag &= ~flag;
886}
887
889
890/* -------------------------------------------------------------------- */
893
895{
896 GHashIterator *ghi = MEM_new_zeroed<GHashIterator>("ghash iterator");
897 BLI_ghashIterator_init(ghi, gh);
898 return ghi;
899}
900
902{
903 ghi->gh = gh;
904 ghi->curEntry = nullptr;
905 ghi->curBucket = UINT_MAX; /* wraps to zero */
906 if (gh->nentries) {
907 do {
908 ghi->curBucket++;
909 if (ghi->curBucket == ghi->gh->nbuckets) [[unlikely]] {
910 break;
911 }
912 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
913 } while (!ghi->curEntry);
914 }
915}
916
918{
919 if (ghi->curEntry) {
920 ghi->curEntry = ghi->curEntry->next;
921 while (!ghi->curEntry) {
922 ghi->curBucket++;
923 if (ghi->curBucket == ghi->gh->nbuckets) {
924 break;
925 }
926 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
927 }
928 }
929}
930
932{
933 MEM_delete(ghi);
934}
935
937
938/* -------------------------------------------------------------------- */
941
943 GSetCmpFP cmpfp,
944 const char *info,
945 const uint nentries_reserve)
946{
947 return reinterpret_cast<GSet *>(
948 ghash_new(hashfp, cmpfp, info, nentries_reserve, GHASH_FLAG_IS_GSET));
949}
950
951GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info)
952{
953 return BLI_gset_new_ex(hashfp, cmpfp, info, 0);
954}
955
956GSet *BLI_gset_copy(const GSet *gs, GHashKeyCopyFP keycopyfp)
957{
958 return reinterpret_cast<GSet *>(
959 ghash_copy(reinterpret_cast<const GHash *>(gs), keycopyfp, nullptr));
960}
961
962uint BLI_gset_len(const GSet *gs)
963{
964 return (reinterpret_cast<GHash *>(const_cast<GSet *>(gs)))->nentries;
965}
966
967void BLI_gset_insert(GSet *gs, void *key)
968{
969 const uint hash = ghash_keyhash(reinterpret_cast<GHash *>(gs), key);
970 const uint bucket_index = ghash_bucket_index(reinterpret_cast<GHash *>(gs), hash);
971 ghash_insert_ex_keyonly(reinterpret_cast<GHash *>(gs), key, bucket_index);
972}
973
974bool BLI_gset_add(GSet *gs, void *key)
975{
976 return ghash_insert_safe_keyonly(reinterpret_cast<GHash *>(gs), key, false, nullptr);
977}
978
979bool BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key)
980{
981 const uint hash = ghash_keyhash(reinterpret_cast<GHash *>(gs), key);
982 const uint bucket_index = ghash_bucket_index(reinterpret_cast<GHash *>(gs), hash);
983 GSetEntry *e = static_cast<GSetEntry *>(
984 ghash_lookup_entry_ex(reinterpret_cast<const GHash *>(gs), key, bucket_index));
985 const bool haskey = (e != nullptr);
986
987 if (!haskey) {
988 /* Pass 'key' in case we resize */
989 e = BLI_mempool_alloc<GSetEntry>((reinterpret_cast<GHash *>(gs))->entrypool);
990 ghash_insert_ex_keyonly_entry(reinterpret_cast<GHash *>(gs),
991 const_cast<void *>(key),
992 bucket_index,
993 static_cast<Entry *>(e));
994 e->key = nullptr; /* caller must re-assign */
995 }
996
997 *r_key = &e->key;
998 return haskey;
999}
1000
1001bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp)
1002{
1003 return ghash_insert_safe_keyonly(reinterpret_cast<GHash *>(gs), key, true, keyfreefp);
1004}
1005
1006void *BLI_gset_replace_key(GSet *gs, void *key)
1007{
1008 return BLI_ghash_replace_key(reinterpret_cast<GHash *>(gs), key);
1009}
1010
1011bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp)
1012{
1013 return BLI_ghash_remove(reinterpret_cast<GHash *>(gs), key, keyfreefp, nullptr);
1014}
1015
1016bool BLI_gset_haskey(const GSet *gs, const void *key)
1017{
1018 return (ghash_lookup_entry(reinterpret_cast<const GHash *>(gs), key) != nullptr);
1019}
1020
1021bool BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key)
1022{
1023 GSetEntry *e = static_cast<GSetEntry *>(
1024 ghash_pop(reinterpret_cast<GHash *>(gs), static_cast<GHashIterState *>(state)));
1025
1026 if (e) {
1027 *r_key = e->key;
1028
1029 BLI_mempool_free((reinterpret_cast<GHash *>(gs))->entrypool, e);
1030 return true;
1031 }
1032
1033 *r_key = nullptr;
1034 return false;
1035}
1036
1037void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, const uint nentries_reserve)
1038{
1039 BLI_ghash_clear_ex(reinterpret_cast<GHash *>(gs), keyfreefp, nullptr, nentries_reserve);
1040}
1041
1042void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
1043{
1044 BLI_ghash_clear(reinterpret_cast<GHash *>(gs), keyfreefp, nullptr);
1045}
1046
1047void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
1048{
1049 BLI_ghash_free(reinterpret_cast<GHash *>(gs), keyfreefp, nullptr);
1050}
1051
1052void BLI_gset_flag_set(GSet *gs, uint flag)
1053{
1054 (reinterpret_cast<GHash *>(gs))->flag |= flag;
1055}
1056
1057void BLI_gset_flag_clear(GSet *gs, uint flag)
1058{
1059 (reinterpret_cast<GHash *>(gs))->flag &= ~flag;
1060}
1061
1063
1064/* -------------------------------------------------------------------- */
1070
1071void *BLI_gset_lookup(const GSet *gs, const void *key)
1072{
1073 Entry *e = ghash_lookup_entry(reinterpret_cast<const GHash *>(gs), key);
1074 return e ? e->key : nullptr;
1075}
1076
1077void *BLI_gset_pop_key(GSet *gs, const void *key)
1078{
1079 const uint hash = ghash_keyhash(reinterpret_cast<GHash *>(gs), key);
1080 const uint bucket_index = ghash_bucket_index(reinterpret_cast<GHash *>(gs), hash);
1081 Entry *e = ghash_remove_ex(reinterpret_cast<GHash *>(gs), key, nullptr, nullptr, bucket_index);
1082 if (e) {
1083 void *key_ret = e->key;
1084 BLI_mempool_free((reinterpret_cast<GHash *>(gs))->entrypool, e);
1085 return key_ret;
1086 }
1087 return nullptr;
1088}
1089
1091
1092/* -------------------------------------------------------------------- */
1095
1097{
1098 return int(gh->nbuckets);
1099}
1100int BLI_gset_buckets_len(const GSet *gs)
1101{
1102 return BLI_ghash_buckets_len(reinterpret_cast<const GHash *>(gs));
1103}
1104
1106 double *r_load,
1107 double *r_variance,
1108 double *r_prop_empty_buckets,
1109 double *r_prop_overloaded_buckets,
1110 int *r_biggest_bucket)
1111{
1112 double mean;
1113 uint i;
1114
1115 if (gh->nentries == 0) {
1116 if (r_load) {
1117 *r_load = 0.0;
1118 }
1119 if (r_variance) {
1120 *r_variance = 0.0;
1121 }
1122 if (r_prop_empty_buckets) {
1123 *r_prop_empty_buckets = 1.0;
1124 }
1125 if (r_prop_overloaded_buckets) {
1126 *r_prop_overloaded_buckets = 0.0;
1127 }
1128 if (r_biggest_bucket) {
1129 *r_biggest_bucket = 0;
1130 }
1131
1132 return 0.0;
1133 }
1134
1135 mean = double(gh->nentries) / double(gh->nbuckets);
1136 if (r_load) {
1137 *r_load = mean;
1138 }
1139 if (r_biggest_bucket) {
1140 *r_biggest_bucket = 0;
1141 }
1142
1143 if (r_variance) {
1144 /* We already know our mean (i.e. load factor), easy to compute variance.
1145 * See https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Two-pass_algorithm
1146 */
1147 double sum = 0.0;
1148 for (i = 0; i < gh->nbuckets; i++) {
1149 int count = 0;
1150 Entry *e;
1151 for (e = gh->buckets[i]; e; e = e->next) {
1152 count++;
1153 }
1154 sum += (double(count) - mean) * (double(count) - mean);
1155 }
1156 *r_variance = sum / double(gh->nbuckets - 1);
1157 }
1158
1159 {
1160 uint64_t sum = 0;
1161 uint64_t overloaded_buckets_threshold = uint64_t(max_ii(GHASH_LIMIT_GROW(1), 1));
1162 uint64_t sum_overloaded = 0;
1163 uint64_t sum_empty = 0;
1164
1165 for (i = 0; i < gh->nbuckets; i++) {
1166 uint64_t count = 0;
1167 Entry *e;
1168 for (e = gh->buckets[i]; e; e = e->next) {
1169 count++;
1170 }
1171 if (r_biggest_bucket) {
1172 *r_biggest_bucket = max_ii(*r_biggest_bucket, int(count));
1173 }
1174 if (r_prop_overloaded_buckets && (count > overloaded_buckets_threshold)) {
1175 sum_overloaded++;
1176 }
1177 if (r_prop_empty_buckets && !count) {
1178 sum_empty++;
1179 }
1180 sum += count * (count + 1);
1181 }
1182 if (r_prop_overloaded_buckets) {
1183 *r_prop_overloaded_buckets = double(sum_overloaded) / double(gh->nbuckets);
1184 }
1185 if (r_prop_empty_buckets) {
1186 *r_prop_empty_buckets = double(sum_empty) / double(gh->nbuckets);
1187 }
1188 return (double(sum) * double(gh->nbuckets) /
1189 (double(gh->nentries) * (gh->nentries + 2 * gh->nbuckets - 1)));
1190 }
1191}
1192double BLI_gset_calc_quality_ex(const GSet *gs,
1193 double *r_load,
1194 double *r_variance,
1195 double *r_prop_empty_buckets,
1196 double *r_prop_overloaded_buckets,
1197 int *r_biggest_bucket)
1198{
1199 return BLI_ghash_calc_quality_ex(reinterpret_cast<const GHash *>(gs),
1200 r_load,
1201 r_variance,
1202 r_prop_empty_buckets,
1203 r_prop_overloaded_buckets,
1204 r_biggest_bucket);
1205}
1206
1208{
1209 return BLI_ghash_calc_quality_ex(gh, nullptr, nullptr, nullptr, nullptr, nullptr);
1210}
1211double BLI_gset_calc_quality(const GSet *gs)
1212{
1213 return BLI_ghash_calc_quality_ex(reinterpret_cast<GHash *>(const_cast<GSet *>(gs)),
1214 nullptr,
1215 nullptr,
1216 nullptr,
1217 nullptr,
1218 nullptr);
1219}
1220
1222
1223} // namespace blender
#define GHASH_MAX_SIZE
Definition BLI_ghash.cc:47
#define GHASH_ENTRY_SIZE(_is_gset)
Definition BLI_ghash.cc:80
#define GHASH_LIMIT_SHRINK(_nbkt)
Definition BLI_ghash.cc:63
#define GHASH_LIMIT_GROW(_nbkt)
Definition BLI_ghash.cc:62
Read Blender memory allocation and freeing.
#define BLI_assert_unreachable()
#define BLI_INLINE
#define UINT_MAX
Definition hash_md5.cc:46
const int state
BMesh Iterators.
BLI_INLINE uint ghash_bucket_index(const GHash *gh, const uint hash)
Definition BLI_ghash.cc:147
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
bool BLI_ghash_ensure_p_ex(GHash *gh, const void *key, void ***r_key, void ***r_val) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:772
void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
bool BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key)
Definition BLI_ghash.cc:979
unsigned __int64 uint64_t
Definition BKE_text.h:91
BLI_STATIC_ASSERT(ARRAY_SIZE(data_mode_strings)==CTX_MODE_NUM+1, "Must have a string for each context mode") const char *CTX_data_mode_string(const bContext *C)
BLI_INLINE void ghash_insert_ex(GHash *gh, void *key, void *val, const uint bucket_index)
Definition BLI_ghash.cc:443
GHash * BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:682
unsigned int uint
Definition BKE_text.h:55
int BLI_ghash_buckets_len(const GHash *gh)
void * BLI_ghash_lookup_default(const GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:742
BLI_INLINE Entry * ghash_lookup_entry_prev_ex(GHash *gh, const void *key, Entry **r_e_prev, const uint bucket_index)
Definition BLI_ghash.cc:389
void * BLI_ghash_replace_key(GHash *gh, void *key)
Definition BLI_ghash.cc:722
void * BLI_gset_lookup(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
GHashCmpFP GSetCmpFP
Definition BLI_ghash.hh:342
BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh, void *key, const bool override, GHashKeyFreeFP keyfreefp)
Definition BLI_ghash.cc:530
unsigned int(*) GHashHashFP(const void *key)
Definition BLI_ghash.hh:33
static Entry * ghash_remove_ex(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, const uint bucket_index)
Definition BLI_ghash.cc:557
bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp)
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:735
void * BLI_gset_pop_key(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
bool BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void(*) GHashKeyFreeFP(void *key)
Definition BLI_ghash.hh:36
GHashKeyFreeFP GSetKeyFreeFP
Definition BLI_ghash.hh:343
MINLINE int max_ii(int a, int b)
void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, unsigned int nentries_reserve)
double BLI_ghash_calc_quality(const GHash *gh)
BLI_INLINE uint ghash_keyhash(const GHash *gh, const void *key)
Definition BLI_ghash.cc:131
void BLI_gset_flag_set(GSet *gs, unsigned int flag)
double BLI_gset_calc_quality(const GSet *gs)
bool(*) GHashCmpFP(const void *a, const void *b)
Definition BLI_ghash.hh:35
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition BLI_ghash.cc:711
void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, unsigned int nentries_reserve)
Definition BLI_ghash.cc:848
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
void BLI_ghash_flag_clear(GHash *gh, unsigned int flag)
Definition BLI_ghash.cc:883
double BLI_ghash_calc_quality_ex(const GHash *gh, double *r_load, double *r_variance, double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket)
void ** BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:749
Entry GSetEntry
Definition BLI_ghash.cc:78
void * BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:807
int BLI_gset_buckets_len(const GSet *gs)
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
void *(*) GHashKeyCopyFP(const void *key)
Definition BLI_ghash.hh:38
void BLI_ghashIterator_step(GHashIterator *ghi)
Definition BLI_ghash.cc:917
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_INLINE uint ghash_entryhash(const GHash *gh, const Entry *e)
Definition BLI_ghash.cc:139
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:866
static void ghash_buckets_contract(GHash *gh, const uint nentries, const bool user_defined, const bool force_shrink)
Definition BLI_ghash.cc:292
static void ghash_buckets_expand(GHash *gh, const uint nentries, const bool user_defined)
Definition BLI_ghash.cc:253
GHashIterState GSetIterState
Definition BLI_ghash.hh:346
BLI_INLINE bool ghash_insert_safe(GHash *gh, void *key, void *val, const bool override, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:500
bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:756
static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:616
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
GHashHashFP GSetHashFP
Definition BLI_ghash.hh:341
BLI_INLINE void ghash_buckets_reset(GHash *gh, const uint nentries)
Definition BLI_ghash.cc:341
void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:861
BLI_INLINE Entry * ghash_lookup_entry(const GHash *gh, const void *key)
Definition BLI_ghash.cc:410
BLI_INLINE Entry * ghash_lookup_entry_ex(const GHash *gh, const void *key, const uint bucket_index)
Definition BLI_ghash.cc:369
void BLI_ghash_flag_set(GHash *gh, unsigned int flag)
Definition BLI_ghash.cc:878
void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
static void ghash_buckets_resize(GHash *gh, const uint nbuckets)
Definition BLI_ghash.cc:184
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
GSet * BLI_gset_copy(const GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:956
@ GHASH_FLAG_ALLOW_DUPES
Definition BLI_ghash.hh:54
@ GHASH_FLAG_ALLOW_SHRINK
Definition BLI_ghash.hh:55
static Entry * ghash_pop(GHash *gh, GHashIterState *state)
Definition BLI_ghash.cc:592
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:706
void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
Definition BLI_ghash.cc:901
void * BLI_gset_replace_key(GSet *gs, void *key)
static GHash * ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, const uint nentries_reserve, const uint flag)
Definition BLI_ghash.cc:417
void BLI_gset_flag_clear(GSet *gs, unsigned int flag)
GSet * BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:951
void void BLI_mempool_clear_ex(BLI_mempool *pool, int elem_num_reserve) ATTR_NONNULL(1)
GHash * BLI_ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:695
@ BLI_MEMPOOL_NOP
static const uint hashsizes[]
Definition BLI_ghash.cc:40
void BLI_gset_insert(GSet *gs, void *key)
Definition BLI_ghash.cc:967
bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp)
void(*) GHashValFreeFP(void *val)
Definition BLI_ghash.hh:37
GHashIterator * BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:894
bool BLI_ghash_remove(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:792
unsigned int BLI_gset_len(const GSet *gs) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:962
void BLI_ghash_reserve(GHash *gh, unsigned int nentries_reserve)
Definition BLI_ghash.cc:700
static GHash * ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
Definition BLI_ghash.cc:640
void *(*) GHashValCopyFP(const void *val)
Definition BLI_ghash.hh:39
bool BLI_gset_haskey(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition BLI_ghash.cc:830
GSet * BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:942
BLI_INLINE void ghash_insert_ex_keyonly(GHash *gh, void *key, const uint bucket_index)
Definition BLI_ghash.cc:478
GHash * BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:690
int BLI_mempool_len(const BLI_mempool *pool) ATTR_NONNULL(1)
BLI_INLINE uint ghash_find_next_bucket_index(const GHash *gh, uint curr_bucket)
Definition BLI_ghash.cc:159
BLI_INLINE void ghash_insert(GHash *gh, void *key, void *val)
Definition BLI_ghash.cc:492
bool BLI_ghash_haskey(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:825
bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:716
BLI_INLINE void ghash_insert_ex_keyonly_entry(GHash *gh, void *key, const uint bucket_index, Entry *e)
Definition BLI_ghash.cc:461
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
BLI_INLINE void ghash_entry_copy(GHash *gh_dst, Entry *dst, const GHash *gh_src, const Entry *src, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
Definition BLI_ghash.cc:106
double BLI_gset_calc_quality_ex(const GSet *gs, double *r_load, double *r_variance, double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket)
bool BLI_gset_add(GSet *gs, void *key)
Definition BLI_ghash.cc:974
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BLI_ghashIterator_free(GHashIterator *ghi)
Definition BLI_ghash.cc:931
#define hash
Definition noise_c.cc:156
struct Entry * curEntry
Definition BLI_ghash.hh:45
unsigned int curBucket
Definition BLI_ghash.hh:46
GHashHashFP hashfp
Definition BLI_ghash.cc:83
Entry ** buckets
Definition BLI_ghash.cc:86
BLI_mempool * entrypool
Definition BLI_ghash.cc:87
GHashCmpFP cmpfp
Definition BLI_ghash.cc:84