#include <patricia.h>
#include <string.h>

static struct patriciaNode_t *root;
static struct patriciaNode_t *newNode;

static struct patriciaNode_t *patriciaSearch(struct patriciaNode_t *node, char *str);
static struct patriciaNode_t *patriciaInsert(struct patriciaNode_t *node, char *str, uint32t val);

void patriciaInit(void *mem) {
	newNode= mem;
}

struct patriciaNode_t *patriciaDeinit() {
	return root;
}

void *patriciaGetEndMem() {
	return newNode;
}

void patriciaInsertStr(char *str, uint32t val) {
	struct patriciaNode_t *new;
	
	if(unlikely(root == 0)) {
		new= root= newNode++;
		
		new->left= new;
		new->right= new;
		new->bit= 0;
		new->str= str;
		new->value= val;
	} else {
		patriciaInsert(root,str,val);
	}
}

uint32t patriciaGetValue(char *str) {
	struct patriciaNode_t *node;
	
	if(likely(root != 0))
		node= patriciaSearch(root,str);
	else
		return 0;
			
	if(likely(strcmp(node->str,str) == 0))
		return node->value;
	else
		return 0;
}

struct patriciaNode_t *patriciaSearch(struct patriciaNode_t *node, char *str) {
	struct patriciaNode_t *parent;
	uint32t maxBit= ((strlen(str) + 1) << 3) - 1;
	
	do {
		parent= node;
		
		if(getBits(str,node->bit) == 0)
			node= node->left;
		else
			node= node->right;
		
		if(unlikely(node->bit > maxBit)) {
			node= parent;
			break;
		}
	} while(likely(parent->bit < node->bit));
	
	return node;
}

struct patriciaNode_t *patriciaInsert(struct patriciaNode_t *node, char *str, uint32t val) {
	struct patriciaNode_t *new, *parent;
	uint32t i;
	
	new= patriciaSearch(node,str);
	
	if(unlikely(strcmp(new->str,str) == 0))
		return 0;
	
	i= new->bit + 1;
	
	while(likely(getBits(str,i) == getBits(new->str,i)))
		i++;
	
	do {
		parent= node;
		
		if(getBits(str,node->bit) == 0)
			node= node->left;
		else
			node= node->right;
	} while(likely(node->bit < i && parent->bit < node->bit));
	
	new= newNode++;
	
	new->bit= i;
	new->str= str;
	new->value= val;
	
	if(getBits(str,i) == 0) {
		new->left= new;
		new->right= node;
	} else {
		new->left= node;
		new->right= new;
	}
	
	if(getBits(str,parent->bit) == 0)
		parent->left= new;
	else
		parent->right= new;
	
	return new;
}