紅黑樹(rbtree)在linux內(nèi)核中使用非常廣泛,cfs調(diào)度任務(wù)管理，vma管理等。本文不會(huì)涉及關(guān)于紅黑樹插入和刪除時(shí)的各種case的詳細(xì)描述,感興趣的讀者可以查閱其他資料。本文主要聚焦于linux內(nèi)核中經(jīng)典rbtree和augment-rbtree操作接口的說(shuō)明。

1、基本概念

二叉樹:每個(gè)結(jié)點(diǎn)最多2棵子樹,無(wú)其它限制了。

二叉查找樹(二叉排序樹/二叉搜索樹):首先它是二叉樹,左子樹上所有結(jié)點(diǎn)的值小于它根結(jié)點(diǎn)的值,右子樹上所有結(jié)點(diǎn)的值大于它根結(jié)點(diǎn)的值(遞歸定義).

二叉平衡樹:也稱為平衡二叉樹,它是"平衡二叉搜索樹"的簡(jiǎn)稱。首先它是"二叉搜索樹",其次它是平衡的,即它的每一個(gè)結(jié)點(diǎn)的左子樹的高度和右子樹的高度差至多為1。

紅黑樹性質(zhì):
紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。除二叉查找樹強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹增加了如下的額外要求:

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。

性質(zhì)2. 根是黑色。

性質(zhì)3. 所有葉子都是黑色（葉子是NULL節(jié)點(diǎn)）。

性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))

性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

?* red-black trees properties: ?http://en.wikipedia.org/wiki/Rbtree

?*

?* ?1) A node is either red or black

?* ?2) The root is black

?* ?3) All leaves (NULL) are black

?* ?4) Both children of every red node are black

?* ?5) Every simple path from root to leaves contains the same number of black nodes.

?*

?* ?4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two

?* ?consecutive red nodes in a path and every red node is therefore followed by

?* ?a black. So if B is the number of black nodes on every simple path (as per

?* ?5), then the longest possible path due to 4 is 2B.

?*

?* ?We shall indicate color with case, where black nodes are uppercase(大寫字母) and red nodes will be lowercase(小寫字母).

?* ?Unknown color nodes shall be drawn as red within parentheses and have some accompanying text comment.

linux內(nèi)核中的紅黑樹分為兩類,一類是經(jīng)典的紅黑樹,用于存放key/value鍵值對(duì)，另一類是增強(qiáng)型紅黑樹(VMA是內(nèi)核中典型的augment-rbtree)。

增強(qiáng)型rbtree是一種在每個(gè)節(jié)點(diǎn)中存儲(chǔ)了“一些”額外數(shù)據(jù)的rbtree，其中節(jié)點(diǎn)N的額外數(shù)據(jù)必須是根為N的子樹中所有節(jié)點(diǎn)內(nèi)容的函數(shù)。

這些數(shù)據(jù)可用于為rbtree增加一些新功能。增強(qiáng)rbtree是建立在基本rbtree基礎(chǔ)設(shè)施之上的可選功能。

需要此特性的rbtree用戶在插入和刪除節(jié)點(diǎn)時(shí)必須使用用戶提供的增強(qiáng)回調(diào)調(diào)用增強(qiáng)函數(shù)。

注意內(nèi)核紅黑樹的實(shí)現(xiàn)將部分工作留給了用戶來(lái)實(shí)現(xiàn):用戶需要編寫自己的樹搜索和插入函數(shù)調(diào)用所提供的rbtree函數(shù),鎖也留給rbtree代碼的用戶。

2、數(shù)據(jù)結(jié)構(gòu)

