diff options
Diffstat (limited to 'source/blender/blenlib/intern/edgehash.c')
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 126 |
1 files changed, 19 insertions, 107 deletions
diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 0eda3e78824..4b4bff7df78 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -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 @@ -35,113 +35,23 @@ #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, TRUE, FALSE); - 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) { |