627
技術社區[雲棲]
網絡子係統41_inet_peer平衡二叉樹的刪除
// 二叉樹刪除節點：
// 1.待刪除節點存在左孩子，則使用p的左孩子的最右孩子替換p，然後重平衡樹
// 2.待刪除節點不存在左孩子，則使用p的右孩子替換p，然後重平衡樹
// 調用路徑：clean_up->unlink_from_pool
1.1 static void unlink_from_pool(struct inet_peer *p)
{
int do_free = 0；
write_lock_bh(&peer_pool_lock);
//在clean_up中，會設置refcnt=0的為1，防止其突然被刪除
if (atomic_read(&p->refcnt) == 1) {//refcnt=1，說明，此節點沒有引用計數
struct inet_peer **stack[PEER_MAXDEPTH];
struct inet_peer ***stackptr, ***delp;
delp = stackptr - 1; //*delp[0]指向p節點在棧中的位置
if (p->avl_left == peer_avl_empty) {//如果p節點沒有左孩子，情況1.1
*delp[0] = p->avl_right;//*delp[0]指向其右孩子
--stackptr;//stackptr指向p節點
} else {//p節點有左孩子，在左子樹中尋找一個節點，替換p，情況1.2
struct inet_peer *t;
t = lookup_rightempty(p);//t為p的左孩子的最右孩子
**--stackptr = t->avl_left;//p的左孩子的最右孩子的左孩子，覆蓋棧中p的最右孩子
*delp[0] = t;//*delp[0]指向p的左孩子的最右孩子
t->avl_left = p->avl_left;
t->avl_right = p->avl_right;
t->avl_height = p->avl_height;
delp[1] = &t->avl_left; /* was &p->avl_left */
}
peer_avl_rebalance(stack, stackptr);
peer_total--;
do_free = 1;
}
write_unlock_bh(&peer_pool_lock);
if (do_free)
kmem_cache_free(peer_cachep, p);
else
inet_putpeer(p);
}
// 查找節點左孩子的最右孩子
1.2 #define lookup_rightempty(start) \
({ \
struct inet_peer *u, **v; \
*stackptr++ = &start->avl_left; //將p的左孩子入棧，此時棧中為p的所有祖先節點，p節點，p的左孩子 \
v = &start->avl_left; \
for (u = *v; u->avl_right != peer_avl_empty; ) { \
v = &u->avl_right; //p的左孩子的右孩子 \
*stackptr++ = v; //入棧，此時棧中為p的所有祖先節點，p節點，p的左孩子，p的左孩子的右孩子 \
u = *v; \
} \
u; \
})
最後更新：2017-04-03 14:53:37