/*linux內(nèi)核中,rbtree作為通用數(shù)據(jù)結(jié)構(gòu)類似鏈表是嵌入到用戶數(shù)據(jù)結(jié)構(gòu)內(nèi)部,在用戶數(shù)據(jù)結(jié)構(gòu)中存放自己的數(shù)據(jù)*/
struct rb_node {/*父節(jié)點(diǎn)，由于struct rb_node是long對(duì)齊,所以其地址低3-0bit或7-0bit未使用,低2位被用來(lái)作為顏色標(biāo)志使用*/unsigned long  __rb_parent_color;struct rb_node *rb_right; /*右子樹*/struct rb_node *rb_left;  /*左子樹*/
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */注意,struct rb_node為long字節(jié)對(duì)齊,其地址最少也是4字節(jié)對(duì)齊,所以其成員__rb_parent_color用于存放其parent的地址,同時(shí)低2bit可以存放自身的----顏色屬性。/*根節(jié)點(diǎn)*/
struct rb_root {struct rb_node *rb_node;
};/*節(jié)點(diǎn)顏色，默認(rèn)插入節(jié)點(diǎn)為紅色*/
#define	RB_RED		0
#define	RB_BLACK		1/*父節(jié)點(diǎn)地址, &~3 去掉顏色標(biāo)志位*/
#define rb_parent(r)   		((struct rb_node *)((r)->__rb_parent_color & ~3))#define RB_ROOT		(struct rb_root) { NULL, }
#define RB_ROOT_CACHED 	(struct rb_root_cached) { {NULL, }, NULL }#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))/*pc節(jié)點(diǎn)的顏色*/
#define __rb_color(pc)     ((pc) & 1)
#define __rb_is_black(pc)  __rb_color(pc)
#define __rb_is_red(pc)    (!__rb_color(pc))/*rb->__rb_parent_color的顏色*/
#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)/*返回內(nèi)嵌struct rb_node的數(shù)據(jù)結(jié)構(gòu)*/
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)#define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
#define RB_EMPTY_NODE(node)  \((node)->__rb_parent_color == (unsigned long)(node))/*注意,這里是賦值操作*/
#define RB_CLEAR_NODE(node)  \((node)->__rb_parent_color = (unsigned long)(node))

3、接口說(shuō)明

3.1、rbtree插入紅黑樹節(jié)點(diǎn)

3.1.1、經(jīng)典rbtree插入紅黑樹節(jié)點(diǎn)

在將數(shù)據(jù)插入rbtree之前，需要用戶實(shí)現(xiàn)查找函數(shù),查找插入節(jié)點(diǎn)應(yīng)該插入到rbtree root中的位置,建立鏈接后,才能將其插入到root中；

系統(tǒng)無(wú)法知道用戶數(shù)據(jù)存放規(guī)則,將節(jié)點(diǎn)存放到rbtree中的位置的查找工作交給用戶來(lái)處理。

通過(guò)rb_link_node(...)接口設(shè)置node要被插入到parent下面,建立位置鏈接關(guān)系
static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,struct rb_node **rb_link)
{/*設(shè)置node__rb_parent_color的值,顏色屬性為紅色*/node->__rb_parent_color = (unsigned long)parent; node->rb_left = node->rb_right = NULL;*rb_link = node;
}在樹中插入數(shù)據(jù)包括首先搜索插入新節(jié)點(diǎn)的位置，然后插入節(jié)點(diǎn)并重新平衡(“重新上色”)樹。
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{__rb_insert(node, root, dummy_rotate);
}
節(jié)點(diǎn)插入的工作交給__rb_insert來(lái)處理。下面是__rb_insert函數(shù)原型:
static __always_inline void __rb_insert(struct rb_node *node, struct rb_root *root,void (*augment_rotate)(struct rb_node *old, struct rb_node *new))其中augment_rotate函數(shù)指針傳入旋轉(zhuǎn)回調(diào)函數(shù),經(jīng)典紅黑樹中未使用，傳入啞旋轉(zhuǎn)回調(diào)函數(shù)dummy_rotate;經(jīng)典紅黑樹只是存儲(chǔ)節(jié)點(diǎn)之間的順序關(guān)系,無(wú)其他"額外"信息,所以其struct rb_augment_callbacks 增強(qiáng)回調(diào)函數(shù)全部實(shí)現(xiàn)為空；
/** Non-augmented rbtree manipulation functions.(非增強(qiáng)紅黑樹操作功能函數(shù))** We use dummy augmented callbacks here, and have the compiler optimize them* out of the rb_insert_color() and rb_erase() function definitions.*/static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}static const struct rb_augment_callbacks dummy_callbacks = {dummy_propagate, dummy_copy, dummy_rotate
};/** Please note - only struct rb_augment_callbacks and the prototypes for* rb_insert_augmented() and rb_erase_augmented() are intended to be public.* The rest are implementation details you are not expected to depend on.** See Documentation/rbtree.txt for documentation and samples.*/struct rb_augment_callbacks {void (*propagate)(struct rb_node *node, struct rb_node *stop);void (*copy)(struct rb_node *old, struct rb_node *new);void (*rotate)(struct rb_node *old, struct rb_node *new);
};

