diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-10-29 08:33:44 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-10-29 08:33:44 +0300 |
commit | 560fa6db170261be0010b2be769bc8591e0a7f7e (patch) | |
tree | 49deb6deac49e7b5f41e0a020cb4d150c688acd1 /extern/curve_fit_nd/intern/generic_heap.c | |
parent | bd0d41059f7fd6082e94d2fc43f189be246fc72f (diff) |
Curve Fitting: heap reinsertion optimization
Diffstat (limited to 'extern/curve_fit_nd/intern/generic_heap.c')
-rw-r--r-- | extern/curve_fit_nd/intern/generic_heap.c | 81 |
1 files changed, 55 insertions, 26 deletions
diff --git a/extern/curve_fit_nd/intern/generic_heap.c b/extern/curve_fit_nd/intern/generic_heap.c index 1e2efa5b43d..f41025318c4 100644 --- a/extern/curve_fit_nd/intern/generic_heap.c +++ b/extern/curve_fit_nd/intern/generic_heap.c @@ -48,13 +48,14 @@ # define UNLIKELY(x) (x) #endif +typedef unsigned int uint; /***/ struct HeapNode { - void *ptr; - double value; - unsigned int index; + void *ptr; + double value; + uint index; }; /* heap_* pool allocator */ @@ -67,8 +68,8 @@ struct HeapNode { #undef TPOOL_STRUCT struct Heap { - unsigned int size; - unsigned int bufsize; + uint size; + uint bufsize; HeapNode **tree; struct HeapMemPool pool; @@ -86,32 +87,32 @@ struct Heap { #define HEAP_EQUALS(a, b) ((a)->value == (b)->value) #endif -static void heap_swap(Heap *heap, const unsigned int i, const unsigned int j) +static void heap_swap(Heap *heap, const uint i, const uint j) { #if 0 - SWAP(unsigned int, heap->tree[i]->index, heap->tree[j]->index); - SWAP(HeapNode *, heap->tree[i], heap->tree[j]); + SWAP(uint, heap->tree[i]->index, heap->tree[j]->index); + SWAP(HeapNode *, heap->tree[i], heap->tree[j]); #else HeapNode **tree = heap->tree; union { - unsigned int index; - HeapNode *node; + uint index; + HeapNode *node; } tmp; SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index); SWAP_TVAL(tmp.node, tree[i], tree[j]); #endif } -static void heap_down(Heap *heap, unsigned int i) +static void heap_down(Heap *heap, uint i) { /* size won't change in the loop */ - const unsigned int size = heap->size; + const uint size = heap->size; while (1) { - const unsigned int l = HEAP_LEFT(i); - const unsigned int r = HEAP_RIGHT(i); - unsigned int smallest; + 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; @@ -128,10 +129,10 @@ static void heap_down(Heap *heap, unsigned int i) } } -static void heap_up(Heap *heap, unsigned int i) +static void heap_up(Heap *heap, uint i) { while (i > 0) { - const unsigned int p = HEAP_PARENT(i); + const uint p = HEAP_PARENT(i); if (HEAP_COMPARE(heap->tree[p], heap->tree[i])) { break; @@ -148,7 +149,7 @@ static void heap_up(Heap *heap, unsigned int i) * \{ */ /* use when the size of the heap is known in advance */ -Heap *HEAP_new(unsigned int tot_reserve) +Heap *HEAP_new(uint tot_reserve) { Heap *heap = malloc(sizeof(Heap)); /* ensure we have at least one so we can keep doubling it */ @@ -164,7 +165,7 @@ Heap *HEAP_new(unsigned int tot_reserve) void HEAP_free(Heap *heap, HeapFreeFP ptrfreefp) { if (ptrfreefp) { - unsigned int i; + uint i; for (i = 0; i < heap->size; i++) { ptrfreefp(heap->tree[i]->ptr); @@ -180,7 +181,7 @@ void HEAP_free(Heap *heap, HeapFreeFP ptrfreefp) void HEAP_clear(Heap *heap, HeapFreeFP ptrfreefp) { if (ptrfreefp) { - unsigned int i; + uint i; for (i = 0; i < heap->size; i++) { ptrfreefp(heap->tree[i]->ptr); @@ -215,12 +216,22 @@ HeapNode *HEAP_insert(Heap *heap, double value, void *ptr) return node; } -bool HEAP_is_empty(Heap *heap) +void HEAP_insert_or_update(Heap *heap, HeapNode **node_p, double value, void *ptr) +{ + if (*node_p == NULL) { + *node_p = HEAP_insert(heap, value, ptr); + } + else { + HEAP_node_value_update_ptr(heap, *node_p, value, ptr); + } +} + +bool HEAP_is_empty(const Heap *heap) { return (heap->size == 0); } -unsigned int HEAP_size(Heap *heap) +uint HEAP_size(const Heap *heap) { return heap->size; } @@ -230,7 +241,7 @@ HeapNode *HEAP_top(Heap *heap) return heap->tree[0]; } -double HEAP_top_value(Heap *heap) +double HEAP_top_value(const Heap *heap) { return heap->tree[0]->value; } @@ -253,12 +264,12 @@ void *HEAP_popmin(Heap *heap) void HEAP_remove(Heap *heap, HeapNode *node) { - unsigned int i = node->index; + uint i = node->index; assert(heap->size != 0); while (i > 0) { - unsigned int p = HEAP_PARENT(i); + uint p = HEAP_PARENT(i); heap_swap(heap, p, i); i = p; @@ -267,7 +278,25 @@ void HEAP_remove(Heap *heap, HeapNode *node) HEAP_popmin(heap); } -double HEAP_node_value(HeapNode *node) +void HEAP_node_value_update(Heap *heap, HeapNode *node, double value) +{ + assert(heap->size != 0); + if (node->value == 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 HEAP_node_value_update_ptr(Heap *heap, HeapNode *node, double value, void *ptr) +{ + node->ptr = ptr; + HEAP_node_value_update(heap, node, value); +} + +double HEAP_node_value(const HeapNode *node) { return node->value; } |