BLI_ghash: Fix initial over-allocation of mempool chunks.
[blender.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_hash_mm2a.h"
47 #include "BLI_mempool.h"
48
49 #define GHASH_INTERNAL_API
50 #include "BLI_ghash.h"
51 #include "BLI_strict_flags.h"
52
53 #define GHASH_USE_MODULO_BUCKETS
54
55 /* Also used by smallhash! */
56 const unsigned int hashsizes[] = {
57         5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
58         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
59         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
60         268435459
61 };
62
63 #ifdef GHASH_USE_MODULO_BUCKETS
64 #  define GHASH_MAX_SIZE 27
65 #else
66 #  define GHASH_BUCKET_BIT_MIN 2
67 #  define GHASH_BUCKET_BIT_MAX 28  /* About 268M of buckets... */
68 #endif
69
70 /**
71  * \note Max load #GHASH_LIMIT_GROW used to be 3. (pre 2.74).
72  * Python uses 0.6666, tommyhaslib even goes down to 0.5.
73  * Reducing our from 3 to 0.75 gives huge speedup (about twice quicker pure GHash insertions/lookup,
74  * about 25% - 30% quicker 'dynamic-topology' stroke drawing e.g.).
75  * Min load #GHASH_LIMIT_SHRINK is a quarter of max load, to avoid resizing to quickly.
76  */
77 #define GHASH_LIMIT_GROW(_nbkt)   (((_nbkt) * 3) /  4)
78 #define GHASH_LIMIT_SHRINK(_nbkt) (((_nbkt) * 3) / 16)
79
80 /***/
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) \
98         ((_is_gset) ? sizeof(GSetEntry) : sizeof(GHashEntry))
99
100 struct GHash {
101         GHashHashFP hashfp;
102         GHashCmpFP cmpfp;
103
104         Entry **buckets;
105         struct BLI_mempool *entrypool;
106         unsigned int nbuckets;
107         unsigned int limit_grow, limit_shrink;
108 #ifdef GHASH_USE_MODULO_BUCKETS
109         unsigned int cursize, size_min;
110 #else
111         unsigned int bucket_mask, bucket_bit, bucket_bit_min;
112 #endif
113
114         unsigned int nentries;
115         unsigned int flag;
116 };
117
118
119 BLI_INLINE void ghash_entry_copy(
120         GHash *gh_dst, Entry *dst, GHash *gh_src, Entry *src,
121         GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
122 {
123         dst->key = (keycopyfp) ? keycopyfp(src->key) : src->key;
124
125         if ((gh_dst->flag & GHASH_FLAG_IS_GSET) == 0) {
126                 if ((gh_src->flag & GHASH_FLAG_IS_GSET) == 0) {
127                         ((GHashEntry *)dst)->val = (valcopyfp) ? valcopyfp(((GHashEntry *)src)->val) : ((GHashEntry *)src)->val;
128                 }
129                 else {
130                         ((GHashEntry *)dst)->val = NULL;
131                 }
132         }
133 }
134
135 /* -------------------------------------------------------------------- */
136 /* GHash API */
137
138 /** \name Internal Utility API
139  * \{ */
140
141 /**
142  * Get the full hash for a key.
143  */
144 BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key)
145 {
146         return gh->hashfp(key);
147 }
148
149 /**
150  * Get the full hash for an entry.
151  */
152 BLI_INLINE unsigned int ghash_entryhash(GHash *gh, const Entry *e)
153 {
154         return gh->hashfp(e->key);
155 }
156
157 /**
158  * Get the bucket-index for an already-computed full hash.
159  */
160 BLI_INLINE unsigned int ghash_bucket_index(GHash *gh, const unsigned int hash)
161 {
162 #ifdef GHASH_USE_MODULO_BUCKETS
163         return hash % gh->nbuckets;
164 #else
165         return hash & gh->bucket_mask;
166 #endif
167 }
168
169 /**
170  * Find the index of next used bucket, starting from \a curr_bucket (\a gh is assumed non-empty).
171  */
172 BLI_INLINE unsigned int ghash_find_next_bucket_index(GHash *gh, unsigned int curr_bucket)
173 {
174         if (curr_bucket >= gh->nbuckets) {
175                 curr_bucket = 0;
176         }
177         if (gh->buckets[curr_bucket]) {
178                 return curr_bucket;
179         }
180         for (; curr_bucket < gh->nbuckets; curr_bucket++) {
181                 if (gh->buckets[curr_bucket]) {
182                         return curr_bucket;
183                 }
184         }
185         for (curr_bucket = 0; curr_bucket < gh->nbuckets; curr_bucket++) {
186                 if (gh->buckets[curr_bucket]) {
187                         return curr_bucket;
188                 }
189         }
190         BLI_assert(0);
191         return 0;
192 }
193
194 /**
195  * Expand buckets to the next size up or down.
196  */
197 static void ghash_buckets_resize(GHash *gh, const unsigned int nbuckets)
198 {
199         Entry **buckets_old = gh->buckets;
200         Entry **buckets_new;
201         const unsigned int nbuckets_old = gh->nbuckets;
202         unsigned int i;
203
204         BLI_assert((gh->nbuckets != nbuckets) || !gh->buckets);
205 //      printf("%s: %d -> %d\n", __func__, nbuckets_old, nbuckets);
206
207         gh->nbuckets = nbuckets;
208 #ifdef GHASH_USE_MODULO_BUCKETS
209 #else
210         gh->bucket_mask = nbuckets - 1;
211 #endif
212
213         buckets_new = (Entry **)MEM_callocN(sizeof(*gh->buckets) * gh->nbuckets, __func__);
214
215         if (buckets_old) {
216                 if (nbuckets > nbuckets_old) {
217                         for (i = 0; i < nbuckets_old; i++) {
218                                 for (Entry *e = buckets_old[i], *e_next; e; e = e_next) {
219                                         const unsigned hash = ghash_entryhash(gh, e);
220                                         const unsigned bucket_index = ghash_bucket_index(gh, hash);
221                                         e_next = e->next;
222                                         e->next = buckets_new[bucket_index];
223                                         buckets_new[bucket_index] = e;
224                                 }
225                         }
226                 }
227                 else {
228                         for (i = 0; i < nbuckets_old; i++) {
229 #ifdef GHASH_USE_MODULO_BUCKETS
230                                 for (Entry *e = buckets_old[i], *e_next; e; e = e_next) {
231                                         const unsigned hash = ghash_entryhash(gh, e);
232                                         const unsigned bucket_index = ghash_bucket_index(gh, hash);
233                                         e_next = e->next;
234                                         e->next = buckets_new[bucket_index];
235                                         buckets_new[bucket_index] = e;
236                                 }
237 #else
238                                 /* No need to recompute hashes in this case, since our mask is just smaller, all items in old bucket i
239                                  * will go in same new bucket (i & new_mask)! */
240                                 const unsigned bucket_index = ghash_bucket_index(gh, i);
241                                 BLI_assert(!buckets_old[i] || (bucket_index == ghash_bucket_index(gh, ghash_entryhash(gh, buckets_old[i]))));
242                                 Entry *e;
243                                 for (e = buckets_old[i]; e && e->next; e = e->next);
244                                 if (e) {
245                                         e->next = buckets_new[bucket_index];
246                                         buckets_new[bucket_index] = buckets_old[i];
247                                 }
248 #endif
249                         }
250                 }
251         }
252
253         gh->buckets = buckets_new;
254         if (buckets_old) {
255                 MEM_freeN(buckets_old);
256         }
257 }
258
259 /**
260  * Check if the number of items in the GHash is large enough to require more buckets,
261  * or small enough to require less buckets, and resize \a gh accordingly.
262  */
263 static void ghash_buckets_expand(
264         GHash *gh, const unsigned int nentries, const bool user_defined)
265 {
266         unsigned int new_nbuckets;
267
268         if (LIKELY(gh->buckets && (nentries < gh->limit_grow))) {
269                 return;
270         }
271
272         new_nbuckets = gh->nbuckets;
273
274 #ifdef GHASH_USE_MODULO_BUCKETS
275         while ((nentries    > gh->limit_grow) &&
276                (gh->cursize < GHASH_MAX_SIZE - 1))
277         {
278                 new_nbuckets = hashsizes[++gh->cursize];
279                 gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
280         }
281 #else
282         while ((nentries       > gh->limit_grow) &&
283                (gh->bucket_bit < GHASH_BUCKET_BIT_MAX))
284         {
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
307 static void ghash_buckets_contract(
308         GHash *gh, const unsigned int nentries, const bool user_defined, const bool force_shrink)
309 {
310         unsigned int new_nbuckets;
311
312         if (!(force_shrink || (gh->flag & GHASH_FLAG_ALLOW_SHRINK))) {
313                 return;
314         }
315
316         if (LIKELY(gh->buckets && (nentries > gh->limit_shrink))) {
317                 return;
318         }
319
320         new_nbuckets = gh->nbuckets;
321
322 #ifdef GHASH_USE_MODULO_BUCKETS
323         while ((nentries    < gh->limit_shrink) &&
324                (gh->cursize > gh->size_min))
325         {
326                 new_nbuckets = hashsizes[--gh->cursize];
327                 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
328         }
329 #else
330         while ((nentries       < gh->limit_shrink) &&
331                (gh->bucket_bit > gh->bucket_bit_min))
332         {
333                 new_nbuckets = 1u << --gh->bucket_bit;
334                 gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
335         }
336 #endif
337
338         if (user_defined) {
339 #ifdef GHASH_USE_MODULO_BUCKETS
340                 gh->size_min = gh->cursize;
341 #else
342                 gh->bucket_bit_min = gh->bucket_bit;
343 #endif
344         }
345
346         if ((new_nbuckets == gh->nbuckets) && gh->buckets) {
347                 return;
348         }
349
350         gh->limit_grow   = GHASH_LIMIT_GROW(new_nbuckets);
351         gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
352         ghash_buckets_resize(gh, new_nbuckets);
353 }
354
355 /**
356  * Clear and reset \a gh buckets, reserve again buckets for given number of entries.
357  */
358 BLI_INLINE void ghash_buckets_reset(GHash *gh, const unsigned int nentries)
359 {
360         MEM_SAFE_FREE(gh->buckets);
361
362 #ifdef GHASH_USE_MODULO_BUCKETS
363         gh->cursize = 0;
364         gh->size_min = 0;
365         gh->nbuckets = hashsizes[gh->cursize];
366 #else
367         gh->bucket_bit = GHASH_BUCKET_BIT_MIN;
368         gh->bucket_bit_min = GHASH_BUCKET_BIT_MIN;
369         gh->nbuckets = 1u << gh->bucket_bit;
370         gh->bucket_mask = gh->nbuckets - 1;
371 #endif
372
373         gh->limit_grow   = GHASH_LIMIT_GROW(gh->nbuckets);
374         gh->limit_shrink = GHASH_LIMIT_SHRINK(gh->nbuckets);
375
376         gh->nentries = 0;
377
378         ghash_buckets_expand(gh, nentries, (nentries != 0));
379 }
380
381 /**
382  * Internal lookup function.
383  * Takes hash and bucket_index arguments to avoid calling #ghash_keyhash and #ghash_bucket_index multiple times.
384  */
385 BLI_INLINE Entry *ghash_lookup_entry_ex(
386         GHash *gh, const void *key, const unsigned int bucket_index)
387 {
388         Entry *e;
389         /* If we do not store GHash, not worth computing it for each entry here!
390          * Typically, comparison function will be quicker, and since it's needed in the end anyway... */
391         for (e = gh->buckets[bucket_index]; e; e = e->next) {
392                 if (UNLIKELY(gh->cmpfp(key, e->key) == false)) {
393                         return e;
394                 }
395         }
396
397         return NULL;
398 }
399
400 /**
401  * Internal lookup function, returns previous entry of target one too.
402  * Takes bucket_index argument to avoid calling #ghash_keyhash and #ghash_bucket_index multiple times.
403  * Useful when modifying buckets somehow (like removing an entry...).
404  */
405 BLI_INLINE Entry *ghash_lookup_entry_prev_ex(
406         GHash *gh, const void *key,
407         Entry **r_e_prev, const unsigned int 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  */
425 BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key)
426 {
427         const unsigned int hash = ghash_keyhash(gh, key);
428         const unsigned int bucket_index = ghash_bucket_index(gh, hash);
429         return ghash_lookup_entry_ex(gh, key, bucket_index);
430 }
431
432 static GHash *ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
433                         const unsigned int nentries_reserve, const unsigned int flag)
434 {
435         GHash *gh = MEM_mallocN(sizeof(*gh), info);
436
437         gh->hashfp = hashfp;
438         gh->cmpfp = cmpfp;
439
440         gh->buckets = NULL;
441         gh->flag = flag;
442
443         ghash_buckets_reset(gh, nentries_reserve);
444         gh->entrypool = BLI_mempool_create(GHASH_ENTRY_SIZE(flag & GHASH_FLAG_IS_GSET), 0, 64, BLI_MEMPOOL_NOP);
445
446         return gh;
447 }
448
449 /**
450  * Internal insert function.
451  * Takes hash and bucket_index arguments to avoid calling #ghash_keyhash and #ghash_bucket_index multiple times.
452  */
453 BLI_INLINE void ghash_insert_ex(
454         GHash *gh, void *key, void *val, const unsigned int bucket_index)
455 {
456         GHashEntry *e = BLI_mempool_alloc(gh->entrypool);
457
458         BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
459         BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
460
461         e->e.next = gh->buckets[bucket_index];
462         e->e.key = key;
463         e->val = val;
464         gh->buckets[bucket_index] = (Entry *)e;
465
466         ghash_buckets_expand(gh, ++gh->nentries, false);
467 }
468
469 /**
470  * Insert function that takes a pre-allocated entry.
471  */
472 BLI_INLINE void ghash_insert_ex_keyonly_entry(
473         GHash *gh, void *key, const unsigned int bucket_index,
474         Entry *e)
475 {
476         BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
477
478         e->next = gh->buckets[bucket_index];
479         e->key = key;
480         gh->buckets[bucket_index] = e;
481
482         ghash_buckets_expand(gh, ++gh->nentries, false);
483 }
484
485 /**
486  * Insert function that doesn't set the value (use for GSet)
487  */
488 BLI_INLINE void ghash_insert_ex_keyonly(
489         GHash *gh, void *key, const unsigned int bucket_index)
490 {
491         Entry *e = BLI_mempool_alloc(gh->entrypool);
492
493         BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
494         BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0);
495
496         e->next = gh->buckets[bucket_index];
497         e->key = key;
498         gh->buckets[bucket_index] = e;
499
500         ghash_buckets_expand(gh, ++gh->nentries, false);
501 }
502
503 BLI_INLINE void ghash_insert(GHash *gh, void *key, void *val)
504 {
505         const unsigned int hash = ghash_keyhash(gh, key);
506         const unsigned int bucket_index = ghash_bucket_index(gh, hash);
507
508         ghash_insert_ex(gh, key, val, bucket_index);
509 }
510
511 BLI_INLINE bool ghash_insert_safe(
512         GHash *gh, void *key, void *val, const bool override,
513         GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
514 {
515         const unsigned int hash = ghash_keyhash(gh, key);
516         const unsigned int bucket_index = ghash_bucket_index(gh, hash);
517         GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index);
518
519         BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
520
521         if (e) {
522                 if (override) {
523                         if (keyfreefp) {
524                                 keyfreefp(e->e.key);
525                         }
526                         if (valfreefp) {
527                                 valfreefp(e->val);
528                         }
529                         e->e.key = key;
530                         e->val = val;
531                 }
532                 return false;
533         }
534         else {
535                 ghash_insert_ex(gh, key, val, bucket_index);
536                 return true;
537         }
538 }
539
540 BLI_INLINE bool ghash_insert_safe_keyonly(
541         GHash *gh, void *key, const bool override,
542         GHashKeyFreeFP keyfreefp)
543 {
544         const unsigned int hash = ghash_keyhash(gh, key);
545         const unsigned int bucket_index = ghash_bucket_index(gh, hash);
546         Entry *e = ghash_lookup_entry_ex(gh, key, bucket_index);
547
548         BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0);
549
550         if (e) {
551                 if (override) {
552                         if (keyfreefp) {
553                                 keyfreefp(e->key);
554                         }
555                         e->key = key;
556                 }
557                 return false;
558         }
559         else {
560                 ghash_insert_ex_keyonly(gh, key, bucket_index);
561                 return true;
562         }
563 }
564
565 /**
566  * Remove the entry and return it, caller must free from gh->entrypool.
567  */
568 static Entry *ghash_remove_ex(
569         GHash *gh, const void *key,
570         GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
571         const unsigned int bucket_index)
572 {
573         Entry *e_prev;
574         Entry *e = ghash_lookup_entry_prev_ex(gh, key, &e_prev, bucket_index);
575
576         BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET));
577
578         if (e) {
579                 if (keyfreefp) {
580                         keyfreefp(e->key);
581                 }
582                 if (valfreefp) {
583                         valfreefp(((GHashEntry *)e)->val);
584                 }
585
586                 if (e_prev) {
587                         e_prev->next = e->next;
588                 }
589                 else {
590                         gh->buckets[bucket_index] = e->next;
591                 }
592
593                 ghash_buckets_contract(gh, --gh->nentries, false, false);
594         }
595
596         return e;
597 }
598
599 /**
600  * Remove a random entry and return it (or NULL if empty), caller must free from gh->entrypool.
601  */
602 static Entry *ghash_pop(GHash *gh, GHashIterState *state)
603 {
604         unsigned int curr_bucket = state->curr_bucket;
605         if (gh->nentries == 0) {
606                 return NULL;
607         }
608
609         /* Note: using first_bucket_index here allows us to avoid potential huge number of loops over buckets,
610          *       in case we are popping from a large ghash with few items in it... */
611         curr_bucket = ghash_find_next_bucket_index(gh, curr_bucket);
612
613         Entry *e = gh->buckets[curr_bucket];
614         BLI_assert(e);
615
616         ghash_remove_ex(gh, e->key, NULL, NULL, curr_bucket);
617
618         state->curr_bucket = curr_bucket;
619         return e;
620 }
621
622 /**
623  * Run free callbacks for freeing entries.
624  */
625 static void ghash_free_cb(
626         GHash *gh,
627         GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
628 {
629         unsigned int i;
630
631         BLI_assert(keyfreefp  || valfreefp);
632         BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET));
633
634         for (i = 0; i < gh->nbuckets; i++) {
635                 Entry *e;
636
637                 for (e = gh->buckets[i]; e; e = e->next) {
638                         if (keyfreefp) {
639                                 keyfreefp(e->key);
640                         }
641                         if (valfreefp) {
642                                 valfreefp(((GHashEntry *)e)->val);
643                         }
644                 }
645         }
646 }
647
648 /**
649  * Copy the GHash.
650  */
651 static GHash *ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
652 {
653         GHash *gh_new;
654         unsigned int i;
655         /* This allows us to be sure to get the same number of buckets in gh_new as in ghash. */
656         const unsigned int reserve_nentries_new = MAX2(GHASH_LIMIT_GROW(gh->nbuckets) - 1, gh->nentries);
657
658         BLI_assert(!valcopyfp || !(gh->flag & GHASH_FLAG_IS_GSET));
659
660         gh_new = ghash_new(gh->hashfp, gh->cmpfp, __func__, 0, gh->flag);
661         ghash_buckets_expand(gh_new, reserve_nentries_new, false);
662
663         BLI_assert(gh_new->nbuckets == gh->nbuckets);
664
665         for (i = 0; i < gh->nbuckets; i++) {
666                 Entry *e;
667
668                 for (e = gh->buckets[i]; e; e = e->next) {
669                         Entry *e_new = BLI_mempool_alloc(gh_new->entrypool);
670                         ghash_entry_copy(gh_new, e_new, gh, e, keycopyfp, valcopyfp);
671
672                         /* Warning!
673                          * This means entries in buckets in new copy will be in reversed order!
674                          * This shall not be an issue though, since order should never be assumed in ghash. */
675
676                         /* Note: We can use 'i' here, since we are sure that 'gh' and 'gh_new' have the same number of buckets! */
677                         e_new->next = gh_new->buckets[i];
678                         gh_new->buckets[i] = e_new;
679                 }
680         }
681         gh_new->nentries = gh->nentries;
682
683         return gh_new;
684 }
685
686 /** \} */
687
688
689 /** \name Public API
690  * \{ */
691
692 /**
693  * Creates a new, empty GHash.
694  *
695  * \param hashfp  Hash callback.
696  * \param cmpfp  Comparison callback.
697  * \param info  Identifier string for the GHash.
698  * \param nentries_reserve  Optionally reserve the number of members that the hash will hold.
699  * Use this to avoid resizing buckets if the size is known or can be closely approximated.
700  * \return  An empty GHash.
701  */
702 GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
703                         const unsigned int nentries_reserve)
704 {
705         return ghash_new(hashfp, cmpfp, info, nentries_reserve, 0);
706 }
707
708 /**
709  * Wraps #BLI_ghash_new_ex with zero entries reserved.
710  */
711 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
712 {
713         return BLI_ghash_new_ex(hashfp, cmpfp, info, 0);
714 }
715
716 /**
717  * Copy given GHash. Keys and values are also copied if relevant callback is provided, else pointers remain the same.
718  */
719 GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
720 {
721         return ghash_copy(gh, keycopyfp, valcopyfp);
722 }
723
724 /**
725  * Reserve given amount of entries (resize \a gh accordingly if needed).
726  */
727 void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve)
728 {
729         ghash_buckets_expand(gh, nentries_reserve, true);
730         ghash_buckets_contract(gh, nentries_reserve, true, false);
731 }
732
733 /**
734  * \return size of the GHash.
735  */
736 unsigned int BLI_ghash_size(GHash *gh)
737 {
738         return gh->nentries;
739 }
740
741 /**
742  * Insert a key/value pair into the \a gh.
743  *
744  * \note Duplicates are not checked,
745  * the caller is expected to ensure elements are unique unless
746  * GHASH_FLAG_ALLOW_DUPES flag is set.
747  */
748 void BLI_ghash_insert(GHash *gh, void *key, void *val)
749 {
750         ghash_insert(gh, key, val);
751 }
752
753 /**
754  * Inserts a new value to a key that may already be in ghash.
755  *
756  * Avoids #BLI_ghash_remove, #BLI_ghash_insert calls (double lookups)
757  *
758  * \returns true if a new key has been added.
759  */
760 bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
761 {
762         return ghash_insert_safe(gh, key, val, true, keyfreefp, valfreefp);
763 }
764
765 /**
766  * Lookup the value of \a key in \a gh.
767  *
768  * \param key  The key to lookup.
769  * \returns the value for \a key or NULL.
770  *
771  * \note When NULL is a valid value, use #BLI_ghash_lookup_p to differentiate a missing key
772  * from a key with a NULL value. (Avoids calling #BLI_ghash_haskey before #BLI_ghash_lookup)
773  */
774 void *BLI_ghash_lookup(GHash *gh, const void *key)
775 {
776         GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key);
777         BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
778         return e ? e->val : NULL;
779 }
780
781 /**
782  * A version of #BLI_ghash_lookup which accepts a fallback argument.
783  */
784 void *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default)
785 {
786         GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key);
787         BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
788         return e ? e->val : val_default;
789 }
790
791 /**
792  * Lookup a pointer to the value of \a key in \a gh.
793  *
794  * \param key  The key to lookup.
795  * \returns the pointer to value for \a key or NULL.
796  *
797  * \note This has 2 main benefits over #BLI_ghash_lookup.
798  * - A NULL return always means that \a key isn't in \a gh.
799  * - The value can be modified in-place without further function calls (faster).
800  */
801 void **BLI_ghash_lookup_p(GHash *gh, const void *key)
802 {
803         GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key);
804         BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
805         return e ? &e->val : NULL;
806 }
807
808 /**
809  * Ensure \a key is exists in \a gh.
810  *
811  * This handles the common situation where the caller needs ensure a key is added to \a gh,
812  * constructing a new value in the case the key isn't found.
813  * Otherwise use the existing value.
814  *
815  * Such situations typically incur multiple lookups, however this function
816  * avoids them by ensuring the key is added,
817  * returning a pointer to the value so it can be used or initialized by the caller.
818  *
819  * \returns true when the value didn't need to be added.
820  * (when false, the caller _must_ initialize the value).
821  */
822 bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val)
823 {
824         const unsigned int hash = ghash_keyhash(gh, key);
825         const unsigned int bucket_index = ghash_bucket_index(gh, hash);
826         GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index);
827         const bool haskey = (e != NULL);
828
829         if (!haskey) {
830                 e = BLI_mempool_alloc(gh->entrypool);
831                 ghash_insert_ex_keyonly_entry(gh, key, bucket_index, (Entry *)e);
832         }
833
834         *r_val = &e->val;
835         return haskey;
836 }
837
838 /**
839  * A version of #BLI_ghash_ensure_p that allows caller to re-assign the key.
840  * Typically used when the key is to be duplicated.
841  *
842  * \warning Caller _must_ write to \a r_key when returning false.
843  */
844 bool BLI_ghash_ensure_p_ex(
845         GHash *gh, const void *key, void ***r_key, void ***r_val)
846 {
847         const unsigned int hash = ghash_keyhash(gh, key);
848         const unsigned int bucket_index = ghash_bucket_index(gh, hash);
849         GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index);
850         const bool haskey = (e != NULL);
851
852         if (!haskey) {
853                 /* pass 'key' incase we resize */
854                 e = BLI_mempool_alloc(gh->entrypool);
855                 ghash_insert_ex_keyonly_entry(gh, (void *)key, bucket_index, (Entry *)e);
856                 e->e.key = NULL;  /* caller must re-assign */
857         }
858
859         *r_key = &e->e.key;
860         *r_val = &e->val;
861         return haskey;
862 }
863
864 /**
865  * Remove \a key from \a gh, or return false if the key wasn't found.
866  *
867  * \param key  The key to remove.
868  * \param keyfreefp  Optional callback to free the key.
869  * \param valfreefp  Optional callback to free the value.
870  * \return true if \a key was removed from \a gh.
871  */
872 bool BLI_ghash_remove(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
873 {
874         const unsigned int hash = ghash_keyhash(gh, key);
875         const unsigned int bucket_index = ghash_bucket_index(gh, hash);
876         Entry *e = ghash_remove_ex(gh, key, keyfreefp, valfreefp, bucket_index);
877         if (e) {
878                 BLI_mempool_free(gh->entrypool, e);
879                 return true;
880         }
881         else {
882                 return false;
883         }
884 }
885
886 /* same as above but return the value,
887  * no free value argument since it will be returned */
888 /**
889  * Remove \a key from \a gh, returning the value or NULL if the key wasn't found.
890  *
891  * \param key  The key to remove.
892  * \param keyfreefp  Optional callback to free the key.
893  * \return the value of \a key int \a gh or NULL.
894  */
895 void *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp)
896 {
897         const unsigned int hash = ghash_keyhash(gh, key);
898         const unsigned int bucket_index = ghash_bucket_index(gh, hash);
899         GHashEntry *e = (GHashEntry *)ghash_remove_ex(gh, key, keyfreefp, NULL, bucket_index);
900         BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
901         if (e) {
902                 void *val = e->val;
903                 BLI_mempool_free(gh->entrypool, e);
904                 return val;
905         }
906         else {
907                 return NULL;
908         }
909 }
910
911 /**
912  * \return true if the \a key is in \a gh.
913  */
914 bool BLI_ghash_haskey(GHash *gh, const void *key)
915 {
916         return (ghash_lookup_entry(gh, key) != NULL);
917 }
918
919 /**
920  * Remove a random entry from \a gh, returning true if a key/value pair could be removed, false otherwise.
921  *
922  * \param r_key: The removed key.
923  * \param r_val: The removed value.
924  * \param state: Used for efficient removal.
925  * \return true if there was something to pop, false if ghash was already empty.
926  */
927 bool BLI_ghash_pop(
928         GHash *gh, GHashIterState *state,
929         void **r_key, void **r_val)
930 {
931         GHashEntry *e = (GHashEntry *)ghash_pop(gh, state);
932
933         BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
934
935         if (e) {
936                 *r_key = e->e.key;
937                 *r_val = e->val;
938
939                 BLI_mempool_free(gh->entrypool, e);
940                 return true;
941         }
942         else {
943                 *r_key = *r_val = NULL;
944                 return false;
945         }
946 }
947
948 /**
949  * Reset \a gh clearing all entries.
950  *
951  * \param keyfreefp  Optional callback to free the key.
952  * \param valfreefp  Optional callback to free the value.
953  * \param nentries_reserve  Optionally reserve the number of members that the hash will hold.
954  */
955 void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
956                         const unsigned int nentries_reserve)
957 {
958         if (keyfreefp || valfreefp)
959                 ghash_free_cb(gh, keyfreefp, valfreefp);
960
961         ghash_buckets_reset(gh, nentries_reserve);
962         BLI_mempool_clear_ex(gh->entrypool, nentries_reserve ? (int)nentries_reserve : -1);
963 }
964
965 /**
966  * Wraps #BLI_ghash_clear_ex with zero entries reserved.
967  */
968 void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
969 {
970         BLI_ghash_clear_ex(gh, keyfreefp, valfreefp, 0);
971 }
972
973 /**
974  * Frees the GHash and its members.
975  *
976  * \param gh  The GHash to free.
977  * \param keyfreefp  Optional callback to free the key.
978  * \param valfreefp  Optional callback to free the value.
979  */
980 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
981 {
982         BLI_assert((int)gh->nentries == BLI_mempool_count(gh->entrypool));
983         if (keyfreefp || valfreefp)
984                 ghash_free_cb(gh, keyfreefp, valfreefp);
985
986         MEM_freeN(gh->buckets);
987         BLI_mempool_destroy(gh->entrypool);
988         MEM_freeN(gh);
989 }
990
991 /**
992  * Sets a GHash flag.
993  */
994 void BLI_ghash_flag_set(GHash *gh, unsigned int flag)
995 {
996         gh->flag |= flag;
997 }
998
999 /**
1000  * Clear a GHash flag.
1001  */
1002 void BLI_ghash_flag_clear(GHash *gh, unsigned int flag)
1003 {
1004         gh->flag &= ~flag;
1005 }
1006
1007 /** \} */
1008
1009
1010 /* -------------------------------------------------------------------- */
1011 /* GHash Iterator API */
1012
1013 /** \name Iterator API
1014  * \{ */
1015
1016 /**
1017  * Create a new GHashIterator. The hash table must not be mutated
1018  * while the iterator is in use, and the iterator will step exactly
1019  * BLI_ghash_size(gh) times before becoming done.
1020  *
1021  * \param gh The GHash to iterate over.
1022  * \return Pointer to a new DynStr.
1023  */
1024 GHashIterator *BLI_ghashIterator_new(GHash *gh)
1025 {
1026         GHashIterator *ghi = MEM_mallocN(sizeof(*ghi), "ghash iterator");
1027         BLI_ghashIterator_init(ghi, gh);
1028         return ghi;
1029 }
1030
1031 /**
1032  * Init an already allocated GHashIterator. The hash table must not
1033  * be mutated while the iterator is in use, and the iterator will
1034  * step exactly BLI_ghash_size(gh) times before becoming done.
1035  *
1036  * \param ghi The GHashIterator to initialize.
1037  * \param gh The GHash to iterate over.
1038  */
1039 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
1040 {
1041         ghi->gh = gh;
1042         ghi->curEntry = NULL;
1043         ghi->curBucket = UINT_MAX;  /* wraps to zero */
1044         if (gh->nentries) {
1045                 do {
1046                         ghi->curBucket++;
1047                         if (UNLIKELY(ghi->curBucket == ghi->gh->nbuckets))
1048                                 break;
1049                         ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
1050                 } while (!ghi->curEntry);
1051         }
1052 }
1053
1054 /**
1055  * Steps the iterator to the next index.
1056  *
1057  * \param ghi The iterator.
1058  */
1059 void BLI_ghashIterator_step(GHashIterator *ghi)
1060 {
1061         if (ghi->curEntry) {
1062                 ghi->curEntry = ghi->curEntry->next;
1063                 while (!ghi->curEntry) {
1064                         ghi->curBucket++;
1065                         if (ghi->curBucket == ghi->gh->nbuckets)
1066                                 break;
1067                         ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
1068                 }
1069         }
1070 }
1071
1072 /**
1073  * Free a GHashIterator.
1074  *
1075  * \param ghi The iterator to free.
1076  */
1077 void BLI_ghashIterator_free(GHashIterator *ghi)
1078 {
1079         MEM_freeN(ghi);
1080 }
1081
1082 /* inline functions now */
1083 #if 0
1084 /**
1085  * Retrieve the key from an iterator.
1086  *
1087  * \param ghi The iterator.
1088  * \return The key at the current index, or NULL if the
1089  * iterator is done.
1090  */
1091 void *BLI_ghashIterator_getKey(GHashIterator *ghi)
1092 {
1093         return ghi->curEntry->key;
1094 }
1095
1096 /**
1097  * Retrieve the value from an iterator.
1098  *
1099  * \param ghi The iterator.
1100  * \return The value at the current index, or NULL if the
1101  * iterator is done.
1102  */
1103 void *BLI_ghashIterator_getValue(GHashIterator *ghi)
1104 {
1105         return ghi->curEntry->val;
1106 }
1107
1108 /**
1109  * Retrieve the value from an iterator.
1110  *
1111  * \param ghi The iterator.
1112  * \return The value at the current index, or NULL if the
1113  * iterator is done.
1114  */
1115 void **BLI_ghashIterator_getValue_p(GHashIterator *ghi)
1116 {
1117         return &ghi->curEntry->val;
1118 }
1119
1120 /**
1121  * Determine if an iterator is done (has reached the end of
1122  * the hash table).
1123  *
1124  * \param ghi The iterator.
1125  * \return True if done, False otherwise.
1126  */
1127 bool BLI_ghashIterator_done(GHashIterator *ghi)
1128 {
1129         return ghi->curEntry == NULL;
1130 }
1131 #endif
1132
1133 /** \} */
1134
1135
1136 /** \name Generic Key Hash & Comparison Functions
1137  * \{ */
1138
1139 /***/
1140
1141 #if 0
1142 /* works but slower */
1143 unsigned int BLI_ghashutil_ptrhash(const void *key)
1144 {
1145         return (unsigned int)(intptr_t)key;
1146 }
1147 #else
1148 /* based python3.3's pointer hashing function */
1149 unsigned int BLI_ghashutil_ptrhash(const void *key)
1150 {
1151         size_t y = (size_t)key;
1152         /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
1153          * excessive hash collisions for dicts and sets */
1154         y = (y >> 4) | (y << (8 * sizeof(void *) - 4));
1155         return (unsigned int)y;
1156 }
1157 #endif
1158 bool BLI_ghashutil_ptrcmp(const void *a, const void *b)
1159 {
1160         return (a != b);
1161 }
1162
1163 unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4])
1164 {
1165         unsigned int hash;
1166         hash  = key[0];
1167         hash *= 37;
1168         hash += key[1];
1169         hash *= 37;
1170         hash += key[2];
1171         hash *= 37;
1172         hash += key[3];
1173         return hash;
1174 }
1175 unsigned int BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4])
1176 {
1177         return BLI_hash_mm2((const unsigned char *)key, sizeof(int) * 4  /* sizeof(key) */, 0);
1178 }
1179
1180 bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b)
1181 {
1182         return (memcmp(a, b, sizeof(unsigned int[4])) != 0);
1183 }
1184
1185 unsigned int BLI_ghashutil_uinthash(unsigned int key)
1186 {
1187         key += ~(key << 16);
1188         key ^=  (key >>  5);
1189         key +=  (key <<  3);
1190         key ^=  (key >> 13);
1191         key += ~(key <<  9);
1192         key ^=  (key >> 17);
1193
1194         return key;
1195 }
1196
1197 unsigned int BLI_ghashutil_inthash_p(const void *ptr)
1198 {
1199         uintptr_t key = (uintptr_t)ptr;
1200
1201         key += ~(key << 16);
1202         key ^=  (key >>  5);
1203         key +=  (key <<  3);
1204         key ^=  (key >> 13);
1205         key += ~(key <<  9);
1206         key ^=  (key >> 17);
1207
1208         return (unsigned int)(key & 0xffffffff);
1209 }
1210
1211 unsigned int BLI_ghashutil_inthash_p_murmur(const void *ptr)
1212 {
1213         uintptr_t key = (uintptr_t)ptr;
1214
1215         return BLI_hash_mm2((const unsigned char *)&key, sizeof(key), 0);
1216 }
1217
1218 unsigned int BLI_ghashutil_inthash_p_simple(const void *ptr)
1219 {
1220         return GET_UINT_FROM_POINTER(ptr);
1221 }
1222
1223 bool BLI_ghashutil_intcmp(const void *a, const void *b)
1224 {
1225         return (a != b);
1226 }
1227
1228 /**
1229  * This function implements the widely used "djb" hash apparently posted
1230  * by Daniel Bernstein to comp.lang.c some time ago.  The 32 bit
1231  * unsigned hash value starts at 5381 and for each byte 'c' in the
1232  * string, is updated: ``hash = hash * 33 + c``.  This
1233  * function uses the signed value of each byte.
1234  *
1235  * note: this is the same hash method that glib 2.34.0 uses.
1236  */
1237 unsigned int BLI_ghashutil_strhash_n(const char *key, size_t n)
1238 {
1239         const signed char *p;
1240         unsigned int h = 5381;
1241
1242         for (p = (const signed char *)key; n-- && *p != '\0'; p++) {
1243                 h = (h << 5) + h + (unsigned int)*p;
1244         }
1245
1246         return h;
1247 }
1248 unsigned int BLI_ghashutil_strhash_p(const void *ptr)
1249 {
1250         const signed char *p;
1251         unsigned int h = 5381;
1252
1253         for (p = ptr; *p != '\0'; p++) {
1254                 h = (h << 5) + h + (unsigned int)*p;
1255         }
1256
1257         return h;
1258 }
1259 unsigned int BLI_ghashutil_strhash_p_murmur(const void *ptr)
1260 {
1261         const unsigned char *key = ptr;
1262
1263         return BLI_hash_mm2(key, strlen((const char *)key) + 1, 0);
1264 }
1265 bool BLI_ghashutil_strcmp(const void *a, const void *b)
1266 {
1267         return (a == b) ? false : !STREQ(a, b);
1268 }
1269
1270 GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second)
1271 {
1272         GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair");
1273         pair->first = first;
1274         pair->second = second;
1275         return pair;
1276 }
1277
1278 unsigned int BLI_ghashutil_pairhash(const void *ptr)
1279 {
1280         const GHashPair *pair = ptr;
1281         unsigned int hash = BLI_ghashutil_ptrhash(pair->first);
1282         return hash ^ BLI_ghashutil_ptrhash(pair->second);
1283 }
1284
1285 bool BLI_ghashutil_paircmp(const void *a, const void *b)
1286 {
1287         const GHashPair *A = a;
1288         const GHashPair *B = b;
1289
1290         return (BLI_ghashutil_ptrcmp(A->first, B->first) &&
1291                 BLI_ghashutil_ptrcmp(A->second, B->second));
1292 }
1293
1294 void BLI_ghashutil_pairfree(void *ptr)
1295 {
1296         MEM_freeN(ptr);
1297 }
1298
1299 /** \} */
1300
1301
1302 /** \name Convenience GHash Creation Functions
1303  * \{ */
1304
1305 GHash *BLI_ghash_ptr_new_ex(const char *info, const unsigned int nentries_reserve)
1306 {
1307         return BLI_ghash_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve);
1308 }
1309 GHash *BLI_ghash_ptr_new(const char *info)
1310 {
1311         return BLI_ghash_ptr_new_ex(info, 0);
1312 }
1313
1314 GHash *BLI_ghash_str_new_ex(const char *info, const unsigned int nentries_reserve)
1315 {
1316         return BLI_ghash_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve);
1317 }
1318 GHash *BLI_ghash_str_new(const char *info)
1319 {
1320         return BLI_ghash_str_new_ex(info, 0);
1321 }
1322
1323 GHash *BLI_ghash_int_new_ex(const char *info, const unsigned int nentries_reserve)
1324 {
1325         return BLI_ghash_new_ex(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, info, nentries_reserve);
1326 }
1327 GHash *BLI_ghash_int_new(const char *info)
1328 {
1329         return BLI_ghash_int_new_ex(info, 0);
1330 }
1331
1332 GHash *BLI_ghash_pair_new_ex(const char *info, const unsigned int nentries_reserve)
1333 {
1334         return BLI_ghash_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve);
1335 }
1336 GHash *BLI_ghash_pair_new(const char *info)
1337 {
1338         return BLI_ghash_pair_new_ex(info, 0);
1339 }
1340
1341 /** \} */
1342
1343
1344 /* -------------------------------------------------------------------- */
1345 /* GSet API */
1346
1347 /* Use ghash API to give 'set' functionality */
1348
1349 /** \name GSet Functions
1350  * \{ */
1351 GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
1352                       const unsigned int nentries_reserve)
1353 {
1354         return (GSet *)ghash_new(hashfp, cmpfp, info, nentries_reserve, GHASH_FLAG_IS_GSET);
1355 }
1356
1357 GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info)
1358 {
1359         return BLI_gset_new_ex(hashfp, cmpfp, info, 0);
1360 }
1361
1362 /**
1363  * Copy given GSet. Keys are also copied if callback is provided, else pointers remain the same.
1364  */
1365 GSet *BLI_gset_copy(GSet *gs, GHashKeyCopyFP keycopyfp)
1366 {
1367         return (GSet *)ghash_copy((GHash *)gs, keycopyfp, NULL);
1368 }
1369
1370 unsigned int BLI_gset_size(GSet *gs)
1371 {
1372         return ((GHash *)gs)->nentries;
1373 }
1374
1375 /**
1376  * Adds the key to the set (no checks for unique keys!).
1377  * Matching #BLI_ghash_insert
1378  */
1379 void BLI_gset_insert(GSet *gs, void *key)
1380 {
1381         const unsigned int hash = ghash_keyhash((GHash *)gs, key);
1382         const unsigned int bucket_index = ghash_bucket_index((GHash *)gs, hash);
1383         ghash_insert_ex_keyonly((GHash *)gs, key, bucket_index);
1384 }
1385
1386 /**
1387  * A version of BLI_gset_insert which checks first if the key is in the set.
1388  * \returns true if a new key has been added.
1389  *
1390  * \note GHash has no equivalent to this because typically the value would be different.
1391  */
1392 bool BLI_gset_add(GSet *gs, void *key)
1393 {
1394         return ghash_insert_safe_keyonly((GHash *)gs, key, false, NULL);
1395 }
1396
1397 /**
1398  * Set counterpart to #BLI_ghash_ensure_p_ex.
1399  * similar to BLI_gset_add, except it returns the key pointer.
1400  *
1401  * \warning Caller _must_ write to \a r_key when returning false.
1402  */
1403 bool BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key)
1404 {
1405         const unsigned int hash = ghash_keyhash((GHash *)gs, key);
1406         const unsigned int bucket_index = ghash_bucket_index((GHash *)gs, hash);
1407         GSetEntry *e = (GSetEntry *)ghash_lookup_entry_ex((GHash *)gs, key, bucket_index);
1408         const bool haskey = (e != NULL);
1409
1410         if (!haskey) {
1411                 /* pass 'key' incase we resize */
1412                 e = BLI_mempool_alloc(((GHash *)gs)->entrypool);
1413                 ghash_insert_ex_keyonly_entry((GHash *)gs, (void *)key, bucket_index, (Entry *)e);
1414                 e->key = NULL;  /* caller must re-assign */
1415         }
1416
1417         *r_key = &e->key;
1418         return haskey;
1419 }
1420
1421 /**
1422  * Adds the key to the set (duplicates are managed).
1423  * Matching #BLI_ghash_reinsert
1424  *
1425  * \returns true if a new key has been added.
1426  */
1427 bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp)
1428 {
1429         return ghash_insert_safe_keyonly((GHash *)gs, key, true, keyfreefp);
1430 }
1431
1432 bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp)
1433 {
1434         return BLI_ghash_remove((GHash *)gs, key, keyfreefp, NULL);
1435 }
1436
1437
1438 bool BLI_gset_haskey(GSet *gs, const void *key)
1439 {
1440         return (ghash_lookup_entry((GHash *)gs, key) != NULL);
1441 }
1442
1443 /**
1444  * Remove a random entry from \a gs, returning true if a key could be removed, false otherwise.
1445  *
1446  * \param r_key: The removed key.
1447  * \param state: Used for efficient removal.
1448  * \return true if there was something to pop, false if gset was already empty.
1449  */
1450 bool BLI_gset_pop(
1451         GSet *gs, GSetIterState *state,
1452         void **r_key)
1453 {
1454         GSetEntry *e = (GSetEntry *)ghash_pop((GHash *)gs, (GHashIterState *)state);
1455
1456         if (e) {
1457                 *r_key = e->key;
1458
1459                 BLI_mempool_free(((GHash *)gs)->entrypool, e);
1460                 return true;
1461         }
1462         else {
1463                 *r_key = NULL;
1464                 return false;
1465         }
1466 }
1467
1468 void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
1469                        const unsigned int nentries_reserve)
1470 {
1471         BLI_ghash_clear_ex((GHash *)gs, keyfreefp, NULL,
1472                            nentries_reserve);
1473 }
1474
1475 void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
1476 {
1477         BLI_ghash_clear((GHash *)gs, keyfreefp, NULL);
1478 }
1479
1480 void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
1481 {
1482         BLI_ghash_free((GHash *)gs, keyfreefp, NULL);
1483 }
1484
1485 void BLI_gset_flag_set(GSet *gs, unsigned int flag)
1486 {
1487         ((GHash *)gs)->flag |= flag;
1488 }
1489
1490 void BLI_gset_flag_clear(GSet *gs, unsigned int flag)
1491 {
1492         ((GHash *)gs)->flag &= ~flag;
1493 }
1494
1495 /** \} */
1496
1497
1498 /** \name Convenience GSet Creation Functions
1499  * \{ */
1500
1501 GSet *BLI_gset_ptr_new_ex(const char *info, const unsigned int nentries_reserve)
1502 {
1503         return BLI_gset_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve);
1504 }
1505 GSet *BLI_gset_ptr_new(const char *info)
1506 {
1507         return BLI_gset_ptr_new_ex(info, 0);
1508 }
1509
1510 GSet *BLI_gset_str_new_ex(const char *info, const unsigned int nentries_reserve)
1511 {
1512         return BLI_gset_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve);
1513 }
1514 GSet *BLI_gset_str_new(const char *info)
1515 {
1516         return BLI_gset_str_new_ex(info, 0);
1517 }
1518
1519 GSet *BLI_gset_pair_new_ex(const char *info, const unsigned int nentries_reserve)
1520 {
1521         return BLI_gset_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve);
1522 }
1523 GSet *BLI_gset_pair_new(const char *info)
1524 {
1525         return BLI_gset_pair_new_ex(info, 0);
1526 }
1527
1528 /** \} */
1529
1530
1531 /** \name Debugging & Introspection
1532  * \{ */
1533
1534 #include "BLI_math.h"
1535
1536 /**
1537  * \return number of buckets in the GHash.
1538  */
1539 int BLI_ghash_buckets_size(GHash *gh)
1540 {
1541         return (int)gh->nbuckets;
1542 }
1543 int BLI_gset_buckets_size(GSet *gs)
1544 {
1545         return BLI_ghash_buckets_size((GHash *)gs);
1546 }
1547
1548 /**
1549  * Measure how well the hash function performs (1.0 is approx as good as random distribution),
1550  * and return a few other stats like load, variance of the distribution of the entries in the buckets, etc.
1551  *
1552  * Smaller is better!
1553  */
1554 double BLI_ghash_calc_quality_ex(
1555         GHash *gh, double *r_load, double *r_variance,
1556         double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket)
1557 {
1558         double mean;
1559         unsigned int i;
1560
1561         if (gh->nentries == 0) {
1562                 if (r_load) {
1563                         *r_load = 0.0;
1564                 }
1565                 if (r_variance) {
1566                         *r_variance = 0.0;
1567                 }
1568                 if (r_prop_empty_buckets) {
1569                         *r_prop_empty_buckets = 1.0;
1570                 }
1571                 if (r_prop_overloaded_buckets) {
1572                         *r_prop_overloaded_buckets = 0.0;
1573                 }
1574                 if (r_biggest_bucket) {
1575                         *r_biggest_bucket = 0;
1576                 }
1577
1578                 return 0.0;
1579         }
1580
1581         mean = (double)gh->nentries / (double)gh->nbuckets;
1582         if (r_load) {
1583                 *r_load = mean;
1584         }
1585         if (r_biggest_bucket) {
1586                 *r_biggest_bucket = 0;
1587         }
1588
1589         if (r_variance) {
1590                 /* We already know our mean (i.e. load factor), easy to compute variance.
1591                  * See http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Two-pass_algorithm
1592                  */
1593                 double sum = 0.0;
1594                 for (i = 0; i < gh->nbuckets; i++) {
1595                         int count = 0;
1596                         Entry *e;
1597                         for (e = gh->buckets[i]; e; e = e->next) {
1598                                 count++;
1599                         }
1600                         sum += ((double)count - mean) * ((double)count - mean);
1601                 }
1602                 *r_variance = sum / (double)(gh->nbuckets - 1);
1603         }
1604
1605         {
1606                 uint64_t sum = 0;
1607                 uint64_t overloaded_buckets_threshold = (uint64_t)max_ii(GHASH_LIMIT_GROW(1), 1);
1608                 uint64_t sum_overloaded = 0;
1609                 uint64_t sum_empty = 0;
1610
1611                 for (i = 0; i < gh->nbuckets; i++) {
1612                         uint64_t count = 0;
1613                         Entry *e;
1614                         for (e = gh->buckets[i]; e; e = e->next) {
1615                                 count++;
1616                         }
1617                         if (r_biggest_bucket) {
1618                                 *r_biggest_bucket = max_ii(*r_biggest_bucket, (int)count);
1619                         }
1620                         if (r_prop_overloaded_buckets && (count > overloaded_buckets_threshold)) {
1621                                 sum_overloaded++;
1622                         }
1623                         if (r_prop_empty_buckets && !count) {
1624                                 sum_empty++;
1625                         }
1626                         sum += count * (count + 1);
1627                 }
1628                 if (r_prop_overloaded_buckets) {
1629                         *r_prop_overloaded_buckets = (double)sum_overloaded / (double)gh->nbuckets;
1630                 }
1631                 if (r_prop_empty_buckets) {
1632                         *r_prop_empty_buckets = (double)sum_empty / (double)gh->nbuckets;
1633                 }
1634                 return ((double)sum * (double)gh->nbuckets /
1635                         ((double)gh->nentries * (gh->nentries + 2 * gh->nbuckets - 1)));
1636         }
1637 }
1638 double BLI_gset_calc_quality_ex(
1639         GSet *gs, double *r_load, double *r_variance,
1640         double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket)
1641 {
1642         return BLI_ghash_calc_quality_ex((GHash *)gs, r_load, r_variance,
1643                                          r_prop_empty_buckets, r_prop_overloaded_buckets, r_biggest_bucket);
1644 }
1645
1646 double BLI_ghash_calc_quality(GHash *gh)
1647 {
1648         return BLI_ghash_calc_quality_ex(gh, NULL, NULL, NULL, NULL, NULL);
1649 }
1650 double BLI_gset_calc_quality(GSet *gs)
1651 {
1652         return BLI_ghash_calc_quality_ex((GHash *)gs, NULL, NULL, NULL, NULL, NULL);
1653 }
1654
1655 /** \} */