diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-08-18 07:41:39 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-08-18 07:41:39 +0400 |
commit | 754b4ab3bcbc92df0bcdff4848ef5ffc9410dce2 (patch) | |
tree | fa1dd64c56c0822962369d2d095f66b76f758e3a /source/blender/blenlib/intern/BLI_ghash.c | |
parent | 7cce5563445a5363f9d125bf8c3cb30734cabdfe (diff) |
add hash function BLI_ghash_assign, BLI_edgehash_assign
avoids remove,insert and only hashes the key once.
Diffstat (limited to 'source/blender/blenlib/intern/BLI_ghash.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 97 |
1 files changed, 71 insertions, 26 deletions
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index da886e59c21..8221393d4d5 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -84,30 +84,35 @@ typedef struct GHash { /* -------------------------------------------------------------------- */ /* GHash API */ -GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) -{ - GHash *gh = MEM_mallocN(sizeof(*gh), info); - gh->hashfp = hashfp; - gh->cmpfp = cmpfp; - gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0); +/* internal utility API */ - gh->cursize = 0; - gh->nentries = 0; - gh->nbuckets = hashsizes[gh->cursize]; +BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key) +{ + return gh->hashfp(key) % gh->nbuckets; +} - gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); +BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key, + const unsigned int hash) +{ + Entry *e; - return gh; + for (e = gh->buckets[hash]; e; e = e->next) { + if (gh->cmpfp(key, e->key) == 0) { + return e; + } + } + return NULL; } -int BLI_ghash_size(GHash *gh) +BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key) { - return (int)gh->nentries; + const unsigned int hash = ghash_keyhash(gh, key); + return ghash_lookup_entry_ex(gh, key, hash); } -void BLI_ghash_insert(GHash *gh, void *key, void *val) +static void ghash_insert_ex(GHash *gh, void *key, void *val, + unsigned int hash) { - unsigned int hash = gh->hashfp(key) % gh->nbuckets; Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool); BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0)); @@ -129,7 +134,7 @@ void BLI_ghash_insert(GHash *gh, void *key, void *val) Entry *e_next; for (e = old[i]; e; e = e_next) { e_next = e->next; - hash = gh->hashfp(e->key) % gh->nbuckets; + hash = ghash_keyhash(gh, e->key); e->next = gh->buckets[hash]; gh->buckets[hash] = e; } @@ -139,17 +144,57 @@ void BLI_ghash_insert(GHash *gh, void *key, void *val) } } -BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key) + +/* Public API */ + +GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) { - const unsigned int hash = gh->hashfp(key) % gh->nbuckets; - Entry *e; + GHash *gh = MEM_mallocN(sizeof(*gh), info); + gh->hashfp = hashfp; + gh->cmpfp = cmpfp; + gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0); - for (e = gh->buckets[hash]; e; e = e->next) { - if (gh->cmpfp(key, e->key) == 0) { - return e; - } + gh->cursize = 0; + gh->nentries = 0; + gh->nbuckets = hashsizes[gh->cursize]; + + gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); + + return gh; +} + +int BLI_ghash_size(GHash *gh) +{ + return (int)gh->nentries; +} + +void BLI_ghash_insert(GHash *gh, void *key, void *val) +{ + const unsigned int hash = ghash_keyhash(gh, key); + ghash_insert_ex(gh, key, val, hash); +} + +/** + * Assign a new value to a key that may already be in ghash. + * Avoids #BLI_ghash_remove, #BLI_ghash_insert calls (double lookups) + * + * \note We may want to have 'BLI_ghash_assign_ex' function that takes + * GHashKeyFreeFP & GHashValFreeFP args. for now aren't needed. + */ +void BLI_ghash_assign(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) +{ + const unsigned int hash = ghash_keyhash(gh, key); + Entry *e = ghash_lookup_entry_ex(gh, key, hash); + if (e) { + if (keyfreefp) keyfreefp(e->key); + if (valfreefp) valfreefp(e->val); + + e->key = key; + e->val = val; + } + else { + ghash_insert_ex(gh, key, val, hash); } - return NULL; } void *BLI_ghash_lookup(GHash *gh, const void *key) @@ -166,7 +211,7 @@ void **BLI_ghash_lookup_p(GHash *gh, const void *key) bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) { - unsigned int hash = gh->hashfp(key) % gh->nbuckets; + const unsigned int hash = ghash_keyhash(gh, key); Entry *e; Entry *p = NULL; @@ -196,7 +241,7 @@ bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFr * no free value argument since it will be returned */ void *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp) { - unsigned int hash = gh->hashfp(key) % gh->nbuckets; + const unsigned int hash = ghash_keyhash(gh, key); Entry *e; Entry *p = NULL; |