1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 *
16 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17 * All rights reserved.
18 */
19
20 /** \file
21 * \ingroup bli
22 *
23 * A general (pointer -> pointer) chaining hash table
24 * for 'Abstract Data Types' (known as an ADT Hash Table).
25 */
26
27 #include <limits.h>
28 #include <stdarg.h>
29 #include <stdlib.h>
30 #include <string.h>
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_mempool.h"
35 #include "BLI_sys_types.h" /* for intptr_t support */
36 #include "BLI_utildefines.h"
37
38 #define GHASH_INTERNAL_API
39 #include "BLI_ghash.h" /* own include */
40
41 /* keep last */
42 #include "BLI_strict_flags.h"
43
44 /* -------------------------------------------------------------------- */
45 /** \name Structs & Constants
46 * \{ */
47
48 #define GHASH_USE_MODULO_BUCKETS
49
50 /**
51 * Next prime after `2^n` (skipping 2 & 3).
52 *
53 * \note Also used by: `BLI_edgehash` & `BLI_smallhash`.
54 */
55 extern const uint BLI_ghash_hash_sizes[]; /* Quiet warning, this is only used by smallhash.c */
56 const uint BLI_ghash_hash_sizes[] = {
57 5, 11, 17, 37, 67, 131, 257, 521, 1031,
58 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309,
59 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
60 };
61 #define hashsizes BLI_ghash_hash_sizes
62
63 #ifdef GHASH_USE_MODULO_BUCKETS
64 # define GHASH_MAX_SIZE 27
65 BLI_STATIC_ASSERT(ARRAY_SIZE(hashsizes) == GHASH_MAX_SIZE, "Invalid 'hashsizes' size");
66 #else
67 # define GHASH_BUCKET_BIT_MIN 2
68 # define GHASH_BUCKET_BIT_MAX 28 /* About 268M of buckets... */
69 #endif
70
71 /**
72 * \note Max load #GHASH_LIMIT_GROW used to be 3. (pre 2.74).
73 * Python uses 0.6666, tommyhashlib even goes down to 0.5.
74 * Reducing our from 3 to 0.75 gives huge speedup
75 * (about twice quicker pure GHash insertions/lookup,
76 * about 25% - 30% quicker 'dynamic-topology' stroke drawing e.g.).
77 * Min load #GHASH_LIMIT_SHRINK is a quarter of max load, to avoid resizing to quickly.
78 */
79 #define GHASH_LIMIT_GROW(_nbkt) (((_nbkt)*3) / 4)
80 #define GHASH_LIMIT_SHRINK(_nbkt) (((_nbkt)*3) / 16)
81
82 /* WARNING! Keep in sync with ugly _gh_Entry in header!!! */
83 typedef struct Entry {
84 struct Entry *next;
85
86 void *key;
87 } Entry;
88
89 typedef struct GHashEntry {
90 Entry e;
91
92 void *val;
93 } GHashEntry;
94
95 typedef Entry GSetEntry;
96
97 #define GHASH_ENTRY_SIZE(_is_gset) ((_is_gset) ? sizeof(GSetEntry) : sizeof(GHashEntry))
98
99 struct GHash {
100 GHashHashFP hashfp;
101 GHashCmpFP cmpfp;
102
103 Entry **buckets;
104 struct BLI_mempool *entrypool;
105 uint nbuckets;
106 uint limit_grow, limit_shrink;
107 #ifdef GHASH_USE_MODULO_BUCKETS
108 uint cursize, size_min;
109 #else
110 uint bucket_mask, bucket_bit, bucket_bit_min;
111 #endif
112
113 uint nentries;
114 uint flag;
115 };
116
117 /** \} */
118
119 /* -------------------------------------------------------------------- */
120 /** \name Internal Utility API
121 * \{ */
122
ghash_entry_copy(GHash * gh_dst,Entry * dst,GHash * gh_src,Entry * src,GHashKeyCopyFP keycopyfp,GHashValCopyFP valcopyfp)123 BLI_INLINE void ghash_entry_copy(GHash *gh_dst,
124 Entry *dst,
125 GHash *gh_src,
126 Entry *src,
127 GHashKeyCopyFP keycopyfp,
128 GHashValCopyFP valcopyfp)
129 {
130 dst->key = (keycopyfp) ? keycopyfp(src->key) : src->key;
131
132 if ((gh_dst->flag & GHASH_FLAG_IS_GSET) == 0) {
133 if ((gh_src->flag & GHASH_FLAG_IS_GSET) == 0) {
134 ((GHashEntry *)dst)->val = (valcopyfp) ? valcopyfp(((GHashEntry *)src)->val) :
135 ((GHashEntry *)src)->val;
136 }
137 else {
138 ((GHashEntry *)dst)->val = NULL;
139 }
140 }
141 }
142
143 /**
144 * Get the full hash for a key.
145 */
ghash_keyhash(GHash * gh,const void * key)146 BLI_INLINE uint ghash_keyhash(GHash *gh, const void *key)
147 {
148 return gh->hashfp(key);
149 }
150
151 /**
152 * Get the full hash for an entry.
153 */
ghash_entryhash(GHash * gh,const Entry * e)154 BLI_INLINE uint ghash_entryhash(GHash *gh, const Entry *e)
155 {
156 return gh->hashfp(e->key);
157 }
158
159 /**
160 * Get the bucket-index for an already-computed full hash.
161 */
ghash_bucket_index(GHash * gh,const uint hash)162 BLI_INLINE uint ghash_bucket_index(GHash *gh, const uint hash)
163 {
164 #ifdef GHASH_USE_MODULO_BUCKETS
165 return hash % gh->nbuckets;
166 #else
167 return hash & gh->bucket_mask;
168 #endif
169 }
170
171 /**
172 * Find the index of next used bucket, starting from \a curr_bucket (\a gh is assumed non-empty).
173 */
ghash_find_next_bucket_index(GHash * gh,uint curr_bucket)174 BLI_INLINE uint ghash_find_next_bucket_index(GHash *gh, uint curr_bucket)
175 {
176 if (curr_bucket >= gh->nbuckets) {
177 curr_bucket = 0;
178 }
179 if (gh->buckets[curr_bucket]) {
180 return curr_bucket;
181 }
182 for (; curr_bucket < gh->nbuckets; curr_bucket++) {
183 if (gh->buckets[curr_bucket]) {
184 return curr_bucket;
185 }
186 }
187 for (curr_bucket = 0; curr_bucket < gh->nbuckets; curr_bucket++) {
188 if (gh->buckets[curr_bucket]) {
189 return curr_bucket;
190 }
191 }
192 BLI_assert(0);
193 return 0;
194 }
195
196 /**
197 * Expand buckets to the next size up or down.
198 */
ghash_buckets_resize(GHash * gh,const uint nbuckets)199 static void ghash_buckets_resize(GHash *gh, const uint nbuckets)
200 {
201 Entry **buckets_old = gh->buckets;
202 Entry **buckets_new;
203 const uint nbuckets_old = gh->nbuckets;
204 uint i;
205
206 BLI_assert((gh->nbuckets != nbuckets) || !gh->buckets);
207 // printf("%s: %d -> %d\n", __func__, nbuckets_old, nbuckets);
208
209 gh->nbuckets = nbuckets;
210 #ifdef GHASH_USE_MODULO_BUCKETS
211 #else
212 gh->bucket_mask = nbuckets - 1;
213 #endif
214
215 buckets_new = (Entry **)MEM_callocN(sizeof(*gh->buckets) * gh->nbuckets, __func__);
216
217 if (buckets_old) {
218 if (nbuckets > nbuckets_old) {
219 for (i = 0; i < nbuckets_old; i++) {
220 for (Entry *e = buckets_old[i], *e_next; e; e = e_next) {
221 const uint hash = ghash_entryhash(gh, e);
222 const uint bucket_index = ghash_bucket_index(gh, hash);
223 e_next = e->next;
224 e->next = buckets_new[bucket_index];
225 buckets_new[bucket_index] = e;
226 }
227 }
228 }
229 else {
230 for (i = 0; i < nbuckets_old; i++) {
231 #ifdef GHASH_USE_MODULO_BUCKETS
232 for (Entry *e = buckets_old[i], *e_next; e; e = e_next) {
233 const uint hash = ghash_entryhash(gh, e);
234 const uint bucket_index = ghash_bucket_index(gh, hash);
235 e_next = e->next;
236 e->next = buckets_new[bucket_index];
237 buckets_new[bucket_index] = e;
238 }
239 #else
240 /* No need to recompute hashes in this case, since our mask is just smaller,
241 * all items in old bucket 'i' will go in same new bucket (i & new_mask)! */
242 const uint bucket_index = ghash_bucket_index(gh, i);
243 BLI_assert(!buckets_old[i] ||
244 (bucket_index == ghash_bucket_index(gh, ghash_entryhash(gh, buckets_old[i]))));
245 Entry *e;
246 for (e = buckets_old[i]; e && e->next; e = e->next) {
247 /* pass */
248 }
249 if (e) {
250 e->next = buckets_new[bucket_index];
251 buckets_new[bucket_index] = buckets_old[i];
252 }
253 #endif
254 }
255 }
256 }
257
258 gh->buckets = buckets_new;
259 if (buckets_old) {
260 MEM_freeN(buckets_old);
261 }
262 }
263
264 /**
265 * Check if the number of items in the GHash is large enough to require more buckets,
266 * or small enough to require less buckets, and resize \a gh accordingly.
267 */
ghash_buckets_expand(GHash * gh,const uint nentries,const bool user_defined)268 static void ghash_buckets_expand(GHash *gh, const uint nentries, const bool user_defined)
269 {
270 uint new_nbuckets;
271
272 if (LIKELY(gh->buckets && (nentries < gh->limit_grow))) {
273 return;
274 }
275
276 new_nbuckets = gh->nbuckets;
277
278 #ifdef GHASH_USE_MODULO_BUCKETS
279 while ((nentries > gh->limit_grow) && (gh->cursize < GHASH_MAX_SIZE - 1)) {
280 new_nbuckets = hashsizes[++gh->cursize];
281 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
282 }
283 #else
284 while ((nentries > gh->limit_grow) && (gh->bucket_bit < GHASH_BUCKET_BIT_MAX)) {
285 new_nbuckets = 1u << ++gh->bucket_bit;
286 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
287 }
288 #endif
289
290 if (user_defined) {
291 #ifdef GHASH_USE_MODULO_BUCKETS
292 gh->size_min = gh->cursize;
293 #else
294 gh->bucket_bit_min = gh->bucket_bit;
295 #endif
296 }
297
298 if ((new_nbuckets == gh->nbuckets) && gh->buckets) {
299 return;
300 }
301
302 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
303 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
304 ghash_buckets_resize(gh, new_nbuckets);
305 }
306
ghash_buckets_contract(GHash * gh,const uint nentries,const bool user_defined,const bool force_shrink)307 static void ghash_buckets_contract(GHash *gh,
308 const uint nentries,
309 const bool user_defined,
310 const bool force_shrink)
311 {
312 uint new_nbuckets;
313
314 if (!(force_shrink || (gh->flag & GHASH_FLAG_ALLOW_SHRINK))) {
315 return;
316 }
317
318 if (LIKELY(gh->buckets && (nentries > gh->limit_shrink))) {
319 return;
320 }
321
322 new_nbuckets = gh->nbuckets;
323
324 #ifdef GHASH_USE_MODULO_BUCKETS
325 while ((nentries < gh->limit_shrink) && (gh->cursize > gh->size_min)) {
326 new_nbuckets = hashsizes[--gh->cursize];
327 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
328 }
329 #else
330 while ((nentries < gh->limit_shrink) && (gh->bucket_bit > gh->bucket_bit_min)) {
331 new_nbuckets = 1u << --gh->bucket_bit;
332 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
333 }
334 #endif
335
336 if (user_defined) {
337 #ifdef GHASH_USE_MODULO_BUCKETS
338 gh->size_min = gh->cursize;
339 #else
340 gh->bucket_bit_min = gh->bucket_bit;
341 #endif
342 }
343
344 if ((new_nbuckets == gh->nbuckets) && gh->buckets) {
345 return;
346 }
347
348 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
349 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
350 ghash_buckets_resize(gh, new_nbuckets);
351 }
352
353 /**
354 * Clear and reset \a gh buckets, reserve again buckets for given number of entries.
355 */
ghash_buckets_reset(GHash * gh,const uint nentries)356 BLI_INLINE void ghash_buckets_reset(GHash *gh, const uint nentries)
357 {
358 MEM_SAFE_FREE(gh->buckets);
359
360 #ifdef GHASH_USE_MODULO_BUCKETS
361 gh->cursize = 0;
362 gh->size_min = 0;
363 gh->nbuckets = hashsizes[gh->cursize];
364 #else
365 gh->bucket_bit = GHASH_BUCKET_BIT_MIN;
366 gh->bucket_bit_min = GHASH_BUCKET_BIT_MIN;
367 gh->nbuckets = 1u << gh->bucket_bit;
368 gh->bucket_mask = gh->nbuckets - 1;
369 #endif
370
371 gh->limit_grow = GHASH_LIMIT_GROW(gh->nbuckets);
372 gh->limit_shrink = GHASH_LIMIT_SHRINK(gh->nbuckets);
373
374 gh->nentries = 0;
375
376 ghash_buckets_expand(gh, nentries, (nentries != 0));
377 }
378
379 /**
380 * Internal lookup function.
381 * Takes hash and bucket_index arguments to avoid calling #ghash_keyhash and #ghash_bucket_index
382 * multiple times.
383 */
ghash_lookup_entry_ex(GHash * gh,const void * key,const uint bucket_index)384 BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key, const uint bucket_index)
385 {
386 Entry *e;
387 /* If we do not store GHash, not worth computing it for each entry here!
388 * Typically, comparison function will be quicker, and since it's needed in the end anyway... */
389 for (e = gh->buckets[bucket_index]; e; e = e->next) {
390 if (UNLIKELY(gh->cmpfp(key, e->key) == false)) {
391 return e;
392 }
393 }
394
395 return NULL;
396 }
397
398 /**
399 * Internal lookup function, returns previous entry of target one too.
400 * Takes bucket_index argument to avoid calling #ghash_keyhash and #ghash_bucket_index
401 * multiple times.
402 * Useful when modifying buckets somehow (like removing an entry...).
403 */
ghash_lookup_entry_prev_ex(GHash * gh,const void * key,Entry ** r_e_prev,const uint bucket_index)404 BLI_INLINE Entry *ghash_lookup_entry_prev_ex(GHash *gh,
405 const void *key,
406 Entry **r_e_prev,
407 const uint bucket_index)
408 {
409 /* If we do not store GHash, not worth computing it for each entry here!
410 * Typically, comparison function will be quicker, and since it's needed in the end anyway... */
411 for (Entry *e_prev = NULL, *e = gh->buckets[bucket_index]; e; e_prev = e, e = e->next) {
412 if (UNLIKELY(gh->cmpfp(key, e->key) == false)) {
413 *r_e_prev = e_prev;
414 return e;
415 }
416 }
417
418 *r_e_prev = NULL;
419 return NULL;
420 }
421
422 /**
423 * Internal lookup function. Only wraps #ghash_lookup_entry_ex
424 */
ghash_lookup_entry(GHash * gh,const void * key)425 BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key)
426 {
427 const uint hash = ghash_keyhash(gh, key);
428 const uint bucket_index = ghash_bucket_index(gh, hash);
429 return ghash_lookup_entry_ex(gh, key, bucket_index);
430 }
431
ghash_new(GHashHashFP hashfp,GHashCmpFP cmpfp,const char * info,const uint nentries_reserve,const uint flag)432 static GHash *ghash_new(GHashHashFP hashfp,
433 GHashCmpFP cmpfp,
434 const char *info,
435 const uint nentries_reserve,
436 const uint flag)
437 {
438 GHash *gh = MEM_mallocN(sizeof(*gh), info);
439
440 gh->hashfp = hashfp;
441 gh->cmpfp = cmpfp;
442
443 gh->buckets = NULL;
444 gh->flag = flag;
445
446 ghash_buckets_reset(gh, nentries_reserve);
447 gh->entrypool = BLI_mempool_create(
448 GHASH_ENTRY_SIZE(flag & GHASH_FLAG_IS_GSET), 64, 64, BLI_MEMPOOL_NOP);
449
450 return gh;
451 }
452
453 /**
454 * Internal insert function.
455 * Takes hash and bucket_index arguments to avoid calling #ghash_keyhash and #ghash_bucket_index
456 * multiple times.
457 */
ghash_insert_ex(GHash * gh,void * key,void * val,const uint bucket_index)458 BLI_INLINE void ghash_insert_ex(GHash *gh, void *key, void *val, const uint bucket_index)
459 {
460 GHashEntry *e = BLI_mempool_alloc(gh->entrypool);
461
462 BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
463 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
464
465 e->e.next = gh->buckets[bucket_index];
466 e->e.key = key;
467 e->val = val;
468 gh->buckets[bucket_index] = (Entry *)e;
469
470 ghash_buckets_expand(gh, ++gh->nentries, false);
471 }
472
473 /**
474 * Insert function that takes a pre-allocated entry.
475 */
ghash_insert_ex_keyonly_entry(GHash * gh,void * key,const uint bucket_index,Entry * e)476 BLI_INLINE void ghash_insert_ex_keyonly_entry(GHash *gh,
477 void *key,
478 const uint bucket_index,
479 Entry *e)
480 {
481 BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
482
483 e->next = gh->buckets[bucket_index];
484 e->key = key;
485 gh->buckets[bucket_index] = e;
486
487 ghash_buckets_expand(gh, ++gh->nentries, false);
488 }
489
490 /**
491 * Insert function that doesn't set the value (use for GSet)
492 */
ghash_insert_ex_keyonly(GHash * gh,void * key,const uint bucket_index)493 BLI_INLINE void ghash_insert_ex_keyonly(GHash *gh, void *key, const uint bucket_index)
494 {
495 Entry *e = BLI_mempool_alloc(gh->entrypool);
496
497 BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
498 BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0);
499
500 e->next = gh->buckets[bucket_index];
501 e->key = key;
502 gh->buckets[bucket_index] = e;
503
504 ghash_buckets_expand(gh, ++gh->nentries, false);
505 }
506
ghash_insert(GHash * gh,void * key,void * val)507 BLI_INLINE void ghash_insert(GHash *gh, void *key, void *val)
508 {
509 const uint hash = ghash_keyhash(gh, key);
510 const uint bucket_index = ghash_bucket_index(gh, hash);
511
512 ghash_insert_ex(gh, key, val, bucket_index);
513 }
514
ghash_insert_safe(GHash * gh,void * key,void * val,const bool override,GHashKeyFreeFP keyfreefp,GHashValFreeFP valfreefp)515 BLI_INLINE bool ghash_insert_safe(GHash *gh,
516 void *key,
517 void *val,
518 const bool override,
519 GHashKeyFreeFP keyfreefp,
520 GHashValFreeFP valfreefp)
521 {
522 const uint hash = ghash_keyhash(gh, key);
523 const uint bucket_index = ghash_bucket_index(gh, hash);
524 GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index);
525
526 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
527
528 if (e) {
529 if (override) {
530 if (keyfreefp) {
531 keyfreefp(e->e.key);
532 }
533 if (valfreefp) {
534 valfreefp(e->val);
535 }
536 e->e.key = key;
537 e->val = val;
538 }
539 return false;
540 }
541 ghash_insert_ex(gh, key, val, bucket_index);
542 return true;
543 }
544
ghash_insert_safe_keyonly(GHash * gh,void * key,const bool override,GHashKeyFreeFP keyfreefp)545 BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh,
546 void *key,
547 const bool override,
548 GHashKeyFreeFP keyfreefp)
549 {
550 const uint hash = ghash_keyhash(gh, key);
551 const uint bucket_index = ghash_bucket_index(gh, hash);
552 Entry *e = ghash_lookup_entry_ex(gh, key, bucket_index);
553
554 BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0);
555
556 if (e) {
557 if (override) {
558 if (keyfreefp) {
559 keyfreefp(e->key);
560 }
561 e->key = key;
562 }
563 return false;
564 }
565 ghash_insert_ex_keyonly(gh, key, bucket_index);
566 return true;
567 }
568
569 /**
570 * Remove the entry and return it, caller must free from gh->entrypool.
571 */
ghash_remove_ex(GHash * gh,const void * key,GHashKeyFreeFP keyfreefp,GHashValFreeFP valfreefp,const uint bucket_index)572 static Entry *ghash_remove_ex(GHash *gh,
573 const void *key,
574 GHashKeyFreeFP keyfreefp,
575 GHashValFreeFP valfreefp,
576 const uint bucket_index)
577 {
578 Entry *e_prev;
579 Entry *e = ghash_lookup_entry_prev_ex(gh, key, &e_prev, bucket_index);
580
581 BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET));
582
583 if (e) {
584 if (keyfreefp) {
585 keyfreefp(e->key);
586 }
587 if (valfreefp) {
588 valfreefp(((GHashEntry *)e)->val);
589 }
590
591 if (e_prev) {
592 e_prev->next = e->next;
593 }
594 else {
595 gh->buckets[bucket_index] = e->next;
596 }
597
598 ghash_buckets_contract(gh, --gh->nentries, false, false);
599 }
600
601 return e;
602 }
603
604 /**
605 * Remove a random entry and return it (or NULL if empty), caller must free from gh->entrypool.
606 */
ghash_pop(GHash * gh,GHashIterState * state)607 static Entry *ghash_pop(GHash *gh, GHashIterState *state)
608 {
609 uint curr_bucket = state->curr_bucket;
610 if (gh->nentries == 0) {
611 return NULL;
612 }
613
614 /* Note: using first_bucket_index here allows us to avoid potential
615 * huge number of loops over buckets,
616 * in case we are popping from a large ghash with few items in it... */
617 curr_bucket = ghash_find_next_bucket_index(gh, curr_bucket);
618
619 Entry *e = gh->buckets[curr_bucket];
620 BLI_assert(e);
621
622 ghash_remove_ex(gh, e->key, NULL, NULL, curr_bucket);
623
624 state->curr_bucket = curr_bucket;
625 return e;
626 }
627
628 /**
629 * Run free callbacks for freeing entries.
630 */
ghash_free_cb(GHash * gh,GHashKeyFreeFP keyfreefp,GHashValFreeFP valfreefp)631 static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
632 {
633 uint i;
634
635 BLI_assert(keyfreefp || valfreefp);
636 BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET));
637
638 for (i = 0; i < gh->nbuckets; i++) {
639 Entry *e;
640
641 for (e = gh->buckets[i]; e; e = e->next) {
642 if (keyfreefp) {
643 keyfreefp(e->key);
644 }
645 if (valfreefp) {
646 valfreefp(((GHashEntry *)e)->val);
647 }
648 }
649 }
650 }
651
652 /**
653 * Copy the GHash.
654 */
ghash_copy(GHash * gh,GHashKeyCopyFP keycopyfp,GHashValCopyFP valcopyfp)655 static GHash *ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
656 {
657 GHash *gh_new;
658 uint i;
659 /* This allows us to be sure to get the same number of buckets in gh_new as in ghash. */
660 const uint reserve_nentries_new = MAX2(GHASH_LIMIT_GROW(gh->nbuckets) - 1, gh->nentries);
661
662 BLI_assert(!valcopyfp || !(gh->flag & GHASH_FLAG_IS_GSET));
663
664 gh_new = ghash_new(gh->hashfp, gh->cmpfp, __func__, 0, gh->flag);
665 ghash_buckets_expand(gh_new, reserve_nentries_new, false);
666
667 BLI_assert(gh_new->nbuckets == gh->nbuckets);
668
669 for (i = 0; i < gh->nbuckets; i++) {
670 Entry *e;
671
672 for (e = gh->buckets[i]; e; e = e->next) {
673 Entry *e_new = BLI_mempool_alloc(gh_new->entrypool);
674 ghash_entry_copy(gh_new, e_new, gh, e, keycopyfp, valcopyfp);
675
676 /* Warning!
677 * This means entries in buckets in new copy will be in reversed order!
678 * This shall not be an issue though, since order should never be assumed in ghash. */
679
680 /* Note: We can use 'i' here, since we are sure that
681 * 'gh' and 'gh_new' have the same number of buckets! */
682 e_new->next = gh_new->buckets[i];
683 gh_new->buckets[i] = e_new;
684 }
685 }
686 gh_new->nentries = gh->nentries;
687
688 return gh_new;
689 }
690
691 /** \} */
692
693 /* -------------------------------------------------------------------- */
694 /** \name GHash Public API
695 * \{ */
696
697 /**
698 * Creates a new, empty GHash.
699 *
700 * \param hashfp: Hash callback.
701 * \param cmpfp: Comparison callback.
702 * \param info: Identifier string for the GHash.
703 * \param nentries_reserve: Optionally reserve the number of members that the hash will hold.
704 * Use this to avoid resizing buckets if the size is known or can be closely approximated.
705 * \return An empty GHash.
706 */
BLI_ghash_new_ex(GHashHashFP hashfp,GHashCmpFP cmpfp,const char * info,const uint nentries_reserve)707 GHash *BLI_ghash_new_ex(GHashHashFP hashfp,
708 GHashCmpFP cmpfp,
709 const char *info,
710 const uint nentries_reserve)
711 {
712 return ghash_new(hashfp, cmpfp, info, nentries_reserve, 0);
713 }
714
715 /**
716 * Wraps #BLI_ghash_new_ex with zero entries reserved.
717 */
BLI_ghash_new(GHashHashFP hashfp,GHashCmpFP cmpfp,const char * info)718 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
719 {
720 return BLI_ghash_new_ex(hashfp, cmpfp, info, 0);
721 }
722
723 /**
724 * Copy given GHash. Keys and values are also copied if relevant callback is provided,
725 * else pointers remain the same.
726 */
BLI_ghash_copy(GHash * gh,GHashKeyCopyFP keycopyfp,GHashValCopyFP valcopyfp)727 GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
728 {
729 return ghash_copy(gh, keycopyfp, valcopyfp);
730 }
731
732 /**
733 * Reserve given amount of entries (resize \a gh accordingly if needed).
734 */
BLI_ghash_reserve(GHash * gh,const uint nentries_reserve)735 void BLI_ghash_reserve(GHash *gh, const uint nentries_reserve)
736 {
737 ghash_buckets_expand(gh, nentries_reserve, true);
738 ghash_buckets_contract(gh, nentries_reserve, true, false);
739 }
740
741 /**
742 * \return size of the GHash.
743 */
BLI_ghash_len(GHash * gh)744 uint BLI_ghash_len(GHash *gh)
745 {
746 return gh->nentries;
747 }
748
749 /**
750 * Insert a key/value pair into the \a gh.
751 *
752 * \note Duplicates are not checked,
753 * the caller is expected to ensure elements are unique unless
754 * GHASH_FLAG_ALLOW_DUPES flag is set.
755 */
BLI_ghash_insert(GHash * gh,void * key,void * val)756 void BLI_ghash_insert(GHash *gh, void *key, void *val)
757 {
758 ghash_insert(gh, key, val);
759 }
760
761 /**
762 * Inserts a new value to a key that may already be in ghash.
763 *
764 * Avoids #BLI_ghash_remove, #BLI_ghash_insert calls (double lookups)
765 *
766 * \returns true if a new key has been added.
767 */
BLI_ghash_reinsert(GHash * gh,void * key,void * val,GHashKeyFreeFP keyfreefp,GHashValFreeFP valfreefp)768 bool BLI_ghash_reinsert(
769 GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
770 {
771 return ghash_insert_safe(gh, key, val, true, keyfreefp, valfreefp);
772 }
773
774 /**
775 * Replaces the key of an item in the \a gh.
776 *
777 * Use when a key is re-allocated or its memory location is changed.
778 *
779 * \returns The previous key or NULL if not found, the caller may free if it's needed.
780 */
BLI_ghash_replace_key(GHash * gh,void * key)781 void *BLI_ghash_replace_key(GHash *gh, void *key)
782 {
783 const uint hash = ghash_keyhash(gh, key);
784 const uint bucket_index = ghash_bucket_index(gh, hash);
785 GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index);
786 if (e != NULL) {
787 void *key_prev = e->e.key;
788 e->e.key = key;
789 return key_prev;
790 }
791 return NULL;
792 }
793
794 /**
795 * Lookup the value of \a key in \a gh.
796 *
797 * \param key: The key to lookup.
798 * \returns the value for \a key or NULL.
799 *
800 * \note When NULL is a valid value, use #BLI_ghash_lookup_p to differentiate a missing key
801 * from a key with a NULL value. (Avoids calling #BLI_ghash_haskey before #BLI_ghash_lookup)
802 */
BLI_ghash_lookup(GHash * gh,const void * key)803 void *BLI_ghash_lookup(GHash *gh, const void *key)
804 {
805 GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key);
806 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
807 return e ? e->val : NULL;
808 }
809
810 /**
811 * A version of #BLI_ghash_lookup which accepts a fallback argument.
812 */
BLI_ghash_lookup_default(GHash * gh,const void * key,void * val_default)813 void *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default)
814 {
815 GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key);
816 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
817 return e ? e->val : val_default;
818 }
819
820 /**
821 * Lookup a pointer to the value of \a key in \a gh.
822 *
823 * \param key: The key to lookup.
824 * \returns the pointer to value for \a key or NULL.
825 *
826 * \note This has 2 main benefits over #BLI_ghash_lookup.
827 * - A NULL return always means that \a key isn't in \a gh.
828 * - The value can be modified in-place without further function calls (faster).
829 */
BLI_ghash_lookup_p(GHash * gh,const void * key)830 void **BLI_ghash_lookup_p(GHash *gh, const void *key)
831 {
832 GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key);
833 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
834 return e ? &e->val : NULL;
835 }
836
837 /**
838 * Ensure \a key is exists in \a gh.
839 *
840 * This handles the common situation where the caller needs ensure a key is added to \a gh,
841 * constructing a new value in the case the key isn't found.
842 * Otherwise use the existing value.
843 *
844 * Such situations typically incur multiple lookups, however this function
845 * avoids them by ensuring the key is added,
846 * returning a pointer to the value so it can be used or initialized by the caller.
847 *
848 * \returns true when the value didn't need to be added.
849 * (when false, the caller _must_ initialize the value).
850 */
BLI_ghash_ensure_p(GHash * gh,void * key,void *** r_val)851 bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val)
852 {
853 const uint hash = ghash_keyhash(gh, key);
854 const uint bucket_index = ghash_bucket_index(gh, hash);
855 GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index);
856 const bool haskey = (e != NULL);
857
858 if (!haskey) {
859 e = BLI_mempool_alloc(gh->entrypool);
860 ghash_insert_ex_keyonly_entry(gh, key, bucket_index, (Entry *)e);
861 }
862
863 *r_val = &e->val;
864 return haskey;
865 }
866
867 /**
868 * A version of #BLI_ghash_ensure_p that allows caller to re-assign the key.
869 * Typically used when the key is to be duplicated.
870 *
871 * \warning Caller _must_ write to \a r_key when returning false.
872 */
BLI_ghash_ensure_p_ex(GHash * gh,const void * key,void *** r_key,void *** r_val)873 bool BLI_ghash_ensure_p_ex(GHash *gh, const void *key, void ***r_key, void ***r_val)
874 {
875 const uint hash = ghash_keyhash(gh, key);
876 const uint bucket_index = ghash_bucket_index(gh, hash);
877 GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index);
878 const bool haskey = (e != NULL);
879
880 if (!haskey) {
881 /* Pass 'key' in case we resize. */
882 e = BLI_mempool_alloc(gh->entrypool);
883 ghash_insert_ex_keyonly_entry(gh, (void *)key, bucket_index, (Entry *)e);
884 e->e.key = NULL; /* caller must re-assign */
885 }
886
887 *r_key = &e->e.key;
888 *r_val = &e->val;
889 return haskey;
890 }
891
892 /**
893 * Remove \a key from \a gh, or return false if the key wasn't found.
894 *
895 * \param key: The key to remove.
896 * \param keyfreefp: Optional callback to free the key.
897 * \param valfreefp: Optional callback to free the value.
898 * \return true if \a key was removed from \a gh.
899 */
BLI_ghash_remove(GHash * gh,const void * key,GHashKeyFreeFP keyfreefp,GHashValFreeFP valfreefp)900 bool BLI_ghash_remove(GHash *gh,
901 const void *key,
902 GHashKeyFreeFP keyfreefp,
903 GHashValFreeFP valfreefp)
904 {
905 const uint hash = ghash_keyhash(gh, key);
906 const uint bucket_index = ghash_bucket_index(gh, hash);
907 Entry *e = ghash_remove_ex(gh, key, keyfreefp, valfreefp, bucket_index);
908 if (e) {
909 BLI_mempool_free(gh->entrypool, e);
910 return true;
911 }
912 return false;
913 }
914
915 /* same as above but return the value,
916 * no free value argument since it will be returned */
917 /**
918 * Remove \a key from \a gh, returning the value or NULL if the key wasn't found.
919 *
920 * \param key: The key to remove.
921 * \param keyfreefp: Optional callback to free the key.
922 * \return the value of \a key int \a gh or NULL.
923 */
BLI_ghash_popkey(GHash * gh,const void * key,GHashKeyFreeFP keyfreefp)924 void *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp)
925 {
926 const uint hash = ghash_keyhash(gh, key);
927 const uint bucket_index = ghash_bucket_index(gh, hash);
928 GHashEntry *e = (GHashEntry *)ghash_remove_ex(gh, key, keyfreefp, NULL, bucket_index);
929 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
930 if (e) {
931 void *val = e->val;
932 BLI_mempool_free(gh->entrypool, e);
933 return val;
934 }
935 return NULL;
936 }
937
938 /**
939 * \return true if the \a key is in \a gh.
940 */
BLI_ghash_haskey(GHash * gh,const void * key)941 bool BLI_ghash_haskey(GHash *gh, const void *key)
942 {
943 return (ghash_lookup_entry(gh, key) != NULL);
944 }
945
946 /**
947 * Remove a random entry from \a gh, returning true
948 * if a key/value pair could be removed, false otherwise.
949 *
950 * \param r_key: The removed key.
951 * \param r_val: The removed value.
952 * \param state: Used for efficient removal.
953 * \return true if there was something to pop, false if ghash was already empty.
954 */
BLI_ghash_pop(GHash * gh,GHashIterState * state,void ** r_key,void ** r_val)955 bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val)
956 {
957 GHashEntry *e = (GHashEntry *)ghash_pop(gh, state);
958
959 BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
960
961 if (e) {
962 *r_key = e->e.key;
963 *r_val = e->val;
964
965 BLI_mempool_free(gh->entrypool, e);
966 return true;
967 }
968
969 *r_key = *r_val = NULL;
970 return false;
971 }
972
973 /**
974 * Reset \a gh clearing all entries.
975 *
976 * \param keyfreefp: Optional callback to free the key.
977 * \param valfreefp: Optional callback to free the value.
978 * \param nentries_reserve: Optionally reserve the number of members that the hash will hold.
979 */
BLI_ghash_clear_ex(GHash * gh,GHashKeyFreeFP keyfreefp,GHashValFreeFP valfreefp,const uint nentries_reserve)980 void BLI_ghash_clear_ex(GHash *gh,
981 GHashKeyFreeFP keyfreefp,
982 GHashValFreeFP valfreefp,
983 const uint nentries_reserve)
984 {
985 if (keyfreefp || valfreefp) {
986 ghash_free_cb(gh, keyfreefp, valfreefp);
987 }
988
989 ghash_buckets_reset(gh, nentries_reserve);
990 BLI_mempool_clear_ex(gh->entrypool, nentries_reserve ? (int)nentries_reserve : -1);
991 }
992
993 /**
994 * Wraps #BLI_ghash_clear_ex with zero entries reserved.
995 */
BLI_ghash_clear(GHash * gh,GHashKeyFreeFP keyfreefp,GHashValFreeFP valfreefp)996 void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
997 {
998 BLI_ghash_clear_ex(gh, keyfreefp, valfreefp, 0);
999 }
1000
1001 /**
1002 * Frees the GHash and its members.
1003 *
1004 * \param gh: The GHash to free.
1005 * \param keyfreefp: Optional callback to free the key.
1006 * \param valfreefp: Optional callback to free the value.
1007 */
BLI_ghash_free(GHash * gh,GHashKeyFreeFP keyfreefp,GHashValFreeFP valfreefp)1008 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
1009 {
1010 BLI_assert((int)gh->nentries == BLI_mempool_len(gh->entrypool));
1011 if (keyfreefp || valfreefp) {
1012 ghash_free_cb(gh, keyfreefp, valfreefp);
1013 }
1014
1015 MEM_freeN(gh->buckets);
1016 BLI_mempool_destroy(gh->entrypool);
1017 MEM_freeN(gh);
1018 }
1019
1020 /**
1021 * Sets a GHash flag.
1022 */
BLI_ghash_flag_set(GHash * gh,uint flag)1023 void BLI_ghash_flag_set(GHash *gh, uint flag)
1024 {
1025 gh->flag |= flag;
1026 }
1027
1028 /**
1029 * Clear a GHash flag.
1030 */
BLI_ghash_flag_clear(GHash * gh,uint flag)1031 void BLI_ghash_flag_clear(GHash *gh, uint flag)
1032 {
1033 gh->flag &= ~flag;
1034 }
1035
1036 /** \} */
1037
1038 /* -------------------------------------------------------------------- */
1039 /** \name GHash Iterator API
1040 * \{ */
1041
1042 /**
1043 * Create a new GHashIterator. The hash table must not be mutated
1044 * while the iterator is in use, and the iterator will step exactly
1045 * #BLI_ghash_len(gh) times before becoming done.
1046 *
1047 * \param gh: The GHash to iterate over.
1048 * \return Pointer to a new iterator.
1049 */
BLI_ghashIterator_new(GHash * gh)1050 GHashIterator *BLI_ghashIterator_new(GHash *gh)
1051 {
1052 GHashIterator *ghi = MEM_mallocN(sizeof(*ghi), "ghash iterator");
1053 BLI_ghashIterator_init(ghi, gh);
1054 return ghi;
1055 }
1056
1057 /**
1058 * Init an already allocated GHashIterator. The hash table must not
1059 * be mutated while the iterator is in use, and the iterator will
1060 * step exactly #BLI_ghash_len(gh) times before becoming done.
1061 *
1062 * \param ghi: The GHashIterator to initialize.
1063 * \param gh: The GHash to iterate over.
1064 */
BLI_ghashIterator_init(GHashIterator * ghi,GHash * gh)1065 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
1066 {
1067 ghi->gh = gh;
1068 ghi->curEntry = NULL;
1069 ghi->curBucket = UINT_MAX; /* wraps to zero */
1070 if (gh->nentries) {
1071 do {
1072 ghi->curBucket++;
1073 if (UNLIKELY(ghi->curBucket == ghi->gh->nbuckets)) {
1074 break;
1075 }
1076 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
1077 } while (!ghi->curEntry);
1078 }
1079 }
1080
1081 /**
1082 * Steps the iterator to the next index.
1083 *
1084 * \param ghi: The iterator.
1085 */
BLI_ghashIterator_step(GHashIterator * ghi)1086 void BLI_ghashIterator_step(GHashIterator *ghi)
1087 {
1088 if (ghi->curEntry) {
1089 ghi->curEntry = ghi->curEntry->next;
1090 while (!ghi->curEntry) {
1091 ghi->curBucket++;
1092 if (ghi->curBucket == ghi->gh->nbuckets) {
1093 break;
1094 }
1095 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
1096 }
1097 }
1098 }
1099
1100 /**
1101 * Free a GHashIterator.
1102 *
1103 * \param ghi: The iterator to free.
1104 */
BLI_ghashIterator_free(GHashIterator * ghi)1105 void BLI_ghashIterator_free(GHashIterator *ghi)
1106 {
1107 MEM_freeN(ghi);
1108 }
1109
1110 /** \} */
1111
1112 /* -------------------------------------------------------------------- */
1113 /** \name GSet Public API
1114 *
1115 * Use ghash API to give 'set' functionality
1116 * \{ */
BLI_gset_new_ex(GSetHashFP hashfp,GSetCmpFP cmpfp,const char * info,const uint nentries_reserve)1117 GSet *BLI_gset_new_ex(GSetHashFP hashfp,
1118 GSetCmpFP cmpfp,
1119 const char *info,
1120 const uint nentries_reserve)
1121 {
1122 return (GSet *)ghash_new(hashfp, cmpfp, info, nentries_reserve, GHASH_FLAG_IS_GSET);
1123 }
1124
BLI_gset_new(GSetHashFP hashfp,GSetCmpFP cmpfp,const char * info)1125 GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info)
1126 {
1127 return BLI_gset_new_ex(hashfp, cmpfp, info, 0);
1128 }
1129
1130 /**
1131 * Copy given GSet. Keys are also copied if callback is provided, else pointers remain the same.
1132 */
BLI_gset_copy(GSet * gs,GHashKeyCopyFP keycopyfp)1133 GSet *BLI_gset_copy(GSet *gs, GHashKeyCopyFP keycopyfp)
1134 {
1135 return (GSet *)ghash_copy((GHash *)gs, keycopyfp, NULL);
1136 }
1137
BLI_gset_len(GSet * gs)1138 uint BLI_gset_len(GSet *gs)
1139 {
1140 return ((GHash *)gs)->nentries;
1141 }
1142
1143 /**
1144 * Adds the key to the set (no checks for unique keys!).
1145 * Matching #BLI_ghash_insert
1146 */
BLI_gset_insert(GSet * gs,void * key)1147 void BLI_gset_insert(GSet *gs, void *key)
1148 {
1149 const uint hash = ghash_keyhash((GHash *)gs, key);
1150 const uint bucket_index = ghash_bucket_index((GHash *)gs, hash);
1151 ghash_insert_ex_keyonly((GHash *)gs, key, bucket_index);
1152 }
1153
1154 /**
1155 * A version of BLI_gset_insert which checks first if the key is in the set.
1156 * \returns true if a new key has been added.
1157 *
1158 * \note GHash has no equivalent to this because typically the value would be different.
1159 */
BLI_gset_add(GSet * gs,void * key)1160 bool BLI_gset_add(GSet *gs, void *key)
1161 {
1162 return ghash_insert_safe_keyonly((GHash *)gs, key, false, NULL);
1163 }
1164
1165 /**
1166 * Set counterpart to #BLI_ghash_ensure_p_ex.
1167 * similar to BLI_gset_add, except it returns the key pointer.
1168 *
1169 * \warning Caller _must_ write to \a r_key when returning false.
1170 */
BLI_gset_ensure_p_ex(GSet * gs,const void * key,void *** r_key)1171 bool BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key)
1172 {
1173 const uint hash = ghash_keyhash((GHash *)gs, key);
1174 const uint bucket_index = ghash_bucket_index((GHash *)gs, hash);
1175 GSetEntry *e = (GSetEntry *)ghash_lookup_entry_ex((GHash *)gs, key, bucket_index);
1176 const bool haskey = (e != NULL);
1177
1178 if (!haskey) {
1179 /* Pass 'key' in case we resize */
1180 e = BLI_mempool_alloc(((GHash *)gs)->entrypool);
1181 ghash_insert_ex_keyonly_entry((GHash *)gs, (void *)key, bucket_index, (Entry *)e);
1182 e->key = NULL; /* caller must re-assign */
1183 }
1184
1185 *r_key = &e->key;
1186 return haskey;
1187 }
1188
1189 /**
1190 * Adds the key to the set (duplicates are managed).
1191 * Matching #BLI_ghash_reinsert
1192 *
1193 * \returns true if a new key has been added.
1194 */
BLI_gset_reinsert(GSet * gs,void * key,GSetKeyFreeFP keyfreefp)1195 bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp)
1196 {
1197 return ghash_insert_safe_keyonly((GHash *)gs, key, true, keyfreefp);
1198 }
1199
1200 /**
1201 * Replaces the key to the set if it's found.
1202 * Matching #BLI_ghash_replace_key
1203 *
1204 * \returns The old key or NULL if not found.
1205 */
BLI_gset_replace_key(GSet * gs,void * key)1206 void *BLI_gset_replace_key(GSet *gs, void *key)
1207 {
1208 return BLI_ghash_replace_key((GHash *)gs, key);
1209 }
1210
BLI_gset_remove(GSet * gs,const void * key,GSetKeyFreeFP keyfreefp)1211 bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp)
1212 {
1213 return BLI_ghash_remove((GHash *)gs, key, keyfreefp, NULL);
1214 }
1215
BLI_gset_haskey(GSet * gs,const void * key)1216 bool BLI_gset_haskey(GSet *gs, const void *key)
1217 {
1218 return (ghash_lookup_entry((GHash *)gs, key) != NULL);
1219 }
1220
1221 /**
1222 * Remove a random entry from \a gs, returning true if a key could be removed, false otherwise.
1223 *
1224 * \param r_key: The removed key.
1225 * \param state: Used for efficient removal.
1226 * \return true if there was something to pop, false if gset was already empty.
1227 */
BLI_gset_pop(GSet * gs,GSetIterState * state,void ** r_key)1228 bool BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key)
1229 {
1230 GSetEntry *e = (GSetEntry *)ghash_pop((GHash *)gs, (GHashIterState *)state);
1231
1232 if (e) {
1233 *r_key = e->key;
1234
1235 BLI_mempool_free(((GHash *)gs)->entrypool, e);
1236 return true;
1237 }
1238
1239 *r_key = NULL;
1240 return false;
1241 }
1242
BLI_gset_clear_ex(GSet * gs,GSetKeyFreeFP keyfreefp,const uint nentries_reserve)1243 void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, const uint nentries_reserve)
1244 {
1245 BLI_ghash_clear_ex((GHash *)gs, keyfreefp, NULL, nentries_reserve);
1246 }
1247
BLI_gset_clear(GSet * gs,GSetKeyFreeFP keyfreefp)1248 void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
1249 {
1250 BLI_ghash_clear((GHash *)gs, keyfreefp, NULL);
1251 }
1252
BLI_gset_free(GSet * gs,GSetKeyFreeFP keyfreefp)1253 void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
1254 {
1255 BLI_ghash_free((GHash *)gs, keyfreefp, NULL);
1256 }
1257
BLI_gset_flag_set(GSet * gs,uint flag)1258 void BLI_gset_flag_set(GSet *gs, uint flag)
1259 {
1260 ((GHash *)gs)->flag |= flag;
1261 }
1262
BLI_gset_flag_clear(GSet * gs,uint flag)1263 void BLI_gset_flag_clear(GSet *gs, uint flag)
1264 {
1265 ((GHash *)gs)->flag &= ~flag;
1266 }
1267
1268 /** \} */
1269
1270 /* -------------------------------------------------------------------- */
1271 /** \name GSet Combined Key/Value Usage
1272 *
1273 * \note Not typical ``set`` use, only use when the pointer identity matters.
1274 * This can be useful when the key references data stored outside the GSet.
1275 * \{ */
1276
1277 /**
1278 * Returns the pointer to the key if it's found.
1279 */
BLI_gset_lookup(GSet * gs,const void * key)1280 void *BLI_gset_lookup(GSet *gs, const void *key)
1281 {
1282 Entry *e = ghash_lookup_entry((GHash *)gs, key);
1283 return e ? e->key : NULL;
1284 }
1285
1286 /**
1287 * Returns the pointer to the key if it's found, removing it from the GSet.
1288 * \note Caller must handle freeing.
1289 */
BLI_gset_pop_key(GSet * gs,const void * key)1290 void *BLI_gset_pop_key(GSet *gs, const void *key)
1291 {
1292 const uint hash = ghash_keyhash((GHash *)gs, key);
1293 const uint bucket_index = ghash_bucket_index((GHash *)gs, hash);
1294 Entry *e = ghash_remove_ex((GHash *)gs, key, NULL, NULL, bucket_index);
1295 if (e) {
1296 void *key_ret = e->key;
1297 BLI_mempool_free(((GHash *)gs)->entrypool, e);
1298 return key_ret;
1299 }
1300 return NULL;
1301 }
1302
1303 /** \} */
1304
1305 /* -------------------------------------------------------------------- */
1306 /** \name Debugging & Introspection
1307 * \{ */
1308
1309 #include "BLI_math.h"
1310
1311 /**
1312 * \return number of buckets in the GHash.
1313 */
BLI_ghash_buckets_len(GHash * gh)1314 int BLI_ghash_buckets_len(GHash *gh)
1315 {
1316 return (int)gh->nbuckets;
1317 }
BLI_gset_buckets_len(GSet * gs)1318 int BLI_gset_buckets_len(GSet *gs)
1319 {
1320 return BLI_ghash_buckets_len((GHash *)gs);
1321 }
1322
1323 /**
1324 * Measure how well the hash function performs (1.0 is approx as good as random distribution),
1325 * and return a few other stats like load,
1326 * variance of the distribution of the entries in the buckets, etc.
1327 *
1328 * Smaller is better!
1329 */
BLI_ghash_calc_quality_ex(GHash * gh,double * r_load,double * r_variance,double * r_prop_empty_buckets,double * r_prop_overloaded_buckets,int * r_biggest_bucket)1330 double BLI_ghash_calc_quality_ex(GHash *gh,
1331 double *r_load,
1332 double *r_variance,
1333 double *r_prop_empty_buckets,
1334 double *r_prop_overloaded_buckets,
1335 int *r_biggest_bucket)
1336 {
1337 double mean;
1338 uint i;
1339
1340 if (gh->nentries == 0) {
1341 if (r_load) {
1342 *r_load = 0.0;
1343 }
1344 if (r_variance) {
1345 *r_variance = 0.0;
1346 }
1347 if (r_prop_empty_buckets) {
1348 *r_prop_empty_buckets = 1.0;
1349 }
1350 if (r_prop_overloaded_buckets) {
1351 *r_prop_overloaded_buckets = 0.0;
1352 }
1353 if (r_biggest_bucket) {
1354 *r_biggest_bucket = 0;
1355 }
1356
1357 return 0.0;
1358 }
1359
1360 mean = (double)gh->nentries / (double)gh->nbuckets;
1361 if (r_load) {
1362 *r_load = mean;
1363 }
1364 if (r_biggest_bucket) {
1365 *r_biggest_bucket = 0;
1366 }
1367
1368 if (r_variance) {
1369 /* We already know our mean (i.e. load factor), easy to compute variance.
1370 * See https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Two-pass_algorithm
1371 */
1372 double sum = 0.0;
1373 for (i = 0; i < gh->nbuckets; i++) {
1374 int count = 0;
1375 Entry *e;
1376 for (e = gh->buckets[i]; e; e = e->next) {
1377 count++;
1378 }
1379 sum += ((double)count - mean) * ((double)count - mean);
1380 }
1381 *r_variance = sum / (double)(gh->nbuckets - 1);
1382 }
1383
1384 {
1385 uint64_t sum = 0;
1386 uint64_t overloaded_buckets_threshold = (uint64_t)max_ii(GHASH_LIMIT_GROW(1), 1);
1387 uint64_t sum_overloaded = 0;
1388 uint64_t sum_empty = 0;
1389
1390 for (i = 0; i < gh->nbuckets; i++) {
1391 uint64_t count = 0;
1392 Entry *e;
1393 for (e = gh->buckets[i]; e; e = e->next) {
1394 count++;
1395 }
1396 if (r_biggest_bucket) {
1397 *r_biggest_bucket = max_ii(*r_biggest_bucket, (int)count);
1398 }
1399 if (r_prop_overloaded_buckets && (count > overloaded_buckets_threshold)) {
1400 sum_overloaded++;
1401 }
1402 if (r_prop_empty_buckets && !count) {
1403 sum_empty++;
1404 }
1405 sum += count * (count + 1);
1406 }
1407 if (r_prop_overloaded_buckets) {
1408 *r_prop_overloaded_buckets = (double)sum_overloaded / (double)gh->nbuckets;
1409 }
1410 if (r_prop_empty_buckets) {
1411 *r_prop_empty_buckets = (double)sum_empty / (double)gh->nbuckets;
1412 }
1413 return ((double)sum * (double)gh->nbuckets /
1414 ((double)gh->nentries * (gh->nentries + 2 * gh->nbuckets - 1)));
1415 }
1416 }
BLI_gset_calc_quality_ex(GSet * gs,double * r_load,double * r_variance,double * r_prop_empty_buckets,double * r_prop_overloaded_buckets,int * r_biggest_bucket)1417 double BLI_gset_calc_quality_ex(GSet *gs,
1418 double *r_load,
1419 double *r_variance,
1420 double *r_prop_empty_buckets,
1421 double *r_prop_overloaded_buckets,
1422 int *r_biggest_bucket)
1423 {
1424 return BLI_ghash_calc_quality_ex((GHash *)gs,
1425 r_load,
1426 r_variance,
1427 r_prop_empty_buckets,
1428 r_prop_overloaded_buckets,
1429 r_biggest_bucket);
1430 }
1431
BLI_ghash_calc_quality(GHash * gh)1432 double BLI_ghash_calc_quality(GHash *gh)
1433 {
1434 return BLI_ghash_calc_quality_ex(gh, NULL, NULL, NULL, NULL, NULL);
1435 }
BLI_gset_calc_quality(GSet * gs)1436 double BLI_gset_calc_quality(GSet *gs)
1437 {
1438 return BLI_ghash_calc_quality_ex((GHash *)gs, NULL, NULL, NULL, NULL, NULL);
1439 }
1440
1441 /** \} */
1442