#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <time.h>
#define INPUT_PORT (50000)
#define OUTPUT_PORT (50001)
#define LOCAL_ADDRESS ("127.0.0.1")
#define MAX_MSG_LEN (200)
#define TREE_NODE_MAX (32)
#define T1_MAX (32) // 5bit
#define T2_MAX (4) // 2bit
#define T3_MAX (4) // 2bit
#define T4_MAX (4) // 2bit
#define T1_BRANCH_NUM (12) // < 32
#define T2_BRANCH_NUM (2) // < 4
#define T3_BRANCH_NUM (2) // < 4
#define T4_BRANCH_NUM (2) // < 4
#define PORT_MAX (8)
typedef struct treeArray{
//data
int port;
int field;//5-2-2-2,所以field的取值0~31或0~3，把char类型数字直接转化位数字存储了
//int fieldBitNum;
//tree message
int childCount;
struct treeArray *child[TREE_NODE_MAX];
struct treeArray *parent;
}treeNode,*pTreeNode;
typedef struct packetArray {
char ip_dest[4][9];
char ip_source[4][9];
short int dataLength;
char data[100];
int frameCheck;
int fromPort;
int toPort;
int sequenceNum;
int portSequenceNum;
int timer;
}packet;
void buildRandomTree(treeNode *pRoot);
void creatNOTRepeatarray(int *array,int num,int t_max);
void addRandomTreeNode(int layer1,int layer2,int layer3,int layer4,int randPort1,int randPort2,int randPort3,int randPort4/*,int prefix*/,treeNode *pRoot);
void add_address(int *IP_txt,int prefixtxt,int porttxt,treeNode *pRoot);
treeNode *InsertNode(treeNode *ppNode,int field,int port,int *isExist);
treeNode *findNode(treeNode *pNode,int field,int *step);
int search(char ip_addr[4][9],treeNode *pRoot,int *step);
int bin2dec(char *binary);
int main()
{
struct sockaddr_in genOUT_addr; // client info (generator) variable, data given when received message
struct sockaddr_in clasIN_addr; // struct for incoming packets
struct sockaddr_in clasOUT_addr; // struct for outgoing packets
packet recvPacket;
int socketIN,socketOUT,recvMsgLen,genAddrLen;
treeNode *pRoot;
FILE *file;
int IP_txt[4],prefixtxt,porttxt;
int sequence[PORT_MAX]={0},port,step;
srand((unsigned) time(NULL));
pRoot = (treeNode *)malloc(sizeof(treeNode));
pRoot->childCount = 0;
if((socketIN = socket(AF_INET, SOCK_DGRAM, 0)) < 0){
printf("socket error\n");
return (0);
}
if((socketOUT = socket(AF_INET, SOCK_DGRAM, 0)) < 0){
printf("socket error\n");
return (0);
}
// Construct address structure
bzero((char *)&clasIN_addr, sizeof(clasIN_addr)); // zeroes out struct before data copied
clasIN_addr.sin_family = AF_INET; // specifies Address Family
clasIN_addr.sin_addr.s_addr = htonl(INADDR_ANY); // accept from any network interface
clasIN_addr.sin_port = htons(INPUT_PORT); // Using port 50000 /*TODO:题目指定端口号了吗？？*/
bzero((char *)&clasOUT_addr,sizeof(clasOUT_addr));
clasOUT_addr.sin_family = AF_INET;
clasOUT_addr.sin_addr.s_addr = inet_addr(LOCAL_ADDRESS); // Connect to local address
clasOUT_addr.sin_port = htons(OUTPUT_PORT); // output port 50001 /*TODO:题目指定端口号了吗？？*/
if((bind(socketIN, (struct sockaddr *)&clasIN_addr, sizeof(clasIN_addr))) < 0){
printf("bind failed\n");
}
buildRandomTree(pRoot);//建立随机数 的多叉树
//插入clasEntry.txt的节点到多叉树
file = fopen("clasEntry.txt", "r");
if(file == NULL){
printf("clasEntry.txt open file ,system return\n");
return;
}
fscanf(file, "Destination:%i.%i.%i.%i Prefix:%i Port:%i", &IP_txt[0], &IP_txt[1], &IP_txt[2], &IP_txt[3], &prefixtxt, &porttxt);
printf("Destination:%d.%d.%d.%d Prefix:%d Port:%d\n", IP_txt[0], IP_txt[1], IP_txt[2], IP_txt[3], prefixtxt, porttxt);
fclose(file);
add_address(IP_txt,prefixtxt,porttxt,pRoot);
//循环接收消息，到多叉树中寻找匹配节点的port
while(1) {
if((recvMsgLen = recvfrom(socketIN, &recvPacket, MAX_MSG_LEN, 0, (struct sockaddr *) &genOUT_addr, &genAddrLen)) > 0){
printf("recvfrom() failed\n");
}
port = search(recvPacket.ip_dest,pRoot,&step);
printf(" takes%d steps,IP desk:%d.%d.%d.%d",step,bin2dec(recvPacket.ip_dest[0]),bin2dec(recvPacket.ip_dest[1]),bin2dec(recvPacket.ip_dest[2]),bin2dec(recvPacket.ip_dest[3]) );
printf(" packet %i will be directed to port %i\n",recvPacket.sequenceNum, port);
recvPacket.toPort = port;
sequence[port]++;
recvPacket.portSequenceNum = sequence[port];
if(sendto(socketOUT, &recvPacket, MAX_MSG_LEN, 0, (struct sockaddr *)&clasOUT_addr, sizeof(clasOUT_addr)) != MAX_MSG_LEN){
printf("sendto() failed");
}
}
}
/*创建数组，每产生一个随机数，和前边所有值比对出，如果不重复的话添加到数组中*/
void creatNOTRepeatarray(int *array,int num,int t_max) //head file
{
int tmp,arrayNum=0,i;
int isRepeat=0;//0:false,1:true
usleep(200);//srand时间间隔太短，获取的时间种子可能会相同，导致随机数结果相同，所以使用usleep等待200ms拉成每次srand的时间间隔)
srand((unsigned) time(NULL));
array[0] = rand()%t_max;//产生第一个随机数
arrayNum++;//记录产生随机数的个数
while(arrayNum < num){
isRepeat = 0;
tmp = rand()%t_max;//继续产生随机数
for(i=0;i<arrayNum;i++){//遍历数组，是否有重复的
if(tmp == array[i])
isRepeat = 1;
break;
}
if(isRepeat != 1){ //not repeat，把产生的随机数放到数组中
array[arrayNum] = tmp;
arrayNum++;
}
}
}
void addRandomTreeNode(int layer1,int layer2,int layer3,int layer4,int randPort1,int randPort2,int randPort3,int randPort4/*,int prefix*/,treeNode *pRoot)
{
treeNode *prev,*prev2,*prev3,*prev4,*pLocalRoot=pRoot;
int findFlag = 0,isExist;
int i;
//if(tmpPrefix>2){
//tmpPrefix = 1;//*由于5-2-2-2只有11位，强制profix=1,(题外话：实际已经没什么所用了，暂时忽略，有要求再加)*/
//}else if(tmpPrefix == 0){//prefix=0即不需要保存任何数据
//return;
//}*/
prev = InsertNode(pLocalRoot,layer1,randPort1,&isExist);
prev2 = InsertNode(prev,layer2,randPort2,&isExist);
prev3 = InsertNode(prev2,layer3,randPort3,&isExist);
prev4 = InsertNode(prev3,layer4,randPort4,&isExist);
printf("add random node:%d(%d),%d(%d),%d(%d),%d(%d)\n",layer1,randPort1,layer2,randPort2,layer3,randPort3,layer4,randPort4);
}
void buildRandomTree(treeNode *pRoot)
{
int randArray1[T1_BRANCH_NUM],randArray2[T2_BRANCH_NUM],randArray3[T3_BRANCH_NUM],randArray4[T4_BRANCH_NUM];
int t1=T1_BRANCH_NUM,t2=T2_BRANCH_NUM,t3=T3_BRANCH_NUM,t4=T4_BRANCH_NUM;
int branch1,branch2,branch3,branch4,rand1,rand2,rand3,rand4;
int port1,port2,port3,port4,prefix,count=0;
treeNode *pLocalRoot=pRoot;
//randArray1[]为产生的前5位 对应随机数，下边一次类推
memset(randArray1,0,sizeof(randArray1[T1_BRANCH_NUM]));
creatNOTRepeatarray(randArray1,T1_BRANCH_NUM,T1_MAX);
for(branch1 = 0;branch1 < T1_BRANCH_NUM;branch1++){
port1 = rand()%PORT_MAX;
//prefix = rand()%4;
memset(randArray2,0,sizeof(randArray2));
creatNOTRepeatarray(randArray2,T2_BRANCH_NUM,T2_MAX);
for(branch2 = 0;branch2 < T2_BRANCH_NUM;branch2++){
port2 = rand()%PORT_MAX;
memset(randArray3,0,sizeof(randArray3[T3_BRANCH_NUM]));
creatNOTRepeatarray(randArray3,T3_BRANCH_NUM,T3_MAX);
for(branch3 = 0;branch3 < T3_BRANCH_NUM;branch3++){
port3 = rand()%PORT_MAX;
memset(randArray4,0,sizeof(randArray4[T4_BRANCH_NUM]));
creatNOTRepeatarray(randArray4,T4_BRANCH_NUM,T4_MAX);
for(branch4 = 0;branch4 < T4_BRANCH_NUM;branch4++){
port4 = rand()%PORT_MAX;
count++;
printf("count:%3d=====",count);
addRandomTreeNode(randArray1[branch1],randArray2[branch2],randArray3[branch3],randArray4[branch4],port1,port2,port3,port4/*,prefix*/,pLocalRoot);
}
}
}
}
}
void add_address(int *IP_txt,int prefixtxt,int porttxt,treeNode *pRoot)
{
int layer1,layer2,layer3,layer4;
treeNode *prev,*prev2,*prev3,*prev4,*pLocal
