radix.c

Details description of Free BSD network source code.Those documents have explained each line of code

			goto on1;
	}
	b = -1 - tt->rn_bit;
	t = saved_tt->rn_parent;
	if (b > t->rn_bit)
		goto on1; /* Wasn't lifted at all */
	do {
		x = t;
		t = t->rn_parent;
	} while (b <= t->rn_bit && x != top);
	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
		if (m == saved_m) {
			*mp = m->rm_mklist;
			MKFree(m);
			break;
		}
	if (m == 0) {
		log(LOG_ERR, "rn_delete: couldn't find our annotation\n");
		if (tt->rn_flags & RNF_NORMAL)
			return (0); /* Dangling ref to us */
	}
on1:
	/*
	 * Eliminate us from tree
	 */
	if (tt->rn_flags & RNF_ROOT)
		return (0);
#ifdef RN_DEBUG
	/* Get us out of the creation list */
	for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}
	if (t) t->rn_ybro = tt->rn_ybro;
#endif
	t = tt->rn_parent;
	dupedkey = saved_tt->rn_dupedkey;
	if (dupedkey) {
		/*
		 * Here, tt is the deletion target and
		 * saved_tt is the head of the dupekey chain.
		 */
		if (tt == saved_tt) {
			/* remove from head of chain */
			x = dupedkey; x->rn_parent = t;
			if (t->rn_left == tt)
				t->rn_left = x;
			else
				t->rn_right = x;
		} else {
			/* find node in front of tt on the chain */
			for (x = p = saved_tt; p && p->rn_dupedkey != tt;)
				p = p->rn_dupedkey;
			if (p) {
				p->rn_dupedkey = tt->rn_dupedkey;
				if (tt->rn_dupedkey)		/* parent */
					tt->rn_dupedkey->rn_parent = p;
								/* parent */
			} else log(LOG_ERR, "rn_delete: couldn't find us\n");
		}
		t = tt + 1;
		if  (t->rn_flags & RNF_ACTIVE) {
#ifndef RN_DEBUG
			*++x = *t;
			p = t->rn_parent;
#else
			b = t->rn_info;
			*++x = *t;
			t->rn_info = b;
			p = t->rn_parent;
#endif
			if (p->rn_left == t)
				p->rn_left = x;
			else
				p->rn_right = x;
			x->rn_left->rn_parent = x;
			x->rn_right->rn_parent = x;
		}
		goto out;
	}
	if (t->rn_left == tt)
		x = t->rn_right;
	else
		x = t->rn_left;
	p = t->rn_parent;
	if (p->rn_right == t)
		p->rn_right = x;
	else
		p->rn_left = x;
	x->rn_parent = p;
	/*
	 * Demote routes attached to us.
	 */
	if (t->rn_mklist) {
		if (x->rn_bit >= 0) {
			for (mp = &x->rn_mklist; (m = *mp);)
				mp = &m->rm_mklist;
			*mp = t->rn_mklist;
		} else {
			/* If there are any key,mask pairs in a sibling
			   duped-key chain, some subset will appear sorted
			   in the same order attached to our mklist */
			for (m = t->rn_mklist; m && x; x = x->rn_dupedkey)
				if (m == x->rn_mklist) {
					struct radix_mask *mm = m->rm_mklist;
					x->rn_mklist = 0;
					if (--(m->rm_refs) < 0)
						MKFree(m);
					m = mm;
				}
			if (m)
				log(LOG_ERR,
				    "rn_delete: Orphaned Mask %p at %p\n",
				    (void *)m, (void *)x);
		}
	}
	/*
	 * We may be holding an active internal node in the tree.
	 */
	x = tt + 1;
	if (t != x) {
#ifndef RN_DEBUG
		*t = *x;
#else
		b = t->rn_info;
		*t = *x;
		t->rn_info = b;
#endif
		t->rn_left->rn_parent = t;
		t->rn_right->rn_parent = t;
		p = x->rn_parent;
		if (p->rn_left == x)
			p->rn_left = t;
		else
			p->rn_right = t;
	}
out:
	tt->rn_flags &= ~RNF_ACTIVE;
	tt[1].rn_flags &= ~RNF_ACTIVE;
	return (tt);
}

