use 'bool' for BLI_/BKE_ functions.
[blender.git] / source / blender / blenlib / intern / BLI_ghash.c
index 943b67c..ebc40eb 100644 (file)
 #include <string.h>
 #include <stdlib.h>
 
-
 #include "MEM_guardedalloc.h"
 
-
-
-// #include "BLI_blenlib.h"
-
 #include "BLI_utildefines.h"
 #include "BLI_mempool.h"
 #include "BLI_ghash.h"
 
-#include "BLO_sys_types.h" // for intptr_t support
+#include "MEM_sys_types.h"  /* for intptr_t support */
 /***/
 
-unsigned int hashsizes[]= {
+unsigned int hashsizes[] = {
        5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
        16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
        4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
@@ -58,18 +53,18 @@ unsigned int hashsizes[]= {
 
 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
 {
-       GHash *gh= MEM_mallocN(sizeof(*gh), info);
-       gh->hashfp= hashfp;
-       gh->cmpfp= cmpfp;
-       gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, FALSE, FALSE);
-
-       gh->cursize= 0;
-       gh->nentries= 0;
-       gh->nbuckets= hashsizes[gh->cursize];
-       
-       gh->buckets= MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets");
-       memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
-       
+       GHash *gh = MEM_mallocN(sizeof(*gh), info);
+       gh->hashfp = hashfp;
+       gh->cmpfp = cmpfp;
+       gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0);
+
+       gh->cursize = 0;
+       gh->nentries = 0;
+       gh->nbuckets = hashsizes[gh->cursize];
+
+       gh->buckets = MEM_mallocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
+       memset(gh->buckets, 0, gh->nbuckets * sizeof(*gh->buckets));
+
        return gh;
 }
 
@@ -80,31 +75,31 @@ int BLI_ghash_size(GHash *gh)
 
 void BLI_ghash_insert(GHash *gh, void *key, void *val)
 {
-       unsigned int hash= gh->hashfp(key)%gh->nbuckets;
-       Entry *e= (Entry*) BLI_mempool_alloc(gh->entrypool);
+       unsigned int hash = gh->hashfp(key) % gh->nbuckets;
+       Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool);
 
-       e->key= key;
-       e->val= val;
-       e->next= gh->buckets[hash];
-       gh->buckets[hash]= e;
+       e->next = gh->buckets[hash];
+       e->key = key;
+       e->val = val;
+       gh->buckets[hash] = e;
 
-       if (++gh->nentries>(float)gh->nbuckets/2) {
-               Entry **old= gh->buckets;
-               int i, nold= gh->nbuckets;
+       if (++gh->nentries > (float)gh->nbuckets / 2) {
+               Entry **old = gh->buckets;
+               int i, nold = gh->nbuckets;
 
-               gh->nbuckets= hashsizes[++gh->cursize];
-               gh->buckets= (Entry**)MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets");
-               memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
+               gh->nbuckets = hashsizes[++gh->cursize];
+               gh->buckets = (Entry **)MEM_mallocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
+               memset(gh->buckets, 0, gh->nbuckets * sizeof(*gh->buckets));
 
-               for (i=0; i<nold; i++) {
-                       for (e= old[i]; e;) {
-                               Entry *n= e->next;
+               for (i = 0; i < nold; i++) {
+                       for (e = old[i]; e; ) {
+                               Entry *n = e->next;
 
-                               hash= gh->hashfp(e->key)%gh->nbuckets;
-                               e->next= gh->buckets[hash];
-                               gh->buckets[hash]= e;
+                               hash = gh->hashfp(e->key) % gh->nbuckets;
+                               e->next = gh->buckets[hash];
+                               gh->buckets[hash] = e;
 
-                               e= n;
+                               e = n;
                        }
                }
 
@@ -114,78 +109,106 @@ void BLI_ghash_insert(GHash *gh, void *key, void *val)
 
 void *BLI_ghash_lookup(GHash *gh, const void *key)
 {
-       if(gh) {
-               unsigned int hash= gh->hashfp(key)%gh->nbuckets;
-               Entry *e;
+       const unsigned int hash = gh->hashfp(key) % gh->nbuckets;
+       Entry *e;
 
-               for (e= gh->buckets[hash]; e; e= e->next)
-                       if (gh->cmpfp(key, e->key)==0)
-                               return e->val;
+       for (e = gh->buckets[hash]; e; e = e->next) {
+               if (gh->cmpfp(key, e->key) == 0) {
+                       return e->val;
+               }
        }
        return NULL;
 }
 
-int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
+bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
 {
-       unsigned int hash= gh->hashfp(key)%gh->nbuckets;
+       unsigned int hash = gh->hashfp(key) % gh->nbuckets;
        Entry *e;
        Entry *p = NULL;
 
-       for (e= gh->buckets[hash]; e; e= e->next) {
-               if (gh->cmpfp(key, e->key)==0) {
-                       Entry *n= e->next;
+       for (e = gh->buckets[hash]; e; e = e->next) {
+               if (gh->cmpfp(key, e->key) == 0) {
+                       Entry *n = e->next;
 
                        if (keyfreefp) keyfreefp(e->key);
                        if (valfreefp) valfreefp(e->val);
                        BLI_mempool_free(gh->entrypool, e);
 
-                       /* correct but 'e' isnt used before return */
-                       /* e= n; */ /*UNUSED*/
-                       if (p)
-                               p->next = n;
-                       else
-                               gh->buckets[hash] = n;
+                       /* correct but 'e' isn't used before return */
+                       /* e = n; *//*UNUSED*/
+                       if (p) p->next = n;
+                       else   gh->buckets[hash] = n;
 
-                       --gh->nentries;
-                       return 1;
+                       gh->nentries--;
+                       return true;
                }
                p = e;
        }
 
-       return 0;
+       return false;
 }
 
-int BLI_ghash_haskey(GHash *gh, void *key)
+/* same as above but return the value,
+ * no free value argument since it will be returned */
+void *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp)
 {
-       unsigned int hash= gh->hashfp(key)%gh->nbuckets;
+       unsigned int hash = gh->hashfp(key) % gh->nbuckets;
        Entry *e;
+       Entry *p = NULL;
 
-       for (e= gh->buckets[hash]; e; e= e->next)
-               if (gh->cmpfp(key, e->key)==0)
-                       return 1;
+       for (e = gh->buckets[hash]; e; e = e->next) {
+               if (gh->cmpfp(key, e->key) == 0) {
+                       Entry *n = e->next;
+                       void *value = e->val;
 
-       return 0;
+                       if (keyfreefp) keyfreefp(e->key);
+                       BLI_mempool_free(gh->entrypool, e);
+
+                       /* correct but 'e' isn't used before return */
+                       /* e = n; *//*UNUSED*/
+                       if (p) p->next = n;
+                       else   gh->buckets[hash] = n;
+
+                       gh->nentries--;
+                       return value;
+               }
+               p = e;
+       }
+
+       return NULL;
+}
+
+bool BLI_ghash_haskey(GHash *gh, const void *key)
+{
+       unsigned int hash = gh->hashfp(key) % gh->nbuckets;
+       Entry *e;
+
+       for (e = gh->buckets[hash]; e; e = e->next)
+               if (gh->cmpfp(key, e->key) == 0)
+                       return true;
+
+       return false;
 }
 
 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
 {
        int i;
-       
+
        if (keyfreefp || valfreefp) {
-               for (i=0; i<gh->nbuckets; i++) {
+               for (i = 0; i < gh->nbuckets; i++) {
                        Entry *e;
-                       
-                       for (e= gh->buckets[i]; e; ) {
-                               Entry *n= e->next;
-                               
+
+                       for (e = gh->buckets[i]; e; ) {
+                               Entry *n = e->next;
+
                                if (keyfreefp) keyfreefp(e->key);
                                if (valfreefp) valfreefp(e->val);
 
-                               e= n;
+                               e = n;
                        }
                }
        }
-       
+
        MEM_freeN(gh->buckets);
        BLI_mempool_destroy(gh->entrypool);
        gh->buckets = NULL;
@@ -198,28 +221,28 @@ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreef
 
 GHashIterator *BLI_ghashIterator_new(GHash *gh)
 {
-       GHashIterator *ghi= MEM_mallocN(sizeof(*ghi), "ghash iterator");
-       ghi->gh= gh;
-       ghi->curEntry= NULL;
-       ghi->curBucket= -1;
+       GHashIterator *ghi = MEM_mallocN(sizeof(*ghi), "ghash iterator");
+       ghi->gh = gh;
+       ghi->curEntry = NULL;
+       ghi->curBucket = -1;
        while (!ghi->curEntry) {
                ghi->curBucket++;
-               if (ghi->curBucket==ghi->gh->nbuckets)
+               if (ghi->curBucket == ghi->gh->nbuckets)
                        break;
-               ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
+               ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
        }
        return ghi;
 }
 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
 {
-       ghi->gh= gh;
-       ghi->curEntry= NULL;
-       ghi->curBucket= -1;
+       ghi->gh = gh;
+       ghi->curEntry = NULL;
+       ghi->curBucket = -1;
        while (!ghi->curEntry) {
                ghi->curBucket++;
-               if (ghi->curBucket==ghi->gh->nbuckets)
+               if (ghi->curBucket == ghi->gh->nbuckets)
                        break;
-               ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
+               ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
        }
 }
 void BLI_ghashIterator_free(GHashIterator *ghi)
@@ -229,28 +252,28 @@ void BLI_ghashIterator_free(GHashIterator *ghi)
 
 void *BLI_ghashIterator_getKey(GHashIterator *ghi)
 {
-       return ghi->curEntry?ghi->curEntry->key:NULL;
+       return ghi->curEntry ? ghi->curEntry->key : NULL;
 }
 void *BLI_ghashIterator_getValue(GHashIterator *ghi)
 {
-       return ghi->curEntry?ghi->curEntry->val:NULL;
+       return ghi->curEntry ? ghi->curEntry->val : NULL;
 }
 
 void BLI_ghashIterator_step(GHashIterator *ghi)
 {
        if (ghi->curEntry) {
-               ghi->curEntry= ghi->curEntry->next;
+               ghi->curEntry = ghi->curEntry->next;
                while (!ghi->curEntry) {
                        ghi->curBucket++;
-                       if (ghi->curBucket==ghi->gh->nbuckets)
+                       if (ghi->curBucket == ghi->gh->nbuckets)
                                break;
-                       ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
+                       ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
                }
        }
 }
-int BLI_ghashIterator_isDone(GHashIterator *ghi)
+bool BLI_ghashIterator_notDone(GHashIterator *ghi)
 {
-       return !ghi->curEntry;
+       return ghi->curEntry != NULL;
 }
 
 /***/
@@ -261,10 +284,10 @@ unsigned int BLI_ghashutil_ptrhash(const void *key)
 }
 int BLI_ghashutil_ptrcmp(const void *a, const void *b)
 {
-       if (a==b)
+       if (a == b)
                return 0;
        else
-               return (a<b)?-1:1;
+               return (a < b) ? -1 : 1;
 }
 
 unsigned int BLI_ghashutil_inthash(const void *ptr)
@@ -283,29 +306,55 @@ unsigned int BLI_ghashutil_inthash(const void *ptr)
 
 int BLI_ghashutil_intcmp(const void *a, const void *b)
 {
-       if (a==b)
+       if (a == b)
                return 0;
        else
-               return (a<b)?-1:1;
+               return (a < b) ? -1 : 1;
 }
 
+/**
+ * This function implements the widely used "djb" hash apparently posted
+ * by Daniel Bernstein to comp.lang.c some time ago.  The 32 bit
+ * unsigned hash value starts at 5381 and for each byte 'c' in the
+ * string, is updated: <literal>hash = hash * 33 + c</literal>.  This
+ * function uses the signed value of each byte.
+ *
+ * note: this is the same hash method that glib 2.34.0 uses.
+ */
 unsigned int BLI_ghashutil_strhash(const void *ptr)
 {
-       const char *s= ptr;
-       unsigned int i= 0;
-       unsigned char c;
-       
-       while ( (c= *s++) )
-               i= i*37 + c;
-               
-       return i;
+       const signed char *p;
+       unsigned int h = 5381;
+
+       for (p = ptr; *p != '\0'; p++) {
+               h = (h << 5) + h + *p;
+       }
+
+       return h;
 }
 int BLI_ghashutil_strcmp(const void *a, const void *b)
 {
        return strcmp(a, b);
 }
 
-GHashPair *BLI_ghashutil_pairalloc(const void *first, int second)
+GHash *BLI_ghash_ptr_new(const char *info)
+{
+       return BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info);
+}
+GHash *BLI_ghash_str_new(const char *info)
+{
+       return BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp, info);
+}
+GHash *BLI_ghash_int_new(const char *info)
+{
+       return BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp, info);
+}
+GHash *BLI_ghash_pair_new(const char *info)
+{
+       return BLI_ghash_new(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info);
+}
+
+GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second)
 {
        GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair");
        pair->first = first;
@@ -317,7 +366,7 @@ unsigned int BLI_ghashutil_pairhash(const void *ptr)
 {
        const GHashPair *pair = ptr;
        unsigned int hash = BLI_ghashutil_ptrhash(pair->first);
-       return hash ^ BLI_ghashutil_inthash(SET_INT_IN_POINTER(pair->second));
+       return hash ^ BLI_ghashutil_ptrhash(pair->second);
 }
 
 int BLI_ghashutil_paircmp(const void *a, const void *b)
@@ -326,13 +375,12 @@ int BLI_ghashutil_paircmp(const void *a, const void *b)
        const GHashPair *B = b;
 
        int cmp = BLI_ghashutil_ptrcmp(A->first, B->first);
-       if(cmp == 0)
-               return BLI_ghashutil_intcmp(SET_INT_IN_POINTER(A->second), SET_INT_IN_POINTER(B->second));
+       if (cmp == 0)
+               return BLI_ghashutil_ptrcmp(A->second, B->second);
        return cmp;
 }
 
 void BLI_ghashutil_pairfree(void *ptr)
 {
-       MEM_freeN((void*)ptr);
+       MEM_freeN((void *)ptr);
 }
-