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