ccan/heap/test/run.c

#include <stdlib.h>
#include <stdio.h>

#include <ccan/heap/heap.h>
/* Include the C files directly. */
#include <ccan/heap/heap.c>
#include <ccan/tap/tap.h>

struct item {
	void *foobar;
	int v;
};

static bool heap_ok(const struct heap *h, heap_less_func_t less, int i)
{
	int l, r;

	l = 2 * i + 1;
	r = l + 1;

	if (l < h->len) {
		if (less(h->data[l], h->data[i])) {
			fprintf(stderr, "heap property violation\n");
			return false;
		}
		if (!heap_ok(h, less, l))
			return false;
	}
	if (r < h->len) {
		if (less(h->data[r], h->data[i])) {
			fprintf(stderr, "heap property violation\n");
			return false;
		}
		if (!heap_ok(h, less, r))
			return false;
	}
	return true;
}

static bool less(const struct item *a, const struct item *b)
{
	return a->v < b->v;
}

static bool __less(const void *a, const void *b)
{
	return less(a, b);
}

static bool more(const struct item *a, const struct item *b)
{
	return a->v > b->v;
}

static bool __more(const void *a, const void *b)
{
	return more(a, b);
}

static bool some_test(size_t n, bool is_less)
{
	struct item *items = calloc(n, sizeof(*items));
	struct item *item, *prev;
	struct heap *h;
	int i;

	if (items == NULL) {
		perror("items");
		exit(EXIT_FAILURE);
	}

	if (is_less)
		h = heap_init(__less);
	else
		h = heap_init(__more);
	if (h == NULL) {
		perror("heap_init");
		exit(EXIT_FAILURE);
	}

	for (i = 0; i < n; i++) {
		item = &items[i];

		item->v = rand();
		/* printf("pushing %d\n", item->v); */
		heap_push(h, item);
		if (!heap_ok(h, is_less ? __less : __more, 0))
			return false;
	}
	if (is_less) {
		heap_ify(h, __more);
		if (!heap_ok(h, __more, 0))
			return false;
		heap_ify(h, __less);
		if (!heap_ok(h, __less, 0))
			return false;
	} else {
		heap_ify(h, NULL);
		if (!heap_ok(h, __more, 0))
			return false;
	}

	for (i = 0; i < n; i++) {
		item = heap_pop(h);
		if (!heap_ok(h, is_less ? __less : __more, 0))
			return false;
		/* printf("popped %d\n", item->v); */
		if (i > 0) {
			if (is_less) {
				if (less(item, prev))
					return false;
			} else {
				if (more(item, prev))
					return false;
			}
		}
		prev = item;
	}
	heap_free(h);
	free(items);
	return true;
}

int main(void)
{
	plan_tests(3);

	ok1(some_test(5000, true));
	ok1(some_test(1, true));
	ok1(some_test(33, false));

	return exit_status();
}