[Bf-blender-cvs] [4af1af70ad4] master: BLI_hash: add BLI_heap_reinsert
Campbell Barton
noreply at git.blender.org
Sat Oct 28 20:23:43 CEST 2017
Commit: 4af1af70ad41015d0126837e856d87b930f61655
Author: Campbell Barton
Date: Sun Oct 29 04:42:58 2017 +1100
Branches: master
https://developer.blender.org/rB4af1af70ad41015d0126837e856d87b930f61655
BLI_hash: add BLI_heap_reinsert
Allows avoiding remove/insert calls.
===================================================================
M source/blender/blenlib/BLI_heap.h
M source/blender/blenlib/intern/BLI_heap.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 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 6b3d797a485..d794332b5df 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)
{
uint 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);
+}
More information about the Bf-blender-cvs
mailing list