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 /source/blender/blenlib/intern/BLI_heap.c | |
parent | 560fa6db170261be0010b2be769bc8591e0a7f7e (diff) |
BLI_heap: add validation check, improve tests
Also minor readability changes, avoid running both heap_up/down
gives minor speedup too.
Diffstat (limited to 'source/blender/blenlib/intern/BLI_heap.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_heap.c | 67 |
1 files changed, 51 insertions, 16 deletions
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); +} + /** \} */ + |