BLI_heap: implement a limited but faster version of heap.

If the user only needs insertion and removal from top, there is
no need to allocate and manage separate HeapNode objects: the
data can be stored directly in the main tree array.

This measured a 24% FPS increase on a ~50% heap-heavy workload.

Reviewers: brecht

Differential Revision: https://developer.blender.org/D3898

1 files changed, 11 insertions, 11 deletions

diff --git a/source/blender/bmesh/operators/bmo_connect_pair.c b/source/blender/bmesh/operators/bmo_connect_pair.c
index b9e5cd927c3..3b3766b6f3a 100644
--- a/source/blender/bmesh/operators/bmo_connect_pair.c
+++ b/source/blender/bmesh/operators/bmo_connect_pair.c
@@ -94,7 +94,7 @@
 // #define DEBUG_PRINT
 
 typedef struct PathContext {
-	Heap *states;
+	FastHeap *states;
 	float matrix[3][3];
 	float axis_sep;
 
@@ -331,7 +331,7 @@ static PathLinkState *state_link_add_test(
 
 	/* after adding a link so we use the updated 'state->dist' */
 	if (is_new) {
-		BLI_heap_insert(pc->states, state->dist, state);
+		BLI_fastheap_insert(pc->states, state->dist, state);
 	}
 
 	return state;
@@ -640,7 +640,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
 
 	/* setup context */
 	{
-		pc.states = BLI_heap_new();
+		pc.states = BLI_fastheap_new();
 		pc.link_pool = BLI_mempool_create(sizeof(PathLink), 0, 512, BLI_MEMPOOL_NOP);
 	}
 
@@ -655,18 +655,18 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
 		PathLinkState *state;
 		state = MEM_callocN(sizeof(*state), __func__);
 		state_link_add(&pc, state, (BMElem *)pc.v_a, NULL);
-		BLI_heap_insert(pc.states, state->dist, state);
+		BLI_fastheap_insert(pc.states, state->dist, state);
 	}
 
 
-	while (!BLI_heap_is_empty(pc.states)) {
+	while (!BLI_fastheap_is_empty(pc.states)) {
 
 #ifdef DEBUG_PRINT
-		printf("\n%s: stepping %u\n", __func__, BLI_heap_len(pc.states));
+		printf("\n%s: stepping %u\n", __func__, BLI_fastheap_len(pc.states));
 #endif
 
-		while (!BLI_heap_is_empty(pc.states)) {
-			PathLinkState *state = BLI_heap_pop_min(pc.states);
+		while (!BLI_fastheap_is_empty(pc.states)) {
+			PathLinkState *state = BLI_fastheap_pop_min(pc.states);
 
 			/* either we insert this into 'pc.states' or its freed */
 			bool continue_search;
@@ -679,7 +679,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
 				state_best = *state;
 
 				/* we're done, exit all loops */
-				BLI_heap_clear(pc.states, MEM_freeN);
+				BLI_fastheap_clear(pc.states, MEM_freeN);
 				continue_search = false;
 			}
 			else if (state_step(&pc, state)) {
@@ -696,7 +696,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
 			}
 
 			if (continue_search) {
-				BLI_heap_insert(pc.states, state->dist, state);
+				BLI_fastheap_insert(pc.states, state->dist, state);
 			}
 			else {
 				MEM_freeN(state);
@@ -732,7 +732,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
 
 	BLI_mempool_destroy(pc.link_pool);
 
-	BLI_heap_free(pc.states, MEM_freeN);
+	BLI_fastheap_free(pc.states, MEM_freeN);
 
 #if 1
 	if (state_best.link_last) {