linux内存管理之红黑树算法源码详解

时间：2018-11-23 11:42:01

关键字：红黑树 linux内存管理

[导读]linux内存管理模块中使用红黑树算法来提升虚拟内存查找速度，源码请参考linux内核目录下rbtree.c文件。红黑树算法原理在阅读红黑树算法源代码之前最好先了解红黑树原理。rb_insert_co

linux内存管理模块中使用红黑树算法来提升虚拟内存查找速度，源码请参考linux内核目录下rbtree.c文件。

红黑树算法原理

在阅读红黑树算法源代码之前最好先了解红黑树原理。

rb_insert_color函数详解：

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;
}

注解：

函数参数

node：新插入的结点。

root：红黑树的根结点。

第5行：往红黑树中插入结点时，总是将新插入结点颜色设置为红色。当新结点的父结点不存在或者父结点颜色为黑色时，不需要做红黑树调整直接跳到第63行。

第7行：获取node结点的祖父结点。

（第9-35行处理node父结点是其祖父结点左子结点的情况）

第12行：获取node的叔父结点。

第13-20行：当叔父结点存在并且颜色为红色，就将node的父结点与叔父结点的颜色设成黑色，并且将node的祖父结点颜色设成红色。现在祖父结点的颜色为红色，但祖父结点的父结点也可能为红色，不满足红黑树性质，因此将祖父结点当做新插入的结点重新进行红黑树调整。

第23-30行：叔父结点不存在或者颜色为黑色，此时node的祖父结点颜色必为黑色（因为node父结点颜色为红色），针对node的父结点进行一次左旋转，让父结点成为node的左子结点，并交换父结点与node结点位置，使以前的父结点成为新插入的结点。

第32-34得：将父结点的颜色设为黑色（此时新node的颜色还是红色），将祖父结点的颜色设为红色。再针对祖父结点进行一次右旋转，此时node拥有一个黑色的父结点及红色的兄弟结点。

（第36-61行处理node的父结点是其祖父结点的右子结点的情况）

第37行：获取node的叔父结点。

第38行：当node的叔父结点存在并且颜色为红色，就将node的父结点与叔父结点设置为黑色，并将node的祖父结点设置为红色。再将祖父结点当做新插入的结点重新进行红黑树调整。

第48-55行：如果node结点是其父结点的左子结点，就针对node的父结点进行一次右旋转，让其父结点成为node的右子结点，并交换父结点与node的位置，让以前的父结点成为新插入的结点

第57-59行：将父结点的颜色设为黑色（此时新node的颜色还是红色），将祖父结点的颜色设置为红色。再针对祖父结点进行一次左旋转，此时node拥有一个黑色的父结点及红色的兄弟结点。

第63行：将根结点的颜色设为黑色。这一步是有必要的，当新插入的结点为根结点或者在树调整过程中将根结点颜色变成了红色，这一行将根结点的颜色设成黑色。

rb_erase函数详解：

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

注解：

函数参数：

node：将要删除的结点

root：红黑树的根结点

（第6-9行处理被删结点至多只有一个子结点的情况，并找出不为空的子结点）

第6-7行：判断node的左子结点是否存在，如果不存在child针指就指向右子结点（右子结点也可能不存在）。

第8-9行：判断node的右子结点是否存在，如果不存在child指针就指向其左子结点。

（第11-53行处理被删结点有两个非空子结点的情况。当结点存在两个非空子结点时就找出其左子树中元素最大的结点或者右子树中元素最小的结点，并将该结点替换到将要被删除的结点位置上，再删除元素最大或者最小的结点。这时就将删除有两个非空子结点的问题变成删除至多只有一个非空子结点的问题。linux内存管理模块中的红黑树是按结点所在的内存首地址来排序存储的，如父结点的内存首地址一定会大于其左子结点首地址且小于右子结点首地址，因此在替换结点时只替换结点的位置不能改变结点的首地址）。

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

第14-16行：找出node的右子树中首地址最小的结点。如果找到就将该结点当做将要被删除的结点。

