From 34257329263c3af108736b8d1047d48091e82d92 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 29 Oct 2017 15:25:13 +1100 Subject: BLI_heap: minor changes to the API Recent addition of 'reinsert' didn't match logic for ghash API. Rename to BLI_heap_node_value_update, also add BLI_heap_insert_or_update since it's a common operation. --- source/blender/blenlib/intern/BLI_heap.c | 46 +++++++++++++++++++++++++------- 1 file changed, 36 insertions(+), 10 deletions(-) (limited to 'source/blender/blenlib/intern/BLI_heap.c') diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index d794332b5df..d6e8721faa7 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -275,6 +275,20 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) return node; } +/** + * Convenience function since this is a common pattern. + */ +void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) +{ + if (*node_p == NULL) { + *node_p = BLI_heap_insert(heap, value, ptr); + } + else { + BLI_heap_node_value_update_ptr(heap, *node_p, value, ptr); + } +} + + bool BLI_heap_is_empty(Heap *heap) { return (heap->size == 0); @@ -306,16 +320,6 @@ 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; @@ -332,6 +336,28 @@ void BLI_heap_remove(Heap *heap, HeapNode *node) BLI_heap_popmin(heap); } +/** + * Can be used to avoid #BLI_heap_remove, #BLI_heap_insert calls, + * balancing the tree still has a performance cost, + * but is often much less than remove/insert, difference is most noticable with large heaps. + */ +void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) +{ + if (value == node->value) { + return; + } + 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); +} + float BLI_heap_node_value(HeapNode *node) { return node->value; -- cgit v1.2.3