From 4af1af70ad41015d0126837e856d87b930f61655 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 29 Oct 2017 04:42:58 +1100 Subject: BLI_hash: add BLI_heap_reinsert Allows avoiding remove/insert calls. --- tests/gtests/blenlib/BLI_heap_test.cc | 45 +++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) (limited to 'tests/gtests') 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); +} -- cgit v1.2.3