[TOC]

lib/rbtree.c 红黑树(Red-Black Tree) 内核中通用的有序数据管理

历史与背景

这项技术是为了解决什么特定问题而诞生的？

lib/rbtree.c 提供的红黑树（Red-Black Tree）是为了解决一个在计算机科学和操作系统内核中都非常普遍的需求：如何在一个动态变化的数据集合中，高效地维护元素的有序性，并提供快速的查找、插入和删除操作。

在红黑树出现之前，内核中的有序数据管理主要依赖于：

  • 有序链表：实现简单，但查找操作需要O(n)的时间，当数据量大时性能极差。
  • 简单的二叉搜索树：在理想情况下查找性能是O(log n)，但在最坏情况下（例如，按顺序插入元素）会退化成一个链表，性能同样下降到O(n)。

红黑树作为一种自平衡的二叉搜索树（Self-balancing Binary Search Tree），被引入来解决这个问题。它通过一套相对简单的规则（着色和旋转），确保树在任何插入和删除操作后都保持“大致平衡”，从而保证了其查找、插入和删除操作在最坏情况下的时间复杂度都能维持在O(log n)。这为内核中需要高效处理有序数据的子系统提供了一个可靠、性能有保障的基础构件。

它的发展经历了哪些重要的里程碑或版本迭代？

红黑树算法本身是在1970年代末发明的，Linux内核从早期就引入了其实现。其在内核中的发展主要体现在：

  • 通用库的建立：内核将红黑树的实现抽象成一个通用的库，位于lib/rbtree.c，并提供了清晰的API（如rb_insert_color, rb_erase, rb_next, rb_prev等），供所有内核子系统使用。
  • API的优化：内核的红黑树API设计得非常高效。它不是一个黑盒实现，而是要求使用者将struct rb_node嵌入到自己的数据结构中。核心的插入和删除操作被分解为“更新链接”和“重新平衡”两个步骤，这使得调用者可以在不了解红黑树内部复杂平衡逻辑的情况下，高效地将其集成到自己的数据结构和锁模型中。
  • 文档和示例的完善：为了帮助内核开发者正确使用这个略显复杂的API，内核文档中包含了详细的解释和示例代码。
  • 被更优化的数据结构取代：在某些特定领域，红黑树的通用性反而成为其弱点。最重要的里程碑是，在管理VMA（虚拟内存区域）这一核心场景中，红黑树因其在高并发下的锁争用和缓存效率问题，被专门为此优化的Maple Tree所取代。这标志着内核数据结构向更高性能、更高并发性的方向演进。

目前该技术的社区活跃度和主流应用情况如何？

红黑树仍然是Linux内核中一个非常重要和活跃的基础数据结构。虽然它在VMA管理这个“明星应用”中的地位被取代，但它仍然被广泛用于许多其他场景：

  • 高精度定时器（hrtimers）：内核使用红黑树来管理所有待处理的高精度定时器，按照它们的到期时间进行排序，以便能快速找到下一个即将到期的定时器。
  • 文件描述符管理 (fdtable)：在某些情况下，当一个进程打开了大量的文件描述符时，内核可能会使用红黑树来管理fd到struct file的映射。
  • I/O调度器：CFQ（Completely Fair Queuing）和BFQ（Budget Fair Queuing）等I/O调度器使用红黑树来管理等待I/O的请求，根据扇区地址或时间片进行排序。
  • 网络：用于管理各种需要排序的连接或会话。

核心原理与设计

它的核心工作原理是什么？

红黑树是一种二叉搜索树，它额外满足以下几条红黑属性：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点是黑色的。
  3. 所有叶子节点（NIL节点，空节点）都是黑色的。
  4. 如果一个节点是红色的，那么它的两个子节点都是黑色的（不能有两个连续的红色节点）。
  5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（黑高平衡）。

lib/rbtree.c 的核心就是实现了在插入和删除操作后，通过**旋转（Rotation）和重新着色（Recoloring）**来维护这五条属性的算法。

  • 插入：新插入的节点总是先被标记为红色。这可能会违反属性4。然后，算法会从插入点开始向上回溯，通过一系列的旋转和重新着色来修复可能出现的“红-红”冲突。
  • 删除：删除操作更复杂。如果删除的是一个黑色节点，会破坏属性5。算法通过一个更复杂的修复过程，移动节点、旋转和重新着色来恢复树的黑高平衡。

正是这些规则，特别是属性4和5，共同保证了树中最长的路径不会超过最短路径的两倍，从而确保了树的高度始终保持在O(log n)级别。

它的主要优势体现在哪些方面？

  • 性能保证：查找、插入、删除操作的最坏时间复杂度都是O(log n)，性能非常稳定。
  • 有序性：它天然地维护了数据的有序性，可以非常高效地进行中序遍历，或者查找某个键的前驱和后继（rb_prev, rb_next）。
  • 通用性：它可以用于任何可以定义比较大小关系的数据类型。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

  • 缓存效率不高：红黑树是典型的指针密集型结构，每个节点都是单独分配的，内存地址不连续。遍历树的过程会导致大量的指针追逐（pointer chasing），造成CPU缓存命中率低。
  • 并发性能差：对红黑树的任何修改操作（插入、删除）通常都需要一个全局锁来保护整棵树，这在高并发环境下会成为严重的性能瓶颈。
  • 实现复杂：虽然内核库封装了这些复杂性，但红黑树的平衡算法本身是相当复杂的。
  • 不适合范围查询：虽然可以实现，但它不如专门为此设计的B树（如Maple Tree）或跳表高效。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

在内核中，如果需要一个有序的数据集合，数据量较大，插入和删除操作频繁，且并发写入的争用不严重时，红黑树是一个非常好的通用解决方案。

  • 定时器管理：高精度定时器的数量可能很多，内核需要频繁地添加新定时器和移除已触发的定时器。红黑树按照到期时间排序，使得内核总能以O(1)的时间复杂度找到最早到期的定时器（树的最左侧节点），并以O(log n)的复杂度添加和删除定时器。
  • I/O请求排序：一个磁盘可能有成千上万个等待处理的I/O请求。I/O调度器使用红黑树按照磁盘扇区号对这些请求进行排序，以便进行电梯调度（elevator algorithm），最大限度地减少磁头移动，提高磁盘吞吐量。

