add some safety checks in debug mode to ensure sets/hashes aren't confused.
[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) hash table ADT
32  *
33  * \note edgehash.c is based on this, make sure they stay in sync.
34  */
35
36 #include <string.h>
37 #include <stdlib.h>
38 #include <limits.h>
39
40 #include "MEM_guardedalloc.h"
41
42 #include "BLI_sys_types.h"  /* for intptr_t support */
43 #include "BLI_utildefines.h"
44 #include "BLI_mempool.h"
45 #include "BLI_ghash.h"
46
47 /***/
48
49 #ifdef __GNUC__
50 #  pragma GCC diagnostic error "-Wsign-conversion"
51 #  if (__GNUC__ * 100 + __GNUC_MINOR__) >= 406  /* gcc4.6+ only */
52 #    pragma GCC diagnostic error "-Wsign-compare"
53 #    pragma GCC diagnostic error "-Wconversion"
54 #  endif
55 #endif
56
57 const unsigned int hashsizes[] = {
58         5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
59         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
60         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
61         268435459
62 };
63
64 /* internal flag to ensure sets values aren't used */
65 #ifndef NDEBUG
66 #  define GHASH_FLAG_IS_SET (1 << 8)
67 #  define IS_GHASH_ASSERT(gh) BLI_assert((gh->flag & GHASH_FLAG_IS_SET) == 0)
68 // #  define IS_GSET_ASSERT(gs) BLI_assert((gs->flag & GHASH_FLAG_IS_SET) != 0)
69 #else
70 #  define IS_GHASH_ASSERT(gh)
71 // #  define IS_GSET_ASSERT(eh)
72 #endif
73
74 /***/
75
76 typedef struct Entry {
77         struct Entry *next;
78
79         void *key, *val;
80 } Entry;
81
82 struct GHash {
83         GHashHashFP hashfp;
84         GHashCmpFP cmpfp;
85
86         Entry **buckets;
87         struct BLI_mempool *entrypool;
88         unsigned int nbuckets;
89         unsigned int nentries;
90         unsigned int cursize, flag;
91 };
92
93
94 /* -------------------------------------------------------------------- */
95 /* GHash API */
96
97 /** \name Internal Utility API
98  * \{ */
99
100 /**
101  * Check if the number of items in the GHash is large enough to require more buckets.
102  */
103 BLI_INLINE bool ghash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
104 {
105         return (nentries > nbuckets * 3);
106 }
107
108 /**
109  * Increase initial bucket size to match a reserved ammount.
110  */
111 BLI_INLINE void ghash_buckets_reserve(GHash *gh, const unsigned int nentries_reserve)
112 {
113         while (ghash_test_expand_buckets(nentries_reserve, gh->nbuckets)) {
114                 gh->nbuckets = hashsizes[++gh->cursize];
115         }
116 }
117
118 /**
119  * Get the hash for a key.
120  */
121 BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key)
122 {
123         return gh->hashfp(key) % gh->nbuckets;
124 }
125
126 /**
127  * Internal lookup function.
128  * Takes a hash argument to avoid calling #ghash_keyhash multiple times.
129  */
130 BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key,
131                                         const unsigned int hash)
132 {
133         Entry *e;
134
135         for (e = gh->buckets[hash]; e; e = e->next) {
136                 if (gh->cmpfp(key, e->key) == 0) {
137                         return e;
138                 }
139         }
140         return NULL;
141 }
142
143 /**
144  * Internal lookup function. Only wraps #ghash_lookup_entry_ex
145  */
146 BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key)
147 {
148         const unsigned int hash = ghash_keyhash(gh, key);
149         return ghash_lookup_entry_ex(gh, key, hash);
150 }
151
152 static GHash *ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
153                         const unsigned int nentries_reserve,
154                         const size_t entry_size)
155 {
156         GHash *gh = MEM_mallocN(sizeof(*gh), info);
157
158         gh->hashfp = hashfp;
159         gh->cmpfp = cmpfp;
160
161         gh->nbuckets = hashsizes[0];  /* gh->cursize */
162         gh->nentries = 0;
163         gh->cursize = 0;
164         gh->flag = 0;
165
166         /* if we have reserved the number of elements that this hash will contain */
167         if (nentries_reserve) {
168                 ghash_buckets_reserve(gh, nentries_reserve);
169         }
170
171         gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
172         gh->entrypool = BLI_mempool_create((int)entry_size, 64, 64, 0);
173
174         return gh;
175 }
176
177 /**
178  * Internal insert function.
179  * Takes a hash argument to avoid calling #ghash_keyhash multiple times.
180  */
181 static Entry *ghash_insert_ex(GHash *gh, void *key,
182                               unsigned int hash)
183 {
184         Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool);
185
186         BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
187
188         e->next = gh->buckets[hash];
189         e->key = key;
190         /* intentionally don't set the value */
191         gh->buckets[hash] = e;
192
193         if (UNLIKELY(ghash_test_expand_buckets(++gh->nentries, gh->nbuckets))) {
194                 Entry *e_iter;
195                 Entry **old = gh->buckets;
196                 const unsigned nold = gh->nbuckets;
197                 unsigned int i;
198
199                 gh->nbuckets = hashsizes[++gh->cursize];
200                 gh->buckets = (Entry **)MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
201
202                 for (i = 0; i < nold; i++) {
203                         Entry *e_next;
204                         for (e_iter = old[i]; e_iter; e_iter = e_next) {
205                                 e_next = e_iter->next;
206                                 hash = ghash_keyhash(gh, e_iter->key);
207                                 e_iter->next = gh->buckets[hash];
208                                 gh->buckets[hash] = e_iter;
209                         }
210                 }
211
212                 MEM_freeN(old);
213         }
214
215         return e;
216 }
217
218 /**
219  * Remove the entry and return it, caller must free from gh->entrypool.
220  */
221 static Entry *ghash_remove_ex(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
222                               unsigned int hash)
223 {
224         Entry *e;
225         Entry *e_prev = NULL;
226
227         for (e = gh->buckets[hash]; e; e = e->next) {
228                 if (gh->cmpfp(key, e->key) == 0) {
229                         Entry *e_next = e->next;
230
231                         if (keyfreefp) keyfreefp(e->key);
232                         if (valfreefp) valfreefp(e->val);
233
234                         if (e_prev) e_prev->next = e_next;
235                         else   gh->buckets[hash] = e_next;
236
237                         gh->nentries--;
238                         return e;
239                 }
240                 e_prev = e;
241         }
242
243         return NULL;
244 }
245
246 /**
247  * Run free callbacks for freeing entries.
248  */
249 static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
250 {
251         unsigned int i;
252
253         BLI_assert(keyfreefp || valfreefp);
254
255         for (i = 0; i < gh->nbuckets; i++) {
256                 Entry *e;
257
258                 for (e = gh->buckets[i]; e; ) {
259                         Entry *e_next = e->next;
260
261                         if (keyfreefp) keyfreefp(e->key);
262                         if (valfreefp) valfreefp(e->val);
263
264                         e = e_next;
265                 }
266         }
267 }
268 /** \} */
269
270
271 /** \name Public API
272  * \{ */
273
274 /**
275  * Creates a new, empty GHash.
276  *
277  * \param hashfp  Hash callback.
278  * \param cmpfp  Comparison callback.
279  * \param info  Identifier string for the GHash.
280  * \param nentries_reserve  Optionally reserve the number of members that the hash will hold.
281  * Use this to avoid resizing buckets if the size is known or can be closely approximated.
282  * \return  An empty GHash.
283  */
284 GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
285                         const unsigned int nentries_reserve)
286 {
287         return ghash_new(hashfp, cmpfp, info,
288                          nentries_reserve,
289                          sizeof(Entry));
290 }
291
292 /**
293  * Wraps #BLI_ghash_new_ex with zero entries reserved.
294  */
295 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
296 {
297         return BLI_ghash_new_ex(hashfp, cmpfp, info, 0);
298 }
299
300 /**
301  * \return size of the GHash.
302  */
303 int BLI_ghash_size(GHash *gh)
304 {
305         return (int)gh->nentries;
306 }
307
308 /**
309  * Insert a key/value pair into the \a gh.
310  *
311  * \note Duplicates are not checked,
312  * the caller is expected to ensure elements are unique unless
313  * GHASH_FLAG_ALLOW_DUPES flag is set.
314  */
315 void BLI_ghash_insert(GHash *gh, void *key, void *val)
316 {
317         const unsigned int hash = ghash_keyhash(gh, key);
318         Entry *e = ghash_insert_ex(gh, key, hash);
319         e->val = val;
320 }
321
322 /**
323  * Inserts a new value to a key that may already be in ghash.
324  *
325  * Avoids #BLI_ghash_remove, #BLI_ghash_insert calls (double lookups)
326  *
327  * \returns true if a new key has been added.
328  */
329 bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
330 {
331         const unsigned int hash = ghash_keyhash(gh, key);
332         Entry *e = ghash_lookup_entry_ex(gh, key, hash);
333         if (e) {
334                 if (keyfreefp) keyfreefp(e->key);
335                 if (valfreefp) valfreefp(e->val);
336                 e->key = key;
337                 e->val = val;
338                 return false;
339         }
340         else {
341                 e = ghash_insert_ex(gh, key, hash);
342                 e->val = val;
343                 return true;
344         }
345 }
346
347 /**
348  * Lookup the value of \a key in \a gh.
349  *
350  * \param key  The key to lookup.
351  * \returns the value for \a key or NULL.
352  *
353  * \note When NULL is a valid value, use #BLI_ghash_lookup_p to differentiate a missing key
354  * from a key with a NULL value. (Avoids calling #BLI_ghash_haskey before #BLI_ghash_lookup)
355  */
356 void *BLI_ghash_lookup(GHash *gh, const void *key)
357 {
358         Entry *e = ghash_lookup_entry(gh, key);
359         IS_GHASH_ASSERT(gh);
360         return e ? e->val : NULL;
361 }
362
363 /**
364  * Lookup a pointer to the value of \a key in \a gh.
365  *
366  * \param key  The key to lookup.
367  * \returns the pointer to value for \a key or NULL.
368  *
369  * \note This has 2 main benifits over #BLI_ghash_lookup.
370  * - A NULL return always means that \a key isn't in \a gh.
371  * - The value can be modified in-place without further function calls (faster).
372  */
373 void **BLI_ghash_lookup_p(GHash *gh, const void *key)
374 {
375         Entry *e = ghash_lookup_entry(gh, key);
376         IS_GHASH_ASSERT(gh);
377         return e ? &e->val : NULL;
378 }
379
380 /**
381  * Remove \a key from \a gh, or return false if the key wasn't found.
382  *
383  * \param key  The key to remove.
384  * \param keyfreefp  Optional callback to free the key.
385  * \param valfreefp  Optional callback to free the value.
386  * \return true if \a key was removed from \a gh.
387  */
388 bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
389 {
390         const unsigned int hash = ghash_keyhash(gh, key);
391         Entry *e = ghash_remove_ex(gh, key, keyfreefp, valfreefp, hash);
392         if (e) {
393                 BLI_mempool_free(gh->entrypool, e);
394                 return true;
395         }
396         else {
397                 return false;
398         }
399 }
400
401 /* same as above but return the value,
402  * no free value argument since it will be returned */
403 /**
404  * Remove \a key from \a gh, returning the value or NULL if the key wasn't found.
405  *
406  * \param key  The key to remove.
407  * \param keyfreefp  Optional callback to free the key.
408  * \return the value of \a key int \a gh or NULL.
409  */
410 void *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp)
411 {
412         const unsigned int hash = ghash_keyhash(gh, key);
413         Entry *e = ghash_remove_ex(gh, key, keyfreefp, NULL, hash);
414         IS_GHASH_ASSERT(gh);
415         if (e) {
416                 void *val = e->val;
417                 BLI_mempool_free(gh->entrypool, e);
418                 return val;
419         }
420         else {
421                 return NULL;
422         }
423 }
424
425 /**
426  * \return true if the \a key is in \a gh.
427  */
428 bool BLI_ghash_haskey(GHash *gh, const void *key)
429 {
430         return (ghash_lookup_entry(gh, key) != NULL);
431 }
432
433 /**
434  * Reset \a gh clearing all entries.
435  *
436  * \param keyfreefp  Optional callback to free the key.
437  * \param valfreefp  Optional callback to free the value.
438  * \param nentries_reserve  Optionally reserve the number of members that the hash will hold.
439  */
440 void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
441                         const unsigned int nentries_reserve)
442 {
443         if (keyfreefp || valfreefp)
444                 ghash_free_cb(gh, keyfreefp, valfreefp);
445
446         gh->nbuckets = hashsizes[0];  /* gh->cursize */
447         gh->nentries = 0;
448         gh->cursize = 0;
449
450         if (nentries_reserve) {
451                 ghash_buckets_reserve(gh, nentries_reserve);
452         }
453
454         MEM_freeN(gh->buckets);
455         gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
456
457         BLI_mempool_clear_ex(gh->entrypool, nentries_reserve ? (int)nentries_reserve : -1);
458 }
459
460 /**
461  * Wraps #BLI_ghash_clear_ex with zero entries reserved.
462  */
463 void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
464 {
465         BLI_ghash_clear_ex(gh, keyfreefp, valfreefp, 0);
466 }
467
468 /**
469  * Frees the GHash and its members.
470  *
471  * \param gh  The GHash to free.
472  * \param keyfreefp  Optional callback to free the key.
473  * \param valfreefp  Optional callback to free the value.
474  */
475 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
476 {
477         BLI_assert((int)gh->nentries == BLI_mempool_count(gh->entrypool));
478         if (keyfreefp || valfreefp)
479                 ghash_free_cb(gh, keyfreefp, valfreefp);
480
481         MEM_freeN(gh->buckets);
482         BLI_mempool_destroy(gh->entrypool);
483         MEM_freeN(gh);
484 }
485
486 /**
487  * Sets a GHash flag.
488  */
489 void BLI_ghash_flag_set(GHash *gh, unsigned int flag)
490 {
491         gh->flag |= flag;
492 }
493
494 /**
495  * Clear a GHash flag.
496  */
497 void BLI_ghash_flag_clear(GHash *gh, unsigned int flag)
498 {
499         gh->flag &= ~flag;
500 }
501
502 /** \} */
503
504
505 /* -------------------------------------------------------------------- */
506 /* GHash Iterator API */
507
508 /** \name Iterator API
509  * \{ */
510
511 /**
512  * Create a new GHashIterator. The hash table must not be mutated
513  * while the iterator is in use, and the iterator will step exactly
514  * BLI_ghash_size(gh) times before becoming done.
515  *
516  * \param gh The GHash to iterate over.
517  * \return Pointer to a new DynStr.
518  */
519 GHashIterator *BLI_ghashIterator_new(GHash *gh)
520 {
521         GHashIterator *ghi = MEM_mallocN(sizeof(*ghi), "ghash iterator");
522         BLI_ghashIterator_init(ghi, gh);
523         return ghi;
524 }
525
526 /**
527  * Init an already allocated GHashIterator. The hash table must not
528  * be mutated while the iterator is in use, and the iterator will
529  * step exactly BLI_ghash_size(gh) times before becoming done.
530  *
531  * \param ghi The GHashIterator to initialize.
532  * \param gh The GHash to iterate over.
533  */
534 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
535 {
536         ghi->gh = gh;
537         ghi->curEntry = NULL;
538         ghi->curBucket = UINT_MAX;  /* wraps to zero */
539         while (!ghi->curEntry) {
540                 ghi->curBucket++;
541                 if (ghi->curBucket == ghi->gh->nbuckets)
542                         break;
543                 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
544         }
545 }
546
547 /**
548  * Free a GHashIterator.
549  *
550  * \param ghi The iterator to free.
551  */
552 void BLI_ghashIterator_free(GHashIterator *ghi)
553 {
554         MEM_freeN(ghi);
555 }
556
557 /**
558  * Retrieve the key from an iterator.
559  *
560  * \param ghi The iterator.
561  * \return The key at the current index, or NULL if the
562  * iterator is done.
563  */
564 void *BLI_ghashIterator_getKey(GHashIterator *ghi)
565 {
566         return ghi->curEntry ? ghi->curEntry->key : NULL;
567 }
568
569 /**
570  * Retrieve the value from an iterator.
571  *
572  * \param ghi The iterator.
573  * \return The value at the current index, or NULL if the
574  * iterator is done.
575  */
576 void *BLI_ghashIterator_getValue(GHashIterator *ghi)
577 {
578         return ghi->curEntry ? ghi->curEntry->val : NULL;
579 }
580
581 /**
582  * Steps the iterator to the next index.
583  *
584  * \param ghi The iterator.
585  */
586 void BLI_ghashIterator_step(GHashIterator *ghi)
587 {
588         if (ghi->curEntry) {
589                 ghi->curEntry = ghi->curEntry->next;
590                 while (!ghi->curEntry) {
591                         ghi->curBucket++;
592                         if (ghi->curBucket == ghi->gh->nbuckets)
593                                 break;
594                         ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
595                 }
596         }
597 }
598
599 /**
600  * Determine if an iterator is done (has reached the end of
601  * the hash table).
602  *
603  * \param ghi The iterator.
604  * \return True if done, False otherwise.
605  */
606 bool BLI_ghashIterator_done(GHashIterator *ghi)
607 {
608         return ghi->curEntry == NULL;
609 }
610
611 /** \} */
612
613
614 /** \name Generic Key Hash & Comparison Functions
615  * \{ */
616
617 /***/
618
619 #if 0
620 /* works but slower */
621 unsigned int BLI_ghashutil_ptrhash(const void *key)
622 {
623         return (unsigned int)(intptr_t)key;
624 }
625 #else
626 /* based python3.3's pointer hashing function */
627 unsigned int BLI_ghashutil_ptrhash(const void *key)
628 {
629         size_t y = (size_t)key;
630         /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
631          * excessive hash collisions for dicts and sets */
632         y = (y >> 4) | (y << (8 * sizeof(void *) - 4));
633         return (unsigned int)y;
634 }
635 #endif
636 int BLI_ghashutil_ptrcmp(const void *a, const void *b)
637 {
638         if (a == b)
639                 return 0;
640         else
641                 return (a < b) ? -1 : 1;
642 }
643
644 unsigned int BLI_ghashutil_inthash(const void *ptr)
645 {
646         uintptr_t key = (uintptr_t)ptr;
647
648         key += ~(key << 16);
649         key ^=  (key >>  5);
650         key +=  (key <<  3);
651         key ^=  (key >> 13);
652         key += ~(key <<  9);
653         key ^=  (key >> 17);
654
655         return (unsigned int)(key & 0xffffffff);
656 }
657
658 int BLI_ghashutil_intcmp(const void *a, const void *b)
659 {
660         if (a == b)
661                 return 0;
662         else
663                 return (a < b) ? -1 : 1;
664 }
665
666 /**
667  * This function implements the widely used "djb" hash apparently posted
668  * by Daniel Bernstein to comp.lang.c some time ago.  The 32 bit
669  * unsigned hash value starts at 5381 and for each byte 'c' in the
670  * string, is updated: <literal>hash = hash * 33 + c</literal>.  This
671  * function uses the signed value of each byte.
672  *
673  * note: this is the same hash method that glib 2.34.0 uses.
674  */
675 unsigned int BLI_ghashutil_strhash(const void *ptr)
676 {
677         const signed char *p;
678         unsigned int h = 5381;
679
680         for (p = ptr; *p != '\0'; p++) {
681                 h = (h << 5) + h + (unsigned int)*p;
682         }
683
684         return h;
685 }
686 int BLI_ghashutil_strcmp(const void *a, const void *b)
687 {
688         return strcmp(a, b);
689 }
690
691 GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second)
692 {
693         GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair");
694         pair->first = first;
695         pair->second = second;
696         return pair;
697 }
698
699 unsigned int BLI_ghashutil_pairhash(const void *ptr)
700 {
701         const GHashPair *pair = ptr;
702         unsigned int hash = BLI_ghashutil_ptrhash(pair->first);
703         return hash ^ BLI_ghashutil_ptrhash(pair->second);
704 }
705
706 int BLI_ghashutil_paircmp(const void *a, const void *b)
707 {
708         const GHashPair *A = a;
709         const GHashPair *B = b;
710
711         int cmp = BLI_ghashutil_ptrcmp(A->first, B->first);
712         if (cmp == 0)
713                 return BLI_ghashutil_ptrcmp(A->second, B->second);
714         return cmp;
715 }
716
717 void BLI_ghashutil_pairfree(void *ptr)
718 {
719         MEM_freeN(ptr);
720 }
721
722 /** \} */
723
724
725 /** \name Convenience GHash Creation Functions
726  * \{ */
727
728 GHash *BLI_ghash_ptr_new_ex(const char *info,
729                             const unsigned int nentries_reserve)
730 {
731         return BLI_ghash_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info,
732                                 nentries_reserve);
733 }
734 GHash *BLI_ghash_ptr_new(const char *info)
735 {
736         return BLI_ghash_ptr_new_ex(info, 0);
737 }
738
739 GHash *BLI_ghash_str_new_ex(const char *info,
740                             const unsigned int nentries_reserve)
741 {
742         return BLI_ghash_new_ex(BLI_ghashutil_strhash, BLI_ghashutil_strcmp, info,
743                                 nentries_reserve);
744 }
745 GHash *BLI_ghash_str_new(const char *info)
746 {
747         return BLI_ghash_str_new_ex(info, 0);
748 }
749
750 GHash *BLI_ghash_int_new_ex(const char *info,
751                             const unsigned int nentries_reserve)
752 {
753         return BLI_ghash_new_ex(BLI_ghashutil_inthash, BLI_ghashutil_intcmp, info,
754                                 nentries_reserve);
755 }
756 GHash *BLI_ghash_int_new(const char *info)
757 {
758         return BLI_ghash_int_new_ex(info, 0);
759 }
760
761 GHash *BLI_ghash_pair_new_ex(const char *info,
762                              const unsigned int nentries_reserve)
763 {
764         return BLI_ghash_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info,
765                                 nentries_reserve);
766 }
767 GHash *BLI_ghash_pair_new(const char *info)
768 {
769         return BLI_ghash_pair_new_ex(info, 0);
770 }
771
772 /** \} */
773
774
775 /* -------------------------------------------------------------------- */
776 /* GSet API */
777
778 /* Use ghash API to give 'set' functionality */
779
780 /* TODO: typical set functions
781  * isdisjoint/issubset/issuperset/union/intersection/difference etc */
782
783 /** \name GSet Functions
784  * \{ */
785 GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
786                       const unsigned int nentries_reserve)
787 {
788         GSet *gs = (GSet *)ghash_new(hashfp, cmpfp, info,
789                                      nentries_reserve,
790                                      sizeof(Entry) - sizeof(void *));
791 #ifndef NDEBUG
792         ((GHash *)gs)->flag |= GHASH_FLAG_IS_SET;
793 #endif
794         return gs;
795 }
796
797 GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info)
798 {
799         return BLI_gset_new_ex(hashfp, cmpfp, info, 0);
800 }
801
802 int BLI_gset_size(GSet *gs)
803 {
804         return (int)((GHash *)gs)->nentries;
805 }
806
807 /**
808  * Adds the key to the set (no checks for unique keys!).
809  * Matching #BLI_ghash_insert
810  */
811 void BLI_gset_insert(GSet *gs, void *key)
812 {
813         const unsigned int hash = ghash_keyhash((GHash *)gs, key);
814         ghash_insert_ex((GHash *)gs, key, hash);
815 }
816
817 /**
818  * Adds the key to the set (duplicates are managed).
819  * Matching #BLI_ghash_reinsert
820  *
821  * \returns true if a new key has been added.
822  */
823 bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp)
824 {
825         const unsigned int hash = ghash_keyhash((GHash *)gs, key);
826         Entry *e = ghash_lookup_entry_ex((GHash *)gs, key, hash);
827         if (e) {
828                 if (keyfreefp) keyfreefp(e->key);
829                 e->key = key;
830                 return false;
831         }
832         else {
833                 ghash_insert_ex((GHash *)gs, key, hash);
834                 return true;
835         }
836 }
837
838 bool BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp)
839 {
840         return BLI_ghash_remove((GHash *)gs, key, keyfreefp, NULL);
841 }
842
843
844 bool BLI_gset_haskey(GSet *gs, const void *key)
845 {
846         return (ghash_lookup_entry((GHash *)gs, key) != NULL);
847 }
848
849 void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
850                        const unsigned int nentries_reserve)
851 {
852         BLI_ghash_clear_ex((GHash *)gs, keyfreefp, NULL,
853                            nentries_reserve);
854 }
855
856 void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
857 {
858         BLI_ghash_clear((GHash *)gs, keyfreefp, NULL);
859 }
860
861 void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
862 {
863         BLI_ghash_free((GHash *)gs, keyfreefp, NULL);
864 }
865 /** \} */
866
867
868 /** \name Convenience GSet Creation Functions
869  * \{ */
870
871 GSet *BLI_gset_ptr_new_ex(const char *info,
872                           const unsigned int nentries_reserve)
873 {
874         return BLI_gset_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info,
875                                nentries_reserve);
876 }
877 GSet *BLI_gset_ptr_new(const char *info)
878 {
879         return BLI_gset_ptr_new_ex(info, 0);
880 }
881
882 GSet *BLI_gset_pair_new_ex(const char *info,
883                              const unsigned int nentries_reserve)
884 {
885         return BLI_gset_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info,
886                                 nentries_reserve);
887 }
888 GSet *BLI_gset_pair_new(const char *info)
889 {
890         return BLI_gset_pair_new_ex(info, 0);
891 }
892
893 /** \} */