ccan/heap/heap.c

/* Licensed under BSD-MIT - see LICENSE file for details */
#include <ccan/heap/heap.h>

/*
 * Allocating memory in chunks greater than needed does not yield measurable
 * speedups of the test program when linking against glibc 2.15.
 *
 * When the data array has to be shrunk though, limiting calls to realloc
 * does help a little bit (~7% speedup), hence the following parameter.
 */
#define HEAP_MEM_HYSTERESIS	4096

static inline void swap(struct heap *h, size_t i, size_t j)
{
	void *foo = h->data[i];

	h->data[i] = h->data[j];
	h->data[j] = foo;
}

static void __up(struct heap *h, size_t j)
{
	size_t i; /* parent */

	while (j) {
		i = (j - 1) / 2;

		if (h->less(h->data[j], h->data[i])) {
			swap(h, i, j);
			j = i;
		} else {
			break;
		}
	}
}

int heap_push(struct heap *h, void *data)
{
	if (h->len == h->cap) {
		void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
		if (m == NULL)
			return -1;
		h->data = m;
		h->cap++;
	}
	h->data[h->len++] = data;
	__up(h, h->len - 1);
	return 0;
}

static void __down(struct heap *h, size_t i)
{
	size_t l, r, j; /* left, right, min child */

	while (1) {
		l = 2 * i + 1;
		if (l >= h->len)
			break;
		r = l + 1;
		if (r >= h->len)
			j = l;
		else
			j = h->less(h->data[l], h->data[r]) ? l : r;

		if (h->less(h->data[j], h->data[i])) {
			swap(h, i, j);
			i = j;
		} else {
			break;
		}
	}
}

void *heap_pop(struct heap *h)
{
	void *ret = h->data[0];
	void *m;

	swap(h, 0, --h->len);
	if (h->len) {
		__down(h, 0);
		if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
			m = realloc(h->data, h->len * sizeof(void *));
			if (m == NULL)
				return NULL;
			h->data = m;
			h->cap = h->len;
		}
	}

	return ret;
}

struct heap *heap_init(heap_less_func_t less)
{
	struct heap *heap = calloc(1, sizeof(*heap));

	if (heap == NULL)
		return NULL;
	heap->less = less;
	return heap;
}

void heap_ify(struct heap *h, heap_less_func_t less)
{
	int i;

	if (less)
		h->less = less;

	for (i = h->len / 2 - 1; i >= 0; i--)
		__down(h, i);
}

void heap_free(struct heap *heap)
{
	free(heap->data);
	free(heap);
}