是否有不推荐使用该技术的场景？为什么？

  • 高并发读写场景：特别是读多写少的场景，如果对性能要求极高，应考虑使用RCU友好、读取无锁的数据结构，如Maple Tree。
  • 只需要键值查找，不关心顺序：如果只关心快速的精确匹配查找，哈希表通常是更好的选择，其平均性能为O(1)。
  • 键是整数且稀疏：对于这种情况，基数树（Radix Tree）或其后继者XArray在空间效率和查找性能上通常更优。

对比分析

请将其 与 其他相似技术 进行详细对比。

特性 红黑树 (Red-Black Tree) Maple Tree 哈希表 (Hash Table) 基数树 / XArray
核心功能 通用的、有序的单键映射 并发的、缓存优化的范围映射 无序的单键映射 针对整数键的空间优化映射
数据顺序 有序 有序 无序 有序
并发/锁 需读写锁或自旋锁保护 读取无锁 (RCU) 需锁保护（通常分桶） 读取通常无锁 (RCU)
缓存效率 低 (指针密集) 高 (B树节点) 高 (数组访问) 高 (Trie结构)
查找性能 O(log n) O(log n) (常数因子小) 平均 O(1) O(k) (k为键的位数)
范围查找 支持 非常高效 不支持 支持，高效
典型用途 定时器管理，I/O调度 VMA管理 dcache, PID表 页缓存
关键优势 通用的、有性能保证的有序容器 高并发读性能和缓存效率 最快的平均查找速度 整数键的空间效率和标签功能

include/linux/rbtree.h

RB_CLEAR_NODE

1
2
#define RB_CLEAR_NODE(node)  \
	((node)->__rb_parent_color = (unsigned long)(node))

RB_EMPTY_NODE

1
2
3
/* 'empty' 节点是已知未插入 RBTREE 的节点*/
#define RB_EMPTY_NODE(node)  \
	((node)->__rb_parent_color == (unsigned long)(node))
1
2
3
4
5
6
7
8
static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
				struct rb_node **rb_link)
{
	node->__rb_parent_color = (unsigned long)parent;
	node->rb_left = node->rb_right = NULL;

	*rb_link = node;
}

rb_insert_color_cached

1
2
3
4
5
6
7
8
static inline void rb_insert_color_cached(struct rb_node *node,
					  struct rb_root_cached *root,
					  bool leftmost)
{
	if (leftmost)
		root->rb_leftmost = node;
	rb_insert_color(node, &root->rb_root);
}

rb_add_cached

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
 * 下面的帮助程序函数使用 2 个运算符和 3 种不同的调用约定。运算符的相关方式如下：
 *
 *	comp(a->key,b) < 0  := less(a,b)
 *	comp(a->key,b) > 0  := less(b,a)
 *	comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
 *
 * 如果这些运算符在元素上定义了部分顺序，则我们无法保证找到与键匹配的元素。参见 rb_find（）。
 *
 * 这样做的原因是允许 find（） 接口，而不需要堆栈上的虚拟对象，由于对象大小，这可能不可行。
 */

/**
 * rb_add_cached（） - 将@node插入到最左侧缓存的树@tree
 * @node：要插入的节点
 * @tree：要将@node插入到的最左侧缓存树
 * @less：定义（部分）节点顺序的运算符
 *
 * 当它是新的最左侧或 NULL 时，返回 @node。
 */

/* 主要功能是将一个节点插入到红黑树中，同时维护树的左侧最小节点缓存（leftmost）。
如果插入的节点成为新的最左节点，则返回该节点；否则返回 NULL。 */
static __always_inline struct rb_node *
rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
	      bool (*less)(struct rb_node *, const struct rb_node *))
{
	struct rb_node **link = &tree->rb_root.rb_node;
	struct rb_node *parent = NULL;
	bool leftmost = true;

	while (*link) {
		parent = *link;
		if (less(node, parent)) {
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = false;
		}
	}

	rb_link_node(node, parent, link);
	rb_insert_color_cached(node, tree, leftmost);

	return leftmost ? node : NULL;
}

rb_parent 返回红黑树的父节点

1
2
/* ~3执行对齐操作以及屏蔽颜色信息 */
#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

rb_entry 红黑树条目获取

1
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)

include/linux/rbtree_augmented.h

RB_RED RB_BLACK

1
2
#define	RB_RED		0
#define	RB_BLACK	1

rb_set_parent_color 红黑树设置父节点颜色

  • 同时设置红黑树节点的父节点和颜色信息。红黑树的节点通常需要存储父节点指针和颜色（红或黑），而为了节省内存和提高效率，这里将父节点指针和颜色信息压缩存储在一个字段中，即 __rb_parent_color
1
2
3
4
5
static inline void rb_set_parent_color(struct rb_node *rb,
				       struct rb_node *p, int color)
{
	rb->__rb_parent_color = (unsigned long)p + color;
}

define

