diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-10-29 07:25:13 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-10-29 07:47:06 +0300 |
commit | 34257329263c3af108736b8d1047d48091e82d92 (patch) | |
tree | 29307361dce6c7bfced0b7b0887278df3c00b568 /source | |
parent | 336885bebaa8c7b60041b139f02a29da475cf3ea (diff) |
BLI_heap: minor changes to the API
Recent addition of 'reinsert' didn't match logic for ghash API.
Rename to BLI_heap_node_value_update,
also add BLI_heap_insert_or_update since it's a common operation.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/BLI_heap.h | 10 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_heap.c | 46 | ||||
-rw-r--r-- | source/blender/blenlib/intern/polyfill2d_beautify.c | 7 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_decimate_collapse.c | 7 |
4 files changed, 45 insertions, 25 deletions
diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h index cf18dfa5d2e..f7c1fd26985 100644 --- a/source/blender/blenlib/BLI_heap.h +++ b/source/blender/blenlib/BLI_heap.h @@ -44,12 +44,12 @@ void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1); * duplicate values are allowed. */ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1); +/* Insert or update */ +void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1, 2); + /* Remove a heap node. */ void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1, 2); -/* Set new value for existing node. */ -void BLI_heap_reinsert(Heap *heap, HeapNode *node, float value); - /* Return 0 if the heap is empty, 1 otherwise. */ bool BLI_heap_is_empty(Heap *heap) ATTR_NONNULL(1); @@ -62,6 +62,10 @@ HeapNode *BLI_heap_top(Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) /* Pop the top node off the heap and return it's pointer. */ void *BLI_heap_popmin(Heap *heap) ATTR_NONNULL(1); +/* Update the priority in the heap (may be slow but generally faster than remove/insert). */ +void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1, 2); +void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr) ATTR_NONNULL(1, 2); + /* Return the value or pointer of a heap node. */ float BLI_heap_node_value(HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); void *BLI_heap_node_ptr(HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index d794332b5df..d6e8721faa7 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -275,6 +275,20 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) return node; } +/** + * Convenience function since this is a common pattern. + */ +void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) +{ + if (*node_p == NULL) { + *node_p = BLI_heap_insert(heap, value, ptr); + } + else { + BLI_heap_node_value_update_ptr(heap, *node_p, value, ptr); + } +} + + bool BLI_heap_is_empty(Heap *heap) { return (heap->size == 0); @@ -306,16 +320,6 @@ void *BLI_heap_popmin(Heap *heap) return ptr; } -void BLI_heap_reinsert(Heap *heap, HeapNode *node, float value) -{ - if (value == node->value) { - return; - } - node->value = value; - heap_up(heap, node->index); - heap_down(heap, node->index); -} - void BLI_heap_remove(Heap *heap, HeapNode *node) { uint i = node->index; @@ -332,6 +336,28 @@ void BLI_heap_remove(Heap *heap, HeapNode *node) BLI_heap_popmin(heap); } +/** + * Can be used to avoid #BLI_heap_remove, #BLI_heap_insert calls, + * balancing the tree still has a performance cost, + * but is often much less than remove/insert, difference is most noticable with large heaps. + */ +void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) +{ + if (value == node->value) { + return; + } + node->value = value; + /* Can be called in either order, makes no difference. */ + heap_up(heap, node->index); + heap_down(heap, node->index); +} + +void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr) +{ + node->ptr = ptr; + BLI_heap_node_value_update(heap, node, value); +} + float BLI_heap_node_value(HeapNode *node) { return node->value; diff --git a/source/blender/blenlib/intern/polyfill2d_beautify.c b/source/blender/blenlib/intern/polyfill2d_beautify.c index 56309a4b115..c0c95da5c63 100644 --- a/source/blender/blenlib/intern/polyfill2d_beautify.c +++ b/source/blender/blenlib/intern/polyfill2d_beautify.c @@ -226,12 +226,7 @@ static void polyedge_beauty_cost_update_single( * Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully? * See T43578, T49478. */ if (cost < -1e-6f) { - if (eheap_table[i]) { - BLI_heap_reinsert(eheap, eheap_table[i], cost); - } - else { - eheap_table[i] = BLI_heap_insert(eheap, cost, e); - } + BLI_heap_insert_or_update(eheap, &eheap_table[i], cost, e); } else { if (eheap_table[i]) { diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c index a081a1b70e4..0a1271c2aa9 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c +++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c @@ -337,12 +337,7 @@ static void bm_decim_build_edge_cost_single( } } - if (eheap_table[BM_elem_index_get(e)]) { - BLI_heap_reinsert(eheap, eheap_table[BM_elem_index_get(e)], cost); - } - else { - eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e); - } + BLI_heap_insert_or_update(eheap, &eheap_table[BM_elem_index_get(e)], cost, e); return; clear: |