/*
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的內(nèi)存空間沒有釋放，釋放它的空間
	//修改時間：08.2.28
	free(original_filters);
	//讀取規(guī)則的過程:首先在函數(shù)read_filters()從文件中讀取規(guī)則庫，數(shù)據(jù)結(jié)構(gòu)是FilteList,是鏈表形式的，
	//然后在函數(shù)transform_filter,將鏈表形式的規(guī)則庫轉(zhuǎn)化為數(shù)組形式的，數(shù)據(jù)結(jié)構(gòu)是original_filter的，返回函數(shù)main
	//第三步又將數(shù)組形式的規(guī)則庫轉(zhuǎn)化為范圍形式的鏈表規(guī)則，數(shù)據(jù)結(jié)構(gòu)是filter,main函數(shù)運(yùn)行到此處
	//hyper函數(shù)運(yùn)行hypercuts算法
	hyper(filters); 
	
#ifdef information_2
	t = time(NULL);
	area = localtime(&t);
	// printf("Local time is: %s", asctime(area));
#endif
	return 0;
}

//函數(shù)p_node()打印樹的結(jié)構(gòu)到文件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);
		}
	}
	
}

//函數(shù)sapce_node()打印樹的結(jié)構(gòu)到文件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);
	}
	
}

//返回?cái)?shù)據(jù)包中數(shù)據(jù)包頭的個數(shù)
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讀取到下一條規(guī)則的開始處@，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()函數(shù)的作用是將新規(guī)則filters對一個新的類型是id_list的內(nèi)存進(jìn)行賦值,然后加入到head的末尾
	for (filter *head=filters; head!=NULL; head=head->next)
		filter_lists=add_id_list(filter_lists, head);
	
	UINT id_list_count(id_list *);
	
	//為了計(jì)算初始化的時間，將這句輸出語句隱去
	//修改時間: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);
	//本函數(shù)運(yùn)行在此之前為建樹過程
	second = clock(); 
	duration1 = (double)(second-first); 
	int level=0;
	#ifdef DEBUG 
	p_node(root,level);
	#endif
    //空間是怎么計(jì)算？
	//	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);
	//函數(shù)space_node()返回樹的空間，以byte計(jì)算
	
	//	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");
	//先計(jì)算下有多少數(shù)據(jù)包，再分 配空間
     
	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++;