#include <assert.h>
#include <err.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#include "container_of.h"
#include "cradix.h"

#ifdef NDEBUG
#define	__diagused	__unused
#else
#define	__diagused
#endif

#define	arraycount(A)	(sizeof(A)/sizeof(*(A)))
#define	K		(const uint8_t[])

struct node {
	uint8_t key[8];
	struct cradix_node cradix;
};

static const void *
getkey(const struct cradix *C __unused, const struct cradix_node *N)
{
	const struct node *n = const_container_of(N, struct node, cradix);

	return n->key;
}

static const struct cradix_ops ops = {
	.keylen = sizeof(((struct node *)0)->key),
	.key = &getkey,
};

static void
test_lookup_delete_empty(void)
{
	struct cradix cradix, *C = &cradix;

	cradix_init(C, &ops);
	assert(cradix_empty(C));
	assert(cradix_lookup(C, 0) == NULL);
	assert(cradix_min(C) == NULL);
	assert(cradix_min_prefix(C, K{0,1}, 2) == NULL);
	assert(cradix_max(C) == NULL);
	assert(cradix_max_prefix(C, K{0,1}, 2) == NULL);
	assert(cradix_delete_key(C, 0, NULL) == NULL);
	cradix_destroy(C);
}

static void
test_one_node(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node = { {0,1,2,3,4,5,6,7} };

	cradix_init(C, &ops);
	assert(cradix_empty(C));
	assert(cradix_insert(C, &node.cradix, NULL) == &node.cradix);
	assert(!cradix_empty(C));
	assert(cradix_lookup(C, K{0,1,2,3,4,5,6,7}) == &node.cradix);
	assert(cradix_lookup(C, K{0,1,2,3,4,5,6,8}) == NULL);
	assert(cradix_min(C) == &node.cradix);
	assert(cradix_min_prefix(C, K{0,0}, 2) == NULL);
	assert(cradix_min_prefix(C, K{0,1}, 2) == &node.cradix);
	assert(cradix_max(C) == &node.cradix);
	assert(cradix_max_prefix(C, K{0,0}, 2) == NULL);
	assert(cradix_max_prefix(C, K{0,1}, 2) == &node.cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,8}, NULL) == NULL);
	assert(!cradix_empty(C));
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) == &node.cradix);
	assert(cradix_empty(C));
	cradix_destroy(C);
}

static void
test_two_nodes(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {15,1,2,3,4,5,6,7} },
	};

	cradix_init(C, &ops);
	assert(cradix_empty(C));
	assert(cradix_insert(C, &node[0].cradix, NULL) == &node[0].cradix);
	assert(!cradix_empty(C));
	assert(cradix_insert(C, &node[1].cradix, NULL) == &node[1].cradix);
	assert(cradix_lookup(C, K{0,1,2,3,4,5,6,7}) == &node[0].cradix);
	assert(cradix_lookup(C, K{0,1,2,3,4,5,6,8}) == NULL);
	assert(cradix_lookup(C, K{15,1,2,3,4,5,6,7}) == &node[1].cradix);
	assert(cradix_lookup(C, K{15,1,2,3,4,5,6,8}) == NULL);
	assert(cradix_lookup(C, K{0x80,1,2,3,4,5,6,8}) == NULL);
	assert(cradix_lookup(C, K{8,1,2,3,4,5,6,8}) == NULL);
	assert(cradix_min(C) == &node[0].cradix);
	assert(cradix_min_prefix(C, K{0}, 1) == &node[0].cradix);
	assert(cradix_min_prefix(C, K{15}, 1) == &node[1].cradix);
	assert(cradix_max(C) == &node[1].cradix);
	assert(cradix_max_prefix(C, K{0}, 1) == &node[0].cradix);
	assert(cradix_max_prefix(C, K{15}, 1) == &node[1].cradix);
	assert(!cradix_empty(C));
	assert(cradix_delete_key(C, K{8,1,2,3,4,5,6,8}, NULL) == NULL);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,8}, NULL) == NULL);
	assert(cradix_delete_key(C, K{0x80,1,2,3,4,5,6,8}, NULL) == NULL);
	cradix_delete(C, &node[0].cradix, NULL);
	assert(cradix_delete_key(C, K{15,1,2,3,4,5,6,8}, NULL) == NULL);
	assert(!cradix_empty(C));
	assert(cradix_delete_key(C, K{15,1,2,3,4,5,6,7}, NULL) ==
	    &node[1].cradix);
	assert(cradix_empty(C));
	cradix_destroy(C);
}

