紅黑樹(rbtree)在linux內核中使用非常廣泛,cfs調度任務管理，vma管理等。本文不會涉及關于紅黑樹插入和刪除時的各種case的詳細描述,感興趣的讀者可以查閱其他資料。本文主要聚焦于linux內核中經典rbtree和augment-rbtree操作接口的說明。

1、基本概念

二叉樹:每個結點最多2棵子樹,無其它限制了。

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

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

紅黑樹性質:
紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。除二叉查找樹強制一般要求以外，對于任何有效的紅黑樹增加了如下的額外要求:

性質1. 節點是紅色或黑色。

性質2. 根是黑色。

性質3. 所有葉子都是黑色（葉子是NULL節點）。

性質4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

性質5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。

?* 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內核中的紅黑樹分為兩類,一類是經典的紅黑樹,用于存放key/value鍵值對，另一類是增強型紅黑樹(VMA是內核中典型的augment-rbtree)。

增強型rbtree是一種在每個節點中存儲了“一些”額外數據的rbtree，其中節點N的額外數據必須是根為N的子樹中所有節點內容的函數。

這些數據可用于為rbtree增加一些新功能。增強rbtree是建立在基本rbtree基礎設施之上的可選功能。

需要此特性的rbtree用戶在插入和刪除節點時必須使用用戶提供的增強回調調用增強函數。

注意內核紅黑樹的實現將部分工作留給了用戶來實現:用戶需要編寫自己的樹搜索和插入函數調用所提供的rbtree函數,鎖也留給rbtree代碼的用戶。

2、數據結構

/*linux內核中,rbtree作為通用數據結構類似鏈表是嵌入到用戶數據結構內部,在用戶數據結構中存放自己的數據*/
struct rb_node {/*父節點，由于struct rb_node是long對齊,所以其地址低3-0bit或7-0bit未使用,低2位被用來作為顏色標志使用*/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字節對齊,其地址最少也是4字節對齊,所以其成員__rb_parent_color用于存放其parent的地址,同時低2bit可以存放自身的----顏色屬性。/*根節點*/
struct rb_root {struct rb_node *rb_node;
};/*節點顏色，默認插入節點為紅色*/
#define	RB_RED		0
#define	RB_BLACK		1/*父節點地址, &~3 去掉顏色標志位*/
#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節點的顏色*/
#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)/*返回內嵌struct rb_node的數據結構*/
#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、接口說明

3.1、rbtree插入紅黑樹節點

3.1.1、經典rbtree插入紅黑樹節點

在將數據插入rbtree之前，需要用戶實現查找函數,查找插入節點應該插入到rbtree root中的位置,建立鏈接后,才能將其插入到root中；

系統無法知道用戶數據存放規則,將節點存放到rbtree中的位置的查找工作交給用戶來處理。

通過rb_link_node(...)接口設置node要被插入到parent下面,建立位置鏈接關系
static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,struct rb_node **rb_link)
{/*設置node__rb_parent_color的值,顏色屬性為紅色*/node->__rb_parent_color = (unsigned long)parent; node->rb_left = node->rb_right = NULL;*rb_link = node;
}在樹中插入數據包括首先搜索插入新節點的位置，然后插入節點并重新平衡(“重新上色”)樹。
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{__rb_insert(node, root, dummy_rotate);
}
節點插入的工作交給__rb_insert來處理。下面是__rb_insert函數原型:
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函數指針傳入旋轉回調函數,經典紅黑樹中未使用，傳入啞旋轉回調函數dummy_rotate;經典紅黑樹只是存儲節點之間的順序關系,無其他"額外"信息,所以其struct rb_augment_callbacks 增強回調函數全部實現為空；
/** Non-augmented rbtree manipulation functions.(非增強紅黑樹操作功能函數)** 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);
};

對于augment-rbtree(增強紅黑樹)rb_augment_callbacks的定義可以通過下面的宏來實現；
/*這個宏定義的內容比較長,定義了augment回調函數接口以及對應的struct rb_augment_callbacks rbname 結構體*/
#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(增強紅黑樹)插入紅黑樹節點

在插入時，用戶必須更新通向插入節點的路徑上的增強信息，然后像往常一樣調用rb_link_node()和rb_augment_inserted()，而不是通常的rb_insert_color()調用。

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

/** 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);
}

和經典紅黑樹插入節點操作一樣,最后的后都是留給__rb_insert來處理的。區別在于需要提供augmet->rotate的實現。

3.2、rbtree刪除紅黑樹節點

3.2.1、經典rbtree刪除紅黑樹節點

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(增強紅黑樹)刪除紅黑樹節點

當擦除節點時，用戶必須調用rb_erase_augmented()而不是rb_erase()。Rb_erase_augmented()回調用戶提供的函數來更新受影響子樹上的增強信息。

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節點遍歷

/*如果rbtree中的節點是按順存放的話,rb_first返回最小值節點*/

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中的節點是按順存放的話,rb_last返回最大值節點*/
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中的節點是按順存放的話,rb_next返回值比node節點值大的節點*/
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無右子樹且node的parent存在:1、如果node為parent的左節點,則返回parent(parent比node大);2、node為其parent的右節點(parent比node小),則繼續遞歸往上找(如果一直為右節點,表明node是以當前parent為root的這棵子樹上的最大值),直到找到node為parent的左節點時返回其parent(parent比左子樹所以節點都大)；*/while ((parent = rb_parent(node)) && node == parent->rb_right)node = parent;return parent; /*這里返回的是parent*/
}/*如果rbtree中的節點是按順存放的話,rb_next返回值比node節點值小的節點*/
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無左子樹且node的parent存在：1、如果node為parent的右節點,則返回parent(parent比node小)；	2、node為其parent的左節點(parent比node大),則繼續遞歸往上找,(如果一直為左節點,表明node是以當前parent為root的這棵子樹上的最小值),直到找到node為parent的右節點時返回其parent(parent比右子樹所以節點都小)；*/while ((parent = rb_parent(node)) && node == parent->rb_left)node = parent;return parent; /*這里返回的是parent*/
}

上面四個宏可以用于遍歷紅黑樹中的節點:

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

...
}