1
2
3
4
5
6
7
8
9
10
/* 提取其最低位的值。最低位通常用来表示颜色，其中 0 表示黑色，1 表示红色 */
#define __rb_color(pc)     ((pc) & 1)
/* 该宏直接调用 __rb_color(pc)，返回颜色值。如果结果是 0，表示节点是黑色 */
#define __rb_is_black(pc)  __rb_color(pc)
/* 判断节点是否为红色。如果最低位是 1，取反后为 0，表示红色 */
#define __rb_is_red(pc)    (!__rb_color(pc))
/* 提取红黑树节点 rb 的颜色信息。它访问节点的 __rb_parent_color 字段，并调用 __rb_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)

RB_DECLARE_CALLBACKS 声明增强红黑树回调函数的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
 * 声明增强红黑树回调函数的模板 (通用情况)
 *
 * RBSTATIC:    'static' 或 空。用于控制生成的结构体和函数的链接属性。
 * RBNAME:      rb_augment_callbacks结构体实例的名称。
 * RBSTRUCT:    树节点所嵌入的数据结构的类型 (例如 struct sched_entity)。
 * RBFIELD:     rb_node结构体在RBSTRUCT中的成员名 (例如 run_node)。
 * RBAUGMENTED: 在RBSTRUCT中，持有子树聚合数据的成员名 (例如 min_vruntime)。
 * RBCOMPUTE:   一个函数的名称，该函数负责重新计算RBAUGMENTED数据。
 */

/*
 * 这是一个C预处理器宏，它会展开为几个函数和一个结构体的定义。
 * 它使用'##'拼接操作符来根据传入的RBNAME动态生成函数名。
 */
#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,				\
			     RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE)	\
/*
 * 生成 _propagate (传播) 回调函数。
 * 当一个节点的子节点聚合数据发生变化时，此函数被调用，
 * 负责将这个变化自底向上地传播到其所有祖先节点。
 */
static inline void							\
RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
{									\
	/* 从节点rb开始，向上遍历直到stop节点（通常是NULL，即根的父节点）。*/\
	while (rb != stop) {						\
		/* 获取rb节点所属的完整数据结构(RBSTRUCT)的指针。*/\
		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
		/* 调用用户提供的RBCOMPUTE函数，重新计算当前节点的聚合数据。
		 * 如果RBCOMPUTE返回true，表示聚合数据没有变化，无需再向上传播，可以提前终止。*/\
		if (RBCOMPUTE(node, true))				\
			break;						\
		/* 获取当前节点的父节点，准备下一次循环。*/\
		rb = rb_parent(&node->RBFIELD);				\
	}								\
}									\
/*
 * 生成 _copy (拷贝) 回调函数。
 * 在红黑树的某些操作中（如节点替换），需要将一个节点的聚合数据
 * 完整地拷贝到另一个节点。
 */
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);		\
	/* 直接将旧节点的聚合数据(RBAUGMENTED)拷贝给新节点。*/\
	new->RBAUGMENTED = old->RBAUGMENTED;				\
}									\
/*
 * 生成 _rotate (旋转) 回调函数。
 * 这是最关键的回调。当红黑树进行一次旋转操作后，此函数被调用。
 * @rb_old: 节点在旋转前的父节点。
 * @rb_new: 节点在旋转后的新父节点。
 */
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;				\
	/* 然后，调用用户提供的RBCOMPUTE函数，重新计算旧父节点的聚合数据，
	 * 因为它的子树结构已经发生了根本变化。*/\
	RBCOMPUTE(old, false);						\
}									\
/*
 * 生成一个const的rb_augment_callbacks结构体实例。
 * RBSTATIC控制其为static或全局。RBNAME是其实例名。
 */
RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
	/* 将刚刚生成的三个函数的地址，赋值给结构体的对应函数指针成员。*/\
	.propagate = RBNAME ## _propagate,				\
	.copy = RBNAME ## _copy,					\
	.rotate = RBNAME ## _rotate					\
};

rb_insert_augmented_cached 将一个节点插入到一个带缓存的增强红黑树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
 * 在重新平衡红黑树时，修复红黑树并更新附加信息。
 *
 * 在插入节点时，用户必须首先更新从根节点到新插入节点路径上的附加信息，
 * 然后照常调用 rb_link_node()，并使用 rb_insert_augmented() 取代通常的
 * rb_insert_color() 调用。
 * 如果 rb_insert_augmented() 在过程中对红黑树进行了重新平衡，它会回调
 * 用户提供的函数，以更新受影响子树上的附加信息。
 */
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);
}

static inline void
rb_insert_augmented_cached(struct rb_node *node,
			   struct rb_root_cached *root, bool newleft,
			   const struct rb_augment_callbacks *augment)
{
	if (newleft)
		root->rb_leftmost = node;
	rb_insert_augmented(node, &root->rb_root, augment);
}

rb_add_augmented_cached 将一个节点插入到一个带缓存的增强红黑树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
 * 这是一个静态、强制内联的函数，用于将一个节点插入到一个带缓存的增强红黑树中。
 * @node:    指向将要被插入的rb_node。
 * @tree:    指向目标红黑树的根结构(rb_root_cached)。它包含了根节点和最左侧节点的缓存。
 * @less:    一个函数指针，指向一个由调用者提供的比较函数。它用于决定节点在树中的排序。
 * @augment: 一个函数指针，指向一个由调用者提供的、包含增强回调函数的结构体。
 * 返回值: 如果新插入的node成为了树中新的最左节点，则返回node；否则返回NULL。
 */
