#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include "rbtree.h"

typedef unsigned int	CORE_ADDR;
typedef struct rb_addr_s {	rb_node_t	rb_node;
	CORE_ADDR	addr;}rb_addr_t;

static inline rb_addr_t *
rb_find_addr_struct(CORE_ADDR addr, rb_root_t *root, rb_node_t **ret_parent, rb_node_t ***ret_link)
{
	rb_node_t	**link = &root->rb_node;	rb_node_t	*parent = NULL;
	rb_addr_t	*rb_addr = NULL;
	rb_addr_t	*ret_rb_addr = NULL;

	while (*link) {
		parent = *link;
		rb_addr = rb_entry(parent, rb_addr_t, rb_node);

		if (addr < rb_addr->addr) {
			link = &(*link)->rb_left;
		}
		else if (addr > rb_addr->addr) {
			link = &(*link)->rb_right;
		}
		else {
			ret_rb_addr = rb_addr;
			break;
		}
	}
	if (ret_parent) {
		*ret_parent = parent;
	}
	if (ret_link) {
		*ret_link = link;
	}

	return(ret_rb_addr);
}

int
rb_insert_addr(CORE_ADDR addr, rb_root_t *root)
{
	rb_node_t	**rb_link;	rb_node_t	*rb_parent;
	rb_addr_t	*rb_addr = NULL;

	if (rb_find_addr_struct(addr, root, &rb_parent, &rb_link)) {
		return(-1);
	}
	rb_addr = (rb_addr_t *)malloc(sizeof(rb_addr_t));
	if (!rb_addr) {
		return(-1);
	}
	rb_addr->addr = addr;
	rb_link_node(&rb_addr->rb_node, rb_parent, rb_link);
	rb_insert_color(&rb_addr->rb_node, root);

	return(0);
}

int
rb_remove_addr(CORE_ADDR addr, rb_root_t *root)
{
	rb_addr_t	*rb_addr = rb_find_addr_struct(addr, root, NULL, NULL);

	if (!rb_addr) {
		return(-1);
	}
	rb_erase(&rb_addr->rb_node, root);
	free(rb_addr);

	return(0);
}

static inline int
rb_find_addr(CORE_ADDR addr, rb_root_t *root)
{
	rb_node_t	**link = &root->rb_node;	rb_node_t	*parent = NULL;
	rb_addr_t	*rb_addr;

	while (*link) {
		parent = *link;
		rb_addr = rb_entry(parent, rb_addr_t, rb_node);

		if (addr < rb_addr->addr) {
			link = &(*link)->rb_left;
		}
		else if (addr > rb_addr->addr) {
			link = &(*link)->rb_right;
		}
		else {
			return(1);
		}
	}

	return(0);
}

int
main(int argc,char *argv[], char *envp[])
{
	rb_root_t	addr_root;

	addr_root = RB_ROOT;

	//right insert
	printf("right insert\n");
	if (rb_insert_addr(0x1, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xc0028018, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xd014cb68, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x74697277, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xc00959f8, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x959f8, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xe3740ffa, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x31321, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x765702, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xf123, &addr_root)) {
		printf("rb_insert_addr error\n");
	}

	//wrong insert
	printf("wrong insert\n");
	if (rb_insert_addr(0x1, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xc0028018, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xd014cb68, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x74697277, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xc00959f8, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x959f8, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xe3740ffa, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x31321, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x765702, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xf123, &addr_root)) {
		printf("rb_insert_addr error\n");
	}

	//right find
	printf("right find\n");
	if (rb_find_addr(0x1, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xc0028018, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xd014cb68, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0x74697277, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xc00959f8, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0x959f8, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xe3740ffa, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0x31321, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0x765702, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xf123, &addr_root)) {
		printf("rb_find_addr ok\n");
	}

	//wrong find
	printf("wrong find\n");
	if (rb_find_addr(0x0, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xc002801, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xd014cb6, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0x7469727, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xc00959f, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0x959f, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xe3740ff, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0x3132, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0x76570, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xf12, &addr_root)) {
		printf("rb_find_addr error\n");
	}

	//right remove
	printf("right remove\n");
	if (rb_remove_addr(0x1, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xc0028018, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xd014cb68, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x74697277, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xc00959f8, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x959f8, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xe3740ffa, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x31321, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x765702, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xf123, &addr_root)) {
		printf("rb_remove_addr error\n");
	}

	//wrong remove
	printf("wrong remove\n");
	if (rb_remove_addr(0x1, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xc0028018, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xd014cb68, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x74697277, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xc00959f8, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x959f8, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xe3740ffa, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x31321, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x765702, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xf123, &addr_root)) {
		printf("rb_remove_addr error\n");
	}

	return(0);
}