linux內(nèi)存管理之紅黑樹算法源碼詳解

linux內(nèi)存管理模塊中使用紅黑樹算法來提升虛擬內(nèi)存查找速度，源碼請參考linux內(nèi)核目錄下rbtree.c文件。

紅黑樹算法原理

在閱讀紅黑樹算法源代碼之前最好先了解紅黑樹原理。

rb_insert_color函數(shù)詳解：

void?rb_insert_color(rb_node_t?*?node,?rb_root_t?*?root)
{
	rb_node_t?*?parent,?*?gparent;

	while?((parent?=?node->rb_parent)?&&?parent->rb_color?==?RB_RED)
	{
		gparent?=?parent->rb_parent;

		if?(parent?==?gparent->rb_left)
		{
			{
				register?rb_node_t?*?uncle?=?gparent->rb_right;
				if?(uncle?&&?uncle->rb_color?==?RB_RED)
				{
					uncle->rb_color?=?RB_BLACK;
					parent->rb_color?=?RB_BLACK;
					gparent->rb_color?=?RB_RED;
					node?=?gparent;
					continue;
				}
			}

			if?(parent->rb_right?==?node)
			{
				register?rb_node_t?*?tmp;
				__rb_rotate_left(parent,?root);
				tmp?=?parent;
				parent?=?node;
				node?=?tmp;
			}

			parent->rb_color?=?RB_BLACK;
			gparent->rb_color?=?RB_RED;
			__rb_rotate_right(gparent,?root);
		}?else?{
			{
				register?rb_node_t?*?uncle?=?gparent->rb_left;
				if?(uncle?&&?uncle->rb_color?==?RB_RED)
				{
					uncle->rb_color?=?RB_BLACK;
					parent->rb_color?=?RB_BLACK;
					gparent->rb_color?=?RB_RED;
					node?=?gparent;
					continue;
				}
			}

			if?(parent->rb_left?==?node)
			{
				register?rb_node_t?*?tmp;
				__rb_rotate_right(parent,?root);
				tmp?=?parent;
				parent?=?node;
				node?=?tmp;
			}

			parent->rb_color?=?RB_BLACK;
			gparent->rb_color?=?RB_RED;
			__rb_rotate_left(gparent,?root);
		}
	}

	root->rb_node->rb_color?=?RB_BLACK;
}

注解：

??? 函數(shù)參數(shù)

??????? node：新插入的結(jié)點(diǎn)。

??????? root：紅黑樹的根結(jié)點(diǎn)。

??? 第5行：往紅黑樹中插入結(jié)點(diǎn)時，總是將新插入結(jié)點(diǎn)顏色設(shè)置為紅色。當(dāng)新結(jié)點(diǎn)的父結(jié)點(diǎn)不存在或者父結(jié)點(diǎn)顏色為黑色時，不需要做紅黑樹調(diào)整直接跳到第63行。

??? 第7行：獲取node結(jié)點(diǎn)的祖父結(jié)點(diǎn)。

??? （第9-35行 處理node父結(jié)點(diǎn)是其祖父結(jié)點(diǎn)左子結(jié)點(diǎn)的情況）

??? 第12行：獲取node的叔父結(jié)點(diǎn)。

??? 第13-20行：當(dāng)叔父結(jié)點(diǎn)存在并且顏色為紅色，就將node的父結(jié)點(diǎn)與叔父結(jié)點(diǎn)的顏色設(shè)成黑色，并且將node的祖父結(jié)點(diǎn)顏色設(shè)成紅色?，F(xiàn)在祖父結(jié)點(diǎn)的顏色為紅色，但祖父結(jié)點(diǎn)的父結(jié)點(diǎn)也可能為紅色，不滿足紅黑樹性質(zhì)，因此將祖父結(jié)點(diǎn)當(dāng)做新插入的結(jié)點(diǎn)重新進(jìn)行紅黑樹調(diào)整。

??? 第23-30行：叔父結(jié)點(diǎn)不存在或者顏色為黑色，此時node的祖父結(jié)點(diǎn)顏色必為黑色（因為node父結(jié)點(diǎn)顏色為紅色），針對node的父結(jié)點(diǎn)進(jìn)行一次左旋轉(zhuǎn)，讓父結(jié)點(diǎn)成為node的左子結(jié)點(diǎn)，并交換父結(jié)點(diǎn)與node結(jié)點(diǎn)位置，使以前的父結(jié)點(diǎn)成為新插入的結(jié)點(diǎn)。