static __always_inline struct rb_node *
rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree,
			bool (*less)(struct rb_node *, const struct rb_node *),
			const struct rb_augment_callbacks *augment)
{
	/* @link: 一个指向rb_node指针的指针。它从根节点指针开始，用于在树中向下遍历。*/
	struct rb_node **link = &tree->rb_root.rb_node;
	/* @parent: 指向遍历路径上的父节点，最终将是新node的父节点。*/
	struct rb_node *parent = NULL;
	/* @leftmost: 布尔标志，用于追踪新node是否被插入到了整棵树的最左侧路径上。*/
	bool leftmost = true;

	/*
	 * 阶段一：标准的二叉搜索树插入，寻找插入位置。
	 * 循环直到找到一个空的link。
	 */
	while (*link) {
		/* 将parent指向当前的link所指向的节点。*/
		parent = *link;
		/* 调用用户提供的less函数，比较新node和当前parent节点。*/
		if (less(node, parent)) {
			/* 如果新node小于parent，则向左子树前进。*/
			link = &parent->rb_left;
		} else {
			/* 如果新node大于等于parent，则向右子树前进。*/
			link = &parent->rb_right;
			/* 只要向右走过一次，就不可能是最左侧的节点了。*/
			leftmost = false;
		}
	}

	/*
	 * 阶段二：链接节点并进行初步的增强属性传播。
	 */
	/* 调用rb_link_node，将新node链接到parent下，其链接指针是link。*/
	rb_link_node(node, parent, link);
	/*
	 * 调用augment->propagate回调。它会从parent开始，自底向上地传播
	 * 增强属性的变更。注释(suboptimal)指出这不是最高效的方式，
	 * 因为后续的旋转可能使其成为冗余操作，但它简化了逻辑。
	 */
	augment->propagate(parent, NULL);

	/*
	 * 阶段三：执行颜色修复和精确的增强属性更新。
	 */
	/*
	 * 调用rb_insert_augmented_cached，这是核心的修复函数。
	 * 它会执行红黑树的颜色调整和旋转，并在每次旋转时，调用augment->rotate
	 * 回调来精确更新增强属性。它还会利用leftmost标志来更新tree->rb_leftmost缓存。
	 */
	rb_insert_augmented_cached(node, tree, leftmost, augment);

	/* 根据leftmost标志，返回node或NULL。*/
	return leftmost ? node : NULL;
}

__rb_erase_augmented 增强红黑树的物理节点删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/*
 * 这是一个静态、强制内联的函数，执行增强型红黑树的物理节点删除。
 * 它返回需要进行颜色修复的起始节点，如果无需修复则返回NULL。
 */
static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
		     const struct rb_augment_callbacks *augment)
{
	/* @child: 指向node的右子节点，用作临时变量。*/
	struct rb_node *child = node->rb_right;
	/* @tmp: 指向node的左子节点，用作临时变量。*/
	struct rb_node *tmp = node->rb_left;
	/* @parent: 指向某个节点的父节点。*/
	/* @rebalance: 指向需要进行颜色修复的起始节点，作为函数的返回值。*/
	struct rb_node *parent, *rebalance;
	/* @pc: 用于存储一个节点的__rb_parent_color字段的原始值。*/
	unsigned long pc;

	/*
	 * 情况1：被删除的节点node最多只有一个子节点。
	 */
	/* 检查node是否没有左子节点。*/
	if (!tmp) {
		/*
		 * 被删除的节点最多只有1个子节点（右子节点），这是简单情况！
		 *
		 * 注意，如果有一个子节点，由于性质5，它必须是红色的；
		 * 而由于性质4，node节点必须是黑色的。我们在这里局部调整颜色，
		 * 以便稍后绕过__rb_erase_color()。
		 */
		/* pc = node的父节点指针和颜色信息。*/
		pc = node->__rb_parent_color;
		/* parent = node的父节点。*/
		parent = __rb_parent(pc);
		/* 调用__rb_change_child，用node的右子节点child替换node的位置。*/
		__rb_change_child(node, child, parent, root);
		/* 如果右子节点存在。*/
		if (child) {
			/* 子节点child继承node的父节点和颜色。因为node是黑，child是红，
			 * 替换后child变为黑色，黑高不变，无需再平衡。*/
			child->__rb_parent_color = pc;
			/* rebalance设为NULL，表示无需再平衡。*/
			rebalance = NULL;
		} else
			/* 如果node没有子节点，则只有当node是黑色时，才可能破坏黑高。
			 * 此时，需要从其父节点开始进行再平衡。*/
			rebalance = __rb_is_black(pc) ? parent : NULL;
		/* 将tmp指向parent，用于最后的统一propagate。*/
		tmp = parent;
	/* 检查node是否没有右子节点（但有左子节点）。*/
	} else if (!child) {
		/* 仍然是情况1，但这次唯一的子节点是node->rb_left */
		/* 左子节点tmp继承node的父节点和颜色。同样，无需再平衡。*/
		tmp->__rb_parent_color = pc = node->__rb_parent_color;
		parent = __rb_parent(pc);
		__rb_change_child(node, tmp, parent, root);
		rebalance = NULL;
		tmp = parent;
	} else {
		/*
		 * 情况2和3：被删除的节点node有两个子节点。
		 * 我们需要找到node的中序后继（successor）来替换它。
		 */
		/* @successor: 指向node的中序后继。初始时，它从node的右子节点开始寻找。*/
		struct rb_node *successor = child;
		/* @child2: 指向后继节点的右子节点。*/
		struct rb_node *child2;

		/* tmp指向后继节点的左子节点，用于判断是情况2还是3。*/
		tmp = child->rb_left;
		/* 如果node的右子节点没有左子树，那么它就是中序后继。*/
		if (!tmp) {
			/*
			 * 情况2：node的后继就是它的右子节点。
			 * 结构变化示意图:
			 *    (n)          (s)
			 *    / \          / \
			 *  (x) (s)  ->  (x) (c)
			 *        \
			 *        (c)
			 */
			/* parent此时是后继节点s自己，因为它的位置将发生变化。*/
			parent = successor;
			/* child2是后继节点s的右子节点c。*/
			child2 = successor->rb_right;

			/* 调用回调，将node的增强数据（如min_vruntime）复制给后继节点s。*/
			augment->copy(node, successor);
		} else {
			/*
			 * 情况3：node的后继是其右子树中最左边的节点。
			 * 结构变化示意图:
			 *    (n)          (s)
			 *    / \          / \
			 *  (x) (y)  ->  (x) (y)
			 *      /            /
			 *    (p)          (p)
			 *    /            /
			 *  (s)          (c)
			 *    \
			 *    (c)
			 */
			/* 循环向下，找到右子树中最左边的节点，即后继s。*/
			do {
				parent = successor;
				successor = tmp;
				tmp = tmp->rb_left;
			} while (tmp);
			/* child2是后继s的右子节点c。*/
			child2 = successor->rb_right;
			/* 将后继s原来的父节点p的左指针，指向后继s的右子节点c。*/
			WRITE_ONCE(parent->rb_left, child2);
			/* 将后继s的右指针，指向node原来的右子节点y。*/
			WRITE_ONCE(successor->rb_right, child);
			/* 设置y的父节点为s。*/
			rb_set_parent(child, successor);

			/* 调用回调，复制增强数据。*/
			augment->copy(node, successor);
			/* 调用回调，从p开始向上更新增强数据，因为它的子树结构变了。*/
			augment->propagate(parent, successor);
		}

		/*
		 * 以下是情况2和3共有的、用后继节点替换被删节点的步骤。
		 */
		/* tmp指向node原来的左子节点x。*/
		tmp = node->rb_left;
		/* 将后继s的左指针，指向node原来的左子节点x。*/
		WRITE_ONCE(successor->rb_left, tmp);
		/* 设置x的父节点为s。*/
		rb_set_parent(tmp, successor);

		/* pc = node原来的颜色和父节点信息。*/
		pc = node->__rb_parent_color;
		/* tmp = node原来的父节点。*/
		tmp = __rb_parent(pc);
		/* 调用__rb_change_child，用后继s替换node的位置。*/
		__rb_change_child(node, successor, tmp, root);

		/* 如果后继s的右子节点c存在。*/
		if (child2) {
			/* 将c的颜色设为黑色，并设置其父节点为p。
			 * 这种情况下，黑高也不会改变，无需再平衡。*/
			rb_set_parent_color(child2, parent, RB_BLACK);
			rebalance = NULL;
		} else {
			/* 如果c不存在，则只有当后继s是黑色时，才可能破坏黑高。
			 * 此时需要从p开始再平衡。*/
			rebalance = rb_is_black(successor) ? parent : NULL;
		}
		/* 后继s继承node原来的颜色。*/
		successor->__rb_parent_color = pc;
		/* 将tmp指向后继s，用于最后的统一propagate。*/
		tmp = successor;
	}

	/*
	 * 最后，从发生结构变化的节点（tmp）开始，向上回溯传播增强数据的变化。
	 */
	augment->propagate(tmp, NULL);
	
	/* 返回需要进行颜色修复的起始节点。*/
	return rebalance;
}