第17行：获取node的右子结点，经过第14-16行的处理现在node结点的首地址最小，所以node不可能存在左子结点，但右子结点可能会存在。

第18行：获取node的父结点。

第19行：获取node的颜色属性。

第21-22行：如果node的子结点存在，就设置其子结点的父结点为node的父结点（因为node结点将要被删除）。

第23-29行：如果node的父结点存在，当node是其父结点的左子结点时就设置node的子结点为其父结点的左子结点，否则就设置为其父结点的右子结点。

第30-31行：这种情况不可能会发生。

第33-34行：如果node等于old，说明old（old中保存有rb_erase函数中node参数的值，即要被替换的结点）的右子结点没有子结点，将父结点指向node结点（当node等于old时，在node替换old之后，node与其子结点的关系保持不变）。

（第35-38行这里将node结点替换掉old结点）

第35行：设置node的父结点为old结点的父结点。

第36行：将old结点颜色替换到node结点中。

第37行：将node的右子结点设置为old的右子结点。

第38行：将node的左子结点设置为old的左子结点。

第40-46行：如果old的父结点存在，当old是其父结点的左子结点时就将node变成其父结点的左子结点，否则为其父结点的右子结点。

第47行：如果old为根结点就设置node为根结点。

第49行：将node设置为old左子结点的父结点。

第50-51行：如果old的右子结点存在，设置node为old右子结点的父结点。

第52行：跳转到70行进一步处理。

（第55-68行进一步处理被删结点至多只有一个非空子结点的情况）

第55-56行：获取node的父结点及颜色。

第58-59行：如果node的子结点存在，就设置其子结点的父结点为node的父结点。

第60-66行：node的父结点存在且node是其父结点的左子结点时就设置node的子结点为父结点的左了结点，否则为父结点的右子结点。

第67-68行：当node为根结点时，删除node后，其子结点成为根结点。

第70-72行：如果被删结点颜色为红色，此时不影响红黑树性质，否则调用__rb_erase_color函数进一步处理。

当rb_erase函数删除有两个非空子结点的结点时比较复杂，难以理解。下面提供两张删除结点的示例图便于理解，本想提供flash动画的，但不知道怎么发到博客上来。

示例1：假设被删结点为父结点的左子结点，且被删结点的右子结点没有子结点

示例2：假设被删结点是父结点的右子结点，且被删结点的右子结点存在两个非空子结点

__rb_erase_color函数详解：

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;
}

注解：

函数参数：

node：被删结点的子结点

parent：被删结点的父结点

root：红黑树根结点

第6行：如果node是根结点或者其颜色为红色while循环结束（调用__rb_erase_color函数的条件是被删结点颜色为黑色，直接将被删结点的子结点node置为黑色就满足红黑树性质）。

（第8-47行处理node是其父结点的左子结点情况）

第10行：获取node的兄弟结点，保存到other变量中。

第11-17行：当other结点颜色为红色时（other父结点颜色必为黑），将其父结点置为红色，other结点置为黑色。并针对其父结点进行一次左旋转让other的父结点成为它的左子结点（此种情况的详细步骤请参考上面提起过的红黑树原理网站中删除结点的情况2），并从新获取node的兄弟结点。

第18-26行：如果other的两个子结点都为黑色，这时就将other置为红色。重新在node的父结点上做红黑树调整（参考红黑树原理网站中删除结点的情况4）。

（第28-46行处理other的子结点颜色为红色的情况）

第29-38行：当other的右子结点为黑色时（此时other的左子结点必为红色），将other的左子结点置为黑色，other置为红色并针对other进行一次右旋转，使other的左子结点成为other的父结点（参考红黑树原理网站中删除结点的情况5），重新获取node的兄弟结点，保存到other变量中。

第39-44行：设置other的颜色为其父结点的颜色，将父结点的颜色置为黑色，设置other的右子结点颜色为黑色并针对node的父结点进行一次左旋转（参考红黑树原理网站中删除结点的情况6）。

第49-87行：这里的处理步骤与8-47行类似。

第89-90行：将根结点置为黑色。