/*
The code is contructed by Borland C++ v5.02 and C++ BuilderX.
I hope to release a GCC version in a short time.
The file formats of filter database and trace are come from ClassBench.

  There are five parameters to control the construction of decision tree.
  
1) common_filter_extraction (defined in hyper.h)
	The most important optimization skill in HyperCuts. It extracts the common filters in all branches.
	To avoid a long filter list for linear search, we apply the common_bucket_size to restrict its maximal length.
	
	Also, we force to generate cuts on multiple dimensions as the number of filters is large.
	This is because adopting only one-dimensional cuts might incur replication of a huge number of filters with wildcard on that dimension.
	Applying cuts on both dimensions could alleviate such condition.
	  
2) redundant_removal (defined in hyper.h)
	If the categoried filters in different branches are identical, these two branches are merged.
	However, the space corresponding to these filters are augumented.
	In the worst case, the resulted space might be identical to the original space before performing cutting.
	In such a case, we should abort the construction since the phenomenon will result in an infinite loop.
		
	In our experiments, the optimization may cause a performance degradation since the occupied space of
	the resulted filters cannot be reduced fast.
		  
3) cut_threshold (defined in hyper.h)
   If the number of cuts is less than cut_threshold, the construction procedure is stopped.
			
4) spfac (input by argument)
	Space factor, control the maximal number of generated branches.
			  
5) common_bucket_size (input by argument)
	Control the maximal number of filters in bucket. These filters are searched by using linear search.
				
The region compaction is also implemented in the codes; however, it seems not very effective.
				  
	If you have any idea to improve our codes, please let me know! Thank you.
	My email address is: pcwang@csie.nctu.edu.tw
*/

#include "hyper.h"

#define information_2

UINT node_count=0, branch_count=0, filters_count=0, spfac, common_bucket_size;
char *filter_file, *trace_file;

int main(int argc, char * argv[]) {
	int i, j;
	void hyper(filter *);
	filter *filters=NULL, *current;
	original_filter *original_filters;
	
	if ( argc <5) {
	printf("Execution: hyper.exe spfac common_bucket_size filter trace\n\n");
	printf("For example: hyper.exe 1 64 filter.txt filter.txt_trace");
	return 0;
	}
	
	  spfac = atoi(argv[1]);
	  common_bucket_size =atoi(argv[2]);
	  filter_file=argv[3];
	  trace_file=argv[4];
	
	
/*	spfac = 1;
	common_bucket_size =72;
	filter_file="my.rtf";
	trace_file="my_trace.rtf";
*/	
	/*if ( argc > 1 ) {
	spfac = atoi( argv[1] );
	if ( argc > 2)
	common_bucket_size =atoi(argv[2]);
	else
	common_bucket_size =0;
	}
	else {
	spfac = 1;
	common_bucket_size =64;
	}
	*/
#ifdef information_2
	time_t t;
	struct tm * area;
	t = time( NULL );
	area = localtime( & t );
	// printf( "Parameter:  spfac %d, common bucket size %d\n", spfac, common_bucket_size );
	// printf( "Size of each filter: %d, header: %d", sizeof( original_filter ), sizeof( header ) );
	//  printf( ", local time is: %s", asctime( area ) );
#endif
	
	original_filter *transform_filter(int *);
	original_filters=transform_filter(&i);
	
	// Transfer the filter format of ClassBench into a generalized form
	for (j=0; j<i; j++) {
		if (filters==NULL) {
			filters=(filter *)calloc(1, sizeof(filter));
			current=filters;
		}
		else {
			current->next=(filter *)calloc(1, sizeof(filter));
			current=current->next;
		}
		current->start[0]=original_filters[j].sa;
		current->end[0]=original_filters[j].sa+pow(2, 32-original_filters[j].sa_len)-1;
		current->start[1]=original_filters[j].da;
		current->end[1]=original_filters[j].da+pow(2, 32-original_filters[j].da_len)-1;
		current->start[2]=original_filters[j].sp[0];
		current->end[2]=original_filters[j].sp[1];
		current->start[3]=original_filters[j].dp[0];
		current->end[3]=original_filters[j].dp[1];
		
		if (original_filters[j].prot_num > 0)
			current->start[4]=current->end[4]=original_filters[j].prot_num;
		else {
			current->start[4]=0;
			current->end[4]=255;
		}
		
		if (original_filters[j].flags_mask > 0)
			current->start[5]=current->end[5]=original_filters[j].flags;
		else {
			current->start[5]=0;
			current->end[5]=65535;
		}
	}
	
	UINT k=0;
	for (current=filters; current!=NULL; current=current->next) {
		current->id=k;
		k++;
	}
	printf( "Parameter:  spfac %d, common bucket size %d\n", spfac, common_bucket_size );
	//  printf("Original Filters: %d, Current Filters: %d, ", i, k);
	//original_filter的內存空間沒有釋放，釋放它的空間
	//修改時間：08.2.28
	free(original_filters);
	//讀取規則的過程:首先在函數read_filters()從文件中讀取規則庫，數據結構是FilteList,是鏈表形式的，
	//然后在函數transform_filter,將鏈表形式的規則庫轉化為數組形式的，數據結構是original_filter的，返回函數main
	//第三步又將數組形式的規則庫轉化為范圍形式的鏈表規則，數據結構是filter,main函數運行到此處
	//hyper函數運行hypercuts算法
	hyper(filters); 
	
#ifdef information_2
	t = time(NULL);
	area = localtime(&t);
	// printf("Local time is: %s", asctime(area));
#endif
	return 0;
}

