svn merge ^/trunk/blender -r41226:41227 .
[blender.git] / source / blender / blenlib / intern / edgehash.c
index 65c5dff..8a8c905 100644 (file)
@@ -20,7 +20,7 @@
  *
  * The Original Code is: none of this file.
  *
- * Contributor(s): Daniel Dunbar
+ * Contributor(s): Daniel Dunbar, Joseph Eagar
  *
  * ***** END GPL LICENSE BLOCK *****
  * A general (pointer -> pointer) hash table ADT
 #include <string.h>
 
 #include "MEM_guardedalloc.h"
-#include "BLI_edgehash.h"
-
-/***/
-
-static unsigned int hashsizes[]= {
-       1, 3, 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, 
-       268435459
-};
-
-#define EDGEHASH(v0,v1)                ((v0*39)^(v1*31))
-
-/***/
-
-typedef struct Entry Entry;
-struct Entry {
-       Entry *next;
-       int v0, v1;
-       void *val;
-};
 
-struct EdgeHash {
-       Entry **buckets;
-       int nbuckets, nentries, cursize;
-};
+#include "BLI_utildefines.h"
+#include "BLI_edgehash.h"
+#include "BLI_mempool.h"
 
 /***/
 
 EdgeHash *BLI_edgehash_new(void) {
-       EdgeHash *eh= MEM_mallocN(sizeof(*eh), "EdgeHash");
+       EdgeHash *eh= MEM_callocN(sizeof(*eh), "EdgeHash");
        eh->cursize= 0;
        eh->nentries= 0;
-       eh->nbuckets= hashsizes[eh->cursize];
-       
-       eh->buckets= malloc(eh->nbuckets*sizeof(*eh->buckets));
-       memset(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets));
-       
-       return eh;
-}
-
-void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) {
-       unsigned int hash;
-       Entry *e= malloc(sizeof(*e));
-
-       if (v1<v0) {
-               v0 ^= v1;
-               v1 ^= v0;
-               v0 ^= v1;
-       }
-        hash = EDGEHASH(v0,v1)%eh->nbuckets;
-
-       e->v0 = v0;
-       e->v1 = v1;
-       e->val = val;
-       e->next= eh->buckets[hash];
-       eh->buckets[hash]= e;
+       eh->nbuckets= _ehash_hashsizes[eh->cursize];
        
-       if (++eh->nentries>eh->nbuckets*3) {
-               Entry **old= eh->buckets;
-               int i, nold= eh->nbuckets;
-               
-               eh->nbuckets= hashsizes[++eh->cursize];
-               eh->buckets= malloc(eh->nbuckets*sizeof(*eh->buckets));
-               memset(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets));
-               
-               for (i=0; i<nold; i++) {
-                       for (e= old[i]; e;) {
-                               Entry *n= e->next;
-                               
-                               hash= EDGEHASH(e->v0,e->v1)%eh->nbuckets;
-                               e->next= eh->buckets[hash];
-                               eh->buckets[hash]= e;
-                               
-                               e= n;
-                       }
-               }
-               
-               free(old);
-       }
-}
-
-void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) {
-       unsigned int hash;
-       Entry *e;
+       eh->buckets= MEM_callocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets 2");
+       eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512, 1, 0);
 
-       if (v1<v0) {
-               v0 ^= v1;
-               v1 ^= v0;
-               v0 ^= v1;
-       }
-       hash = EDGEHASH(v0,v1)%eh->nbuckets;
-       for (e= eh->buckets[hash]; e; e= e->next)
-               if (v0==e->v0 && v1==e->v1)
-                       return &e->val;
-       
-       return NULL;
-}
-
-void* BLI_edgehash_lookup(EdgeHash *eh, int v0, int v1) {
-       void **value_p = BLI_edgehash_lookup_p(eh,v0,v1);
-
-       return value_p?*value_p:NULL;
-}
-
-int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) {
-       return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL;
+       return eh;
 }
 
 int BLI_edgehash_size(EdgeHash *eh) {
@@ -152,13 +62,13 @@ void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) {
        int i;
        
        for (i=0; i<eh->nbuckets; i++) {
-               Entry *e;
+               EdgeEntry *e;
                
                for (e= eh->buckets[i]; e; ) {
-                       Entry *n= e->next;
+                       EdgeEntry *n= e->next;
                        
                        if (valfreefp) valfreefp(e->val);
-                       free(e);
+                       BLI_mempool_free(eh->epool, e);
                        
                        e= n;
                }
@@ -170,8 +80,10 @@ void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) {
 
 void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) {
        BLI_edgehash_clear(eh, valfreefp);
-       
-       free(eh->buckets);
+
+       BLI_mempool_destroy(eh->epool);
+
+       MEM_freeN(eh->buckets);
        MEM_freeN(eh);
 }
 
@@ -181,11 +93,11 @@ void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) {
 struct EdgeHashIterator {
        EdgeHash *eh;
        int curBucket;
-       Entry *curEntry;
+       EdgeEntry *curEntry;
 };
 
 EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) {
-       EdgeHashIterator *ehi= malloc(sizeof(*ehi));
+       EdgeHashIterator *ehi= MEM_mallocN(sizeof(*ehi), "eh iter");
        ehi->eh= eh;
        ehi->curEntry= NULL;
        ehi->curBucket= -1;
@@ -198,7 +110,7 @@ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) {
        return ehi;
 }
 void BLI_edgehashIterator_free(EdgeHashIterator *ehi) {
-       free(ehi);
+       MEM_freeN(ehi);
 }
 
 void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, int *v0_r, int *v1_r) {