??? 第32-34得：將父結(jié)點(diǎn)的顏色設(shè)為黑色（此時新node的顏色還是紅色），將祖父結(jié)點(diǎn)的顏色設(shè)為紅色。再針對祖父結(jié)點(diǎn)進(jìn)行一次右旋轉(zhuǎn)，此時node擁有一個黑色的父結(jié)點(diǎn)及紅色的兄弟結(jié)點(diǎn)。

??? （第36-61行處理node的父結(jié)點(diǎn)是其祖父結(jié)點(diǎn)的右子結(jié)點(diǎn)的情況）

??? 第37行：獲取node的叔父結(jié)點(diǎn)。

??? 第38行：當(dāng)node的叔父結(jié)點(diǎn)存在并且顏色為紅色，就將node的父結(jié)點(diǎn)與叔父結(jié)點(diǎn)設(shè)置為黑色，并將node的祖父結(jié)點(diǎn)設(shè)置為紅色。再將祖父結(jié)點(diǎn)當(dāng)做新插入的結(jié)點(diǎn)重新進(jìn)行紅黑樹調(diào)整。

??? 第48-55行：如果node結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)，就針對node的父結(jié)點(diǎn)進(jìn)行一次右旋轉(zhuǎn)，讓其父結(jié)點(diǎn)成為node的右子結(jié)點(diǎn)，并交換父結(jié)點(diǎn)與node的位置，讓以前的父結(jié)點(diǎn)成為新插入的結(jié)點(diǎn)

??? 第57-59行：將父結(jié)點(diǎn)的顏色設(shè)為黑色（此時新node的顏色還是紅色），將祖父結(jié)點(diǎn)的顏色設(shè)置為紅色。再針對祖父結(jié)點(diǎn)進(jìn)行一次左旋轉(zhuǎn)，此時node擁有一個黑色的父結(jié)點(diǎn)及紅色的兄弟結(jié)點(diǎn)。

??? 第63行：將根結(jié)點(diǎn)的顏色設(shè)為黑色。這一步是有必要的，當(dāng)新插入的結(jié)點(diǎn)為根結(jié)點(diǎn)或者在樹調(diào)整過程中將根結(jié)點(diǎn)顏色變成了紅色，這一行將根結(jié)點(diǎn)的顏色設(shè)成黑色。

?rb_erase函數(shù)詳解：

void?rb_erase(rb_node_t?*?node,?rb_root_t?*?root)
{
	rb_node_t?*?child,?*?parent;
	int?color;

	if?(!node->rb_left)
		child?=?node->rb_right;
	else?if?(!node->rb_right)
		child?=?node->rb_left;
	else
	{
		rb_node_t?*?old?=?node,?*?left;

		node?=?node->rb_right;
		while?((left?=?node->rb_left))
			node?=?left;
		child?=?node->rb_right;
		parent?=?node->rb_parent;
		color?=?node->rb_color;

		if?(child)
			child->rb_parent?=?parent;
		if?(parent)
		{
			if?(parent->rb_left?==?node)
				parent->rb_left?=?child;
			else
				parent->rb_right?=?child;
		}
		else
			root->rb_node?=?child;

		if?(node->rb_parent?==?old)
			parent?=?node;
		node->rb_parent?=?old->rb_parent;
		node->rb_color?=?old->rb_color;
		node->rb_right?=?old->rb_right;
		node->rb_left?=?old->rb_left;

		if?(old->rb_parent)
		{
			if?(old->rb_parent->rb_left?==?old)
				old->rb_parent->rb_left?=?node;
			else
				old->rb_parent->rb_right?=?node;
		}?else
			root->rb_node?=?node;

		old->rb_left->rb_parent?=?node;
		if?(old->rb_right)
			old->rb_right->rb_parent?=?node;
		goto?color;
	}

	parent?=?node->rb_parent;
	color?=?node->rb_color;

	if?(child)
		child->rb_parent?=?parent;
	if?(parent)
	{
		if?(parent->rb_left?==?node)
			parent->rb_left?=?child;
		else
			parent->rb_right?=?child;
	}
	else
		root->rb_node?=?child;

?color:
	if?(color?==?RB_BLACK)
		__rb_erase_color(child,?parent,?root);
}

注解：

