网络子系统40_inet_peer平衡二叉树的安插

网络子系统40_inet_peer平衡二叉树的插入
//在create指定为1时，创建新的inet_peer并插入到平衡二叉树中
1.1 struct inet_peer *inet_getpeer(__be32 daddr, int create)
{
	struct inet_peer *p, *n;
	struct inet_peer **stack[PEER_MAXDEPTH], ***stackptr;
	...

	n = kmem_cache_alloc(peer_cachep, GFP_ATOMIC);//分配新的inet_peer结构
	...

	write_lock_bh(&peer_pool_lock);//在插入时，获取二叉查找树的锁

	p = lookup(daddr, stack);//此处查找操作的意义在于，将目标节点的父节点，都保存在栈stack中，栈顶为peer_avl_empty，stackptr指向下一个空闲的位置
	...

	link_to_pool(n);//添加到二叉查找树中
	...
	write_unlock_bh(&peer_pool_lock);

	...
	return n;
}

1.2 #define lookup(_daddr,_stack) 				\
({								\
	struct inet_peer *u, **v;				\
	if (_stack != NULL) {					\
		stackptr = _stack;//栈指针指向栈底		\
		*stackptr++ = &peer_root;//栈底为root，移动栈指针	\
	}							\
	for (u = peer_root; u != peer_avl_empty; ) {		\
		if (_daddr == u->v4daddr)			\
			break;					\
		if ((__force __u32)_daddr < (__force __u32)u->v4daddr)	\
			v = &u->avl_left;			\
		else						\
			v = &u->avl_right;			\
		if (_stack != NULL)				\
			*stackptr++ = v;	//将路径上的所有节点添加到栈中，当lookup因为添加操作被调用时，目标节点不存在，所以最终栈顶为peer_avl_empty，栈指针指向下一个未用的元素		\
		u = *v;						\
	}							\
	u;							\
})

#define link_to_pool(n)						\
do {								\
	n->avl_height = 1;	//高度为1，仅自己		\
	n->avl_left = peer_avl_empty;	//左右均为empty		\
	n->avl_right = peer_avl_empty;				\
	**--stackptr = n;	//覆盖栈顶的peer_avl_empty，栈顶指针指向新加入的节点	\
	peer_avl_rebalance(stack, stackptr);//平衡操作			\
} while(0)

//平衡操作
1.3 static void peer_avl_rebalance(struct inet_peer **stack[],
		struct inet_peer ***stackend)
{
	struct inet_peer **nodep, *node, *l, *r;
	int lh, rh;

	while (stackend > stack) {//stackend指向的节点非根节点
		nodep = *--stackend;//nodep为指向要插入节点的父节点的指针
		node = *nodep;//父节点的指针
		l = node->avl_left;//父节点的左孩子
		r = node->avl_right;//右孩子
		lh = node_height(l);//高度
		rh = node_height(r);
		if (lh > rh + 1) { //根平衡因子变为2
			struct inet_peer *ll, *lr, *lrl, *lrr;
			int lrh;
			ll = l->avl_left;//根的左孩子的左孩子
			lr = l->avl_right;//根的左孩子的右孩子
			lrh = node_height(lr);//左孩子的右孩子的高度
			if (lrh <= node_height(ll)) {	//并且是在左孩子的左子树插入节点,RR,情况1.1
				node->avl_left = lr;	/* lr: RH or RH+1 */
				node->avl_right = r;	/* r: RH */
				node->avl_height = lrh + 1; /* RH+1 or RH+2 */
				l->avl_left = ll;	/* ll: RH+1 */
				l->avl_right = node;	/* node: RH+1 or RH+2 */
				l->avl_height = node->avl_height + 1;
				*nodep = l;	//左孩子成为
			} else { //并且是在左孩子的右子树插入节点,LL,RR,情况1.2
				lrl = lr->avl_left;	/* lrl: RH or RH-1 */
				lrr = lr->avl_right;	/* lrr: RH or RH-1 */
				node->avl_left = lrr;	/* lrr: RH or RH-1 */
				node->avl_right = r;	/* r: RH */
				node->avl_height = rh + 1; /* node: RH+1 */
				l->avl_left = ll;	/* ll: RH */
				l->avl_right = lrl;	/* lrl: RH or RH-1 */
				l->avl_height = rh + 1;	/* l: RH+1 */
				lr->avl_left = l;	/* l: RH+1 */
				lr->avl_right = node;	/* node: RH+1 */
				lr->avl_height = rh + 2;
				*nodep = lr;	//左孩子的右子树根成为当前的根节点
			}
		} else if (rh > lh + 1) { //根平衡因子变为-2
			struct inet_peer *rr, *rl, *rlr, *rll;
			int rlh;
			rr = r->avl_right;
			rl = r->avl_left;
			rlh = node_height(rl);
			if (rlh <= node_height(rr)) {	//在右孩子的右子树上插入节点，LL,情况1.3
				node->avl_right = rl;	/* rl: LH or LH+1 */
				node->avl_left = l;	/* l: LH */
				node->avl_height = rlh + 1; /* LH+1 or LH+2 */
				r->avl_right = rr;	/* rr: LH+1 */
				r->avl_left = node;	/* node: LH+1 or LH+2 */
				r->avl_height = node->avl_height + 1;
				*nodep = r;//右孩子作为根节点
			} else { //在右孩子的左子树上插入节点，RR，LL,情况1.4
				rlr = rl->avl_right;	/* rlr: LH or LH-1 */
				rll = rl->avl_left;	/* rll: LH or LH-1 */
				node->avl_right = rll;	/* rll: LH or LH-1 */
				node->avl_left = l;	/* l: LH */
				node->avl_height = lh + 1; /* node: LH+1 */
				r->avl_right = rr;	/* rr: LH */
				r->avl_left = rlr;	/* rlr: LH or LH-1 */
				r->avl_height = lh + 1;	/* r: LH+1 */
				rl->avl_right = r;	/* r: LH+1 */
				rl->avl_left = node;	/* node: LH+1 */
				rl->avl_height = lh + 2;
				*nodep = rl;	//右孩子的左子树根作为当前的根节点
			}
		} else {//平衡因子为0,1,-1
			node->avl_height = (lh > rh ? lh : rh) + 1;
		}
	}
}
网络子系统40_inet_peer平衡二叉树的安插

相关推荐
