diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-08-26 17:41:13 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-08-26 17:41:13 +0400 |
commit | 1dba986505f64cbf9758a42e4fff2c09502b9c22 (patch) | |
tree | 98cde96a1e80150e18847fbe4f6ee68a2f957c8e /source/blender | |
parent | a26c048fdeff3e82657fdab85dc90e0e71ea5eb1 (diff) |
internal changes to ghash/edgehash, reorganize to split out resizing the hash from insertion.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 107 | ||||
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 136 |
2 files changed, 165 insertions, 78 deletions
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 5462a61d967..dc9d4db7e8a 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -98,6 +98,14 @@ struct GHash { * \{ */ /** + * Get the hash for a key. + */ +BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key) +{ + return gh->hashfp(key) % gh->nbuckets; +} + +/** * Check if the number of items in the GHash is large enough to require more buckets. */ BLI_INLINE bool ghash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets) @@ -106,21 +114,43 @@ BLI_INLINE bool ghash_test_expand_buckets(const unsigned int nentries, const uns } /** - * Increase initial bucket size to match a reserved ammount. + * Expand buckets to the next size up. */ -BLI_INLINE void ghash_buckets_reserve(GHash *gh, const unsigned int nentries_reserve) +BLI_INLINE void ghash_resize_buckets(GHash *gh, const unsigned int nbuckets) { - while (ghash_test_expand_buckets(nentries_reserve, gh->nbuckets)) { - gh->nbuckets = hashsizes[++gh->cursize]; + Entry **buckets_old = gh->buckets; + Entry **buckets_new; + const unsigned int nbuckets_old = gh->nbuckets; + unsigned int i; + Entry *e; + + BLI_assert(gh->nbuckets != nbuckets); + + gh->nbuckets = nbuckets; + buckets_new = (Entry **)MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); + + for (i = 0; i < nbuckets_old; i++) { + Entry *e_next; + for (e = buckets_old[i]; e; e = e_next) { + const unsigned hash = ghash_keyhash(gh, e->key); + e_next = e->next; + e->next = buckets_new[hash]; + buckets_new[hash] = e; + } } + + gh->buckets = buckets_new; + MEM_freeN(buckets_old); } /** - * Get the hash for a key. + * Increase initial bucket size to match a reserved ammount. */ -BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key) +BLI_INLINE void ghash_buckets_reserve(GHash *gh, const unsigned int nentries_reserve) { - return gh->hashfp(key) % gh->nbuckets; + while (ghash_test_expand_buckets(nentries_reserve, gh->nbuckets)) { + gh->nbuckets = hashsizes[++gh->cursize]; + } } /** @@ -133,7 +163,7 @@ BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key, Entry *e; for (e = gh->buckets[hash]; e; e = e->next) { - if (gh->cmpfp(key, e->key) == 0) { + if (UNLIKELY(gh->cmpfp(key, e->key) == 0)) { return e; } } @@ -178,41 +208,45 @@ static GHash *ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, * Internal insert function. * Takes a hash argument to avoid calling #ghash_keyhash multiple times. */ -static Entry *ghash_insert_ex(GHash *gh, void *key, - unsigned int hash) +BLI_INLINE void ghash_insert_ex(GHash *gh, void *key, void *val, + unsigned int hash) { Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool); - BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0)); + IS_GHASH_ASSERT(gh); e->next = gh->buckets[hash]; e->key = key; - /* intentionally don't set the value */ + e->val = val; gh->buckets[hash] = e; if (UNLIKELY(ghash_test_expand_buckets(++gh->nentries, gh->nbuckets))) { - Entry *e_iter; - Entry **old = gh->buckets; - const unsigned nold = gh->nbuckets; - unsigned int i; + ghash_resize_buckets(gh, hashsizes[++gh->cursize]); + } +} - gh->nbuckets = hashsizes[++gh->cursize]; - gh->buckets = (Entry **)MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); - - for (i = 0; i < nold; i++) { - Entry *e_next; - for (e_iter = old[i]; e_iter; e_iter = e_next) { - e_next = e_iter->next; - hash = ghash_keyhash(gh, e_iter->key); - e_iter->next = gh->buckets[hash]; - gh->buckets[hash] = e_iter; - } - } +/** + * Insert function that doesn't set the value (use for GSet) + */ +BLI_INLINE void ghash_insert_ex_keyonly(GHash *gh, void *key, + unsigned int hash) +{ + Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool); + BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0)); + e->next = gh->buckets[hash]; + e->key = key; + /* intentionally leave value unset */ + gh->buckets[hash] = e; - MEM_freeN(old); + if (UNLIKELY(ghash_test_expand_buckets(++gh->nentries, gh->nbuckets))) { + ghash_resize_buckets(gh, hashsizes[++gh->cursize]); } +} - return e; +BLI_INLINE void ghash_insert(GHash *gh, void *key, void *val) +{ + const unsigned int hash = ghash_keyhash(gh, key); + return ghash_insert_ex(gh, key, val, hash); } /** @@ -225,7 +259,7 @@ static Entry *ghash_remove_ex(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GH Entry *e_prev = NULL; for (e = gh->buckets[hash]; e; e = e->next) { - if (gh->cmpfp(key, e->key) == 0) { + if (UNLIKELY(gh->cmpfp(key, e->key) == 0)) { Entry *e_next = e->next; if (keyfreefp) keyfreefp(e->key); @@ -314,9 +348,7 @@ int BLI_ghash_size(GHash *gh) */ void BLI_ghash_insert(GHash *gh, void *key, void *val) { - const unsigned int hash = ghash_keyhash(gh, key); - Entry *e = ghash_insert_ex(gh, key, hash); - e->val = val; + ghash_insert(gh, key, val); } /** @@ -338,8 +370,7 @@ bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreef return false; } else { - e = ghash_insert_ex(gh, key, hash); - e->val = val; + ghash_insert_ex(gh, key, val, hash); return true; } } @@ -811,7 +842,7 @@ int BLI_gset_size(GSet *gs) void BLI_gset_insert(GSet *gs, void *key) { const unsigned int hash = ghash_keyhash((GHash *)gs, key); - ghash_insert_ex((GHash *)gs, key, hash); + ghash_insert_ex_keyonly((GHash *)gs, key, hash); } /** @@ -830,7 +861,7 @@ bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp) return false; } else { - ghash_insert_ex((GHash *)gs, key, hash); + ghash_insert_ex_keyonly((GHash *)gs, key, hash); return true; } } diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 03822e894cf..5e07920b6e3 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -95,12 +95,55 @@ struct EdgeHash { /** \name Internal Utility API * \{ */ +/** + * Get the hash for a key. + */ +BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1) +{ + BLI_assert(v0 < v1); + + return ((v0 * 39) ^ (v1 * 31)) % eh->nbuckets; +} + +/** + * Check if the number of items in the GHash is large enough to require more buckets. + */ BLI_INLINE bool edgehash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets) { return (nentries > nbuckets * 3); } /** + * Expand buckets to the next size up. + */ +BLI_INLINE void edgehash_resize_buckets(EdgeHash *eh, const unsigned int nbuckets) +{ + EdgeEntry **buckets_old = eh->buckets; + EdgeEntry **buckets_new; + const unsigned int nbuckets_old = eh->nbuckets; + unsigned int i; + EdgeEntry *e; + + BLI_assert(eh->nbuckets != nbuckets); + + eh->nbuckets = nbuckets; + buckets_new = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets"); + + for (i = 0; i < nbuckets_old; i++) { + EdgeEntry *e_next; + for (e = buckets_old[i]; e; e = e_next) { + const unsigned hash = edgehash_keyhash(eh, e->v0, e->v1); + e_next = e->next; + e->next = buckets_new[hash]; + buckets_new[hash] = e; + } + } + + eh->buckets = buckets_new; + MEM_freeN(buckets_old); +} + +/** * Increase initial bucket size to match a reserved ammount. */ BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const unsigned int nentries_reserve) @@ -110,26 +153,26 @@ BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const unsigned int nentri } } -BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1) -{ - BLI_assert(v0 < v1); - - return ((v0 * 39) ^ (v1 * 31)) % eh->nbuckets; -} - +/** + * Internal lookup function. + * Takes a hash argument to avoid calling #ghash_keyhash multiple times. + */ BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, const unsigned int hash) { EdgeEntry *e; BLI_assert(v0 < v1); for (e = eh->buckets[hash]; e; e = e->next) { - if (v0 == e->v0 && v1 == e->v1) { + if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) { return e; } } return NULL; } +/** + * Internal lookup function. Only wraps #edgehash_lookup_entry_ex + */ BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, unsigned int v0, unsigned int v1) { unsigned int hash; @@ -138,6 +181,7 @@ BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, unsigned int v0, unsig return edgehash_lookup_entry_ex(eh, v0, v1, hash); } + static EdgeHash *edgehash_new(const char *info, const unsigned int nentries_reserve, const size_t entry_size) @@ -160,12 +204,17 @@ static EdgeHash *edgehash_new(const char *info, return eh; } -static EdgeEntry *edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, - unsigned int hash) +/** + * Internal insert function. + * Takes a hash argument to avoid calling #edgehash_keyhash multiple times. + */ +BLI_INLINE void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val, + unsigned int hash) { EdgeEntry *e = BLI_mempool_alloc(eh->epool); BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0)); + IS_EDGEHASH_ASSERT(eh); /* this helps to track down errors with bad edge data */ BLI_assert(v0 < v1); @@ -174,31 +223,45 @@ static EdgeEntry *edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int e->next = eh->buckets[hash]; e->v0 = v0; e->v1 = v1; - /* intentionally don't set the value */ + e->val = val; eh->buckets[hash] = e; if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) { - EdgeEntry *e_iter; - EdgeEntry **old = eh->buckets; - const unsigned int nold = eh->nbuckets; - unsigned int i; + edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]); + } +} - eh->nbuckets = _ehash_hashsizes[++eh->cursize]; - eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets"); - - for (i = 0; i < nold; i++) { - EdgeEntry *e_next; - for (e_iter = old[i]; e_iter; e_iter = e_next) { - e_next = e_iter->next; - hash = edgehash_keyhash(eh, e_iter->v0, e_iter->v1); - e_iter->next = eh->buckets[hash]; - eh->buckets[hash] = e_iter; - } - } +/** + * Insert function that doesn't set the value (use for EdgeSet) + */ +BLI_INLINE void edgehash_insert_ex_keyonly(EdgeHash *eh, unsigned int v0, unsigned int v1, + unsigned int hash) +{ + EdgeEntry *e = BLI_mempool_alloc(eh->epool); - MEM_freeN(old); + BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0)); + + /* this helps to track down errors with bad edge data */ + BLI_assert(v0 < v1); + BLI_assert(v0 != v1); + + e->next = eh->buckets[hash]; + e->v0 = v0; + e->v1 = v1; + /* intentionally leave value unset */ + eh->buckets[hash] = e; + + if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) { + edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]); } - return e; +} + +BLI_INLINE void edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val) +{ + unsigned int hash; + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); + edgehash_insert_ex(eh, v0, v1, val, hash); } /** @@ -250,13 +313,7 @@ EdgeHash *BLI_edgehash_new(const char *info) */ void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val) { - unsigned int hash; - EdgeEntry *e; - IS_EDGEHASH_ASSERT(eh); - EDGE_ORD(v0, v1); /* ensure v0 is smaller */ - hash = edgehash_keyhash(eh, v0, v1); - e = edgehash_insert_ex(eh, v0, v1, hash); - e->val = val; + edgehash_insert(eh, v0, v1, val); } /** @@ -278,8 +335,7 @@ bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned int v1, void return false; } else { - e = edgehash_insert_ex(eh, v0, v1, hash); - e->val = val; + edgehash_insert_ex(eh, v0, v1, val, hash); return true; } } @@ -510,7 +566,7 @@ void BLI_edgeset_insert(EdgeSet *es, unsigned int v0, unsigned int v1) unsigned int hash; EDGE_ORD(v0, v1); /* ensure v0 is smaller */ hash = edgehash_keyhash((EdgeHash *)es, v0, v1); - edgehash_insert_ex((EdgeHash *)es, v0, v1, hash); + edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, hash); } /** @@ -529,7 +585,7 @@ bool BLI_edgeset_reinsert(EdgeSet *es, unsigned int v0, unsigned int v1) return false; } else { - edgehash_insert_ex((EdgeHash *)es, v0, v1, hash); + edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, hash); return true; } } |