网络子系统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) { //根平衡因子变为2struct 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.1node->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.2lrl = 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) { //根平衡因子变为-2struct 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.3node->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.4rlr = 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,-1node->avl_height = (lh > rh ? lh : rh) + 1;}}}