//函數p_node()打印樹的結構到文件node.txt中
//修改時間：3月3日
void  p_node(struct node *nodes,int level)
{
	struct node *cnodes;
	FILE * fp;
	int i=0,totalcuts=1;
	id_list *fs;
	
	if (!nodes)
		return ;
	if(nodes)
	{   
		fp=fopen("node.txt","a");
		totalcuts=1;
		fprintf(fp,"level:%d \n",level++);
		fprintf(fp,"filter count:%d \n",nodes->filter_count);
		if(nodes->rectangle)
			fprintf(fp,"rectangle:%u %u %u %u\n",nodes->rectangle->start[0],nodes->rectangle->end[0],nodes->rectangle->start[1],nodes->rectangle->end[1]);
		for(i=0;i<2;i++)
		{
			fprintf(fp,"region:%u %u %u\n",nodes->start[i],nodes->end[i],nodes->cut[i]);
			totalcuts=totalcuts*nodes->cut[i];
		}
		for(fs=nodes->filters;fs;fs=fs->next)
			fprintf(fp,"%d\t",fs->id);
		fprintf(fp,"totalcuts:%d\n",totalcuts);
		fclose(fp);
		cnodes=nodes;
		for(i=0;i<totalcuts;i++)
		{   
			nodes=cnodes->branch[i];
			p_node(nodes,level);
		}
	}
	
}

//函數sapce_node()打印樹的結構到文件node.txt中
//修改時間：3月3日
void space_node(struct node *nodes,long int &space)
{
	struct node *cnodes;
	int i=0,totalcuts=1;
	struct id_list *list,*L;
	struct filter *fs,*F;
	int count_l=0,count_f=0;
	if (!nodes)
	 	return;
	else 
	{   
		space=space+sizeof(node);
		totalcuts=1;
	
		count_l=0;
		count_f=0;
		for(list=nodes->filters;list;)
		{  
			count_l++;
			for(fs=list->filters;fs;)
			{
			count_f++;	F=fs;fs=fs->next;
			//free(F);
			}
			L=list;
			list=list->next;
		//	free(L); 
		}
		space=space+sizeof(id_list)*count_l+sizeof(filter)*count_f;
		if(nodes->rectangle)
		space=space+sizeof(hyper_rectangle);
		for(i=0;i<DIMENSIONS;i++)
		{
			totalcuts=totalcuts*nodes->cut[i];
		}
		cnodes=nodes;
		if(nodes->branch)
		{for(i=0;i<totalcuts&&totalcuts!=1;i++)
		{   
			if(nodes=cnodes->branch[i])
			space_node(nodes,space);
			else{ space=space+sizeof(node *); }
		}}
	//	free(nodes->branch);
	//	free(nodes);
	}
	
}

//返回數據包中數據包頭的個數
int count_f(const char *filename)
{	
	char ch ;
    FILE *fp;
	int count=0;	
	
	fp=fopen(filename, "r");
	if (!fp) 
	{
		printf("filename error!\n");
		return 0;
	}
	
	ch='\0';
	
	//讀取文件，直到讀到文件末尾，文件類型是文本文件
	while (ch!=EOF)
	{   
		ch=fgetc(fp);
		if(ch=='\n') count++;//buffer讀取到下一條規則的開始處@，buffer最后一位賦值'0'	
	}
	fclose (fp);
//	printf("%d\n",count);
	return count;	
}
// The function repeatedly divide the filters into different groups according to different criterion.
void hyper(filter *filters) {
	UINT i;
	node *root, *tree_construction(id_list *, hyper_rectangle, UINT);
	//   filter *current;
	UINT filter_count(filter *), original=filter_count(filters);
	id_list *filter_lists=NULL, *add_id_list(id_list *head, filter *filters);
	
	clock_t first,second,third,forth; 
	double duration1=0,duration2=0; 
	
	first = clock(); 
	//add_id_list()函數的作用是將新規則filters對一個新的類型是id_list的內存進行賦值,然后加入到head的末尾
	for (filter *head=filters; head!=NULL; head=head->next)
		filter_lists=add_id_list(filter_lists, head);
	
	UINT id_list_count(id_list *);
	
	//為了計算初始化的時間，將這句輸出語句隱去
	//修改時間:08.2.28
	//	printf("id list count: %d", id_list_count(filter_lists));
	//初始化
	hyper_rectangle rectangle;
	for (i=0; i<DIMENSIONS; i++) {
		rectangle.start[i]=0;
		rectangle.end[i]=0xffffffff;
	}
	root=tree_construction(filter_lists, rectangle, 1);
	//本函數運行在此之前為建樹過程
	second = clock(); 
	duration1 = (double)(second-first); 
	int level=0;
	#ifdef DEBUG 
	p_node(root,level);
	#endif
    //空間是怎么計算？
	//	printf("Node count: %d, branch count: %d, filter count: %d (Storage: %d Kbytes)\n", node_count, branch_count, filters_count, (node_count*32+branch_count*4+filters_count*16)/1024);
	//函數space_node()返回樹的空間，以byte計算
	
	//	UINT decision_tree_depth(node *, UINT);
	//   printf(", depth: %d", decision_tree_depth(root, 1));

	/******************************************************************************/
	/* Read the trace file generated by trace_generator.*/
	void trace_evaluation(header *, UINT, node *);
	//  struct stat statbuf;
	FILE *fd;
    int count_head=count_f(trace_file);
//	printf("%d\n",count_head);
	fd=fopen(trace_file, "rt");
	//先計算下有多少數據包，再分 配空間
     
	header *trace=NULL;
	if(count_head) trace=(header *)calloc(count_head, sizeof(header));
	i=0;
	UINT temp;
	while (fscanf(fd, "%d %d %d %d %d %d %d", &trace[i].value[0], &trace[i].value[1], &trace[i].value[2],
		&trace[i].value[3], &trace[i].value[4], &trace[i].value[5], &temp) != EOF)
		i++;