one_bit.c

单比特树查找算法

/*b_tree.c*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include "one_bit.h"

int leaf_num;
int inner_num;
int true_num;
int total_num;
int exist = 0;
int find = 0;
float timeuse;
struct timeval time_start,time_end;
int lnode_num = 0;
int ltrie_num = 0;
node_t *root;

int construct_tree(val32_t pre[4], val16_t next_hop, int length)
{
	node_t *tempnode;
	int i, pos, templength, level;
	if(root == NULL)
	{
		root = initialize_node(root);
		ltrie_num++;
	}
	tempnode = root;
	templength = level = 0;
	for(i = 0; i < 4; i++)
	{
		pos = 0;
		while(pos < MAXLENGTH)
		{
			if(length == templength)
			{
				if(tempnode->real_entry == TRUE) 
					exist++;
				tempnode->len = length;
				tempnode->level = level;
				tempnode->nh = next_hop;
				tempnode->real_entry = TRUE;
				copy(pre, tempnode->prefix);
				return total_num;
			}
			if(bit_value(pre[i], pos) == 0)
			{
				if(tempnode->lchild == NULL)
				{
					tempnode->lchild = initialize_node(tempnode->lchild);
					ltrie_num++;
					total_num++;
				}
				tempnode = tempnode ->lchild;
			}
			else if(bit_value(pre[i], pos) == 1)
			{
				if(tempnode->rchild == NULL)
				{
					tempnode->rchild = initialize_node(tempnode->rchild);
					ltrie_num++;
					total_num++;
				}
				tempnode = tempnode->rchild;
			}	
			pos++;
			templength++;
			level++;
		}//end while
	}//end for
}

node_t * initialize_node(node_t *treenode)
{
	treenode = (node_t *)malloc(sizeof(node_t));
	memset(treenode, 0, sizeof(node_t));
	treenode->nh = DEFAULT_NH;
	return treenode;
}

void stat()
{
	int i;
	val8_t length, next_hop;
	val32_t * prefix;
	leaf_num = 0;
	inner_num = 0;
	true_num = 0;
	printf("construct num is %d,exist num is %d\n",total_num, exist);
	total_num = 0;
	traverse_tree(root);
	fprintf(stderr, "leaf_num is %d, true_num is %d,total_num is %d\n", leaf_num, true_num,total_num);
}

val8_t search_tree(val32_t *prefix)
{
	node_t *tempnode;
	tempnode = root;
	int i = 0;
	val8_t next_hop = 0;
	while(tempnode != NULL)
	{
		if(tempnode->real_entry == TRUE)
			next_hop = tempnode->nh;
		if(bit_value6(prefix, i) == 0)
			tempnode = tempnode->lchild;
		else 
			tempnode = tempnode->rchild;
		i++;
	}
	return next_hop;
}

bool traverse_tree(node_t *tree_node)
{
	if(tree_node != NULL)
	{
		if(tree_node->real_entry == TRUE)
		{
			true_num++;
			if((tree_node->lchild == NULL)&&(tree_node->rchild == NULL))
			{
				leaf_num++;
			}
			else
			{
				inner_num++;
			}
		}
		total_num++;
		if(traverse_tree(tree_node->lchild))
			if(traverse_tree(tree_node->rchild))
				return TRUE;
		return FALSE;
	}
	else
		return TRUE;
}

bool bit_value(val32_t prefix, int position)
{
	val32_t temp = 1;
	prefix = prefix >> (MAXLENGTH - position - 1);
	return prefix & temp;
}

bool bit_value6(val32_t *prefix, int position)
{
	val32_t temp_pre, temp = 1;
	int i, k;
	i = (position >> 5);
//	i = position / 32;
	k = position % 32;
	temp_pre = prefix[i] >> (MAXLENGTH - k - 1);
	return temp_pre & temp;
}

val32_t *copy(val32_t *prefix, val32_t *result)
{
	int i;
	for( i = 0; i < 4; i++)
		result[i] = prefix[i];
	return result;
}

int compare(val32_t *pre1, val32_t *pre2)
{
	int i;
	for(i = 0; i < 4; i++)
	{
		if(pre1[i] > pre2[i])
			return 1;//pre1>pre2
		else if(pre1[i] < pre2[i])
			return -1;//pre1<pre2
	}
	return 0;//pre1==pre2
}