static void
test_lookup_tombstone(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {8,1,2,3,4,5,6,7} },
		{ {15,1,2,3,4,5,6,7} },
	};

	cradix_init(C, &ops);
	assert(cradix_insert(C, &node[0].cradix, NULL) == &node[0].cradix);
	assert(cradix_insert(C, &node[1].cradix, NULL) == &node[1].cradix);
	assert(cradix_insert(C, &node[2].cradix, NULL) == &node[2].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) ==
	    &node[0].cradix);
	assert(cradix_min(C) == &node[1].cradix);
	assert(cradix_min_prefix(C, K{0}, 1) == NULL);
	assert(cradix_min_prefix(C, K{8}, 1) == &node[1].cradix);
	assert(cradix_min_prefix(C, K{15}, 1) == &node[2].cradix);
	assert(cradix_max(C) == &node[2].cradix);
	assert(cradix_max_prefix(C, K{0}, 1) == NULL);
	assert(cradix_max_prefix(C, K{8}, 1) == &node[1].cradix);
	assert(cradix_max_prefix(C, K{15}, 1) == &node[2].cradix);
	assert(cradix_lookup(C, K{0,1,2,3,4,5,6,7}) == NULL);
	assert(cradix_lookup(C, K{8,1,2,3,4,5,6,7}) == &node[1].cradix);
	assert(cradix_lookup(C, K{15,1,2,3,4,5,6,7}) == &node[2].cradix);
	assert(cradix_delete_key(C, K{8,1,2,3,4,5,6,7}, NULL) ==
	    &node[1].cradix);
	assert(cradix_delete_key(C, K{15,1,2,3,4,5,6,7}, NULL) ==
	    &node[2].cradix);
	cradix_destroy(C);
}

static void
test_collision(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {0,1,2,3,4,5,6,7} },
	};

	cradix_init(C, &ops);
	assert(cradix_insert(C, &node[0].cradix, NULL) == &node[0].cradix);
	assert(cradix_insert(C, &node[1].cradix, NULL) == &node[1].cradix);
	assert(cradix_insert(C, &node[2].cradix, NULL) == &node[0].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) ==
	    &node[0].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,8}, NULL) ==
	    &node[1].cradix);
	cradix_destroy(C);
}

static void
test_insert_post_nested(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {8,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {8,1,2,3,4,5,6,8} },
	};
	unsigned i;

	cradix_init(C, &ops);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_insert(C, &node[i].cradix, NULL) ==
		    &node[i].cradix);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_lookup(C, node[i].key) == &node[i].cradix);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_delete_key(C, node[i].key, NULL) ==
		    &node[i].cradix);
	cradix_destroy(C);
}

static void
test_insert_pre_nested(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {8,1,2,3,4,5,6,7} },
		{ {8,1,2,3,4,5,6,8} },
	};
	unsigned i;

	cradix_init(C, &ops);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_insert(C, &node[i].cradix, NULL) ==
		    &node[i].cradix);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_lookup(C, node[i].key) == &node[i].cradix);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_delete_key(C, node[i].key, NULL) ==
		    &node[i].cradix);
	cradix_destroy(C);
}

static void
test_refill_tombstone(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {0,1,2,3,4,5,6,9} },
		{ {0,1,2,3,4,5,6,7} },
	};
	unsigned i;

	cradix_init(C, &ops);
	assert(cradix_insert(C, &node[0].cradix, NULL) == &node[0].cradix);
	assert(cradix_insert(C, &node[1].cradix, NULL) == &node[1].cradix);
	assert(cradix_insert(C, &node[2].cradix, NULL) == &node[2].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) ==
	    &node[0].cradix);
	assert(cradix_insert(C, &node[3].cradix, NULL) == &node[3].cradix);
	for (i = 1; i < 4; i++)
		assert(cradix_lookup(C, node[i].key) == &node[i].cradix);
	for (i = 1; i < 4; i++)
		assert(cradix_delete_key(C, node[i].key, NULL) ==
		    &node[i].cradix);
	cradix_destroy(C);
}

