diff options
-rw-r--r-- | source/blender/blenlib/BLI_edgehash.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 149 | ||||
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 65 |
3 files changed, 120 insertions, 96 deletions
diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index 0ac1660484b..de9b61527e1 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -50,6 +50,8 @@ void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1); bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1); int BLI_edgehash_size(EdgeHash *eh); +void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp, + const unsigned int nentries_reserve); void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp); void BLI_edgehash_flag_set(EdgeHash *eh, unsigned int flag); void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag); diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 27ab65fd92f..2adc24b657c 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -204,6 +204,57 @@ static Entry *ghash_insert_ex(GHash *gh, void *key, return e; } + +/** + * Remove the entry and return it, caller must free from gh->entrypool. + */ +static Entry *ghash_remove_ex(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, + unsigned int hash) +{ + Entry *e; + Entry *e_prev = NULL; + + for (e = gh->buckets[hash]; e; e = e->next) { + if (gh->cmpfp(key, e->key) == 0) { + Entry *e_next = e->next; + + if (keyfreefp) keyfreefp(e->key); + if (valfreefp) valfreefp(e->val); + + if (e_prev) e_prev->next = e_next; + else gh->buckets[hash] = e_next; + + gh->nentries--; + return e; + } + e_prev = e; + } + + return NULL; +} + +/** + * Run free callbacks for freeing entries. + */ +static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) +{ + unsigned int i; + + BLI_assert(keyfreefp || valfreefp); + + for (i = 0; i < gh->nbuckets; i++) { + Entry *e; + + for (e = gh->buckets[i]; e; ) { + Entry *e_next = e->next; + + if (keyfreefp) keyfreefp(e->key); + if (valfreefp) valfreefp(e->val); + + e = e_next; + } + } +} /** \} */ @@ -325,29 +376,14 @@ void **BLI_ghash_lookup_p(GHash *gh, const void *key) bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) { const unsigned int hash = ghash_keyhash(gh, key); - Entry *e; - Entry *p = NULL; - - for (e = gh->buckets[hash]; e; e = e->next) { - if (gh->cmpfp(key, e->key) == 0) { - Entry *n = e->next; - - if (keyfreefp) keyfreefp(e->key); - if (valfreefp) valfreefp(e->val); - BLI_mempool_free(gh->entrypool, e); - - /* correct but 'e' isn't used before return */ - /* e = n; *//*UNUSED*/ - if (p) p->next = n; - else gh->buckets[hash] = n; - - gh->nentries--; - return true; - } - p = e; + Entry *e = ghash_remove_ex(gh, key, keyfreefp, valfreefp, hash); + if (e) { + BLI_mempool_free(gh->entrypool, e); + return true; + } + else { + return false; } - - return false; } /* same as above but return the value, @@ -362,29 +398,15 @@ bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFr void *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp) { const unsigned int hash = ghash_keyhash(gh, key); - Entry *e; - Entry *p = NULL; - - for (e = gh->buckets[hash]; e; e = e->next) { - if (gh->cmpfp(key, e->key) == 0) { - Entry *n = e->next; - void *value = e->val; - - if (keyfreefp) keyfreefp(e->key); - BLI_mempool_free(gh->entrypool, e); - - /* correct but 'e' isn't used before return */ - /* e = n; *//*UNUSED*/ - if (p) p->next = n; - else gh->buckets[hash] = n; - - gh->nentries--; - return value; - } - p = e; + Entry *e = ghash_remove_ex(gh, key, keyfreefp, NULL, hash); + if (e) { + void *val = e->val; + BLI_mempool_free(gh->entrypool, e); + return val; + } + else { + return NULL; } - - return NULL; } /** @@ -405,22 +427,8 @@ bool BLI_ghash_haskey(GHash *gh, const void *key) void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, const unsigned int nentries_reserve) { - unsigned int i; - - if (keyfreefp || valfreefp) { - for (i = 0; i < gh->nbuckets; i++) { - Entry *e; - - for (e = gh->buckets[i]; e; ) { - Entry *n = e->next; - - if (keyfreefp) keyfreefp(e->key); - if (valfreefp) valfreefp(e->val); - - e = n; - } - } - } + if (keyfreefp || valfreefp) + ghash_free_cb(gh, keyfreefp, valfreefp); gh->nbuckets = hashsizes[0]; /* gh->cursize */ gh->nentries = 0; @@ -453,28 +461,13 @@ void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfree */ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) { - unsigned int i; - - if (keyfreefp || valfreefp) { - for (i = 0; i < gh->nbuckets; i++) { - Entry *e; - - for (e = gh->buckets[i]; e; ) { - Entry *n = e->next; + BLI_assert((int)gh->nentries == BLI_mempool_count(gh->entrypool)); - if (keyfreefp) keyfreefp(e->key); - if (valfreefp) valfreefp(e->val); - - e = n; - } - } - } + if (keyfreefp || valfreefp) + ghash_free_cb(gh, keyfreefp, valfreefp); MEM_freeN(gh->buckets); BLI_mempool_destroy(gh->entrypool); - gh->buckets = NULL; - gh->nentries = 0; - gh->nbuckets = 0; MEM_freeN(gh); } diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index e90b78620c4..8870bce435b 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -144,7 +144,7 @@ static EdgeHash *edgehash_new(const char *info, edgehash_buckets_reserve(eh, nentries_reserve); } - eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets 2"); + eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets"); eh->epool = BLI_mempool_create((int)entry_size, 512, 512, BLI_MEMPOOL_SYSMALLOC); return eh; @@ -190,6 +190,29 @@ static EdgeEntry *edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int } return e; } + +/** + * Run free callbacks for freeing entries. + */ +static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp) +{ + unsigned int i; + + BLI_assert(valfreefp); + + for (i = 0; i < eh->nbuckets; i++) { + EdgeEntry *e; + + for (e = eh->buckets[i]; e; ) { + EdgeEntry *e_next = e->next; + + if (valfreefp) valfreefp(e->val); + + e = e_next; + } + } +} + /** \} */ @@ -289,30 +312,32 @@ int BLI_edgehash_size(EdgeHash *eh) /** * Remove all edges from hash. */ -void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) +void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp, + const unsigned int nentries_reserve) { - unsigned int i; - - for (i = 0; i < eh->nbuckets; i++) { - EdgeEntry *e; - - for (e = eh->buckets[i]; e; ) { - EdgeEntry *n = e->next; - - if (valfreefp) valfreefp(e->val); - BLI_mempool_free(eh->epool, e); - - e = n; - } - eh->buckets[i] = NULL; - } + if (valfreefp) + edgehash_free_cb(eh, valfreefp); + eh->nbuckets = _ehash_hashsizes[0]; /* eh->cursize */ eh->nentries = 0; + eh->cursize = 0; + + if (nentries_reserve) { + edgehash_buckets_reserve(eh, nentries_reserve); + } + + MEM_freeN(eh->buckets); + eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets"); + + BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1); } void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) { - BLI_edgehash_clear(eh, valfreefp); + BLI_assert((int)eh->nentries == BLI_mempool_count(eh->epool)); + + if (valfreefp) + edgehash_free_cb(eh, valfreefp); BLI_mempool_destroy(eh->epool); @@ -437,6 +462,8 @@ bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) /* Use edgehash API to give 'set' functionality */ +/** \name EdgeSet Functions + * \{ */ EdgeSet *BLI_edgeset_new_ex(const char *info, const unsigned int nentries_reserve) { @@ -498,3 +525,5 @@ void BLI_edgeset_free(EdgeSet *es) { BLI_edgehash_free((EdgeHash *)es, NULL); } + +/** \} */ |