/*
 * 和下面的rn_walktree函数相同,只是参数不同.请看下面的函数说明.
 * 注:此函数和下面的函数在核心代码中并没有使用,怀疑是NFS或其他方面使用,与原理没有很大关系.
 * 他的作用是用来在路由树中进行遍历各叶子
 */
static int
rn_walktree_from(h, a, m, f, w)
	struct radix_node_head *h;
	void *a, *m;
	walktree_f_t *f;
	void *w;
{
	int error;
	struct radix_node *base, *next;
	u_char *xa = (u_char *)a;
	u_char *xm = (u_char *)m;
	register struct radix_node *rn, *last = 0 /* shut up gcc */;
	int stopping = 0;
	int lastb;

	/*
	 * rn_search_m is sort-of-open-coded here.
	 */
	/* printf("about to search\n"); */
	for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) {
		last = rn;
		/* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n",
		       rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */
		if (!(rn->rn_bmask & xm[rn->rn_offset])) {
			break;
		}
		if (rn->rn_bmask & xa[rn->rn_offset]) {
			rn = rn->rn_right;
		} else {
			rn = rn->rn_left;
		}
	}
	/* printf("done searching\n"); */

	/*
	 * Two cases: either we stepped off the end of our mask,
	 * in which case last == rn, or we reached a leaf, in which
	 * case we want to start from the last node we looked at.
	 * Either way, last is the node we want to start from.
	 */
	rn = last;
	lastb = rn->rn_bit;

	/* printf("rn %p, lastb %d\n", rn, lastb);*/

	/*
	 * This gets complicated because we may delete the node
	 * while applying the function f to it, so we need to calculate
	 * the successor node in advance.
	 */
	while (rn->rn_bit >= 0)
		rn = rn->rn_left;

	while (!stopping) {
		/* printf("node %p (%d)\n", rn, rn->rn_bit); */
		base = rn;
		/* If at right child go back up, otherwise, go right */
		while (rn->rn_parent->rn_right == rn
		       && !(rn->rn_flags & RNF_ROOT)) {
			rn = rn->rn_parent;

			/* if went up beyond last, stop */
			if (rn->rn_bit < lastb) {
				stopping = 1;
				/* printf("up too far\n"); */
			}
		}

		/* Find the next *leaf* since next node might vanish, too */
		for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
			rn = rn->rn_left;
		next = rn;
		/* Process leaves */
		while ((rn = base) != 0) {
			base = rn->rn_dupedkey;
			/* printf("leaf %p\n", rn); */
			if (!(rn->rn_flags & RNF_ROOT)
			    && (error = (*f)(rn, w)))
				return (error);
		}
		rn = next;

		if (rn->rn_flags & RNF_ROOT) {
			/* printf("root, stopping"); */
			stopping = 1;
		}

	}
	return 0;
}

static int
rn_walktree(h, f, w)
	struct radix_node_head *h;/*协议radix树的头*/
	walktree_f_t *f;/*定义为typedef int walktree_f_t(struct radix_node *, void *);定义一自定义函数来处理叶子(比如打印)*/
	void *w;
{
	int error;
	struct radix_node *base, *next;
	register struct radix_node *rn = h->rnh_treetop;/*该协议radix树的顶节点*/
	while (rn->rn_bit >= 0)/*是节点则执行下面*/
		rn = rn->rn_left;/*一直到最左边的radix的节点，但是出循环的时候就到了整个树最左边的一个叶子(注意：不是节点)*/
	for (;;) {
		base = rn;/*base开始为最左边的叶子,循环后代表上一次处理完的左边的叶子*/
		/* 其实是数学里的左边原理，就和编程序走“迷宫”游戏一样 */
		while (rn->rn_parent->rn_right == rn
		       && (rn->rn_flags & RNF_ROOT) == 0)/*当父节点的右下节点等于父节点本身并且还没到顶节点时(即父节点无右下节点)*/
			rn = rn->rn_parent;/*再回朔一次，到父父节点，循环一直到有右下节点*/
		/* 又开始查询左边(左边原理),for循环一直到左边第一个叶子 */
		for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)/*循环后到一个叶子*/
			rn = rn->rn_left;
		next = rn;/*暂时保存到next中*/
		/* 处理重复键*/
		while ((rn = base)) {
			base = rn->rn_dupedkey;
			if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) /*自定义函数处理*/
				return (error);
		}
		rn = next;/*回到当前的叶子*/
		if (rn->rn_flags & RNF_ROOT)/*到顶了,结束*/
			return (0);
	}
	/* 不可能到这 */
}