??? 函數(shù)參數(shù)：

? ? ? ??node： 將要刪除的結(jié)點(diǎn)

? ? ? ? root： 紅黑樹的根結(jié)點(diǎn)

??? （第6-9行處理被刪結(jié)點(diǎn)至多只有一個子結(jié)點(diǎn)的情況，并找出不為空的子結(jié)點(diǎn)）

? ? 第6-7行：判斷node的左子結(jié)點(diǎn)是否存在，如果不存在child針指就指向右子結(jié)點(diǎn)（右子結(jié)點(diǎn)也可能不存在）。

??? 第8-9行：判斷node的右子結(jié)點(diǎn)是否存在，如果不存在child指針就指向其左子結(jié)點(diǎn)。

??? （第11-53行 處理被刪結(jié)點(diǎn)有兩個非空子結(jié)點(diǎn)的情況。當(dāng)結(jié)點(diǎn)存在兩個非空子結(jié)點(diǎn)時就找出其左子樹中元素最大的結(jié)點(diǎn)或者右子樹中元素最小的結(jié)點(diǎn)，并將該結(jié)點(diǎn)替換到將要被刪除的結(jié)點(diǎn)位置上，再刪除元素最大或者最小的結(jié)點(diǎn)。這時就將刪除有兩個非空子結(jié)點(diǎn)的問題變成刪除至多只有一個非空子結(jié)點(diǎn)的問題。linux內(nèi)存管理模塊中的紅黑樹是按結(jié)點(diǎn)所在的內(nèi)存首地址來排序存儲的，如父結(jié)點(diǎn)的內(nèi)存首地址一定會大于其左子結(jié)點(diǎn)首地址且小于右子結(jié)點(diǎn)首地址，因此在替換結(jié)點(diǎn)時只替換結(jié)點(diǎn)的位置不能改變結(jié)點(diǎn)的首地址）。

??? 第12行：保存node到old變量中。

??? 第14-16行：找出node的右子樹中首地址最小的結(jié)點(diǎn)。如果找到就將該結(jié)點(diǎn)當(dāng)做將要被刪除的結(jié)點(diǎn)。

??? 第17行：獲取node的右子結(jié)點(diǎn)，經(jīng)過第14-16行的處理現(xiàn)在node結(jié)點(diǎn)的首地址最小，所以node不可能存在左子結(jié)點(diǎn)，但右子結(jié)點(diǎn)可能會存在。

??? 第18行：獲取node的父結(jié)點(diǎn)。

??? 第19行：獲取node的顏色屬性。

??? 第21-22行：如果node的子結(jié)點(diǎn)存在，就設(shè)置其子結(jié)點(diǎn)的父結(jié)點(diǎn)為node的父結(jié)點(diǎn)（因為node結(jié)點(diǎn)將要被刪除）。

??? 第23-29行：如果node的父結(jié)點(diǎn)存在，當(dāng)node是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)時就設(shè)置node的子結(jié)點(diǎn)為其父結(jié)點(diǎn)的左子結(jié)點(diǎn)，否則就設(shè)置為其父結(jié)點(diǎn)的右子結(jié)點(diǎn)。

??? 第30-31行：這種情況不可能會發(fā)生。

??? 第33-34行：如果node等于old，說明old（old中保存有rb_erase函數(shù)中node參數(shù)的值，即要被替換的結(jié)點(diǎn)）的右子結(jié)點(diǎn)沒有子結(jié)點(diǎn)，將父結(jié)點(diǎn)指向node結(jié)點(diǎn)（當(dāng)node等于old時，在node替換old之后，node與其子結(jié)點(diǎn)的關(guān)系保持不變）。

??? （第35-38行 這里將node結(jié)點(diǎn)替換掉old結(jié)點(diǎn)）

??? 第35行：設(shè)置node的父結(jié)點(diǎn)為old結(jié)點(diǎn)的父結(jié)點(diǎn)。

??? 第36行：將old結(jié)點(diǎn)顏色替換到node結(jié)點(diǎn)中。

??? 第37行：將node的右子結(jié)點(diǎn)設(shè)置為old的右子結(jié)點(diǎn)。

??? 第38行：將node的左子結(jié)點(diǎn)設(shè)置為old的左子結(jié)點(diǎn)。