rb_erase_augmented_cached 从增强红黑树中删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
 * 这是一个静态、强制内联的函数，用于从一个增强型红黑树中删除一个节点。
 * 这是处理增强型红黑树删除的标准接口。
 *
 * @node:    指向将要被删除的rb_node。
 * @root:    指向红黑树的根结构体rb_root。
 * @augment: 指向一组回调函数，用于在树旋转时更新节点的增强数据。
 */
static __always_inline void
rb_erase_augmented(struct rb_node *node, struct rb_root *root,
		   const struct rb_augment_callbacks *augment)
{
	/* @rebalance: 声明一个指向rb_node的指针，用于接收需要再平衡的起始节点。*/
	struct rb_node *rebalance;

	/*
	 * 调用底层的__rb_erase_augmented函数，执行核心的节点摘除和替换操作。
	 * 这个函数会处理所有指针的修改，并返回一个指向需要进行颜色修复的起始节点的指针。
	 * 如果返回NULL，说明树的黑高属性未被破坏，无需再平衡。
	 * @augment参数被透传下去，以便在结构调整时，能正确地更新增强数据。
	 */
	rebalance = __rb_erase_augmented(node, root, augment);
	
	/*
	 * 检查__rb_erase_augmented的返回值。
	 */
	if (rebalance)
		/*
		 * 如果rebalance不为NULL，说明红黑树的属性已被破坏。
		 * 调用__rb_erase_color函数，从rebalance节点开始，
		 * 执行一系列的颜色变换和树旋转操作，以恢复红黑树的平衡。
		 * augment->rotate是一个函数指针，指向在旋转时用于更新增强数据的回调函数。
		 */
		__rb_erase_color(rebalance, root, augment->rotate);
}

/*
 * 这是一个静态、强制内联的函数，用于从一个带缓存的、增强型红黑树中删除一个节点。
 *
 * @node: 指向将要被删除的rb_node。
 * @root: 指向rb_root_cached结构体，它包含了红黑树的根和一个指向最左节点的缓存指针。
 * @augment: 指向一组回调函数，用于在树旋转时更新节点的增强数据。
 */
static __always_inline void
rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
			  const struct rb_augment_callbacks *augment)
{
	/*
	 * 检查被删除的节点node，是否就是被root缓存的最左节点(rb_leftmost)。
	 */
	if (root->rb_leftmost == node)
		/*
		 * 如果是，说明最左节点即将被删除，缓存会失效。
		 * 必须在删除前，找到该节点的中序后继节点（即树中下一个最小的节点），
		 * 并用它来更新最左节点的缓存。rb_next(node)负责找到这个后继。
		 * 如果node没有后继（即它是树中最后一个节点），rb_next会返回NULL，
		 * 此时rb_leftmost也被正确地更新为NULL。
		 */
		root->rb_leftmost = rb_next(node);
	
	/*
	 * 调用通用的、非缓存版的增强型红黑树节点删除函数。
	 * @node:      要删除的节点。
	 * @&root->rb_root: 从缓存版root结构体中，取出标准的rb_root成员的地址传进去。
	 * @augment:   透传增强回调函数。
	 *
	 * rb_erase_augmented会执行实际的节点摘除、颜色修复和树再平衡（旋转）等
	 * 所有复杂操作，并在需要时调用augment回调。
	 */
	rb_erase_augmented(node, &root->rb_root, augment);
}

lib/rbtree.c

rb_red_parent 返回树的红色父节点

1
2
3
4
static inline struct rb_node *rb_red_parent(struct rb_node *red)
{1
	return (struct rb_node *)red->__rb_parent_color;
}