對(duì)于augment-rbtree(增強(qiáng)紅黑樹)rb_augment_callbacks的定義可以通過(guò)下面的宏來(lái)實(shí)現(xiàn)；
/*這個(gè)宏定義的內(nèi)容比較長(zhǎng),定義了augment回調(diào)函數(shù)接口以及對(duì)應(yīng)的struct rb_augment_callbacks rbname 結(jié)構(gòu)體*/
#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\rbtype, rbaugmented, rbcompute)		\
static inline void							\
rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
{									\while (rb != stop) {						\rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\rbtype augmented = rbcompute(node);			\if (node->rbaugmented == augmented)			\break;						\node->rbaugmented = augmented;				\rb = rb_parent(&node->rbfield);				\}								\
}									\
static inline void							\
rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
{									\rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\new->rbaugmented = old->rbaugmented;				\
}									\
static void								\
rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
{									\rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\new->rbaugmented = old->rbaugmented;				\old->rbaugmented = rbcompute(old);				\
}									\
rbstatic const struct rb_augment_callbacks rbname = {			\rbname ## _propagate, rbname ## _copy, rbname ## _rotate	\
};

3.1.2、augment-rbtree(增強(qiáng)紅黑樹)插入紅黑樹節(jié)點(diǎn)

在插入時(shí)，用戶必須更新通向插入節(jié)點(diǎn)的路徑上的增強(qiáng)信息，然后像往常一樣調(diào)用rb_link_node()和rb_augment_inserted()，而不是通常的rb_insert_color()調(diào)用。

如果rb_augment_inserts()重新平衡了rbtree，它將回調(diào)為用戶提供的函數(shù)，以更新受影響子樹上的增強(qiáng)信息。

/** Fixup the rbtree and update the augmented information when rebalancing.** On insertion, the user must update the augmented information on the path* leading to the inserted node, then call rb_link_node() as usual and* rb_augment_inserted() instead of the usual rb_insert_color() call.* If rb_augment_inserted() rebalances the rbtree, it will callback into* a user provided function to update the augmented information on the* affected subtrees.*/
static inline void rb_insert_augmented(struct rb_node *node, struct rb_root *root,const struct rb_augment_callbacks *augment)
{__rb_insert_augmented(node, root, augment->rotate);
}/** Augmented rbtree manipulation functions.** This instantiates the same __always_inline functions as in the non-augmented* case, but this time with user-defined callbacks.*/void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{__rb_insert(node, root, augment_rotate);
}

和經(jīng)典紅黑樹插入節(jié)點(diǎn)操作一樣,最后的后都是留給__rb_insert來(lái)處理的。區(qū)別在于需要提供augmet->rotate的實(shí)現(xiàn)。

3.2、rbtree刪除紅黑樹節(jié)點(diǎn)

3.2.1、經(jīng)典rbtree刪除紅黑樹節(jié)點(diǎn)

void rb_erase(struct rb_node *node, struct rb_root *root)
{struct rb_node *rebalance;rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);if (rebalance)____rb_erase_color(rebalance, root, dummy_rotate);
}/* Fast replacement of a single node without remove/rebalance/add/rebalance */
void rb_replace_node(struct rb_node *victim, struct rb_node *new,struct rb_root *root)
{struct rb_node *parent = rb_parent(victim);/* Set the surrounding nodes to point to the replacement */__rb_change_child(victim, new, parent, root);if (victim->rb_left)rb_set_parent(victim->rb_left, new);if (victim->rb_right)rb_set_parent(victim->rb_right, new);/* Copy the pointers/colour from the victim to the replacement */*new = *victim;
}

3.2.2、augment-rbtree(增強(qiáng)紅黑樹)刪除紅黑樹節(jié)點(diǎn)

