Cleanup: move fast heap into own source & header

1 files changed, 0 insertions, 199 deletions

diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c
index 4d662f067ba..c785c1ac012 100644
--- a/source/blender/blenlib/intern/BLI_heap.c
+++ b/source/blender/blenlib/intern/BLI_heap.c
@@ -73,17 +73,6 @@ struct Heap {
 	} nodes;
 };
 
-typedef struct FastHeapNode {
-	float value;
-	void *ptr;
-} FastHeapNode;
-
-struct FastHeap {
-	uint size;
-	uint bufsize;
-	FastHeapNode *tree;
-};
-
 /** \name Internal Functions
  * \{ */
 
@@ -452,191 +441,3 @@ bool BLI_heap_is_valid(const Heap *heap)
 }
 
 /** \} */
-
-/** \name FastHeap Internal Functions
- * \{ */
-
-static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *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)))
-#else
-	FastHeapNode *const tree = heap->tree;
-
-#define OFFSET(i) (i)
-#define NODE(i) tree[i]
-#endif
-
-#define HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1))
-
-	const uint size = OFFSET(heap->size);
-
-	/* Pull the active node values into locals. This allows spilling
-	 * the data from registers instead of literally swapping nodes. */
-	float active_val = init->value;
-	void *active_ptr = init->ptr;
-
-	/* Prepare the first iteration and spill value. */
-	uint i = OFFSET(start_i);
-
-	NODE(i).value = active_val;
-
-	for (;;) {
-		const uint l = HEAP_LEFT_OFFSET(i);
-		const uint r = l + OFFSET(1); /* right */
-
-		/* Find the child with the smallest value. */
-		uint smallest = i;
-
-		if (LIKELY(l < size) && NODE(l).value < active_val) {
-			smallest = l;
-		}
-		if (LIKELY(r < size) && NODE(r).value < NODE(smallest).value) {
-			smallest = r;
-		}
-
-		if (UNLIKELY(smallest == i)) {
-			break;
-		}
-
-		/* Move the smallest child into the current node.
-		 * Skip padding: for some reason that makes it faster here. */
-		NODE(i).value = NODE(smallest).value;
-		NODE(i).ptr = NODE(smallest).ptr;
-
-		/* Proceed to next iteration and spill value. */
-		i = smallest;
-		NODE(i).value = active_val;
-	}
-
-	/* Spill the pointer into the final position of the node. */
-	NODE(i).ptr = active_ptr;
-
-#undef NODE
-#undef OFFSET
-#undef HEAP_LEFT_OFFSET
-}
-
-static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_ptr)
-{
-	FastHeapNode *const tree = heap->tree;
-
-	while (LIKELY(i > 0)) {
-		const uint p = HEAP_PARENT(i);
-
-		if (active_val >= tree[p].value) {
-			break;
-		}
-
-		tree[i] = tree[p];
-		i = p;
-	}
-
-	tree[i].value = active_val;
-	tree[i].ptr = active_ptr;
-}
-
-/** \} */
-
-/** \name Public FastHeap API
- * \{ */
-
-/**
- * Creates a new fast 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)
-{
-	FastHeap *heap = MEM_mallocN(sizeof(FastHeap), __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");
-	return heap;
-}
-
-FastHeap *BLI_fastheap_new(void)
-{
-	return BLI_fastheap_new_ex(1);
-}
-
-void BLI_fastheap_free(FastHeap *heap, HeapFreeFP ptrfreefp)
-{
-	if (ptrfreefp) {
-		for (uint i = 0; i < heap->size; i++) {
-			ptrfreefp(heap->tree[i].ptr);
-		}
-	}
-
-	MEM_freeN(heap->tree);
-	MEM_freeN(heap);
-}
-
-void BLI_fastheap_clear(FastHeap *heap, HeapFreeFP ptrfreefp)
-{
-	if (ptrfreefp) {
-		for (uint i = 0; i < heap->size; i++) {
-			ptrfreefp(heap->tree[i].ptr);
-		}
-	}
-
-	heap->size = 0;
-}
-
-/**
- * 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)
-{
-	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);
-}
-
-bool BLI_fastheap_is_empty(const FastHeap *heap)
-{
-	return (heap->size == 0);
-}
-
-uint BLI_fastheap_len(const FastHeap *heap)
-{
-	return heap->size;
-}
-
-/**
- * Return the lowest value of the heap.
- */
-float BLI_fastheap_top_value(const FastHeap *heap)
-{
-	BLI_assert(heap->size != 0);
-
-	return heap->tree[0].value;
-}
-
-/**
- * Pop the top node off the heap and return it's pointer.
- */
-void *BLI_fastheap_pop_min(FastHeap *heap)
-{
-	BLI_assert(heap->size != 0);
-
-	void *ptr = heap->tree[0].ptr;
-
-	if (--heap->size) {
-		fastheap_down(heap, 0, &heap->tree[heap->size]);
-	}
-
-	return ptr;
-}
-
-/** \} */