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