diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-10-28 20:42:58 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2018-01-03 14:49:51 +0300 |
commit | 71d79e6ea292a63d85321f46552a10dd673f72aa (patch) | |
tree | 730695acb99db26795182e1afecc6950591d00ee | |
parent | a68cc528dd2358b4730692a5ce054f81d847db5e (diff) |
BLI_hash: add BLI_heap_reinsert
Allows avoiding remove/insert calls.
-rw-r--r-- | source/blender/blenlib/BLI_heap.h | 3 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_heap.c | 10 | ||||
-rw-r--r-- | tests/gtests/blenlib/BLI_heap_test.cc | 45 |
3 files changed, 58 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h index ea361097b7b..cf18dfa5d2e 100644 --- a/source/blender/blenlib/BLI_heap.h +++ b/source/blender/blenlib/BLI_heap.h @@ -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); diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index d7fd1caa8da..5e7603668a4 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -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) { unsigned int i = node->index; diff --git a/tests/gtests/blenlib/BLI_heap_test.cc b/tests/gtests/blenlib/BLI_heap_test.cc index 80a2b6a99c7..02729e7dcfb 100644 --- a/tests/gtests/blenlib/BLI_heap_test.cc +++ b/tests/gtests/blenlib/BLI_heap_test.cc @@ -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); +} |