1 files changed, 81 insertions, 56 deletions

diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c
index ee7d93ea1a9..dcc028630e2 100644
--- a/source/blender/blenlib/intern/BLI_heap.c
+++ b/source/blender/blenlib/intern/BLI_heap.c
@@ -40,9 +40,9 @@
 /***/
 
 struct HeapNode {
-	void *ptr;
-	float value;
-	int index;
+	void        *ptr;
+	float        value;
+	unsigned int index;
 };
 
 struct Heap {
@@ -54,48 +54,43 @@ struct Heap {
 	HeapNode **tree;
 };
 
+/* internal functions */
+
 #define HEAP_PARENT(i) ((i - 1) >> 1)
 #define HEAP_LEFT(i)   ((i << 1) + 1)
 #define HEAP_RIGHT(i)  ((i << 1) + 2)
 #define HEAP_COMPARE(a, b) (a->value < b->value)
-// #define HEAP_EQUALS(a, b) (a->value == b->value) // UNUSED
-#define HEAP_SWAP(heap, i, j) \
-	{                                                                            \
-		SWAP(int, heap->tree[i]->index, heap->tree[j]->index);                   \
-		SWAP(HeapNode *, heap->tree[i], heap->tree[j]);                          \
-	} (void)0
 
-/***/
+#if 0  /* UNUSED */
+#define HEAP_EQUALS(a, b) (a->value == b->value)
+#endif
 
-Heap *BLI_heap_new(void)
+BLI_INLINE void heap_swap(Heap *heap, const unsigned int i, const unsigned int j)
 {
-	Heap *heap = (Heap *)MEM_callocN(sizeof(Heap), __func__);
-	heap->bufsize = 1;
-	heap->tree = (HeapNode **)MEM_mallocN(sizeof(HeapNode *), "BLIHeapTree");
-	heap->arena = BLI_memarena_new(1 << 16, "heap arena");
 
-	return heap;
+#if 0
+	SWAP(unsigned int,  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;
+	} tmp;
+	SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index);
+	SWAP_TVAL(tmp.node,  tree[i],        tree[j]);
+#endif
 }
 
-void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
+static void heap_down(Heap *heap, unsigned int i)
 {
-	int i;
-
-	if (ptrfreefp)
-		for (i = 0; i < heap->size; i++)
-			ptrfreefp(heap->tree[i]->ptr);
+	/* size won't change in the loop */
+	const unsigned int size = heap->size;
 
-	MEM_freeN(heap->tree);
-	BLI_memarena_free(heap->arena);
-	MEM_freeN(heap);
-}
-
-static void BLI_heap_down(Heap *heap, int i)
-{
 	while (1) {
-		int size = heap->size, smallest;
-		int l = HEAP_LEFT(i);
-		int r = HEAP_RIGHT(i);
+		const unsigned int l = HEAP_LEFT(i);
+		const unsigned int r = HEAP_RIGHT(i);
+		unsigned int smallest;
 
 		smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i;
 
@@ -105,46 +100,75 @@ static void BLI_heap_down(Heap *heap, int i)
 		if (smallest == i)
 			break;
 
-		HEAP_SWAP(heap, i, smallest);
+		heap_swap(heap, i, smallest);
 		i = smallest;
 	}
 }
 
-static void BLI_heap_up(Heap *heap, int i)
+static void heap_up(Heap *heap, unsigned int i)
 {
 	while (i > 0) {
-		int p = HEAP_PARENT(i);
+		const unsigned int p = HEAP_PARENT(i);
 
 		if (HEAP_COMPARE(heap->tree[p], heap->tree[i]))
 			break;
 
-		HEAP_SWAP(heap, p, i);
+		heap_swap(heap, p, i);
 		i = p;
 	}
 }
 
-HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
+
+/***/
+
+/* use when the size of the heap is known in advance */
+Heap *BLI_heap_new_ex(unsigned int tot_reserve)
 {
-	HeapNode *node;
+	Heap *heap = (Heap *)MEM_callocN(sizeof(Heap), __func__);
+	/* ensure we have at least one so we can keep doubling it */
+	heap->bufsize = MAX2(1, tot_reserve);
+	heap->tree = (HeapNode **)MEM_mallocN(heap->bufsize * sizeof(HeapNode *), "BLIHeapTree");
+	heap->arena = BLI_memarena_new(1 << 16, "heap arena");
 
-	if ((heap->size + 1) > heap->bufsize) {
-		int newsize = heap->bufsize * 2;
-		HeapNode **newtree;
+	return heap;
+}
+
+Heap *BLI_heap_new(void)
+{
+	return BLI_heap_new_ex(1);
+}
+
+void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
+{
+	unsigned int i;
+
+	if (ptrfreefp) {
+		for (i = 0; i < heap->size; i++) {
+			ptrfreefp(heap->tree[i]->ptr);
+		}
+	}
 
-		newtree = (HeapNode **)MEM_mallocN(newsize * sizeof(*newtree), __func__);
-		memcpy(newtree, heap->tree, sizeof(HeapNode *) * heap->size);
-		MEM_freeN(heap->tree);
+	MEM_freeN(heap->tree);
+	BLI_memarena_free(heap->arena);
+	MEM_freeN(heap);
+}
 
-		heap->tree = newtree;
-		heap->bufsize = newsize;
+HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
+{
+	HeapNode *node;
+
+	if (UNLIKELY((heap->size + 1) > heap->bufsize)) {
+		heap->bufsize *= 2;
+		heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
 	}
 
 	if (heap->freenodes) {
 		node = heap->freenodes;
 		heap->freenodes = (HeapNode *)(((HeapNode *)heap->freenodes)->ptr);
 	}
-	else
+	else {
 		node = (HeapNode *)BLI_memarena_alloc(heap->arena, sizeof *node);
+	}
 
 	node->value = value;
 	node->ptr = ptr;
@@ -154,17 +178,17 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
 
 	heap->size++;
 
-	BLI_heap_up(heap, heap->size - 1);
+	heap_up(heap, heap->size - 1);
 
 	return node;
 }
 
-int BLI_heap_empty(Heap *heap)
+int BLI_heap_is_empty(Heap *heap)
 {
 	return (heap->size == 0);
 }
 
-int BLI_heap_size(Heap *heap)
+unsigned int BLI_heap_size(Heap *heap)
 {
 	return heap->size;
 }
@@ -181,13 +205,14 @@ void *BLI_heap_popmin(Heap *heap)
 	heap->tree[0]->ptr = heap->freenodes;
 	heap->freenodes = heap->tree[0];
 
-	if (heap->size == 1)
+	if (UNLIKELY(heap->size == 1)) {
 		heap->size--;
+	}
 	else {
-		HEAP_SWAP(heap, 0, heap->size - 1);
+		heap_swap(heap, 0, heap->size - 1);
 		heap->size--;
 
-		BLI_heap_down(heap, 0);
+		heap_down(heap, 0);
 	}
 
 	return ptr;
@@ -195,12 +220,12 @@ void *BLI_heap_popmin(Heap *heap)
 
 void BLI_heap_remove(Heap *heap, HeapNode *node)
 {
-	int i = node->index;
+	unsigned int i = node->index;
 
 	while (i > 0) {
-		int p = HEAP_PARENT(i);
+		unsigned int p = HEAP_PARENT(i);
 
-		HEAP_SWAP(heap, p, i);
+		heap_swap(heap, p, i);
 		i = p;
 	}