diff options
-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 | ||||
-rw-r--r-- | tests/gtests/blenlib/BLI_heap_test.cc | 4 |
5 files changed, 47 insertions, 27 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: diff --git a/tests/gtests/blenlib/BLI_heap_test.cc b/tests/gtests/blenlib/BLI_heap_test.cc index 02729e7dcfb..e23e89b9cae 100644 --- a/tests/gtests/blenlib/BLI_heap_test.cc +++ b/tests/gtests/blenlib/BLI_heap_test.cc @@ -146,7 +146,7 @@ TEST(heap, ReInsertSimple) nodes[in] = BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in)); } for (int i = 0; i < items_total; i++) { - BLI_heap_reinsert(heap, nodes[i], (float)(items_total + i)); + BLI_heap_node_value_update(heap, nodes[i], (float)(items_total + i)); } for (int out_test = 0; out_test < items_total; out_test++) { @@ -168,7 +168,7 @@ TEST(heap, ReInsertRandom) } BLI_array_randomize(nodes, sizeof(HeapNode *), items_total, 1234); for (int i = 0; i < items_total; i++) { - BLI_heap_reinsert(heap, nodes[i], (float)i); + BLI_heap_node_value_update(heap, nodes[i], (float)i); } for (int out_test = 0; out_test < items_total; out_test++) { HeapNode *node_top = BLI_heap_top(heap); |