diff options
Diffstat (limited to 'source/blender/blenlib/intern/edgehash.c')
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 102 |
1 files changed, 4 insertions, 98 deletions
diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index cdc952e7b04..a7b2ae9edeb 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -37,32 +37,6 @@ /***/ -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; - BLI_mempool *epool; - int nbuckets, nentries, cursize; -}; - -/***/ - EdgeHash *BLI_edgehash_new(void) { EdgeHash *eh= MEM_callocN(sizeof(*eh), "EdgeHash"); eh->cursize= 0; @@ -70,79 +44,11 @@ EdgeHash *BLI_edgehash_new(void) { eh->nbuckets= hashsizes[eh->cursize]; eh->buckets= MEM_callocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets 2"); - eh->epool = BLI_mempool_create(sizeof(Entry), 512, 512); + eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512); return eh; } -void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) { - unsigned int hash; - Entry *e= BLI_mempool_alloc(eh->epool); - - 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; - - if (++eh->nentries>eh->nbuckets*3) { - Entry *e, **old= eh->buckets; - int i, nold= eh->nbuckets; - - eh->nbuckets= hashsizes[++eh->cursize]; - eh->buckets= MEM_mallocN(eh->nbuckets*sizeof(*eh->buckets), "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; - } - } - - MEM_freeN(old); - } -} - -void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) { - unsigned int hash; - Entry *e; - - 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; -} - int BLI_edgehash_size(EdgeHash *eh) { return eh->nentries; } @@ -151,10 +57,10 @@ 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); BLI_mempool_free(eh->epool, e); @@ -182,7 +88,7 @@ void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) { struct EdgeHashIterator { EdgeHash *eh; int curBucket; - Entry *curEntry; + EdgeEntry *curEntry; }; EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) { |