??? 第40-46行：如果old的父結(jié)點(diǎn)存在，當(dāng)old是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)時就將node變成其父結(jié)點(diǎn)的左子結(jié)點(diǎn)，否則為其父結(jié)點(diǎn)的右子結(jié)點(diǎn)。

??? 第47行：如果old為根結(jié)點(diǎn)就設(shè)置node為根結(jié)點(diǎn)。

??? 第49行：將node設(shè)置為old左子結(jié)點(diǎn)的父結(jié)點(diǎn)。

??? 第50-51行：如果old的右子結(jié)點(diǎn)存在，設(shè)置node為old右子結(jié)點(diǎn)的父結(jié)點(diǎn)。

??? 第52行：跳轉(zhuǎn)到70行進(jìn)一步處理。

??? （第55-68行 進(jìn)一步處理被刪結(jié)點(diǎn)至多只有一個非空子結(jié)點(diǎn)的情況）

??? 第55-56行：獲取node的父結(jié)點(diǎn)及顏色。

??? 第58-59行：如果node的子結(jié)點(diǎn)存在，就設(shè)置其子結(jié)點(diǎn)的父結(jié)點(diǎn)為node的父結(jié)點(diǎn)。

??? 第60-66行：node的父結(jié)點(diǎn)存在且node是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)時就設(shè)置node的子結(jié)點(diǎn)為父結(jié)點(diǎn)的左了結(jié)點(diǎn)，否則為父結(jié)點(diǎn)的右子結(jié)點(diǎn)。

??? 第67-68行：當(dāng)node為根結(jié)點(diǎn)時，刪除node后，其子結(jié)點(diǎn)成為根結(jié)點(diǎn)。

??? 第70-72行：如果被刪結(jié)點(diǎn)顏色為紅色，此時不影響紅黑樹性質(zhì)，否則調(diào)用__rb_erase_color函數(shù)進(jìn)一步處理。

??? 當(dāng)rb_erase函數(shù)刪除有兩個非空子結(jié)點(diǎn)的結(jié)點(diǎn)時比較復(fù)雜，難以理解。下面提供兩張刪除結(jié)點(diǎn)的示例圖便于理解，本想提供flash動畫的，但不知道怎么發(fā)到博客上來。

???? 示例1：假設(shè)被刪結(jié)點(diǎn)為父結(jié)點(diǎn)的左子結(jié)點(diǎn)，且被刪結(jié)點(diǎn)的右子結(jié)點(diǎn)沒有子結(jié)點(diǎn)

??? 示例2：假設(shè)被刪結(jié)點(diǎn)是父結(jié)點(diǎn)的右子結(jié)點(diǎn)，且被刪結(jié)點(diǎn)的右子結(jié)點(diǎn)存在兩個非空子結(jié)點(diǎn)

__rb_erase_color函數(shù)詳解：

static?void?__rb_erase_color(rb_node_t?*?node,?rb_node_t?*?parent,
			?????rb_root_t?*?root)
{
	rb_node_t?*?other;

	while?((!node?||?node->rb_color?==?RB_BLACK)?&&?node?!=?root->rb_node)
	{
		if?(parent->rb_left?==?node)
		{
			other?=?parent->rb_right;
			if?(other->rb_color?==?RB_RED)
			{
				other->rb_color?=?RB_BLACK;
				parent->rb_color?=?RB_RED;
				__rb_rotate_left(parent,?root);
				other?=?parent->rb_right;
			}
			if?((!other->rb_left?||
			?????other->rb_left->rb_color?==?RB_BLACK)
			????&&?(!other->rb_right?||
				other->rb_right->rb_color?==?RB_BLACK))
			{
				other->rb_color?=?RB_RED;
				node?=?parent;
				parent?=?node->rb_parent;
			}
			else
			{
				if?(!other->rb_right?||
				????other->rb_right->rb_color?==?RB_BLACK)
				{
					register?rb_node_t?*?o_left;
					if?((o_left?=?other->rb_left))
						o_left->rb_color?=?RB_BLACK;
					other->rb_color?=?RB_RED;
					__rb_rotate_right(other,?root);
					other?=?parent->rb_right;
				}
				other->rb_color?=?parent->rb_color;
				parent->rb_color?=?RB_BLACK;
				if?(other->rb_right)
					other->rb_right->rb_color?=?RB_BLACK;
				__rb_rotate_left(parent,?root);
				node?=?root->rb_node;
				break;
			}
		}
		else
		{
			other?=?parent->rb_left;
			if?(other->rb_color?==?RB_RED)
			{
				other->rb_color?=?RB_BLACK;
				parent->rb_color?=?RB_RED;
				__rb_rotate_right(parent,?root);
				other?=?parent->rb_left;
			}
			if?((!other->rb_left?||
			?????other->rb_left->rb_color?==?RB_BLACK)
			????&&?(!other->rb_right?||
				other->rb_right->rb_color?==?RB_BLACK))
			{
				other->rb_color?=?RB_RED;
				node?=?parent;
				parent?=?node->rb_parent;
			}
			else
			{
				if?(!other->rb_left?||
				????other->rb_left->rb_color?==?RB_BLACK)
				{
					register?rb_node_t?*?o_right;
					if?((o_right?=?other->rb_right))
						o_right->rb_color?=?RB_BLACK;
					other->rb_color?=?RB_RED;
					__rb_rotate_left(other,?root);
					other?=?parent->rb_left;
				}
				other->rb_color?=?parent->rb_color;
				parent->rb_color?=?RB_BLACK;
				if?(other->rb_left)
					other->rb_left->rb_color?=?RB_BLACK;
				__rb_rotate_right(parent,?root);
				node?=?root->rb_node;
				break;
			}
		}
	}
	if?(node)
		node->rb_color?=?RB_BLACK;
}

