diff options
author | Campbell Barton <ideasman42@gmail.com> | 2011-12-28 13:47:24 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2011-12-28 13:47:24 +0400 |
commit | 86b184dc9b8ae1c08955ebe168d2223da17adc95 (patch) | |
tree | c08803e23e215a5550675c92cf4d1a889997cea1 /source/blender/blenlib | |
parent | 74ea65d5084708f2724e9e2ca6746ab441618bd0 (diff) |
un-inline edgehash functions, BLI_edgehash_insert especially was too large to inline
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_edgehash.h | 106 | ||||
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 99 |
2 files changed, 102 insertions, 103 deletions
diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index 0538932c8a5..283b52e06b9 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -34,10 +34,6 @@ * \brief A general unordered 2-int pair hash table ADT. */ -#include "MEM_guardedalloc.h" -#include "BKE_utildefines.h" -#include "BLI_mempool.h" - struct EdgeHash; struct EdgeHashIterator; typedef struct EdgeHash EdgeHash; @@ -51,22 +47,22 @@ void BLI_edgehash_free (EdgeHash *eh, EdgeHashFreeFP valfreefp); /* Insert edge (v0,v1) into hash with given value, does * not check for duplicates. */ -//void BLI_edgehash_insert (EdgeHash *eh, int v0, int v1, void *val); +void BLI_edgehash_insert (EdgeHash *eh, int v0, int v1, void *val); /* Return value for given edge (v0,v1), or NULL if * if key does not exist in hash. (If need exists * to differentiate between key-value being NULL and * lack of key then see BLI_edgehash_lookup_p(). */ -//void* BLI_edgehash_lookup (EdgeHash *eh, int v0, int v1); +void* BLI_edgehash_lookup (EdgeHash *eh, int v0, int v1); /* Return pointer to value for given edge (v0,v1), * or NULL if key does not exist in hash. */ -//void** BLI_edgehash_lookup_p (EdgeHash *eh, int v0, int v1); +void** BLI_edgehash_lookup_p (EdgeHash *eh, int v0, int v1); /* Return boolean true/false if edge (v0,v1) in hash. */ -//int BLI_edgehash_haskey (EdgeHash *eh, int v0, int v1); +int BLI_edgehash_haskey (EdgeHash *eh, int v0, int v1); /* Return number of keys in hash. */ int BLI_edgehash_size (EdgeHash *eh); @@ -101,99 +97,5 @@ void BLI_edgehashIterator_step (EdgeHashIterator *ehi); /* Determine if an iterator is done. */ int BLI_edgehashIterator_isDone (EdgeHashIterator *ehi); -/**************inlined code************/ -static unsigned int _ehash_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 EdgeEntry EdgeEntry; -struct EdgeEntry { - EdgeEntry *next; - int v0, v1; - void *val; -}; - -struct EdgeHash { - EdgeEntry **buckets; - BLI_mempool *epool; - int nbuckets, nentries, cursize; -}; - - -BM_INLINE void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) { - unsigned int hash; - EdgeEntry *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) { - EdgeEntry *e, **old= eh->buckets; - int i, nold= eh->nbuckets; - - eh->nbuckets= _ehash_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;) { - EdgeEntry *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); - } -} - -BM_INLINE void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) { - unsigned int hash; - EdgeEntry *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; -} - -BM_INLINE 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; -} - -BM_INLINE int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) { - return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL; -} - #endif diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index dbd138a3563..c646c59ea0e 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -40,6 +40,31 @@ #include "BLI_edgehash.h" #include "BLI_mempool.h" +/**************inlined code************/ +static unsigned int _ehash_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 EdgeEntry EdgeEntry; +struct EdgeEntry { + EdgeEntry *next; + int v0, v1; + void *val; +}; + +struct EdgeHash { + EdgeEntry **buckets; + BLI_mempool *epool; + int nbuckets, nentries, cursize; +}; + /***/ EdgeHash *BLI_edgehash_new(void) @@ -55,6 +80,77 @@ EdgeHash *BLI_edgehash_new(void) return eh; } + +void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) { + unsigned int hash; + EdgeEntry *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) { + EdgeEntry *e, **old= eh->buckets; + int i, nold= eh->nbuckets; + + eh->nbuckets= _ehash_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;) { + EdgeEntry *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; + EdgeEntry *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; @@ -149,7 +245,8 @@ void BLI_edgehashIterator_step(EdgeHashIterator *ehi) } } } -int BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) { +int BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) +{ return !ehi->curEntry; } |