static void
test_pick_leaf_fallback(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {8,1,2,3,4,5,6,7} },
		{ {8,1,2,3,4,5,6,8} },
		{ {15,1,2,3,4,5,6,7} },
	};
	unsigned i;

	cradix_init(C, &ops);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_insert(C, &node[i].cradix, NULL) ==
		    &node[i].cradix);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_lookup(C, node[i].key) == &node[i].cradix);
	for (i = 0; i < arraycount(node); i++)
		assert(cradix_delete_key(C, node[i].key, NULL) ==
		    &node[i].cradix);
	cradix_destroy(C);
}

static void
test_grow_from_tombstone(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {0,1,2,3,4,5,6,9} },
		{ {0,1,2,3,4,5,6,10} },
	};
	unsigned i;

	cradix_init(C, &ops);
	assert(cradix_insert(C, &node[0].cradix, NULL) == &node[0].cradix);
	assert(cradix_insert(C, &node[1].cradix, NULL) == &node[1].cradix);
	assert(cradix_insert(C, &node[2].cradix, NULL) == &node[2].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) ==
	    &node[0].cradix);
	assert(cradix_insert(C, &node[3].cradix, NULL) == &node[3].cradix);
	for (i = 1; i < arraycount(node); i++)
		assert(cradix_lookup(C, node[i].key) == &node[i].cradix);
	for (i = 1; i < arraycount(node); i++)
		assert(cradix_delete_key(C, node[i].key, NULL) ==
		    &node[i].cradix);
	cradix_destroy(C);
}

static void
test_grow_shrink(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {0,1,2,3,4,5,6,9} },
		{ {0,1,2,3,4,5,6,10} },
		{ {0,1,2,3,4,5,6,11} },
		{ {0,1,2,3,4,5,6,12} },
		{ {0,1,2,3,4,5,6,13} },
	};
	unsigned i;

	cradix_init(C, &ops);

	/* Insert all but one.  */
	for (i = 0; i < arraycount(node) - 1; i++)
		assert(cradix_insert(C, &node[i].cradix, NULL) ==
		    &node[i].cradix);

	/* Delete all but two of what we inserted.  */
	for (i = 2; i < arraycount(node) - 1; i++)
		assert(cradix_delete_key(C, node[i].key, NULL) ==
		    &node[i].cradix);

	/*
	 * Insert the last one.  The branch is full of tombstones, so
	 * it should shrink.
	 */
	assert(cradix_insert(C, &node[arraycount(node) - 1].cradix, NULL) ==
	    &node[arraycount(node) - 1].cradix);

	/* Confirm they can all be looked up.  */
	assert(cradix_lookup(C, K{0,1,2,3,4,5,6,7}) == &node[0].cradix);
	assert(cradix_lookup(C, K{0,1,2,3,4,5,6,8}) == &node[1].cradix);
	assert(cradix_lookup(C, K{0,1,2,3,4,5,6,13}) ==
	    &node[arraycount(node) - 1].cradix);

	/* Confirm they can all be deleted.  */
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) ==
	    &node[0].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,8}, NULL) ==
	    &node[1].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,13}, NULL) ==
	    &node[arraycount(node) - 1].cradix);

	cradix_destroy(C);
}

static void
test_delete_tombstone(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {0,1,2,3,4,5,6,9} },
	};
	unsigned i;

	cradix_init(C, &ops);
	assert(cradix_insert(C, &node[0].cradix, NULL) == &node[0].cradix);
	assert(cradix_insert(C, &node[1].cradix, NULL) == &node[1].cradix);
	assert(cradix_insert(C, &node[2].cradix, NULL) == &node[2].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) ==
	    &node[0].cradix);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) == NULL);
	for (i = 1; i < arraycount(node); i++)
		assert(cradix_lookup(C, node[i].key) == &node[i].cradix);
	for (i = 1; i < arraycount(node); i++)
		assert(cradix_delete_key(C, node[i].key, NULL) ==
		    &node[i].cradix);
	cradix_destroy(C);
}

static uint8_t custom_buf[4096];
static bool custom_allocated = false;
static bool custom_recycled = false;
static size_t custom_size = 0;

