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, 7 insertions, 7 deletions

diff --git a/source/blender/editors/curve/editcurve_select.c b/source/blender/editors/curve/editcurve_select.c
index 43ab3f2ccbc..573161d1024 100644
--- a/source/blender/editors/curve/editcurve_select.c
+++ b/source/blender/editors/curve/editcurve_select.c
@@ -1704,7 +1704,7 @@ static void curve_select_shortest_path_curve(Nurb *nu, int vert_src, int vert_ds
 
 static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst)
 {
-	Heap *heap;
+	FastHeap *heap;
 
 	int i, vert_curr;
 
@@ -1727,18 +1727,18 @@ static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst
 	}
 
 	/* init heap */
-	heap = BLI_heap_new();
+	heap = BLI_fastheap_new();
 
 	vert_curr = data[vert_src].vert;
-	BLI_heap_insert(heap, 0.0f, &data[vert_src].vert);
+	BLI_fastheap_insert(heap, 0.0f, &data[vert_src].vert);
 	data[vert_src].cost = 0.0f;
 	data[vert_src].vert_prev = vert_src;  /* nop */
 
-	while (!BLI_heap_is_empty(heap)) {
+	while (!BLI_fastheap_is_empty(heap)) {
 		int axis, sign;
 		int u, v;
 
-		vert_curr = *((int *)BLI_heap_pop_min(heap));
+		vert_curr = *((int *)BLI_fastheap_pop_min(heap));
 		if (vert_curr == vert_dst) {
 			break;
 		}
@@ -1760,7 +1760,7 @@ static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst
 					if (data[vert_other].cost > dist) {
 						data[vert_other].cost = dist;
 						if (data[vert_other].vert_prev == -1) {
-							BLI_heap_insert(heap, data[vert_other].cost, &data[vert_other].vert);
+							BLI_fastheap_insert(heap, data[vert_other].cost, &data[vert_other].vert);
 						}
 						data[vert_other].vert_prev = vert_curr;
 					}
@@ -1771,7 +1771,7 @@ static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst
 
 	}
 
-	BLI_heap_free(heap, NULL);
+	BLI_fastheap_free(heap, NULL);
 
 	if (vert_curr == vert_dst) {
 		i = 0;