BLI_hash: add BLI_heap_reinsert
authorCampbell Barton <ideasman42@gmail.com>
Sat, 28 Oct 2017 17:42:58 +0000 (04:42 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Sat, 28 Oct 2017 17:42:58 +0000 (04:42 +1100)
Allows avoiding remove/insert calls.

source/blender/blenlib/BLI_heap.h
source/blender/blenlib/intern/BLI_heap.c
tests/gtests/blenlib/BLI_heap_test.cc

index ea361097b7b13f56dbf6737bf56aeb166709806a..cf18dfa5d2e3e11e1d915c22c071051e29c65b80 100644 (file)
@@ -47,6 +47,9 @@ HeapNode       *BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL
 /* 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);
 
index 6b3d797a485748f6684dcfb224d58c28cbbcbd94..d794332b5df4251c1aed5cf9a829c944b4fb987a 100644 (file)
@@ -306,6 +306,16 @@ 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;
index 80a2b6a99c769b26bc698c37d4d1836932078183..02729e7dcfb40f603e784b742634e02d39ea36d3 100644 (file)
@@ -135,3 +135,48 @@ static void random_heap_helper(
 TEST(heap, Rand1)       { random_heap_helper(1, 1234); }
 TEST(heap, Rand2)       { random_heap_helper(2, 1234); }
 TEST(heap, Rand100)     { random_heap_helper(100, 4321); }
+
+
+TEST(heap, ReInsertSimple)
+{
+       const int items_total = SIZE;
+       Heap *heap = BLI_heap_new();
+       HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
+       for (int in = 0; in < items_total; in++) {
+               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));
+       }
+
+       for (int out_test = 0; out_test < items_total; out_test++) {
+               EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap)));
+       }
+
+       EXPECT_TRUE(BLI_heap_is_empty(heap));
+       BLI_heap_free(heap, NULL);
+       MEM_freeN(nodes);
+}
+
+TEST(heap, ReInsertRandom)
+{
+       const int items_total = SIZE;
+       Heap *heap = BLI_heap_new();
+       HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
+       for (int in = 0; in < items_total; in++) {
+               nodes[in] = BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in));
+       }
+       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);
+       }
+       for (int out_test = 0; out_test < items_total; out_test++) {
+               HeapNode *node_top = BLI_heap_top(heap);
+               float out = BLI_heap_node_value(node_top);
+               EXPECT_EQ((float)out_test, out);
+               BLI_heap_popmin(heap);
+       }
+       EXPECT_TRUE(BLI_heap_is_empty(heap));
+       BLI_heap_free(heap, NULL);
+       MEM_freeN(nodes);
+}