注解：

??? 函數(shù)參數(shù)：

??????? node：被刪結(jié)點(diǎn)的子結(jié)點(diǎn)

??????? parent：被刪結(jié)點(diǎn)的父結(jié)點(diǎn)

??????? root：紅黑樹根結(jié)點(diǎn)

??? 第6行：如果node是根結(jié)點(diǎn)或者其顏色為紅色while循環(huán)結(jié)束（調(diào)用__rb_erase_color函數(shù)的條件是被刪結(jié)點(diǎn)顏色為黑色，直接將被刪結(jié)點(diǎn)的子結(jié)點(diǎn)node置為黑色就滿足紅黑樹性質(zhì)）。

??? （第8-47行 處理node是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)情況）

??? 第10行：獲取node的兄弟結(jié)點(diǎn)，保存到other變量中。

??? 第11-17行：當(dāng)other結(jié)點(diǎn)顏色為紅色時（other父結(jié)點(diǎn)顏色必為黑），將其父結(jié)點(diǎn)置為紅色，other結(jié)點(diǎn)置為黑色。并針對其父結(jié)點(diǎn)進(jìn)行一次左旋轉(zhuǎn)讓other的父結(jié)點(diǎn)成為它的左子結(jié)點(diǎn)（此種情況的詳細(xì)步驟請參考上面提起過的紅黑樹原理網(wǎng)站中刪除結(jié)點(diǎn)的情況2），并從新獲取node的兄弟結(jié)點(diǎn)。

??? 第18-26行：如果other的兩個子結(jié)點(diǎn)都為黑色，這時就將other置為紅色。重新在node的父結(jié)點(diǎn)上做紅黑樹調(diào)整（參考紅黑樹原理網(wǎng)站中刪除結(jié)點(diǎn)的情況4）。

??? （第28-46行 處理other的子結(jié)點(diǎn)顏色為紅色的情況）

??? 第29-38行：當(dāng)other的右子結(jié)點(diǎn)為黑色時（此時other的左子結(jié)點(diǎn)必為紅色），將other的左子結(jié)點(diǎn)置為黑色，other置為紅色并針對other進(jìn)行一次右旋轉(zhuǎn)，使other的左子結(jié)點(diǎn)成為other的父結(jié)點(diǎn)（參考紅黑樹原理網(wǎng)站中刪除結(jié)點(diǎn)的情況5），重新獲取node的兄弟結(jié)點(diǎn)，保存到other變量中。

??? 第39-44行：設(shè)置other的顏色為其父結(jié)點(diǎn)的顏色，將父結(jié)點(diǎn)的顏色置為黑色，設(shè)置other的右子結(jié)點(diǎn)顏色為黑色并針對node的父結(jié)點(diǎn)進(jìn)行一次左旋轉(zhuǎn)（參考紅黑樹原理網(wǎng)站中刪除結(jié)點(diǎn)的情況6）。

??? 第49-87行：這里的處理步驟與8-47行類似。

??? 第89-90行：將根結(jié)點(diǎn)置為黑色。