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.

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);