static void *
custom_alloc(struct cradix *C __unused, size_t size)
{

	assert(!custom_allocated);
	assert(size > 0);
	custom_allocated = true;
	custom_size = size;
	return custom_buf;
}

static void
custom_free(struct cradix *C __unused, void *ptr __unused,
    size_t size __unused)
{

	abort();
}

static void
custom_recycle(struct cradix *C __unused, void *ptr __diagused, size_t size)
{

	assert(custom_allocated);
	assert(ptr == custom_buf);
	assert(size == custom_size);
	custom_allocated = false;
	custom_size = 0;
	custom_recycled = true;
}

static const struct cradix_ops custom_cradix_ops = {
	.keylen = sizeof(((struct node *)0)->key),
	.key = &getkey,
	.alloc = &custom_alloc,
	.free = &custom_free,
	.recycle = &custom_recycle,
};

static void
test_custom_alloc(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
	};

	cradix_init(C, &custom_cradix_ops);

	assert(cradix_insert(C, &node[0].cradix, NULL) == &node[0].cradix);
	assert(!custom_allocated);
	assert(!custom_recycled);

	assert(cradix_insert(C, &node[1].cradix, NULL) == &node[1].cradix);
	assert(custom_allocated);
	assert(!custom_recycled);

	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) ==
	    &node[0].cradix);
	assert(!custom_allocated);
	assert(custom_recycled);

	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,8}, NULL) ==
	    &node[1].cradix);
	assert(!custom_allocated);
	assert(custom_recycled);

	cradix_destroy(C);
}

/* 0 = no fault, 1 = delayed fault, 2 = fault */
static unsigned inject_alloc_fault = 0;
static unsigned faulty_nalloc = 0;
static unsigned faulty_nfree = 0;

static void *
faulty_alloc(struct cradix *C __unused, size_t size)
{

	if (inject_alloc_fault == 2)
		return NULL;
	if (inject_alloc_fault)
		inject_alloc_fault++;
	faulty_nalloc++;
	return malloc(size);
}

static void
faulty_free(struct cradix *C __unused, void *ptr, size_t size __unused)
{

	faulty_nfree++;
	free(ptr);
}

static const struct cradix_ops faulty_cradix_ops = {
	.keylen = sizeof(((struct node *)0)->key),
	.key = &getkey,
	.alloc = &faulty_alloc,
	.free = &faulty_free,
};

static void
test_insert_begin_fail(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {0,1,2,3,4,5,6,9} },
		{ {8,1,2,3,4,5,6,7} },
	};
	struct cradix_insert insert, *I = &insert;
	struct cradix_delete delete, *D = &delete;

	cradix_init(C, &faulty_cradix_ops);

	assert(cradix_insert(C, &node[0].cradix, NULL) == &node[0].cradix);
	assert(cradix_insert(C, &node[1].cradix, NULL) == &node[1].cradix);

	/* Confirm growing the branch fails.  */
	inject_alloc_fault = 2;
	assert(cradix_insert(C, &node[2].cradix, NULL) == NULL);

	/* Confirm it fails.  */
	inject_alloc_fault = 2;
	faulty_nalloc = faulty_nfree = 0;
	assert(!cradix_insert_begin(C, I));
	assert(faulty_nalloc == 0);
	assert(faulty_nfree == 0);

	/* Confirm it runs the error branch.  */
	inject_alloc_fault = 1;
	faulty_nalloc = faulty_nfree = 0;
	assert(!cradix_insert_begin(C, I));
	assert(faulty_nalloc == 1);
	assert(faulty_nfree == 1);

	/* Confirm no allocation is needed after cradix_insert_begin.  */
	inject_alloc_fault = 0;
	assert(cradix_insert_begin(C, I));
	inject_alloc_fault = 2;
	assert(cradix_insert(C, &node[2].cradix, I) == &node[2].cradix);
	cradix_insert_end(C, I);

	/* Confirm making a new branch fails too.  */
	inject_alloc_fault = 2;
	assert(cradix_insert(C, &node[3].cradix, NULL) == NULL);

	/* Confirm making a new branch works with preallocation.  */
	inject_alloc_fault = 0;
	assert(cradix_insert_begin(C, I));
	inject_alloc_fault = 2;
	assert(cradix_insert(C, &node[3].cradix, I) == &node[3].cradix);
	cradix_insert_end(C, I);

	/* Confirm deletion still works despite allocq failure.  */
	inject_alloc_fault = 2;
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,7}, NULL) ==
	    &node[0].cradix);
	assert(cradix_delete_key(C, K{8,1,2,3,4,5,6,7}, NULL) ==
	    &node[3].cradix);

	/* Confirm cradix_delete_begin/end work despite alloc failure.  */
	inject_alloc_fault = 2;
	cradix_delete_begin(C, D);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,8}, D) == &node[1].cradix);
	cradix_delete_end(C, D);

	/* Confirm they work if we reuse the transaction record.  */
	inject_alloc_fault = 2;
	cradix_delete_begin(C, D);
	assert(cradix_delete_key(C, K{0,1,2,3,4,5,6,9}, D) == &node[2].cradix);
	cradix_delete_end(C, D);

	cradix_destroy(C);
	inject_alloc_fault = 0;
}

