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