test.c

单比特树查找算法

#include <stdio.h>
#include <stdlib.h>
#include <arpa/inet.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <fcntl.h>
#include "one_bit.h"
#include "test.h"


int main(int argc, char *argv[])
{
	float timeuse = 0;
	struct timeval time_start,time_end;
//	entry entries[2000];
	entry *entries;
	entry *readentries;
	val32_t i,k,next_hop;
	val16_t entry_num = 0;
	char *file_name;
	val32_t pre[4], temp[4];
	val32_t readnum;
	entries = (entry *)malloc(1000000*sizeof(entry));
	readentries = (entry *)malloc(1000000*sizeof(entry));
	entry_num = read_entry(entries);
	if(entry_num > MAXTRAFFIC)
	{
		fprintf(stderr, "The traffic is too large.\n");
		return -1;
	}
#ifndef _DEBUG_
	fprintf(stderr, "the number is %d\n", entry_num);	
#endif
	for(i = 0; i < entry_num; i++)
	{
		construct_tree(entries[i].pre, entries[i].next_hop, entries[i].length);
	}
	for(i = 0; i < entry_num; i++)
	{
		next_hop = search_tree(entries[i].pre);
		if(next_hop != entries[i].next_hop)
			printf("error at %d\n", i);
	}
	readnum = read_traffic(readentries);
	if(entry_num > MAXTRAFFIC)
	{
		fprintf(stderr, "The traffic is too large.\n");
		return -1;
	}
	printf("begin search.....\n");
	gettimeofday(&time_start,NULL);
//	for(k = 0; k < 10; k++)
		for(i = 0; i < 1000000; i++)
			search_tree(readentries[i].pre);
	gettimeofday(&time_end,NULL);
	timeuse = (time_start.tv_sec - time_end.tv_sec)+((float)time_start.tv_usec - (float)time_end.tv_usec)/(1000000);
	printf("time use is %f\n",timeuse);
#ifndef _DEBUG_
//	fprintf(stderr, "leaf number is %d\n", leaf_num);
#endif
//	release_node(root);
//	get_storage();
//	printf("end_____________\n");
	free(readentries);
	free(entries);
}

int read_entry(entry *entries)
{
	char Buffer[256];
	uchar addr[16];
	val32_t tempaddr;
	int nentries = 0;
	FILE * ff;
	int length, next_hop, i, k;
	if (!(ff = fopen("BGPv6.tilab", "rb")))
   	{
     		exit(-1);
   	}
	while (fgets( Buffer, MLEN, ff))
   	{
   		char *p = strchr( Buffer , '/' ) ;
		if( !p )
		{
			 printf("[Error] Invalid Routing Table Entry\n" );
		}
		sscanf(p+1, "%i %d", &length, &next_hop);
		(*p) = '\0';
		entries[nentries].length = length;
		entries[nentries].next_hop = next_hop;
		if( 1 != inet_pton ( AF_INET6 , Buffer , addr))
		{
			printf("Error: Invalid IPv6 Address Prefix\n");
			return 0;
		}
		for(i = 0; i < 4; i++)
		{
			entries[nentries].pre[i] = 0;
			for(k = 0; k < 4; k++)
			{
				tempaddr = addr[4*i+k];
				tempaddr = tempaddr << 8*(3-k);
				entries[nentries].pre[i] |= tempaddr;
			}
		}
		nentries++;
	}//while
	return nentries;
}

val32_t read_traffic(entry *readentries)
{
	char Buffer[40];
	uchar addr[16];
	val32_t tempaddr;
	val32_t nentries = 0;
	FILE * ff;
	int length, next_hop, i, k;
	if (!(ff = fopen("tilab80.trfc", "rb")))
   	{
     		exit(-1);
   	}
	while(fscanf(ff, "%s", Buffer) != EOF)
//	while (fgets( Buffer, MLEN, ff))
   	{
		if( 1 != inet_pton ( AF_INET6 , Buffer , addr))
		{
			printf("Error: Invalid IPv6 Address Prefix\n");
			return 0;
		}
		for(i = 0; i < 4; i++)
		{
			readentries[nentries].pre[i] = 0;
			for(k = 0; k < 4; k++)
			{
				tempaddr = addr[4*i+k];
				tempaddr = tempaddr << 8*(3-k);
				readentries[nentries].pre[i] |= tempaddr;
			}
		}
		nentries++;
		}//while
	return nentries;
}