#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <elwix.h>
#include <sys/time.h>

struct blah {
	int n;
	RB_ENTRY(blah) node;
	SPLAY_ENTRY(blah) node1;
	AVL_ENTRY(blah) node2;
	SLIST_ENTRY(blah) node3;
	TAILQ_ENTRY(blah) node4;
};
RB_HEAD(rb_head, blah) rbh;
SPLAY_HEAD(sp_head, blah) sph;
AVL_HEAD(avl_head, blah) avlh;
SLIST_HEAD(, blah) slh;
TAILQ_HEAD(, blah) tqh;

static int
rb_cmp(struct blah *a, struct blah *b)
{
	int n = (a ? a->n : 0) - (b ? b->n : 0);

	if (!n)
		return 0;
	else if (n < 0)
		return -1;
	else
		return 1;
}

RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
RB_GENERATE(rb_head, blah, node, rb_cmp);
SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
AVL_GENERATE(avl_head, blah, node2, rb_cmp)


int
main()
{
	struct blah *b, *b2;
	register int i;
	struct timeval before, after;

	RB_INIT(&rbh);
	SPLAY_INIT(&sph);
	AVL_INIT(&avlh);
	SLIST_INIT(&slh);
	TAILQ_INIT(&tqh);
	srandom(getpid());

	gettimeofday(&before, NULL);
	for (i = 0; i < 1000000; i++) {
		b = malloc(sizeof(struct blah));
		memset(b, 0, sizeof(struct blah));
		b->n = random();
		if (RB_INSERT(rb_head, &rbh, b))
			free(b);
	}
	gettimeofday(&after, NULL);
	printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
	gettimeofday(&before, NULL);
	for (i = 0; i < 1000000; i++) {
		b = malloc(sizeof(struct blah));
		memset(b, 0, sizeof(struct blah));
		b->n = random();
		if (SPLAY_INSERT(sp_head, &sph, b))
			free(b);
	}
	gettimeofday(&after, NULL);
	printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	gettimeofday(&before, NULL);
	for (i = 0; i < 1000000; i++) {
		b = malloc(sizeof(struct blah));
		memset(b, 0, sizeof(struct blah));
		b->n = random();
		if (AVL_INSERT(avl_head, &avlh, b))
			free(b);
	}
	gettimeofday(&after, NULL);
	printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	gettimeofday(&before, NULL);
	for (i = 0; i < 1000000; i++) {
		b = malloc(sizeof(struct blah));
		memset(b, 0, sizeof(struct blah));
		b->n = random();
		SLIST_INSERT_HEAD(&slh, b, node3);
	}
	gettimeofday(&after, NULL);
	printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
	gettimeofday(&before, NULL);
	for (i = 0; i < 1000000; i++) {
		b = malloc(sizeof(struct blah));
		memset(b, 0, sizeof(struct blah));
		b->n = random();
		TAILQ_INSERT_HEAD(&tqh, b, node4);
	}
	gettimeofday(&after, NULL);
	printf("TAILQ::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	printf("---\n");

	b2 = malloc(sizeof(struct blah));
	gettimeofday(&before, NULL);
	for (i = 0; i < 10000; i++) {
		memset(b2, 0, sizeof(struct blah));
		b2->n = random();
		b = SPLAY_FIND(sp_head, &sph, b2);
		if (b)
			printf("SP::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
	}
	gettimeofday(&after, NULL);
	printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	printf("---\n");

	gettimeofday(&before, NULL);
	for (i = 0; i < 10000; i++) {
		memset(b2, 0, sizeof(struct blah));
		b2->n = random();
		b = RB_FIND(rb_head, &rbh, b2);
		if (b)
			printf("RB::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
	}
	gettimeofday(&after, NULL);
	printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	printf("---\n");

	gettimeofday(&before, NULL);
	for (i = 0; i < 10000; i++) {
		memset(b2, 0, sizeof(struct blah));
		b2->n = random();
		b = AVL_FIND(avl_head, &avlh, b2);
		if (b)
			printf("AVL::Found key %d %d-> %d next=%d prev=%d\n", i, b2->n, b->n, 
					AVL_NEXT(avl_head, &avlh, b) ? AVL_NEXT(avl_head, &avlh, b)->n : 0,
					AVL_PREV(avl_head, &avlh, b) ? AVL_PREV(avl_head, &avlh, b)->n : 0);
	}
	gettimeofday(&after, NULL);
	printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	printf("---\n");

	free(b2);

	gettimeofday(&before, NULL);
	while ((b = TAILQ_FIRST(&tqh))) {
		TAILQ_REMOVE(&tqh, b, node4);
		free(b);
	}
	gettimeofday(&after, NULL);
	printf("TAILQ::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
	gettimeofday(&before, NULL);
	while ((b = SLIST_FIRST(&slh))) {
		SLIST_REMOVE(&slh, b, blah, node3);
		free(b);
	}
	gettimeofday(&after, NULL);
	printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	gettimeofday(&before, NULL);
	AVL_FOREACH_SAFE(b, avl_head, &avlh, b2) {
		/*
		printf("aaa %p[%d] %p[%d] --- ", b, b ? b->n : 0, b2, b2 ? b2->n : 0);
		printf("b:%p %p /// ", b ? AVL_LEFT(b, node2) : b, b ? AVL_RIGHT(b, node2) : b);
		printf("b2:%p %p\n", b2 ? AVL_LEFT(b2, node2) : b2, b2 ? AVL_RIGHT(b2, node2) : b2); fflush(stdout);
		*/
		AVL_REMOVE(avl_head, &avlh, b);
		free(b);
	}
	gettimeofday(&after, NULL);
	printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	gettimeofday(&before, NULL);
	for (b = SPLAY_MIN(sp_head, &sph); b; b = b2) {
		b2 = SPLAY_NEXT(sp_head, &sph, b);
		SPLAY_REMOVE(sp_head, &sph, b);
	}
	gettimeofday(&after, NULL);
	printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);

	gettimeofday(&before, NULL);
	RB_FOREACH_SAFE(b, rb_head, &rbh, b2) {
		RB_REMOVE(rb_head, &rbh, b);
		free(b);
	}
	gettimeofday(&after, NULL);
	printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
	return !AVL_EMPTY(&avlh);
}