__rb_change_child 在红黑树的结构发生变化时更新子节点

  • 在红黑树的结构发生变化时（例如旋转或节点替换），将父节点的子节点指针从旧节点（old）更新为新节点（new）。如果旧节点是根节点，则更新红黑树的根节点指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 
struct rb_node *old：指向需要被替换的旧节点。
struct rb_node *new：指向替换旧节点的新节点。
struct rb_node *parent：指向旧节点的父节点。如果旧节点是根节点，则 parent 为 NULL。
struct rb_root *root：指向红黑树的根节点，用于在必要时更新根节点指针 
*/
static inline void
__rb_change_child(struct rb_node *old, struct rb_node *new,
		  struct rb_node *parent, struct rb_root *root)
{
	/* 如果 parent 不为 NULL，说明旧节点有父节点，需要更新父节点的子节点指针 */
	if (parent) {
		/* 如果旧节点是父节点的左子节点（parent->rb_left == old），将父节点的左子节点指针更新为新节点 */
		if (parent->rb_left == old)
			WRITE_ONCE(parent->rb_left, new);
		else
			WRITE_ONCE(parent->rb_right, new);
	} else
		/* 如果 parent 为 NULL，说明旧节点是红黑树的根节点。此时，将红黑树的根节点指针（root->rb_node）更新为新节点 */
		WRITE_ONCE(root->rb_node, new);
}

__rb_rotate_set_parents 在树的旋转操作中更新节点的父节点和颜色信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * 旋转辅助函数：
 * - old 的 parent 和 color 被分配给 new
 * - old 被指定为父级，将 'color' 指定为颜色。
 */
static inline void
__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
			struct rb_root *root, int color)
{
	struct rb_node *parent = rb_parent(old);
	/* 将旧节点（old）的父节点和颜色信息赋值给新节点（new */
	new->__rb_parent_color = old->__rb_parent_color;
	/* 将新节点（new）设置为旧节点（old）的父节点，并为旧节点设置新的颜色 */
	rb_set_parent_color(old, new, color);
	/* 更新父节点的子节点指向，确保树的结构正确 */
	__rb_change_child(old, new, parent, root);
}

__rb_insert 将一个新节点插入到红黑树中

  • __rb_insert 函数用于将一个新节点插入到红黑树中，并通过旋转和重新着色来修复可能违反红黑树性质的情况
  • augment_rotate: 在旋转节点时更新增强信息
    • 在 左旋 / 右旋 过程中，红黑树的结构发生变化，某些增强信息（如最大值、区间范围等）可能需要更新。
    • augment_rotate() 负责在旋转后 调整这些额外信息，确保树的增强数据仍然正确。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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))
{
    struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;

    while (true) {
        /*
         * 循环不变式：当前节点 node 是红色。
         */
        if (unlikely(!parent)) {
            /*
             * 情况 1：插入的节点是根节点。
             * 这是树的第一个节点，或者在后续递归中回到根节点。
             * 根据红黑树性质，将根节点设置为黑色。
             */
            rb_set_parent_color(node, NULL, RB_BLACK);
            break;
        }

        /*
         * 如果父节点是黑色，则红黑树性质未被破坏，直接退出。
         * 否则需要修复，因为红黑树不允许连续的红色节点。
         */
        if (rb_is_black(parent))
            break;

        /*
         * 获取祖父节点（父节点的父节点），祖父节点必定存在。
         */
        gparent = rb_red_parent(parent);

        /*
         * 检查父节点是祖父节点的左子节点还是右子节点。
         * 以下逻辑分为两部分：父节点是祖父节点的左子节点或右子节点。
         */
        tmp = gparent->rb_right;
        if (parent != tmp) {	/* 父节点是祖父节点的左子节点 */
            if (tmp && rb_is_red(tmp)) {
                /*
                 * 情况 1：叔节点是红色（颜色翻转）。
                 *
                 *       G            g
                 *      / \          / \
                 *     p   u  -->   P   U
                 *    /            /
                 *   n            n
                 *
                 * 将父节点和叔节点设置为黑色，将祖父节点设置为红色。
                 * 然后将祖父节点作为新的当前节点，继续向上检查。
                 */
                rb_set_parent_color(tmp, gparent, RB_BLACK);
                rb_set_parent_color(parent, gparent, RB_BLACK);
                node = gparent;
                parent = rb_parent(node);
                rb_set_parent_color(node, parent, RB_RED);
                continue;
            }

            tmp = parent->rb_right;
            if (node == tmp) {
                /*
                 * 情况 2：叔节点是黑色，且当前节点是父节点的右子节点。
                 * 对父节点进行左旋，转换为情况 3。
                 *
                 *      G             G
                 *     / \           / \
                 *    p   U  -->    n   U
                 *     \           /
                 *      n         p
                 */
                tmp = node->rb_left;
                WRITE_ONCE(parent->rb_right, tmp);
                WRITE_ONCE(node->rb_left, parent);
                if (tmp)
                    rb_set_parent_color(tmp, parent, RB_BLACK);
                rb_set_parent_color(parent, node, RB_RED);
                augment_rotate(parent, node);
                parent = node;
                tmp = node->rb_right;
            }

            /*
             * 情况 3：叔节点是黑色，且当前节点是父节点的左子节点。
             * 对祖父节点进行右旋，修复红黑树性质。
             *
             *        G           P
             *       / \         / \
             *      p   U  -->  n   g
             *     /                 \
             *    n                   U
             */
            WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
            WRITE_ONCE(parent->rb_right, gparent);
            if (tmp)
                rb_set_parent_color(tmp, gparent, RB_BLACK);
            __rb_rotate_set_parents(gparent, parent, root, RB_RED);
            augment_rotate(gparent, parent);
            break;
        } else { /* 父节点是祖父节点的右子节点 */
            tmp = gparent->rb_left;
            if (tmp && rb_is_red(tmp)) {
                /*
                 * 情况 1：叔节点是红色（颜色翻转）。
                 * 逻辑与父节点为祖父节点左子节点时对称。
                 */
                rb_set_parent_color(tmp, gparent, RB_BLACK);
                rb_set_parent_color(parent, gparent, RB_BLACK);
                node = gparent;
                parent = rb_parent(node);
                rb_set_parent_color(node, parent, RB_RED);
                continue;
            }

            tmp = parent->rb_left;
            if (node == tmp) {
                /*
                 * 情况 2：叔节点是黑色，且当前节点是父节点的左子节点。
                 * 对父节点进行右旋，转换为情况 3。
                 */
                tmp = node->rb_right;
                WRITE_ONCE(parent->rb_left, tmp);
                WRITE_ONCE(node->rb_right, parent);
                if (tmp)
                    rb_set_parent_color(tmp, parent, RB_BLACK);
                rb_set_parent_color(parent, node, RB_RED);
                augment_rotate(parent, node);
                parent = node;
                tmp = node->rb_left;
            }

            /*
             * 情况 3：叔节点是黑色，且当前节点是父节点的右子节点。
             * 对祖父节点进行左旋，修复红黑树性质。
             */
            WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
            WRITE_ONCE(parent->rb_left, gparent);
            if (tmp)
                rb_set_parent_color(tmp, gparent, RB_BLACK);
            __rb_rotate_set_parents(gparent, parent, root, RB_RED);
            augment_rotate(gparent, parent);
            break;
        }
    }
}

