#include <u.h>
#include <libc.h>
#include "trie.h"

enum {
	Keysize = 32
};

static void
printallocs(void)
{
	print("trieallocs=%d\n", trieallocs);
}

static void
add(Trie *t, Rune *key, void *val, void *old)
{
	void *v;

	print("add \"%S\"\n", key);
	v = trieadd(t, key, val);
	assert(v == old);
}

static void
get(Trie *t, Rune *key, void *val)
{
	void *v;

	print("get \"%S\"\n", key);
	v = trieget(t, key);
	assert(v == val);
}

static void
del(Trie *t, Rune *key, void *old)
{
	void *v;

	print("del \"%S\"\n", key);
	v = triedel(t, key);
	assert(v == old);
}

static void
walk(Triewalk *w)
{
	void *v;

	print("walk:\n");

	while(v = trienext(w))
		print("key=\"%S\" val=\"%S\"\n", w->key, v);
}

void
main(void)
{
	/* unique strings */
	Rune *words[] = { L"one", L"two", L"three", L"four", L"five",
	                  L"six", L"seven", L"eight", L"nine", L"" };
	Rune key[Keysize+1], *k, *v;
	Trie *t;
	Triewalk w;
	int i, n, free;

	/*triedebug++;*/
	n = nelem(words);
	free = 1;
start:
	print("create trie\n");
	t = triealloc();
	assert(trieallocs == 1);
	printallocs();

	for(i = 0; i < n; i++){
		k = v = words[i];
		add(t, k, v, nil);
	}
	printallocs();

	if(free--){
		print("free trie\n");
		triefree(t);
		assert(trieallocs == 0);
		printallocs();
		goto start;
	}
	for(i = 0; i < n; i++){
		k = v = words[i];
		add(t, k, v, v);
	}
	for(i = 0; i < n; i++){
		k = v = words[i];
		get(t, k, v);
	}
	triewalk(t, &w, key, nelem(key));

	walk(&w);

	for(i = 0; i < n; i += 2){
		k = v = words[i];
		del(t, k, v);
	}
	printallocs();

	for(i = 0; i < n; i += 2){
		k = words[i];
		get(t, k, nil);
		del(t, k, nil);
	}
	walk(&w);

	for(i = 1; i < n; i += 2){
		k = v = words[i];
		del(t, k, v);
	}
	walk(&w);

	assert(trieallocs == 1);
	print("free trie\n");
	triefree(t);
	assert(trieallocs == 0);
	printallocs();
	exits(0);
}