[Bf-blender-cvs] [942b6e933bb] blender-v2.79a-release: BLI_heap: minor changes to the API
Campbell Barton
noreply at git.blender.org
Wed Jan 3 12:48:32 CET 2018
Commit: 942b6e933bb4cab8eac24d2fc95dc40fc7e36dfd
Author: Campbell Barton
Date: Sun Oct 29 15:25:13 2017 +1100
Branches: blender-v2.79a-release
https://developer.blender.org/rB942b6e933bb4cab8eac24d2fc95dc40fc7e36dfd
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.
===================================================================
M source/blender/blenlib/BLI_heap.h
M source/blender/blenlib/intern/BLI_heap.c
M source/blender/blenlib/intern/polyfill2d_beautify.c
M source/blender/bmesh/tools/bmesh_decimate_collapse.c
M tests/gtests/blenlib/BLI_heap_test.cc
===================================================================
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 5e7603668a4..e8ce49ddc1a 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)
{
unsigned int 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 906283a6f7b..b9e286dbe85 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);
More information about the Bf-blender-cvs
mailing list