myvtm/libtoolkit/heaputil.c

#include "precompile.h"
#include "heaputil.h"

/* heap */

static void swap_elem(void**arr, int x, int y)
{
	void* t = arr[x];
	arr[x] = arr[y];
	arr[y] = t;
}

TOOLKIT_API void heap_up(void**arr, int arr_n, int slot, heap_priority_cmp prio_cmp)
{
	int i;
	assert(arr);
	assert(prio_cmp);
	i = slot;
	while (i) {
		int p = heap_parent(i);
		if (prio_cmp(arr[i], arr[p]) < 0) {
			swap_elem(arr, i, p);
			i = p;
		} else {
			break;
		}
	}
}

TOOLKIT_API void heap_down(void**arr, int arr_n, int slot, heap_priority_cmp prio_cmp)
{
	int i = slot;
	int n = arr_n;
	assert(arr);
	assert(prio_cmp);
	while (i < n) {
		int l = heap_left_child(i);
		int r = heap_right_child(i);
		if (r < n) {
			int min = (prio_cmp(arr[l], arr[r]) < 0) ? l : r;
			if (prio_cmp(arr[min], arr[i]) < 0) {
				swap_elem(arr, i, min);
				i = min;
			} else {
				break;
			}
		} else if (l < n) { /* r is out of range */
			if (prio_cmp(arr[l], arr[i]) < 0) {
				swap_elem(arr, i, l);
				i = l;
			}
			else{
				break;
			}
		} else {
			break;
		}
	}
}

TOOLKIT_API void heap_push(void**arr, int *arr_n, void* obj, heap_priority_cmp prio_cmp)
{
	assert(arr);
	assert(arr_n);
	assert(obj);
	assert(prio_cmp);
	arr[*arr_n] = obj;
	++*arr_n;
	heap_up(arr, *arr_n, *arr_n-1, prio_cmp);
}

TOOLKIT_API void* heap_pop(void** arr, int *arr_n, heap_priority_cmp prio_cmp)
{
	void *root = NULL;
	assert(arr);
	assert(arr_n);
	assert(prio_cmp);
	if (*arr_n) {
		root = arr[0];
		--*arr_n;
	}
	if (*arr_n) {
		arr[0] = arr[*arr_n];
		heap_down(arr, *arr_n, 0, prio_cmp);
	}
	return root;
}