當(dāng)擦除節(jié)點(diǎn)時(shí)，用戶必須調(diào)用rb_erase_augmented()而不是rb_erase()。Rb_erase_augmented()回調(diào)用戶提供的函數(shù)來(lái)更新受影響子樹上的增強(qiáng)信息。

static __always_inline void rb_erase_augmented(struct rb_node *node, struct rb_root *root,const struct rb_augment_callbacks *augment)
{struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);if (rebalance)__rb_erase_color(rebalance, root, augment->rotate);
}	

3.3、rbtree節(jié)點(diǎn)遍歷

/*如果rbtree中的節(jié)點(diǎn)是按順存放的話,rb_first返回最小值節(jié)點(diǎn)*/

struct rb_node *rb_first(const struct rb_root *root)
{struct rb_node	*n;n = root->rb_node;if (!n)return NULL;while (n->rb_left)n = n->rb_left;return n;
}/*如果rbtree中的節(jié)點(diǎn)是按順存放的話,rb_last返回最大值節(jié)點(diǎn)*/
struct rb_node *rb_last(const struct rb_root *root)
{struct rb_node	*n;n = root->rb_node;if (!n)return NULL;while (n->rb_right)n = n->rb_right;return n;
}/*如果rbtree中的節(jié)點(diǎn)是按順存放的話,rb_next返回值比node節(jié)點(diǎn)值大的節(jié)點(diǎn)*/
struct rb_node *rb_next(const struct rb_node *node)
{struct rb_node *parent;if (RB_EMPTY_NODE(node))return NULL;/** If we have a right-hand child, go down and then left as far* as we can.*/if (node->rb_right) { /*node右子樹上的值都比node大*/node = node->rb_right;while (node->rb_left) /*一直尋找左子樹*/node=node->rb_left;return (struct rb_node *)node;}/** No right-hand children. Everything down and left is smaller than us,* so any 'next' node must be in the general direction of our parent.* Go up the tree; any time the ancestor is a right-hand child of its* parent, keep going up. First time it's a left-hand child of its* parent, said parent is our 'next' node.*//*node無(wú)右子樹且node的parent存在:1、如果node為parent的左節(jié)點(diǎn),則返回parent(parent比node大);2、node為其parent的右節(jié)點(diǎn)(parent比node小),則繼續(xù)遞歸往上找(如果一直為右節(jié)點(diǎn),表明node是以當(dāng)前parent為root的這棵子樹上的最大值),直到找到node為parent的左節(jié)點(diǎn)時(shí)返回其parent(parent比左子樹所以節(jié)點(diǎn)都大)；*/while ((parent = rb_parent(node)) && node == parent->rb_right)node = parent;return parent; /*這里返回的是parent*/
}/*如果rbtree中的節(jié)點(diǎn)是按順存放的話,rb_next返回值比node節(jié)點(diǎn)值小的節(jié)點(diǎn)*/
struct rb_node *rb_prev(const struct rb_node *node)
{struct rb_node *parent;if (RB_EMPTY_NODE(node))return NULL;/** If we have a left-hand child, go down and then right as far* as we can.*/if (node->rb_left) {  /*node左子樹上的值都比node小*/node = node->rb_left; while (node->rb_right) /*一直找右子樹*/node=node->rb_right;return (struct rb_node *)node;}/** No left-hand children. Go up till we find an ancestor which* is a right-hand child of its parent.*//*node無(wú)左子樹且node的parent存在：1、如果node為parent的右節(jié)點(diǎn),則返回parent(parent比node小)；	2、node為其parent的左節(jié)點(diǎn)(parent比node大),則繼續(xù)遞歸往上找,(如果一直為左節(jié)點(diǎn),表明node是以當(dāng)前parent為root的這棵子樹上的最小值),直到找到node為parent的右節(jié)點(diǎn)時(shí)返回其parent(parent比右子樹所以節(jié)點(diǎn)都小)；*/while ((parent = rb_parent(node)) && node == parent->rb_left)node = parent;return parent; /*這里返回的是parent*/
}

上面四個(gè)宏可以用于遍歷紅黑樹中的節(jié)點(diǎn):

for (node = rb_first(&mytree); node; node = rb_next(node)){

...
}