diff options
| -rw-r--r-- | source/blender/blenlib/BLI_edgehash.h | 3 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_heap.h | 1 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_heap.c | 19 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 92 |
4 files changed, 111 insertions, 4 deletions
diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index a0455489d24..c5323a4cf12 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -55,6 +55,9 @@ bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned in void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; void *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val_default) ATTR_WARN_UNUSED_RESULT; void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; +bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp); + +void *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; int BLI_edgehash_size(EdgeHash *eh) ATTR_WARN_UNUSED_RESULT; void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp, diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h index ac9edfd46a2..ea361097b7b 100644 --- a/source/blender/blenlib/BLI_heap.h +++ b/source/blender/blenlib/BLI_heap.h @@ -37,6 +37,7 @@ typedef void (*HeapFreeFP)(void *ptr); * are recycled, so memory usage will not shrink. */ Heap *BLI_heap_new_ex(unsigned int tot_reserve) ATTR_WARN_UNUSED_RESULT; Heap *BLI_heap_new(void) ATTR_WARN_UNUSED_RESULT; +void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1); void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1); /* Insert heap node with a value (often a 'cost') and pointer into the heap, diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index 05bd1074bf0..66dfa87b7b9 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -138,9 +138,9 @@ Heap *BLI_heap_new(void) void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) { - unsigned int i; - if (ptrfreefp) { + unsigned int i; + for (i = 0; i < heap->size; i++) { ptrfreefp(heap->tree[i]->ptr); } @@ -151,6 +151,21 @@ void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) MEM_freeN(heap); } +void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) +{ + if (ptrfreefp) { + unsigned int i; + + for (i = 0; i < heap->size; i++) { + ptrfreefp(heap->tree[i]->ptr); + } + } + + heap->size = 0; + BLI_memarena_clear(heap->arena); + heap->freenodes = NULL; +} + HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) { HeapNode *node; diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 4ed82f8a473..385d9ecb1ec 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -146,7 +146,7 @@ BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const unsigned int nentri /** * Internal lookup function. - * Takes a hash argument to avoid calling #ghash_keyhash multiple times. + * Takes a hash argument to avoid calling #edgehash_keyhash multiple times. */ BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, const unsigned int hash) @@ -256,6 +256,35 @@ BLI_INLINE void edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, } /** + * Remove the entry and return it, caller must free from eh->epool. + */ +static EdgeEntry *edgehash_remove_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp, + unsigned int hash) +{ + EdgeEntry *e; + EdgeEntry *e_prev = NULL; + + BLI_assert(v0 < v1); + + for (e = eh->buckets[hash]; e; e = e->next) { + if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) { + EdgeEntry *e_next = e->next; + + if (valfreefp) valfreefp(e->val); + + if (e_prev) e_prev->next = e_next; + else eh->buckets[hash] = e_next; + + eh->nentries--; + return e; + } + e_prev = e; + } + + return NULL; +} + +/** * Run free callbacks for freeing entries. */ static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp) @@ -366,6 +395,57 @@ void *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1 } /** + * Remove \a key from \a eh, or return false if the key wasn't found. + * + * \param key The key to remove. + * \param valfreefp Optional callback to free the value. + * \return true if \a key was removed from \a eh. + */ +bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp) +{ + unsigned int hash; + EdgeEntry *e; + + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); + e = edgehash_remove_ex(eh, v0, v1, valfreefp, hash); + if (e) { + BLI_mempool_free(eh->epool, e); + return true; + } + else { + return false; + } +} + +/* same as above but return the value, + * no free value argument since it will be returned */ +/** + * Remove \a key from \a eh, returning the value or NULL if the key wasn't found. + * + * \param key The key to remove. + * \return the value of \a key int \a eh or NULL. + */ +void *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1) +{ + unsigned int hash; + EdgeEntry *e; + + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); + e = edgehash_remove_ex(eh, v0, v1, NULL, hash); + IS_EDGEHASH_ASSERT(eh); + if (e) { + void *val = e->val; + BLI_mempool_free(eh->epool, e); + return val; + } + else { + return NULL; + } +} + +/** * Return boolean true/false if edge (v0,v1) in hash. */ bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1) @@ -404,6 +484,14 @@ void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp, BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1); } +/** + * Wraps #BLI_edgehash_clear_ex with zero entries reserved. + */ +void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) +{ + BLI_edgehash_clear_ex(eh, valfreefp, 0); +} + void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) { BLI_assert((int)eh->nentries == BLI_mempool_count(eh->epool)); @@ -440,7 +528,7 @@ void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag) /** * Create a new EdgeHashIterator. The hash table must not be mutated * while the iterator is in use, and the iterator will step exactly - * BLI_edgehash_size(gh) times before becoming done. + * BLI_edgehash_size(eh) times before becoming done. */ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) { |