static void
test_iter_init_destroy(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {0,1,2,3,4,5,6,9} },
		{ {8,1,2,3,4,5,6,7} },
		{ {8,1,2,3,4,5,6,8} },
		{ {8,1,2,3,4,5,6,9} },
	};
	struct cradix_iter iter, *I = &iter;
	CRADIX_ITER_STACK(stack, sizeof(node[0].key));
	struct cradix_node *N;
	unsigned i;

	cradix_init(C, &ops);

	cradix_iter_init(C, I, stack, sizeof stack);
	assert(cradix_iter_min(C, I) == NULL);
	assert(cradix_iter_max(C, I) == NULL);
	cradix_iter_destroy(C, I);

	for (i = 0; i < arraycount(node); i++)
		assert(cradix_insert(C, &node[i].cradix, NULL) ==
		    &node[i].cradix);

	cradix_iter_init(C, I, stack, sizeof stack);
	for (i = 0, N = cradix_iter_min(C, I);
	     i < arraycount(node) && N != NULL;
	     i++, N = cradix_iter_next(C, I))
		assert(N == &node[i].cradix);
	assert(i == arraycount(node));
	cradix_iter_destroy(C, I);

	cradix_iter_init(C, I, stack, sizeof stack);
	for (i = arraycount(node), N = cradix_iter_max(C, I);
	     N != NULL && i --> 0;
	     N = cradix_iter_prev(C, I))
		assert(N == &node[i].cradix);
	assert(i == 0);
	cradix_iter_destroy(C, I);

	for (i = 0; i < arraycount(node); i++)
		cradix_delete(C, &node[i].cradix, NULL);

	cradix_iter_init(C, I, stack, sizeof stack);
	assert(cradix_iter_min(C, I) == NULL);
	assert(cradix_iter_max(C, I) == NULL);
	cradix_iter_destroy(C, I);

	cradix_destroy(C);
}

static void
test_iter_begin_end(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,1,2,3,4,5,6,7} },
		{ {0,1,2,3,4,5,6,8} },
		{ {0,1,2,3,4,5,6,9} },
		{ {8,1,2,3,4,5,6,7} },
		{ {8,1,2,3,4,5,6,8} },
		{ {8,1,2,3,4,5,6,9} },
	};
	struct cradix_iter iter, *I = &iter;
	struct cradix_node *N;
	unsigned i;

	cradix_init(C, &ops);

	cradix_iter_begin(C, I);
	assert(cradix_iter_min(C, I) == NULL);
	assert(cradix_iter_max(C, I) == NULL);
	cradix_iter_end(C, I);

	for (i = 0; i < arraycount(node); i++)
		assert(cradix_insert(C, &node[i].cradix, NULL) ==
		    &node[i].cradix);

	cradix_iter_begin(C, I);
	for (i = 0, N = cradix_iter_min(C, I);
	     i < arraycount(node) && N != NULL;
	     i++, N = cradix_iter_next(C, I))
		assert(N == &node[i].cradix);
	assert(i == arraycount(node));
	cradix_iter_end(C, I);

	cradix_iter_begin(C, I);
	for (i = arraycount(node), N = cradix_iter_max(C, I);
	     N != NULL && i --> 0;
	     N = cradix_iter_prev(C, I))
		assert(N == &node[i].cradix);
	assert(i == 0);
	cradix_iter_end(C, I);

	for (i = 0; i < arraycount(node); i++)
		cradix_delete(C, &node[i].cradix, NULL);

	cradix_iter_begin(C, I);
	assert(cradix_iter_min(C, I) == NULL);
	assert(cradix_iter_max(C, I) == NULL);
	cradix_iter_end(C, I);

	cradix_destroy(C);
}

