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

2 files changed, 38 insertions, 38 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) {
diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c
index cc5ac6dd8ce..57abd2c4726 100644
--- a/source/blender/bmesh/tools/bmesh_path.c
+++ b/source/blender/bmesh/tools/bmesh_path.c
@@ -72,7 +72,7 @@ static float step_cost_3_v3(
 /* BM_mesh_calc_path_vert */
 
 static void verttag_add_adjacent(
-        Heap *heap, BMVert *v_a, BMVert **verts_prev, float *cost,
+        FastHeap *heap, BMVert *v_a, BMVert **verts_prev, float *cost,
         const struct BMCalcPathParams *params)
 {
 	const int v_a_index = BM_elem_index_get(v_a);
@@ -93,7 +93,7 @@ static void verttag_add_adjacent(
 				if (cost[v_b_index] > cost_new) {
 					cost[v_b_index] = cost_new;
 					verts_prev[v_b_index] = v_a;
-					BLI_heap_insert(heap, cost_new, v_b);
+					BLI_fastheap_insert(heap, cost_new, v_b);
 				}
 			}
 		}
@@ -119,7 +119,7 @@ static void verttag_add_adjacent(
 						if (cost[v_b_index] > cost_new) {
 							cost[v_b_index] = cost_new;
 							verts_prev[v_b_index] = v_a;
-							BLI_heap_insert(heap, cost_new, v_b);
+							BLI_fastheap_insert(heap, cost_new, v_b);
 						}
 					}
 				} while ((l_iter = l_iter->next) != l->prev);
@@ -136,7 +136,7 @@ LinkNode *BM_mesh_calc_path_vert(
 	/* BM_ELEM_TAG flag is used to store visited edges */
 	BMVert *v;
 	BMIter viter;
-	Heap *heap;
+	FastHeap *heap;
 	float *cost;
 	BMVert **verts_prev;
 	int i, totvert;
@@ -169,12 +169,12 @@ LinkNode *BM_mesh_calc_path_vert(
 	 */
 
 	/* regular dijkstra shortest path, but over faces instead of vertices */
-	heap = BLI_heap_new();
-	BLI_heap_insert(heap, 0.0f, v_src);
+	heap = BLI_fastheap_new();
+	BLI_fastheap_insert(heap, 0.0f, v_src);
 	cost[BM_elem_index_get(v_src)] = 0.0f;
 
-	while (!BLI_heap_is_empty(heap)) {
-		v = BLI_heap_pop_min(heap);
+	while (!BLI_fastheap_is_empty(heap)) {
+		v = BLI_fastheap_pop_min(heap);
 
 		if (v == v_dst)
 			break;
@@ -193,7 +193,7 @@ LinkNode *BM_mesh_calc_path_vert(
 
 	MEM_freeN(verts_prev);
 	MEM_freeN(cost);
-	BLI_heap_free(heap, NULL);
+	BLI_fastheap_free(heap, NULL);
 
 	return path;
 }
@@ -221,7 +221,7 @@ static float edgetag_cut_cost_face(BMEdge *e_a, BMEdge *e_b, BMFace *f)
 }
 
 static void edgetag_add_adjacent(
-        Heap *heap, BMEdge *e_a, BMEdge **edges_prev, float *cost,
+        FastHeap *heap, BMEdge *e_a, BMEdge **edges_prev, float *cost,
         const struct BMCalcPathParams *params)
 {
 	const int e_a_index = BM_elem_index_get(e_a);
@@ -255,7 +255,7 @@ static void edgetag_add_adjacent(
 					if (cost[e_b_index] > cost_new) {
 						cost[e_b_index] = cost_new;
 						edges_prev[e_b_index] = e_a;
-						BLI_heap_insert(heap, cost_new, e_b);
+						BLI_fastheap_insert(heap, cost_new, e_b);
 					}
 				}
 			}
@@ -291,7 +291,7 @@ static void edgetag_add_adjacent(
 					if (cost[e_b_index] > cost_new) {
 						cost[e_b_index] = cost_new;
 						edges_prev[e_b_index] = e_a;
-						BLI_heap_insert(heap, cost_new, e_b);
+						BLI_fastheap_insert(heap, cost_new, e_b);
 					}
 				}
 			} while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_end);
@@ -308,7 +308,7 @@ LinkNode *BM_mesh_calc_path_edge(
 	/* BM_ELEM_TAG flag is used to store visited edges */
 	BMEdge *e;
 	BMIter eiter;
-	Heap *heap;
+	FastHeap *heap;
 	float *cost;
 	BMEdge **edges_prev;
 	int i, totedge;
@@ -341,12 +341,12 @@ LinkNode *BM_mesh_calc_path_edge(
 	 */
 
 	/* regular dijkstra shortest path, but over edges instead of vertices */
-	heap = BLI_heap_new();
-	BLI_heap_insert(heap, 0.0f, e_src);
+	heap = BLI_fastheap_new();
+	BLI_fastheap_insert(heap, 0.0f, e_src);
 	cost[BM_elem_index_get(e_src)] = 0.0f;
 
-	while (!BLI_heap_is_empty(heap)) {
-		e = BLI_heap_pop_min(heap);
+	while (!BLI_fastheap_is_empty(heap)) {
+		e = BLI_fastheap_pop_min(heap);
 
 		if (e == e_dst)
 			break;
@@ -365,7 +365,7 @@ LinkNode *BM_mesh_calc_path_edge(
 
 	MEM_freeN(edges_prev);
 	MEM_freeN(cost);
-	BLI_heap_free(heap, NULL);
+	BLI_fastheap_free(heap, NULL);
 
 	return path;
 }
@@ -421,7 +421,7 @@ static float facetag_cut_cost_vert(BMFace *f_a, BMFace *f_b, BMVert *v, const vo
 }
 
 static void facetag_add_adjacent(
-        Heap *heap, BMFace *f_a, BMFace **faces_prev, float *cost,
+        FastHeap *heap, BMFace *f_a, BMFace **faces_prev, float *cost,
         const void * const f_endpoints[2], const struct BMCalcPathParams *params)
 {
 	const int f_a_index = BM_elem_index_get(f_a);
@@ -447,7 +447,7 @@ static void facetag_add_adjacent(
 					if (cost[f_b_index] > cost_new) {
 						cost[f_b_index] = cost_new;
 						faces_prev[f_b_index] = f_a;
-						BLI_heap_insert(heap, cost_new, f_b);
+						BLI_fastheap_insert(heap, cost_new, f_b);
 					}
 				}
 			} while ((l_iter = l_iter->radial_next) != l_first);
@@ -474,7 +474,7 @@ static void facetag_add_adjacent(
 						if (cost[f_b_index] > cost_new) {
 							cost[f_b_index] = cost_new;
 							faces_prev[f_b_index] = f_a;
-							BLI_heap_insert(heap, cost_new, f_b);
+							BLI_fastheap_insert(heap, cost_new, f_b);
 						}
 					}
 				}
@@ -491,7 +491,7 @@ LinkNode *BM_mesh_calc_path_face(
 	/* BM_ELEM_TAG flag is used to store visited edges */
 	BMFace *f;
 	BMIter fiter;
-	Heap *heap;
+	FastHeap *heap;
 	float *cost;
 	BMFace **faces_prev;
 	int i, totface;
@@ -527,12 +527,12 @@ LinkNode *BM_mesh_calc_path_face(
 	 */
 
 	/* regular dijkstra shortest path, but over faces instead of vertices */
-	heap = BLI_heap_new();
-	BLI_heap_insert(heap, 0.0f, f_src);
+	heap = BLI_fastheap_new();
+	BLI_fastheap_insert(heap, 0.0f, f_src);
 	cost[BM_elem_index_get(f_src)] = 0.0f;
 
-	while (!BLI_heap_is_empty(heap)) {
-		f = BLI_heap_pop_min(heap);
+	while (!BLI_fastheap_is_empty(heap)) {
+		f = BLI_fastheap_pop_min(heap);
 
 		if (f == f_dst)
 			break;
@@ -551,7 +551,7 @@ LinkNode *BM_mesh_calc_path_face(
 
 	MEM_freeN(faces_prev);
 	MEM_freeN(cost);
-	BLI_heap_free(heap, NULL);
+	BLI_fastheap_free(heap, NULL);
 
 	return path;
 }