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