int
rn_inithead(head, off)/*该函数的工作是初始化某一种可路由协议的radix_node_head结构,包括左中右3个radix_node,及*/
					  /*加,删除,查询节点的函数指针*/
	void **head;
	int off;/*off是协议地址在sockaddr结构中的偏移量(以字节计算)*/
{
	register struct radix_node_head *rnh;/*协议的路由节点头*/
	register struct radix_node *t, *tt, *ttt;/*实际上是在radix_node_head(上面的结构)的三个成员*/
	if (*head)/*这说明该协议已经初始化了树的三顶点*/
		return (1);
	R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));/*分配一radix_node_head结构长的内存区,起始指针为rnh*/
	if (rnh == 0)
		return (0);/*内存分配不成功*/
	Bzero(rnh, sizeof (*rnh));/*把他里面初始化为0*/
#ifdef _KERNEL
	RADIX_NODE_HEAD_LOCK_INIT(rnh);/*互斥锁*/
#endif
	*head = rnh;
	t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);/*函数在上面,主要是初始化左中两个radix_node*/
	ttt = rnh->rnh_nodes + 2;/*现在初始化右边的radix_node*/
	t->rn_right = ttt;/*把指针填充到相应的成员中(右边的)*/
	t->rn_parent = t;/*填上中间的*/
	tt = t->rn_left;/*tt是左边的radix_node*/
	tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;/*RNF_ROOT代表树的原始节点*/
	tt->rn_bit = -1 - off;
	*ttt = *tt;
	ttt->rn_key = rn_ones;
	rnh->rnh_addaddr = rn_addroute;/*函数在上面,添加一路由节点.*/
	rnh->rnh_deladdr = rn_delete;/*函数在上面,删除一路由节点.*/
	rnh->rnh_matchaddr = rn_match;/*函数在上面,查询一匹配的路由节点.*/
	rnh->rnh_lookup = rn_lookup;
	rnh->rnh_walktree = rn_walktree;
	rnh->rnh_walktree_from = rn_walktree_from;
	rnh->rnh_treetop = t;/*树的顶点*/
	return (1);
}

void
rn_init()/*由route.c中的route_init()调用*/
{
	char *cp, *cplim;
#ifdef _KERNEL
	struct domain *dom;

	for (dom = domains; dom; dom = dom->dom_next)/*遍历所有协议*/
		if (dom->dom_maxrtkey > max_keylen)
			max_keylen = dom->dom_maxrtkey;/*看看哪种协议地址最长，用最长的(ipx也可路由且地址长度比Internet协议地址长)*/
#endif
	if (max_keylen == 0) {/*除非把所有协议都关了*/
		log(LOG_ERR,
		    "rn_init: radix functions require max_keylen be set\n");
		return;
	}
	R_Malloc(rn_zeros, char *, 3 * max_keylen);/*即分配3个max_keylen长度的内存,rn_zeros是首指针*/
	if (rn_zeros == NULL)
		panic("rn_init");
	Bzero(rn_zeros, 3 * max_keylen);/*初始化为0*/
	rn_ones = cp = rn_zeros + max_keylen;/*在rn_zeros后面一个max_keylen长度后是rn_ones,cp是为了要把他置为1而准备的*/
	addmask_key = cplim = rn_ones + max_keylen;/*在rn_ones后面一个max_keylen长度后是addmask_key,cplim是尾部+1的指针*/
	/*addmask_key是为了临时存放掩码而设置的*/
	while (cp < cplim)   /*把rn_ones开始的长度为max_keylen的区域置为FF填满*/
		*cp++ = -1;
	if (rn_inithead((void **)&mask_rnhead, 0) == 0)/*初始化掩码radix树.*/
		panic("rn_init 2");
}