__rb_insert_augmented 增强版红黑树的操作函数

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * 增强版红黑树的操作函数。
 *
 * 它实例化了与非增强版本中相同的 __always_inline 函数，
 * 但这一次使用了用户自定义的回调函数。
 */

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);
}
EXPORT_SYMBOL(__rb_insert_augmented);

rb_insert_color

1
2
3
4
5
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
	__rb_insert(node, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_insert_color);

rb_erase 从红黑树中删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
/*
 * 这是rb_erase()使用的内联版本 - 我们希望能够内联
 * 并消除那里的dummy_rotate回调
 */
static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	/* @node: 指向黑高比其他路径少1的那个“问题”节点。初始时为NULL，在循环中可能指向parent。*/
	struct rb_node *node = NULL;
	/* @sibling: 指向node的兄弟节点。*/
	struct rb_node *sibling;
	/* @tmp1, @tmp2: 用于在旋转操作中临时保存节点的指针。*/
	struct rb_node *tmp1, *tmp2;

	/* 这是一个无限循环，通过内部的break或continue来控制流程。*/
	while (true) {
		/*
		 * 循环不变量:
		 * - node是黑色的 (或在第一次迭代时为NULL)
		 * - node不是根节点 (parent不为NULL)
		 * - 所有经过parent和node的叶子路径，其黑色节点计数都比其他叶子路径少1。
		 */
		
		/* sibling指向parent的右子节点。*/
		sibling = parent->rb_right;
		/*
		 * --- 第一大分支：处理node是parent的左子节点的情况 ---
		 */
		if (node != sibling) {
			/*
			 * 情况1 - 在parent处左旋
			 *
			 *     P               S
			 *    / \             / \
			 *   N   s    -->    p   Sr
			 *      / \         / \
			 *     Sl  Sr      N   Sl
			 */
			/* 如果兄弟节点s是红色的。*/
			if (rb_is_red(sibling)) {
				/* 记录s的左子节点Sl。*/
				tmp1 = sibling->rb_left;
				/* p的右指针指向Sl。*/
				WRITE_ONCE(parent->rb_right, tmp1);
				/* s的左指针指向p。*/
				WRITE_ONCE(sibling->rb_left, parent);
				/* Sl变为黑色，其父节点变为p。*/
				rb_set_parent_color(tmp1, parent, RB_BLACK);
				/* 执行旋转，s成为新的父节点，p变为红色。*/
				__rb_rotate_set_parents(parent, sibling, root, RB_RED);
				/* 调用回调，更新旋转后节点的增强数据。*/
				augment_rotate(parent, sibling);
				/* 更新sibling，现在node的新兄弟是Sl。*/
				sibling = tmp1;
			}
			/* 获取新sibling的右子节点Sr。*/
			tmp1 = sibling->rb_right;
			/* 如果Sr不存在或者是黑色的。*/
			if (!tmp1 || rb_is_black(tmp1)) {
				/* 获取新sibling的左子节点Sl。*/
				tmp2 = sibling->rb_left;
				/* 如果Sl也不存在或者是黑色的。*/
				if (!tmp2 || rb_is_black(tmp2)) {
					/*
					 * 情况2 - 兄弟节点颜色翻转
					 * (此时p可以是任何颜色)
					 *
					 *    (p)           (p)
					 *    / \           / \
					 *   N   S    -->  N   s
					 *      / \           / \
					 *     Sl  Sr        Sl  Sr
					 *
					 * 这会使我们违反性质5，可以通过将p翻转为黑色（如果它曾是红色），
					 * 或者在p处递归来修复。当从情况1过来时，p是红色的。
					 */
					/* 将兄弟节点S变为红色。*/
					rb_set_parent_color(sibling, parent, RB_RED);
					/* 如果父节点p是红色的。*/
					if (rb_is_red(parent))
						/* 将p变为黑色，黑高平衡，修复完成，退出循环。*/
						rb_set_black(parent);
					else {
						/* 如果p是黑色的，则问题被上移到p。*/
						node = parent;
						parent = rb_parent(node);
						/* 如果p不是根节点，则继续下一轮循环。*/
						if (parent)
							continue;
					}
					/* 修复完成或已达根节点，退出循环。*/
					break;
				}
				/*
				 * 情况3 - 在sibling处右旋
				 * (此时p可以是任何颜色)
				 *
				 *   (p)           (p)
				 *   / \           / \
				 *  N   S    -->  N   sl
				 *     / \             \
				 *    sl  Sr            S
				 *                       \
				 *                        Sr
				 */
				/* ... (省略了与情况1、4类似的指针操作和颜色翻转) ... */
				tmp1 = tmp2->rb_right;
				WRITE_ONCE(sibling->rb_left, tmp1);
				WRITE_ONCE(tmp2->rb_right, sibling);
				WRITE_ONCE(parent->rb_right, tmp2);
				if (tmp1)
					rb_set_parent_color(tmp1, sibling, RB_BLACK);
				augment_rotate(sibling, tmp2);
				tmp1 = sibling;
				sibling = tmp2;
			}
			/*
			 * 情况4 - 在parent处左旋 + 颜色翻转
			 *
			 *      (p)             (s)
			 *      / \             / \
			 *     N   S     -->   P   Sr
			 *        / \         / \
			 *      (sl) sr      N  (sl)
			 */
			/* ... (省略了与情况1类似的指针操作和颜色翻转) ... */
			tmp2 = sibling->rb_left;
			WRITE_ONCE(parent->rb_right, tmp2);
			WRITE_ONCE(sibling->rb_left, parent);
			rb_set_parent_color(tmp1, sibling, RB_BLACK);
			if (tmp2)
				rb_set_parent(tmp2, parent);
			__rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
			augment_rotate(parent, sibling);
			/* 这是终止情况，修复完成，退出循环。*/
			break;
		} else {
		/*
		 * --- 第二大分支：处理node是parent的右子节点的情况 ---
		 * 这部分代码与第一大分支完全对称，只是旋转方向和左右子节点的处理相反。
		 */
			sibling = parent->rb_left;
			if (rb_is_red(sibling)) {
				/* 对称的情况1 - 在parent处右旋 */
				tmp1 = sibling->rb_right;
				WRITE_ONCE(parent->rb_left, tmp1);
				WRITE_ONCE(sibling->rb_right, parent);
				rb_set_parent_color(tmp1, parent, RB_BLACK);
				__rb_rotate_set_parents(parent, sibling, root, RB_RED);
				augment_rotate(parent, sibling);
				sibling = tmp1;
			}
			tmp1 = sibling->rb_left;
			if (!tmp1 || rb_is_black(tmp1)) {
				tmp2 = sibling->rb_right;
				if (!tmp2 || rb_is_black(tmp2)) {
					/* 对称的情况2 - 兄弟节点颜色翻转 */
					rb_set_parent_color(sibling, parent, RB_RED);
					if (rb_is_red(parent))
						rb_set_black(parent);
					else {
						node = parent;
						parent = rb_parent(node);
						if (parent)
							continue;
					}
					break;
				}
				/* 对称的情况3 - 在sibling处左旋 */
				tmp1 = tmp2->rb_left;
				WRITE_ONCE(sibling->rb_right, tmp1);
				WRITE_ONCE(tmp2->rb_left, sibling);
				WRITE_ONCE(parent->rb_left, tmp2);
				if (tmp1)
					rb_set_parent_color(tmp1, sibling, RB_BLACK);
				augment_rotate(sibling, tmp2);
				tmp1 = sibling;
				sibling = tmp2;
			}
			/* 对称的情况4 - 在parent处右旋 + 颜色翻转 */
			tmp2 = sibling->rb_right;
			WRITE_ONCE(parent->rb_left, tmp2);
			WRITE_ONCE(sibling->rb_right, parent);
			rb_set_parent_color(tmp1, sibling, RB_BLACK);
			if (tmp2)
				rb_set_parent(tmp2, parent);
			__rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
			augment_rotate(parent, sibling);
			/* 这是终止情况，修复完成，退出循环。*/
			break;
		}
	}
}

