diff options
author | Campbell Barton <ideasman42@gmail.com> | 2018-11-06 05:01:18 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2018-11-06 05:06:49 +0300 |
commit | 900c562b71b6efcf68d649cb639cc8bc246d5899 (patch) | |
tree | 2081430f831481789bea1a48ac4f39113ee829b2 /source/blender/blenlib | |
parent | d805a4a5efd53de234302d22fc0917db53b50e2b (diff) |
Cleanup: rename fast-heap -> heap-simple
In general prefer API names don't start with adjectives
since it causes grouping of unrelated API's for completion.
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_heap_simple.h | 23 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_heap_simple.c | 58 | ||||
-rw-r--r-- | source/blender/blenlib/intern/astar.c | 26 |
3 files changed, 55 insertions, 52 deletions
diff --git a/source/blender/blenlib/BLI_heap_simple.h b/source/blender/blenlib/BLI_heap_simple.h index 077c8cc1bb9..eed33558d84 100644 --- a/source/blender/blenlib/BLI_heap_simple.h +++ b/source/blender/blenlib/BLI_heap_simple.h @@ -26,20 +26,19 @@ * \brief A min-heap / priority queue ADT */ - -struct FastHeap; -typedef struct FastHeap FastHeap; +struct HeapSimple; +typedef struct HeapSimple HeapSimple; typedef void (*HeapSimpleFreeFP)(void *ptr); -FastHeap *BLI_fastheap_new_ex(unsigned int tot_reserve) ATTR_WARN_UNUSED_RESULT; -FastHeap *BLI_fastheap_new(void) ATTR_WARN_UNUSED_RESULT; -void BLI_fastheap_clear(FastHeap *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1); -void BLI_fastheap_free(FastHeap *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1); -void BLI_fastheap_insert(FastHeap *heap, float value, void *ptr) ATTR_NONNULL(1); -bool BLI_fastheap_is_empty(const FastHeap *heap) ATTR_NONNULL(1); -uint BLI_fastheap_len(const FastHeap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); -float BLI_fastheap_top_value(const FastHeap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); -void *BLI_fastheap_pop_min(FastHeap *heap) ATTR_NONNULL(1); +HeapSimple *BLI_heapsimple_new_ex(unsigned int tot_reserve) ATTR_WARN_UNUSED_RESULT; +HeapSimple *BLI_heapsimple_new(void) ATTR_WARN_UNUSED_RESULT; +void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1); +void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1); +void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1); +bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1); +uint BLI_heapsimple_len(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +float BLI_heapsimple_top_value(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +void *BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1); #endif /* __BLI_HEAP_SIMPLE_H__ */ diff --git a/source/blender/blenlib/intern/BLI_heap_simple.c b/source/blender/blenlib/intern/BLI_heap_simple.c index 66766489781..777b9c61b28 100644 --- a/source/blender/blenlib/intern/BLI_heap_simple.c +++ b/source/blender/blenlib/intern/BLI_heap_simple.c @@ -24,6 +24,8 @@ * A min-heap / priority queue ADT. * * Simplified version of the heap that only supports insertion and removal from top. + * + * See BLI_heap.c for a more full featured heap implementation. */ #include <stdlib.h> @@ -38,37 +40,37 @@ #define HEAP_PARENT(i) (((i) - 1) >> 1) /* -------------------------------------------------------------------- */ -/** \name FastHeap Internal Structs +/** \name HeapSimple Internal Structs * \{ */ -typedef struct FastHeapNode { +typedef struct HeapSimpleNode { float value; void *ptr; -} FastHeapNode; +} HeapSimpleNode; -struct FastHeap { +struct HeapSimple { uint size; uint bufsize; - FastHeapNode *tree; + HeapSimpleNode *tree; }; /** \} */ /* -------------------------------------------------------------------- */ -/** \name FastHeap Internal Functions +/** \name HeapSimple Internal Functions * \{ */ -static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *init) +static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode *init) { #if 1 /* The compiler isn't smart enough to realize that all computations * using index here can be modified to work with byte offset. */ uint8_t * const tree_buf = (uint8_t *)heap->tree; -#define OFFSET(i) (i * (uint)sizeof(FastHeapNode)) -#define NODE(offset) (*(FastHeapNode*)(tree_buf + (offset))) +#define OFFSET(i) (i * (uint)sizeof(HeapSimpleNode)) +#define NODE(offset) (*(HeapSimpleNode*)(tree_buf + (offset))) #else - FastHeapNode *const tree = heap->tree; + HeapSimpleNode *const tree = heap->tree; #define OFFSET(i) (i) #define NODE(i) tree[i] @@ -124,9 +126,9 @@ static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *init #undef HEAP_LEFT_OFFSET } -static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_ptr) +static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *active_ptr) { - FastHeapNode *const tree = heap->tree; + HeapSimpleNode *const tree = heap->tree; while (LIKELY(i > 0)) { const uint p = HEAP_PARENT(i); @@ -146,30 +148,30 @@ static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_p /** \} */ /* -------------------------------------------------------------------- */ -/** \name Public FastHeap API +/** \name Public HeapSimple API * \{ */ /** - * Creates a new fast heap, which only supports insertion and removal from top. + * Creates a new simple heap, which only supports insertion and removal from top. * * \note Use when the size of the heap is known in advance. */ -FastHeap *BLI_fastheap_new_ex(uint tot_reserve) +HeapSimple *BLI_heapsimple_new_ex(uint tot_reserve) { - FastHeap *heap = MEM_mallocN(sizeof(FastHeap), __func__); + HeapSimple *heap = MEM_mallocN(sizeof(HeapSimple), __func__); /* ensure we have at least one so we can keep doubling it */ heap->size = 0; heap->bufsize = MAX2(1u, tot_reserve); - heap->tree = MEM_mallocN(heap->bufsize * sizeof(FastHeapNode), "BLIFastHeapTree"); + heap->tree = MEM_mallocN(heap->bufsize * sizeof(HeapSimpleNode), "BLIHeapSimpleTree"); return heap; } -FastHeap *BLI_fastheap_new(void) +HeapSimple *BLI_heapsimple_new(void) { - return BLI_fastheap_new_ex(1); + return BLI_heapsimple_new_ex(1); } -void BLI_fastheap_free(FastHeap *heap, HeapSimpleFreeFP ptrfreefp) +void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) { if (ptrfreefp) { for (uint i = 0; i < heap->size; i++) { @@ -181,7 +183,7 @@ void BLI_fastheap_free(FastHeap *heap, HeapSimpleFreeFP ptrfreefp) MEM_freeN(heap); } -void BLI_fastheap_clear(FastHeap *heap, HeapSimpleFreeFP ptrfreefp) +void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) { if (ptrfreefp) { for (uint i = 0; i < heap->size; i++) { @@ -196,22 +198,22 @@ void BLI_fastheap_clear(FastHeap *heap, HeapSimpleFreeFP ptrfreefp) * Insert heap node with a value (often a 'cost') and pointer into the heap, * duplicate values are allowed. */ -void BLI_fastheap_insert(FastHeap *heap, float value, void *ptr) +void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) { if (UNLIKELY(heap->size >= heap->bufsize)) { heap->bufsize *= 2; heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree)); } - fastheap_up(heap, heap->size++, value, ptr); + heapsimple_up(heap, heap->size++, value, ptr); } -bool BLI_fastheap_is_empty(const FastHeap *heap) +bool BLI_heapsimple_is_empty(const HeapSimple *heap) { return (heap->size == 0); } -uint BLI_fastheap_len(const FastHeap *heap) +uint BLI_heapsimple_len(const HeapSimple *heap) { return heap->size; } @@ -219,7 +221,7 @@ uint BLI_fastheap_len(const FastHeap *heap) /** * Return the lowest value of the heap. */ -float BLI_fastheap_top_value(const FastHeap *heap) +float BLI_heapsimple_top_value(const HeapSimple *heap) { BLI_assert(heap->size != 0); @@ -229,14 +231,14 @@ float BLI_fastheap_top_value(const FastHeap *heap) /** * Pop the top node off the heap and return it's pointer. */ -void *BLI_fastheap_pop_min(FastHeap *heap) +void *BLI_heapsimple_pop_min(HeapSimple *heap) { BLI_assert(heap->size != 0); void *ptr = heap->tree[0].ptr; if (--heap->size) { - fastheap_down(heap, 0, &heap->tree[heap->size]); + heapsimple_down(heap, 0, &heap->tree[heap->size]); } return ptr; diff --git a/source/blender/blenlib/intern/astar.c b/source/blender/blenlib/intern/astar.c index 959d1a46ac5..30ad6c7838c 100644 --- a/source/blender/blenlib/intern/astar.c +++ b/source/blender/blenlib/intern/astar.c @@ -206,7 +206,7 @@ bool BLI_astar_graph_solve( BLI_AStarGraph *as_graph, const int node_index_src, const int node_index_dst, astar_f_cost f_cost_cb, BLI_AStarSolution *r_solution, const int max_steps) { - FastHeap *todo_nodes; + HeapSimple *todo_nodes; BLI_bitmap *done_nodes = r_solution->done_nodes; int *prev_nodes = r_solution->prev_nodes; @@ -225,13 +225,14 @@ bool BLI_astar_graph_solve( return true; } - todo_nodes = BLI_fastheap_new(); - BLI_fastheap_insert(todo_nodes, - f_cost_cb(as_graph, r_solution, NULL, -1, node_index_src, node_index_dst), - POINTER_FROM_INT(node_index_src)); + todo_nodes = BLI_heapsimple_new(); + BLI_heapsimple_insert( + todo_nodes, + f_cost_cb(as_graph, r_solution, NULL, -1, node_index_src, node_index_dst), + POINTER_FROM_INT(node_index_src)); - while (!BLI_fastheap_is_empty(todo_nodes)) { - const int node_curr_idx = POINTER_AS_INT(BLI_fastheap_pop_min(todo_nodes)); + while (!BLI_heapsimple_is_empty(todo_nodes)) { + const int node_curr_idx = POINTER_AS_INT(BLI_heapsimple_pop_min(todo_nodes)); BLI_AStarGNode *node_curr = &as_graph->nodes[node_curr_idx]; LinkData *ld; @@ -249,7 +250,7 @@ bool BLI_astar_graph_solve( /* Success! Path found... */ r_solution->steps = g_steps[node_curr_idx] + 1; - BLI_fastheap_free(todo_nodes, NULL); + BLI_heapsimple_free(todo_nodes, NULL); return true; } @@ -269,14 +270,15 @@ bool BLI_astar_graph_solve( g_steps[node_next_idx] = g_steps[node_curr_idx] + 1; /* We might have this node already in heap, but since this 'instance' will be evaluated first, * no problem. */ - BLI_fastheap_insert(todo_nodes, - f_cost_cb(as_graph, r_solution, link, node_curr_idx, node_next_idx, node_index_dst), - POINTER_FROM_INT(node_next_idx)); + BLI_heapsimple_insert( + todo_nodes, + f_cost_cb(as_graph, r_solution, link, node_curr_idx, node_next_idx, node_index_dst), + POINTER_FROM_INT(node_next_idx)); } } } } - BLI_fastheap_free(todo_nodes, NULL); + BLI_heapsimple_free(todo_nodes, NULL); return false; } |