BLI_heap: minor changes to the API
authorCampbell Barton <ideasman42@gmail.com>
Sun, 29 Oct 2017 04:25:13 +0000 (15:25 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Sun, 29 Oct 2017 04:47:06 +0000 (15:47 +1100)
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.

source/blender/blenlib/BLI_heap.h
source/blender/blenlib/intern/BLI_heap.c
source/blender/blenlib/intern/polyfill2d_beautify.c
source/blender/bmesh/tools/bmesh_decimate_collapse.c
tests/gtests/blenlib/BLI_heap_test.cc

index cf18dfa5d2e3e11e1d915c22c071051e29c65b80..f7c1fd269859913a1cf348331538af630dff7253 100644 (file)
@@ -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);
index d794332b5df4251c1aed5cf9a829c944b4fb987a..d6e8721faa7fa07926d1503a5c6ba5e540410e06 100644 (file)
@@ -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;
index 56309a4b1157255ea70d19e4933a64ec7dd9010a..c0c95da5c6395a36892adffc541e9057168c6639 100644 (file)
@@ -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]) {
index a081a1b70e4b478017107bed523e5b1eb3999f94..0a1271c2aa9e1f69f9f3071e15b231173cf90a0b 100644 (file)
@@ -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:
index 02729e7dcfb40f603e784b742634e02d39ea36d3..e23e89b9cae52dfbffc9f5a57589d0fd41fc8772 100644 (file)
@@ -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);