/*
 * 非内联版本，供rb_erase_augmented()使用。
 * 它被导出(EXPORT_SYMBOL)，以便内核模块也能调用。
 */
void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	/* 直接调用内联的、实现核心逻辑的函数。*/
	____rb_erase_color(parent, root, augment_rotate);
}
/* 将__rb_erase_color符号导出到内核符号表。*/
EXPORT_SYMBOL(__rb_erase_color);

rb_first 返回树的第一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * 此函数返回树的第一个节点（按排序顺序）.
 */
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;
}
EXPORT_SYMBOL(rb_first);

rb_next 红黑树中找到给定节点的“后继节点”

  • 如果节点有右子树：
    后继节点是右子树中最左的节点。
    这是因为在中序遍历中，右子树的最左节点是当前节点的下一个较大节点。
  • 如果节点没有右子树：
    后继节点是当前节点的祖先节点中，第一个将当前节点作为左子节点的节点。
    这是因为在中序遍历中，当前节点的后继节点必须比它大，而没有右子树时，后继节点只能在祖先节点中找到。
  • 假设有以下二叉搜索树:
1
2
3
4
5
     20
    /  \
  10    30
 /  \     \
5   15    35
  • 节点 10 的后继节点是 15（右子树的最左节点）。
  • 节点 15 的后继节点是 20（第一个将 15 作为左子节点的祖先节点）。
  • 节点 30 的后继节点是 35（右子树的最左节点）。
  • 节点 35 没有后继节点，因为它是树中最大的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct rb_node *rb_next(const struct rb_node *node)
{
	struct rb_node *parent;

	if (RB_EMPTY_NODE(node))
		return NULL;

	/*
	 * 如果当前节点有右子树，后继节点位于右子树的最左节点。
    * 这是因为在二叉搜索树中，右子树的最左节点是当前节点的下一个较大节点
	 */
	if (node->rb_right) {
		node = node->rb_right;
		while (node->rb_left)
			node = node->rb_left;
		return (struct rb_node *)node;
	}

	/*
	 * 如果当前节点没有右子树，后继节点位于其祖先节点中。
    * 向上遍历树，直到找到一个祖先节点，该节点是其父节点的左子节点。
    * 此时，该父节点就是当前节点的后继节点
	 */
	while ((parent = rb_parent(node)) && node == parent->rb_right)
		node = parent;

	return parent;
}
EXPORT_SYMBOL(rb_next);