static void
test_iter_prefix_init_destroy(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,   1,2,3,4 ,5,6,7} }, /* 0 */
		{ {0,   1,2,3,4 ,5,6,8} }, /* 1 */
		{ {0,   1,2,3,4 ,5,6,9} }, /* 2 */
		{ {0,   1,2,3,11,5,6,7} }, /* 3 */
		{ {0,   1,2,3,12,5,6,8} }, /* 4 */
		{ {0,   1,2,3,13,5,6,9} }, /* 5 */
		{ {0,0x41,2,3,4, 4,5,7} }, /* 6 (*) */
		{ {0,0x61,2,3,4, 4,5,7} }, /* 7 */
		{ {8,   1,2,3,4 ,5,6,7} }, /* 8 (**) */
		{ {8,   1,2,3,4 ,5,6,8} }, /* 9 */
		{ {8,   1,2,3,4 ,5,6,9} }, /* 10 */
	};
	const struct {
		uint8_t p[3];
		unsigned n;
		unsigned m;
	} m[] = {
		{ {0}, 1, 8 },		/* matches with submask (**) */
		{ {0,1}, 2, 6 },	/* matches with no submask (*) */
	}, n[] = {
		{ {1,0}, 2, -1 },	/* doesn't match at all */
		{ {0,1,3}, 3, -1 },	/* mismatches after partial match */
	};
	struct cradix_iter iter, *I = &iter;
	CRADIX_ITER_STACK(stack, sizeof(node[0].key));
	struct cradix_node *N;
	unsigned p, i;

	cradix_init(C, &ops);

	cradix_iter_init(C, I, stack, sizeof stack);
	for (p = 0; p < arraycount(m); p++) {
		assert(cradix_iter_min_prefix(C, I, m[p].p, m[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, m[p].p, m[p].n) == NULL);
	}
	for (p = 0; p < arraycount(n); p++) {
		assert(cradix_iter_min_prefix(C, I, n[p].p, n[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, n[p].p, n[p].n) == NULL);
	}
	cradix_iter_destroy(C, I);

	for (i = 0; i < arraycount(node); i++)
		assert(cradix_insert(C, &node[i].cradix, NULL) ==
		    &node[i].cradix);

	cradix_iter_init(C, I, stack, sizeof stack);
	for (p = 0; p < arraycount(n); p++) {
		assert(cradix_iter_min_prefix(C, I, n[p].p, n[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, n[p].p, n[p].n) == NULL);
	}
	cradix_iter_destroy(C, I);

	for (p = 0; p < arraycount(m); p++) {
		cradix_iter_init(C, I, stack, sizeof stack);
		for (i = 0, N = cradix_iter_min_prefix(C, I, m[p].p, m[p].n);
		     i < m[p].m && N != NULL;
		     i++, N = cradix_iter_next(C, I))
			assert(N == &node[i].cradix);
		assert(i == m[p].m);
		cradix_iter_destroy(C, I);
	}

	for (p = 0; p < arraycount(m); p++) {
		cradix_iter_init(C, I, stack, sizeof stack);
		for (i = m[p].m,
			 N = cradix_iter_max_prefix(C, I, m[p].p, m[p].n);
		     N != NULL && i --> 0;
		     N = cradix_iter_prev(C, I))
			assert(N == &node[i].cradix);
		assert(i == 0);
		cradix_iter_destroy(C, I);
	}

	for (i = 0; i < arraycount(node); i++)
		cradix_delete(C, &node[i].cradix, NULL);

	cradix_iter_init(C, I, stack, sizeof stack);
	for (p = 0; p < arraycount(m); p++) {
		assert(cradix_iter_min_prefix(C, I, m[p].p, m[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, m[p].p, m[p].n) == NULL);
	}
	for (p = 0; p < arraycount(n); p++) {
		assert(cradix_iter_min_prefix(C, I, n[p].p, n[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, n[p].p, n[p].n) == NULL);
	}
	cradix_iter_destroy(C, I);

	cradix_destroy(C);
}

static void
test_iter_prefix_begin_end(void)
{
	struct cradix cradix, *C = &cradix;
	struct node node[] = {
		{ {0,   1,2,3,4 ,5,6,7} }, /* 0 */
		{ {0,   1,2,3,4 ,5,6,8} }, /* 1 */
		{ {0,   1,2,3,4 ,5,6,9} }, /* 2 */
		{ {0,   1,2,3,11,5,6,7} }, /* 3 */
		{ {0,   1,2,3,12,5,6,8} }, /* 4 */
		{ {0,   1,2,3,13,5,6,9} }, /* 5 */
		{ {0,0x41,2,3,4, 4,5,7} }, /* 6 (*) */
		{ {0,0x61,2,3,4, 4,5,7} }, /* 7 */
		{ {8,   1,2,3,4 ,5,6,7} }, /* 8 (**) */
		{ {8,   1,2,3,4 ,5,6,8} }, /* 9 */
		{ {8,   1,2,3,4 ,5,6,9} }, /* 10 */
	};
	const struct {
		uint8_t p[3];
		unsigned n;
		unsigned m;
	} m[] = {
		{ {0}, 1, 8 },		/* matches with submask (**) */
		{ {0,1}, 2, 6 },	/* matches with no submask (*) */
	}, n[] = {
		{ {1,0}, 2, -1 },	/* doesn't match at all */
		{ {0,1,3}, 3, -1 },	/* mismatches after partial match */
	};
	struct cradix_iter iter, *I = &iter;
	struct cradix_node *N;
	unsigned p, i;

	cradix_init(C, &ops);

	cradix_iter_begin(C, I);
	for (p = 0; p < arraycount(m); p++) {
		assert(cradix_iter_min_prefix(C, I, m[p].p, m[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, m[p].p, m[p].n) == NULL);
	}
	for (p = 0; p < arraycount(n); p++) {
		assert(cradix_iter_min_prefix(C, I, n[p].p, n[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, n[p].p, n[p].n) == NULL);
	}
	cradix_iter_end(C, I);

	for (i = 0; i < arraycount(node); i++)
		assert(cradix_insert(C, &node[i].cradix, NULL) ==
		    &node[i].cradix);

	cradix_iter_begin(C, I);
	for (p = 0; p < arraycount(n); p++) {
		assert(cradix_iter_min_prefix(C, I, n[p].p, n[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, n[p].p, n[p].n) == NULL);
	}
	cradix_iter_end(C, I);

	for (p = 0; p < arraycount(m); p++) {
		cradix_iter_begin(C, I);
		for (i = 0, N = cradix_iter_min_prefix(C, I, m[p].p, m[p].n);
		     i < m[p].m && N != NULL;
		     i++, N = cradix_iter_next(C, I))
			assert(N == &node[i].cradix);
		assert(i == m[p].m);
		cradix_iter_end(C, I);
	}

	for (p = 0; p < arraycount(m); p++) {
		cradix_iter_begin(C, I);
		for (i = m[p].m,
			 N = cradix_iter_max_prefix(C, I, m[p].p, m[p].n);
		     N != NULL && i --> 0;
		     N = cradix_iter_prev(C, I))
			assert(N == &node[i].cradix);
		assert(i == 0);
		cradix_iter_end(C, I);
	}

	for (i = 0; i < arraycount(node); i++)
		cradix_delete(C, &node[i].cradix, NULL);

	cradix_iter_begin(C, I);
	for (p = 0; p < arraycount(m); p++) {
		assert(cradix_iter_min_prefix(C, I, m[p].p, m[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, m[p].p, m[p].n) == NULL);
	}
	for (p = 0; p < arraycount(n); p++) {
		assert(cradix_iter_min_prefix(C, I, n[p].p, n[p].n) == NULL);
		assert(cradix_iter_max_prefix(C, I, n[p].p, n[p].n) == NULL);
	}
	cradix_iter_end(C, I);

	cradix_destroy(C);
}

static void
test_misc(void)
{
	struct node nodes[] = {
		{ {0,1,2,3,13,5,6,7} },
		{ {0,1,2,3,11,5,6,7} },
		{ {0,1,2,3,12,5,6,7} },
		{ {0,1,2,3,4,5,6,7} },
		{ {0x1a,0x72,0x79,0x38,0x25,0xc2,0x99,0x27} },
		{ {0x1a,0x26,0x45,0x93,0x22,0x58,0x44,0x2f} },
		{ {0x1a,0x1d,0xbd,0xec,0xdf,0x86,0x7a,0x27} },
		{ {0x1b,0xe7,0x34,0xb8,0x71,0x3f,0x08,0x91} },
		{ {0xb3,0x70,0x60,0x73,0xf2,0x7e,0x7e,0x75} },
		{ {0x1b,0x10,0x1b,0xb7,0xda,0x4c,0x18,0x27} },
		{ {0x1b,0xca,0x0c,0x13,0x8c,0x8a,0xb3,0x27} },
		{ {0x1a,0x0b,0x82,0x28,0x70,0xa6,0x64,0x33} },
		{ {0x53,0x76,0x42,0x33,0x93,0x1a,0xb6,0xd8} },
		{ {0x8e,0xa4,0x9a,0x59,0xa2,0xc1,0xc0,0xb3} },
		{ {0x8d,0x3c,0x54,0xac,0xd5,0xb7,0x68,0x27} },
		{ {0x1a,0xe5,0x02,0xfb,0x06,0x0e,0xe4,0x27} },
		{ {0x1a,0xe5,0x02,0xfb,0x06,0x0e,0xe4,0x28} },
		{ {0x1a,0x1d,0xbd,0xec,0xdf,0x86,0x7a,0x26} },
		{ {0x1a,0xe5,0x02,0xfb,0x06,0x0e,0xe4,0x29} },
	};
	struct cradix cradix, *C = &cradix;
	struct cradix_node *N;
	struct cradix_insert insert, *I = &insert;
	unsigned i;

	cradix_init(C, &ops);
	cradix_dump(C);
	for (i = 0; i < arraycount(nodes) - 2; i++) {
		N = cradix_insert(C, &nodes[i].cradix, NULL);
		assert(N == &nodes[i].cradix);
	}
	for (i = 0; i < arraycount(nodes) - 2; i++) {
		N = cradix_lookup(C, nodes[i].key);
		assert(N == &nodes[i].cradix);
	}
	for (i = 0; i < arraycount(nodes) - 2; i += 2) {
		N = cradix_delete_key(C, nodes[i].key, NULL);
		assert(N == &nodes[i].cradix);
	}
	for (i = 0; i < arraycount(nodes) - 2; i++) {
		N = cradix_lookup(C, nodes[i].key);
		if (i % 2)
			assert(N == &nodes[i].cradix);
		else
			assert(N == NULL);
	}
	N = cradix_insert(C, &nodes[arraycount(nodes) - 2].cradix, NULL);
	assert(N == &nodes[arraycount(nodes) - 2].cradix);
	assert(cradix_insert_begin(C, I));
	N = cradix_insert(C, &nodes[arraycount(nodes) - 1].cradix, I);
	assert(N == &nodes[arraycount(nodes) - 1].cradix);
	cradix_insert_end(C, I);
	cradix_dump(C);
	for (i = 1; i < arraycount(nodes) - 2; i += 2)
		cradix_delete(C, &nodes[i].cradix, NULL);
	cradix_delete(C, &nodes[arraycount(nodes) - 2].cradix, NULL);
	cradix_delete(C, &nodes[arraycount(nodes) - 1].cradix, NULL);
	cradix_destroy(C);
}

int
main(void)
{

	test_lookup_delete_empty();
	test_one_node();
	test_two_nodes();
	test_lookup_tombstone();
	test_collision();
	test_insert_post_nested();
	test_insert_pre_nested();
	test_refill_tombstone();
	test_pick_leaf_fallback();
	test_grow_from_tombstone();
	test_grow_shrink();
	test_delete_tombstone();
	test_custom_alloc();
	test_insert_begin_fail();
	test_iter_init_destroy();
	test_iter_begin_end();
	test_iter_prefix_init_destroy();
	test_iter_prefix_begin_end();

	test_misc();

	fflush(stdout);
	return ferror(stdout);
}