diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-10-29 10:23:33 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-10-29 10:23:33 +0300 |
commit | 512b879241d79bf91f70eecdc97944505d64bf6e (patch) | |
tree | c3f8619435940642fcced1e9bf5463cc23dfb494 | |
parent | 560fa6db170261be0010b2be769bc8591e0a7f7e (diff) |
BLI_heap: add validation check, improve tests
Also minor readability changes, avoid running both heap_up/down
gives minor speedup too.
-rw-r--r-- | source/blender/blenlib/BLI_heap.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_heap.c | 67 | ||||
-rw-r--r-- | tests/gtests/blenlib/BLI_heap_test.cc | 15 |
3 files changed, 65 insertions, 19 deletions
diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h index dcdbf53c0bb..d3f6d44e164 100644 --- a/source/blender/blenlib/BLI_heap.h +++ b/source/blender/blenlib/BLI_heap.h @@ -50,5 +50,7 @@ void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float /* Return the value or pointer of a heap node. */ float BLI_heap_node_value(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); void *BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +/* only for gtest */ +bool BLI_heap_is_valid(const Heap *heap); #endif /* __BLI_HEAP_H__ */ diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index 4643b98f520..7c249344541 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -110,10 +110,11 @@ static void heap_down(Heap *heap, uint i) while (1) { const uint l = HEAP_LEFT(i); const uint r = HEAP_RIGHT(i); - uint smallest; - - smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i; + uint smallest = i; + if ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[smallest])) { + smallest = l; + } if ((r < size) && HEAP_COMPARE(heap->tree[r], heap->tree[smallest])) { smallest = r; } @@ -321,10 +322,10 @@ HeapNode *BLI_heap_top(const Heap *heap) */ void *BLI_heap_popmin(Heap *heap) { - void *ptr = heap->tree[0]->ptr; - BLI_assert(heap->size != 0); + void *ptr = heap->tree[0]->ptr; + heap_node_free(heap, heap->tree[0]); if (--heap->size) { @@ -337,13 +338,12 @@ void *BLI_heap_popmin(Heap *heap) void BLI_heap_remove(Heap *heap, HeapNode *node) { - uint i = node->index; - BLI_assert(heap->size != 0); + uint i = node->index; + while (i > 0) { uint p = HEAP_PARENT(i); - heap_swap(heap, p, i); i = p; } @@ -358,19 +358,27 @@ void BLI_heap_remove(Heap *heap, HeapNode *node) */ void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) { - if (value == node->value) { - return; + if (value < node->value) { + node->value = value; + heap_up(heap, node->index); + } + else if (value > node->value) { + node->value = value; + heap_down(heap, node->index); } - 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); + node->ptr = ptr; /* only difference */ + if (value < node->value) { + node->value = value; + heap_up(heap, node->index); + } + else if (value > node->value) { + node->value = value; + heap_down(heap, node->index); + } } float BLI_heap_node_value(const HeapNode *node) @@ -383,4 +391,31 @@ void *BLI_heap_node_ptr(const HeapNode *node) return node->ptr; } +static bool heap_is_minheap(const Heap *heap, uint root) +{ + if (root < heap->size) { + const uint l = HEAP_LEFT(root); + if (l < heap->size) { + if (HEAP_COMPARE(heap->tree[l], heap->tree[root]) || !heap_is_minheap(heap, l)) { + return false; + } + } + const uint r = HEAP_RIGHT(root); + if (r < heap->size) { + if (HEAP_COMPARE(heap->tree[r], heap->tree[root]) || !heap_is_minheap(heap, r)) { + return false; + } + } + } + return true; +} +/** + * Only for checking internal errors (gtest). + */ +bool BLI_heap_is_valid(const Heap *heap) +{ + return heap_is_minheap(heap, 0); +} + /** \} */ + diff --git a/tests/gtests/blenlib/BLI_heap_test.cc b/tests/gtests/blenlib/BLI_heap_test.cc index e23e89b9cae..89e271d5167 100644 --- a/tests/gtests/blenlib/BLI_heap_test.cc +++ b/tests/gtests/blenlib/BLI_heap_test.cc @@ -158,18 +158,21 @@ TEST(heap, ReInsertSimple) MEM_freeN(nodes); } -TEST(heap, ReInsertRandom) +static void random_heap_reinsert_helper( + const int items_total, + const int random_seed) { - 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); + BLI_array_randomize(nodes, sizeof(HeapNode *), items_total, random_seed); for (int i = 0; i < items_total; i++) { BLI_heap_node_value_update(heap, nodes[i], (float)i); } + EXPECT_TRUE(BLI_heap_is_valid(heap)); + 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); @@ -180,3 +183,9 @@ TEST(heap, ReInsertRandom) BLI_heap_free(heap, NULL); MEM_freeN(nodes); } + +TEST(heap, ReInsertRandom1) { random_heap_reinsert_helper(1, 1234); } +TEST(heap, ReInsertRandom2) { random_heap_reinsert_helper(2, 1234); } +TEST(heap, ReInsertRandom100) { random_heap_reinsert_helper(100, 4321); } +TEST(heap, ReInsertRandom1024) { random_heap_reinsert_helper(1024, 9876); } +TEST(heap, ReInsertRandom2048) { random_heap_reinsert_helper(2048, 5321); } |