基于二叉树实现路由匹配算法

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

struct node {
	struct node *left;
	struct node *right;
	char *gateway;
};

void buildtree(struct node *root, char *rule);
void ruleSplit(char *rule, int *dest, int *masklen, char *gw);
int ipparser(const char *dststr);
void route(struct node *root, const char *to, char *dst);

int main(int argc, char **argv)
{

	char rule1[] = "192.168.5.0/24 192.168.5.254";
	char rule2[] = "10.131.0.0/16 10.131.0.254";
	char rule3[] = "16.0.0.0/8 16.0.0.254";

	printf("------------ route table ------------\n");
	printf("%s\n", rule1);
	printf("%s\n", rule2);
	printf("%s\n", rule3);
	printf("0.0.0.0/0 192.168.102.253\n");
	printf("-------------------------------------\n");

	char *defaultroute = "192.168.102.253";

	struct node *root = (struct node *)malloc(sizeof(struct node));
	if (NULL != root) {
		root->left = NULL;
		root->right = NULL;
		root->gateway = defaultroute;
	}
	buildtree(root, rule1);
	buildtree(root, rule2);
	buildtree(root, rule3);

	char to1[16] = "192.168.5.20";
	char gw[16] = "";
	route(root, to1, gw);
	printf("%s --> %s\n", to1, gw);

	char to2[16] = "192.168.102.40";
	route(root, to2, gw);
	printf("%s --> %s\n", to2, gw);

	char to3[16] = "10.238.20.11";
	route(root, to3, gw);
	printf("%s --> %s\n", to3, gw);

	char to4[16] = "16.0.0.169";
	route(root, to4, gw);
	printf("%s --> %s\n", to4, gw);

	exit(EXIT_SUCCESS);
}

void buildtree(struct node *root, char *rule)
{
	int netip, masklen;
	char *gw = (char *)malloc(16);
	ruleSplit(rule, &netip, &masklen, gw);

	struct node *p = root;
	int i = 0;
	for (i = 31; i >= 0 && masklen > 0; i--, masklen--) {
		if (netip & (1 << i)) {
			// 1: -->
			if (NULL == p->right) {
				struct node *newNode =
				    (struct node *)malloc(sizeof(struct node));
				p->right = newNode;
			}
			p = p->right;
		} else {
			// 0: <--
			if (NULL == p->left) {
				struct node *newNode =
				    (struct node *)malloc(sizeof(struct node));
				p->left = newNode;
			}
			p = p->left;
		}
	}
	p->gateway = gw;
}

void ruleSplit(char *rule, int *dest, int *masklen, char *gw)
{
	char *p = strchr(rule, '/');
	char ip[16];
	strncpy(ip, rule, p - rule + 1);
	ip[p - rule] = '\0';
	*dest = ipparser(ip);

	char *q = strchr(rule, ' ');
	char len[3];
	strncpy(len, p + 1, q - p);
	len[q - p] = '\0';
	*masklen = atoi(len);

	strcpy(gw, q + 1);
}

void route(struct node *root, const char *to, char *dst)
{
	char *gw = root->gateway;
	struct node *p = root;
	int netip = ipparser(to);
	int i;
	for (i = 31; i >= 0; i--) {
		int k = 1 << i;
		if (k < 0)
			k = 0 - k;
		if (netip & k) {	// 指定位为1, 向右走
			if (NULL == p->right) {
				break;
			} else {
				p = p->right;
				if (p->gateway != NULL) {
					gw = p->gateway;
				}
			}
		} else {	// 指定位为0, 向左走
			if (NULL == p->left) {
				break;
			} else {
				p = p->left;
				if (p->gateway != NULL) {
					gw = p->gateway;
				}
			}
		}
	}
	strcpy(dst, gw);
}

int ipparser(const char *dststr)
{
	char str[strlen(dststr)];
	strcpy(str, dststr);
	char *token = strtok(str, ".");
	int ip = 0;
	while (NULL != token) {
		ip <<= 8;
		ip += atoi(token);
		token = strtok(NULL, ".");
	}
	return ip;
}

// 运行结果
steven@lenny:~/study/c$ ./a.out 
------------ route table ------------
192.168.5.0/24 192.168.5.254
10.131.0.0/16 10.131.0.254
16.0.0.0/8 16.0.0.254
0.0.0.0/0 192.168.102.253
-------------------------------------
192.168.5.20 --> 192.168.5.254
192.168.102.40 --> 192.168.102.253
10.238.20.11 --> 192.168.102.253
16.0.0.169 --> 16.0.0.254
steven@lenny:~/study/c$