XWOS API  4.0
XWOS C/C++ API参考手册
载入中...
搜索中...
未找到
结构体 | 宏定义 | 枚举 | 函数
红黑树
XWOS内核 » XWOS的通用库
红黑树 的协作图:

结构体

struct  xwlib_rbtree_node
 红黑树节点 更多...
 
struct  xwlib_rbtree
 红黑树 更多...
 

宏定义

#define xwlib_rbtree_get_link(lpc)    ((struct xwlib_rbtree_node **)(((xwptr_t)(lpc)) & (~((xwptr_t)3UL))))
 获取lpc信息中的link指针
 
#define xwlib_rbtree_get_lnpos(lpc)   ((xwptr_t)(lpc) & (~((xwptr_t)2UL)))
 获取lpc信息中的link指针和位置信息（屏蔽颜色信息）
 
#define xwlib_rbtree_get_pos(lpc)   ((xwptr_t)(((xwptr_t)(lpc)) & (xwptr_t)1UL))
 获取lpc信息中的位置信息
 
#define xwlib_rbtree_tst_right(lpc)   (!!xwlib_rbtree_get_pos(lpc))
 测试当前lpc中的位置信息是否为右侧
 
#define xwlib_rbtree_tst_left(lpc)   (!xwlib_rbtree_tst_right(lpc))
 测试当前lpc中的位置信息是否为左侧
 
#define xwlib_rbtree_gen_lc(n, color)    ((xwptr_t)(&((n)->left)) | (xwptr_t)(color))
 生成节点左边的链指针、位置和颜色信息
 
#define xwlib_rbtree_gen_rc(n, color)    ((xwptr_t)(&((n)->right)) | (xwptr_t)(color) | (xwptr_t)XWLIB_RBTREE_POS_RIGHT)
 生成节点右边的链指针、位置和颜色信息
 
#define xwlib_rbtree_gen_lr(n)   xwlib_rbtree_gen_lc((n), XWLIB_RBTREE_COLOR_RED)
 生成节点左边的链指针、位置和红色信息
 
#define xwlib_rbtree_gen_lb(n)   xwlib_rbtree_gen_lc((n), XWLIB_RBTREE_COLOR_BLACK)
 生成节点左边的链指针、位置和红色信息
 
#define xwlib_rbtree_gen_rr(n)   xwlib_rbtree_gen_rc((n), XWLIB_RBTREE_COLOR_RED)
 生成节点右边的链指针、位置和红色信息
 
#define xwlib_rbtree_gen_rb(n)   xwlib_rbtree_gen_rc((n), XWLIB_RBTREE_COLOR_BLACK)
 生成节点右边的链指针、位置和红色信息
 
#define xwlib_rbtree_get_color(lpc)   (((xwptr_t)(lpc)) & (xwptr_t)2UL)
 获取lpc信息中的颜色信息
 
#define xwlib_rbtree_tst_black(lpc)   (!!xwlib_rbtree_get_color(lpc))
 测试当前lpc中的颜色信息是否为黑色
 
#define xwlib_rbtree_tst_red(lpc)   (!xwlib_rbtree_get_color(lpc))
 测试当前lpc中的颜色信息是否为红色
 
#define xwlib_rbtree_entry(ptr, type, member)   xwcc_derof((ptr), type, member)
 从红黑树节点指针值计算出包含该节点成员的外层结构体的指针值
 

枚举

enum  xwlib_rbtree_pos_em { XWLIB_RBTREE_POS_LEFT = 0 , XWLIB_RBTREE_POS_RIGHT = 1 }
 红黑树节点位置枚举 更多...
 
enum  xwlib_rbtree_color_em { XWLIB_RBTREE_COLOR_RED = 0 , XWLIB_RBTREE_COLOR_BLACK = 2 }
 红黑树节点颜色枚举 更多...
 

函数

static void xwlib_rbtree_init (struct xwlib_rbtree *rbt)
 初始化红黑树
 
static void xwlib_rbtree_init_node (struct xwlib_rbtree_node *rbn)
 初始化红黑树节点
 
static struct xwlib_rbtree_node * xwlib_rbtree_get_parent (struct xwlib_rbtree_node *node)
 返回节点的父节点指针
 
static struct xwlib_rbtree_node * xwlib_rbtree_get_parent_from_lpc (xwptr_t lpc)
 从lpc信息返回父节点指针
 
static bool xwlib_rbtree_tst_root (struct xwlib_rbtree *rbt, struct xwlib_rbtree_node *node)
 测试当前节点是否为根节点
 
static bool xwlib_rbtree_tst_link_root (struct xwlib_rbtree *rbt, struct xwlib_rbtree_node **link)
 测试是否连接到根节点（是否为根节点的子节点）
 
static void xwlib_rbtree_flip_color (struct xwlib_rbtree_node *node)
 反转节点的颜色
 
static void xwlib_rbtree_set_black (struct xwlib_rbtree_node *node)
 将节点设置为黑色
 
static void xwlib_rbtree_set_red (struct xwlib_rbtree_node *node)
 将节点设置为红色
 
static void xwlib_rbtree_link (struct xwlib_rbtree_node *node, xwptr_t lpc)
 链接节点，并设置位置及颜色信息
 
static void xwlib_rbtree_link_nil (struct xwlib_rbtree_node **link)
 链接空（叶子）节点
 
static struct xwlib_rbtree_node * xwlib_rbtree_get_predecessor (struct xwlib_rbtree_node *node)
 返回节点的前趋节点
 
static struct xwlib_rbtree_node * xwlib_rbtree_get_successor (struct xwlib_rbtree_node *node)
 返回节点的后继节点
 
static void xwlib_rbtree_transplant (struct xwlib_rbtree_node *newn, struct xwlib_rbtree_node *oldn)
 用新节点代替旧节点并继承它的链指针、颜色和位置信息， 但新节点并不接管旧节点的子节点
 
static void xwlib_rbtree_transplant_nil (struct xwlib_rbtree_node *oldn)
 用叶子(NIL)替换一个旧节点
 
static bool xwlib_rbtree_tst_empty (struct xwlib_rbtree *t)
 测试一棵红黑树是否为空树
 
static bool xwlib_rbtree_tst_node_unlinked (struct xwlib_rbtree_node *n)
 测试红黑树节点是否已经链接到红黑树中
 
void xwlib_rbtree_insert_color (struct xwlib_rbtree *tree, struct xwlib_rbtree_node *node)
 插入一个红色节点后修正红黑树的颜色
 
void xwlib_rbtree_remove (struct xwlib_rbtree *tree, struct xwlib_rbtree_node *node)
 删除一个节点，并修正红黑树的颜色
 
void xwlib_rbtree_replace (struct xwlib_rbtree_node *newn, struct xwlib_rbtree_node *oldn)
 用一个新节点代替旧节点，继承它的颜色、位置信息并接管它的子树
 

详细描述

红黑树性质

本算法的特点

和传统的红黑树算法不同，本算法实现时比较有技巧性。

宏定义说明

◆ xwlib_rbtree_entry

#define xwlib_rbtree_entry (   ptr,
  type,
  member 
)    xwcc_derof((ptr), type, member)

从红黑树节点指针值计算出包含该节点成员的外层结构体的指针值

参数
[in]ptr红黑树节点指针
[in]type外层结构体类型
[in]member红黑树节点在外层结构体中的成员符号名(symbol)

在文件 rbtree.h 第 236 行定义.

◆ xwlib_rbtree_gen_lb

#define xwlib_rbtree_gen_lb (   n)    xwlib_rbtree_gen_lc((n), XWLIB_RBTREE_COLOR_BLACK)

生成节点左边的链指针、位置和红色信息

参数
[in]n节点指针
返回
指向节点左边的链指针、位置和黑色信息

在文件 rbtree.h 第 191 行定义.

◆ xwlib_rbtree_gen_lc

#define xwlib_rbtree_gen_lc (   n,
  color 
)     ((xwptr_t)(&((n)->left)) | (xwptr_t)(color))

生成节点左边的链指针、位置和颜色信息

参数
[in]n父节点指针
[in]color颜色
返回
指向节点左边的链指针、位置和颜色信息

在文件 rbtree.h 第 167 行定义.

◆ xwlib_rbtree_gen_lr

#define xwlib_rbtree_gen_lr (   n)    xwlib_rbtree_gen_lc((n), XWLIB_RBTREE_COLOR_RED)

生成节点左边的链指针、位置和红色信息

参数
[in]n节点指针
返回
指向节点左边的链指针、位置和红色信息

在文件 rbtree.h 第 184 行定义.

◆ xwlib_rbtree_gen_rb

#define xwlib_rbtree_gen_rb (   n)    xwlib_rbtree_gen_rc((n), XWLIB_RBTREE_COLOR_BLACK)

生成节点右边的链指针、位置和红色信息

参数
[in]n节点指针
返回
指向节点右边的链指针、位置和黑色信息

在文件 rbtree.h 第 205 行定义.

◆ xwlib_rbtree_gen_rc

#define xwlib_rbtree_gen_rc (   n,
  color 
)     ((xwptr_t)(&((n)->right)) | (xwptr_t)(color) | (xwptr_t)XWLIB_RBTREE_POS_RIGHT)

生成节点右边的链指针、位置和颜色信息

参数
[in]n父节点指针
[in]color颜色
返回
指向节点右边的链指针、位置和颜色信息

在文件 rbtree.h 第 176 行定义.

◆ xwlib_rbtree_gen_rr

#define xwlib_rbtree_gen_rr (   n)    xwlib_rbtree_gen_rc((n), XWLIB_RBTREE_COLOR_RED)

生成节点右边的链指针、位置和红色信息

参数
[in]n节点指针
返回
指向节点右边的链指针、位置和红色信息

在文件 rbtree.h 第 198 行定义.

◆ xwlib_rbtree_get_color

#define xwlib_rbtree_get_color (   lpc)    (((xwptr_t)(lpc)) & (xwptr_t)2UL)

获取lpc信息中的颜色信息

参数
[in]lpc链指针，位置，颜色的合并值
返回
颜色信息

在文件 rbtree.h 第 212 行定义.

◆ xwlib_rbtree_get_link

#define xwlib_rbtree_get_link (   lpc)     ((struct xwlib_rbtree_node **)(((xwptr_t)(lpc)) & (~((xwptr_t)3UL))))

获取lpc信息中的link指针

参数
[in]lpc链指针，位置，颜色的合并值
返回
链指针

在文件 rbtree.h 第 126 行定义.

◆ xwlib_rbtree_get_lnpos

#define xwlib_rbtree_get_lnpos (   lpc)    ((xwptr_t)(lpc) & (~((xwptr_t)2UL)))

获取lpc信息中的link指针和位置信息（屏蔽颜色信息）

参数
[in]lpc链指针，位置，颜色的合并值
返回
链指针和位置信息

在文件 rbtree.h 第 134 行定义.

◆ xwlib_rbtree_get_pos

#define xwlib_rbtree_get_pos (   lpc)    ((xwptr_t)(((xwptr_t)(lpc)) & (xwptr_t)1UL))

获取lpc信息中的位置信息

参数
[in]lpc链指针，位置，颜色的合并值
返回
位置信息

在文件 rbtree.h 第 141 行定义.

◆ xwlib_rbtree_tst_black

#define xwlib_rbtree_tst_black (   lpc)    (!!xwlib_rbtree_get_color(lpc))

测试当前lpc中的颜色信息是否为黑色

参数
[in]lpc链指针，位置，颜色的合并值
返回值
true是
false否

在文件 rbtree.h 第 220 行定义.

◆ xwlib_rbtree_tst_left

#define xwlib_rbtree_tst_left (   lpc)    (!xwlib_rbtree_tst_right(lpc))

测试当前lpc中的位置信息是否为左侧

参数
[in]lpc链指针，位置，颜色的合并值
返回
布尔值
返回值
true是
false否

在文件 rbtree.h 第 159 行定义.

◆ xwlib_rbtree_tst_red

#define xwlib_rbtree_tst_red (   lpc)    (!xwlib_rbtree_get_color(lpc))

测试当前lpc中的颜色信息是否为红色

参数
[in]lpc链指针，位置，颜色的合并值
返回值
true是
false否

在文件 rbtree.h 第 228 行定义.

◆ xwlib_rbtree_tst_right

#define xwlib_rbtree_tst_right (   lpc)    (!!xwlib_rbtree_get_pos(lpc))

测试当前lpc中的位置信息是否为右侧

参数
[in]lpc链指针，位置，颜色的合并值
返回
布尔值
返回值
true是
false否

在文件 rbtree.h 第 150 行定义.

枚举类型说明

◆ xwlib_rbtree_color_em

enum xwlib_rbtree_color_em

红黑树节点颜色枚举

枚举值
XWLIB_RBTREE_COLOR_RED 

红色

XWLIB_RBTREE_COLOR_BLACK 

黑色

在文件 rbtree.h 第 73 行定义.

73 {
74 XWLIB_RBTREE_COLOR_RED = 0,
75 XWLIB_RBTREE_COLOR_BLACK = 2,
76};
XWLIB_RBTREE_COLOR_RED
@ XWLIB_RBTREE_COLOR_RED
Definition rbtree.h:74
XWLIB_RBTREE_COLOR_BLACK
@ XWLIB_RBTREE_COLOR_BLACK
Definition rbtree.h:75

◆ xwlib_rbtree_pos_em

enum xwlib_rbtree_pos_em

红黑树节点位置枚举

枚举值
XWLIB_RBTREE_POS_LEFT 

左

XWLIB_RBTREE_POS_RIGHT 

右

在文件 rbtree.h 第 65 行定义.

65 {
66 XWLIB_RBTREE_POS_LEFT = 0,
67 XWLIB_RBTREE_POS_RIGHT = 1,
68};
XWLIB_RBTREE_POS_RIGHT
@ XWLIB_RBTREE_POS_RIGHT
Definition rbtree.h:67
XWLIB_RBTREE_POS_LEFT
@ XWLIB_RBTREE_POS_LEFT
Definition rbtree.h:66

函数说明

◆ xwlib_rbtree_flip_color()

static void xwlib_rbtree_flip_color ( struct xwlib_rbtree_node *  node)
inlinestatic

反转节点的颜色

参数
[in]node红黑树节点指针

在文件 rbtree.h 第 319 行定义.

320{
321 node->lpc.color ^= (xwptr_t)2UL;
322}
xwptr_t
unsigned long xwptr_t
Definition type.h:375
xwlib_rbtree_node::color
xwptr_t color
Definition rbtree.h:87
xwlib_rbtree_node::lpc
union xwlib_rbtree_node::@5 lpc
这是这个函数的调用关系图:

◆ xwlib_rbtree_get_parent()

static struct xwlib_rbtree_node * xwlib_rbtree_get_parent ( struct xwlib_rbtree_node *  node)
inlinestatic

返回节点的父节点指针

参数
[in]node子节点指针
返回
父节点指针
注解
  • left 是 xwlib_rbtree_node 的第一个成员。
  • &parent->left 与 &parent 在数值上是相等的（指针 就是位宽等于CPU位宽的无符号整数）。
    • 当 link 指向 parent->left 时，其数值就等于 parent 的地址；
    • 当 link 指向 parent->right 时，其数值减去 sizeof(void *) 后， 可获取 parent 地址。
  • 当父节点不存在，表示此节点是红黑树的第一个节点，其 link 指针指向 root ， 此函数返回 root 的地址。

在文件 rbtree.h 第 253 行定义.

254{
255 xwptr_t pos;
256 struct xwlib_rbtree_node ** link;
257
258 pos = xwlib_rbtree_get_pos(node->lpc.pos);
259 link = &(xwlib_rbtree_get_link(node->lpc.link)[-pos]);
260 return (struct xwlib_rbtree_node *)link;
261}
xwlib_rbtree_get_link
#define xwlib_rbtree_get_link(lpc)
获取lpc信息中的link指针
Definition rbtree.h:126
xwlib_rbtree_get_pos
#define xwlib_rbtree_get_pos(lpc)
获取lpc信息中的位置信息
Definition rbtree.h:141
xwlib_rbtree_node
红黑树节点
Definition rbtree.h:81
xwlib_rbtree_node::link
struct xwlib_rbtree_node ** link
Definition rbtree.h:85
xwlib_rbtree_node::pos
xwptr_t pos
Definition rbtree.h:86
这是这个函数的调用关系图:

◆ xwlib_rbtree_get_parent_from_lpc()

static struct xwlib_rbtree_node * xwlib_rbtree_get_parent_from_lpc ( xwptr_t  lpc)
inlinestatic

从lpc信息返回父节点指针

参数
[in]lpc链指针，位置，颜色的合并值
返回
父节点指针
注解
lpc 是从节点内取出的值，说明同 xwlib_rbtree_get_parent() 。

在文件 rbtree.h 第 271 行定义.

272{
273 xwptr_t pos;
274 struct xwlib_rbtree_node ** link;
275
276 pos = xwlib_rbtree_get_pos(lpc);
277 link = &(xwlib_rbtree_get_link(lpc)[-pos]);
278 return (struct xwlib_rbtree_node *)link;
279}
这是这个函数的调用关系图:

◆ xwlib_rbtree_get_predecessor()

static struct xwlib_rbtree_node * xwlib_rbtree_get_predecessor ( struct xwlib_rbtree_node *  node)
inlinestatic

返回节点的前趋节点

参数
[in]node节点指针
返回
前趋节点指针

在文件 rbtree.h 第 373 行定义.

374{
375 struct xwlib_rbtree_node * c = node->left;
376 if (!c) {
377 c = node;
378 } else {
379 while (NULL != c->right) {
380 c = c->right;
381 }
382 }
383 return c;
384}
NULL
#define NULL
Definition type.h:28
xwlib_rbtree_node::left
struct xwlib_rbtree_node * left
Definition rbtree.h:82
xwlib_rbtree_node::right
struct xwlib_rbtree_node * right
Definition rbtree.h:83

◆ xwlib_rbtree_get_successor()

static struct xwlib_rbtree_node * xwlib_rbtree_get_successor ( struct xwlib_rbtree_node *  node)
inlinestatic

返回节点的后继节点

参数
[in]node节点指针
返回
后继节点指针

在文件 rbtree.h 第 393 行定义.

394{
395 struct xwlib_rbtree_node * c = node->right;
396 if (!c) {
397 c = node;
398 } else {
399 while (NULL != c->left) {
400 c = c->left;
401 }
402 }
403 return c;
404}
这是这个函数的调用关系图:

◆ xwlib_rbtree_init()

static void xwlib_rbtree_init ( struct xwlib_rbtree *  rbt)
inlinestatic

初始化红黑树

参数
[in]rbt红黑树指针

在文件 rbtree.h 第 104 行定义.

105{
106 rbt->root = NULL;
107}
xwlib_rbtree::root
struct xwlib_rbtree_node * root
Definition rbtree.h:96
这是这个函数的调用关系图:

◆ xwlib_rbtree_init_node()

static void xwlib_rbtree_init_node ( struct xwlib_rbtree_node *  rbn)
inlinestatic

初始化红黑树节点

参数
[in]rbn红黑树节点指针

在文件 rbtree.h 第 114 行定义.

115{
116 rbn->left = NULL;
117 rbn->right = NULL;
118 rbn->lpc.v = 0;
119}
xwlib_rbtree_node::v
xwptr_t v
Definition rbtree.h:88
这是这个函数的调用关系图:

◆ xwlib_rbtree_insert_color()

void xwlib_rbtree_insert_color ( struct xwlib_rbtree *  tree,
struct xwlib_rbtree_node *  node 
)

插入一个红色节点后修正红黑树的颜色

参数
[in]tree红黑树的指针
[in]node待修正颜色的节点的指针

在文件 rbtree.c 第 17 行定义.

19{
20 struct xwlib_rbtree_node * parent;
21 struct xwlib_rbtree_node * gparent;
22 union {
23 struct xwlib_rbtree_node * child;
24 struct xwlib_rbtree_node * sibling;
25 struct xwlib_rbtree_node * uncle;
26 } tmp;
27 xwptr_t rotation;
28 xwptr_t lpc;
29
30recursively_fix:
31 if (node == tree->root) {
32 /*
33 * 情况 1 红黑树为空
34 * ==================
35 * n(r)
36 * / \
37 * NULL(B) NULL(B)
38 *
39 * flip_color(n)
40 * --------------->
41 *
42 * n(B)
43 * / \
44 * NULL(B) NULL(B)
45 *
46 */
47 xwlib_rbtree_flip_color(node);
48 return; // cppcheck-suppress [misra-c2012-15.5]
49 }
50
51 parent = xwlib_rbtree_get_parent(node);
52 if (xwlib_rbtree_tst_black(parent->lpc.v)) {
53 /*
54 * 情况 2 父节点为黑色
55 * ====================
56 */
57 return; // cppcheck-suppress [misra-c2012-15.5]
58 }
59
60 /* 情况 3： 父节点为红色 */
61 gparent = xwlib_rbtree_get_parent(parent);
62 if (xwlib_rbtree_tst_right(parent->lpc.v)) {
63 tmp.uncle = gparent->left;
64 rotation = xwlib_rbtree_gen_rr(node); /* `rotation' 用于右旋 */
65 } else {
66 tmp.uncle = gparent->right;
67 rotation = xwlib_rbtree_gen_lr(node); /* `rotation' 用于左旋 */
68 }
69
70 if ((tmp.uncle) && xwlib_rbtree_tst_red(tmp.uncle->lpc.v)) {
71 /*
72 * 情况 3.1 叔节点(u)是红色
73 * =========================
74 *
75 * |
76 * g(B)
77 * __/ \__
78 * / \
79 * p(r) u(r)
80 * / \ / \
81 * n(r)
82 * / \
83 *
84 * flip_color(p); flip_color(u); flip_color(g);
85 * ---------------------------------------------->
86 *
87 * |
88 * g(r)
89 * __/ \__
90 * / \
91 * p(B) u(B)
92 * / \ / \
93 * n(r)
94 * / \
95 *
96 * recursively fix_color(g);
97 * --------------------------->
98 *
99 * ******** ******** ******** OR ******** ******** ********
100 *
101 * |
102 * g(B)
103 * __/ \__
104 * / \
105 * u(r) p(r)
106 * / \ / \
107 * n(r)
108 * / \
109 *
110 * flip_color(p); flip_color(u); flip_color(g);
111 * ---------------------------------------------->
112 *
113 * |
114 * g(r)
115 * __/ \__
116 * / \
117 * u(B) p(B)
118 * / \ / \
119 * n(r)
120 * / \
121 *
122 * 递归地修正颜色，节点g为待修正颜色的节点
123 * ----------------------------------------->
124 *
125 */
126 xwlib_rbtree_flip_color(parent);
127 xwlib_rbtree_flip_color(tmp.uncle);
128 xwlib_rbtree_flip_color(gparent);
129 node = gparent; // cppcheck-suppress [misra-c2012-17.8]
130 goto recursively_fix; // cppcheck-suppress [misra-c2012-15.2]
131 }
132
133 /* 情况 3.2 叔节点(U)是叶子或黑色 */
134 if (xwlib_rbtree_get_pos(parent->lpc.v) != xwlib_rbtree_get_pos(node->lpc.v)) {
135 /*
136 * Case 3.2.1: node->lpc.pos != parent->lpc.pos
137 * ============================================
138 *
139 * |
140 * g(B)
141 * __/ \__
142 * / \
143 * p(r) u(B)
144 * __/ \__ / \
145 * / \
146 * s(B) n(r)
147 * / \ / \
148 * l(B) r(B)
149 * / \ / \
150 *
151 * left_rotate(p);
152 * ----------------->
153 *
154 * |
155 * g(B)
156 * __/ \__
157 * / \
158 * n(r) u(B)
159 * __/ \__ / \
160 * / \
161 * p(r) r(B)
162 * / \ / \
163 * s(B) l(B)
164 * / \ / \
165 *
166 * ******** ******** ******** OR ******** ******** ********
167 *
168 * |
169 * g(B)
170 * __/ \__
171 * / \
172 * u(B) p(r)
173 * / \ __/ \__
174 * / \
175 * n(r) s(B)
176 * / \ / \
177 * l(B) r(B)
178 * / \ / \
179 *
180 * right_rotate(p);
181 * ----------------->
182 *
183 * |
184 * g(B)
185 * __/ \__
186 * / \
187 * u(B) n(r)
188 * / \ __/ \__
189 * / \
190 * l(B) p(r)
191 * / \
192 * r(B) s(B)
193 * / \ / \
194 *
195 * 转换为情况 3.2.2，原来的父节点变为待修正颜色的节点(n)。
196 */
197 tmp.child = *xwlib_rbtree_get_link(rotation);
198 lpc = parent->lpc.v;
199
200 *xwlib_rbtree_get_link(node->lpc.v) = tmp.child;
201 if (NULL != tmp.child) {
202 tmp.child->lpc.v = node->lpc.v |
203 (xwptr_t)XWLIB_RBTREE_COLOR_BLACK;
204 }
205
206 *xwlib_rbtree_get_link(rotation) = parent;
207 parent->lpc.v = rotation; /* color: red */
208
209 /* *xwlib_rbtree_get_link(lpc) = node; */ /* omitted */
210 node->lpc.v = lpc; /* color: red */
211
212 /* 转换为情况 3.2.2 */
213 tmp.child = parent;
214 parent = node;
215 node = tmp.child; // cppcheck-suppress [misra-c2012-17.8]
216 /* lpc = parent->lpc.v; */ /* omitted */
217 }
218
219 /*
220 * 情况 3.2.2 node->lpc.pos == parent->lpc.pos
221 * ============================================
222 *
223 * |
224 * g(B)
225 * __/ \__
226 * / \
227 * p(r) u(B)
228 * __/ \__ / \
229 * / \
230 * n(r) s(B)
231 * / \ / \
232 * l(B) r(B)
233 * / \ / \
234 *
235 * right_rotate(g);
236 * ------------------>
237 *
238 * |
239 * p(r)
240 * ___/ \___
241 * / \
242 * n(r) g(B)
243 * / \ / \
244 * l(B) r(B) s(B) u(B)
245 * / \ / \ / \ / \
246 *
247 * flip_color(p); flip_color(g);
248 * ------------------------------->
249 *
250 * |
251 * P(B)
252 * ___/ \___
253 * / \
254 * n(r) g(r)
255 * / \ / \
256 * l(B) r(B) s(B) u(B)
257 * / \ / \ / \ / \
258 *
259 * ******** ******** ******** OR ******** ******** ********
260 *
261 * |
262 * g(B)
263 * __/ \__
264 * / \
265 * u(B) p(r)
266 * / \ __/ \__
267 * / \
268 * s(B) n(r)
269 * / \
270 * l(B) r(B)
271 * / \ / \
272 *
273 * left_rotate(g);
274 * ------------------>
275 *
276 * |
277 * p(r)
278 * ___/ \___
279 * / \
280 * g(B) n(r)
281 * / \ / \
282 * u(B) s(B) l(B) r(B)
283 * / \ / \ / \ / \
284 *
285 * flip_color(p); flip_color(g);
286 * ------------------------------->
287 *
288 * |
289 * p(B)
290 * ___/ \___
291 * / \
292 * g(r) n(r)
293 * / \ / \
294 * u(B) s(B) l(B) r(B)
295 * / \ / \ / \ / \
296 *
297 */
298 if (xwlib_rbtree_tst_right(node->lpc.v)) {
299 tmp.sibling = parent->left;
300 rotation = xwlib_rbtree_gen_lr(parent); /* 左旋g */
301 } else {
302 tmp.sibling = parent->right;
303 rotation = xwlib_rbtree_gen_rr(parent); /* 右旋g */
304 }
305 lpc = parent->lpc.v;
306
307 *xwlib_rbtree_get_link(gparent->lpc.v) = parent;
308 parent->lpc.v = gparent->lpc.v; /* flip_color(p): 黑 */
309
310 *xwlib_rbtree_get_link(lpc) = tmp.sibling;
311 if (NULL != tmp.sibling) {
312 tmp.sibling->lpc.v = ((xwptr_t)lpc) | (xwptr_t)XWLIB_RBTREE_COLOR_BLACK;
313 }
314
315 *xwlib_rbtree_get_link(rotation) = gparent;
316 gparent->lpc.v = rotation; /* flip_color(g): 红 */
317}
xwlib_rbtree_tst_red
#define xwlib_rbtree_tst_red(lpc)
测试当前lpc中的颜色信息是否为红色
Definition rbtree.h:228
xwlib_rbtree_flip_color
static void xwlib_rbtree_flip_color(struct xwlib_rbtree_node *node)
反转节点的颜色
Definition rbtree.h:319
xwlib_rbtree_gen_lr
#define xwlib_rbtree_gen_lr(n)
生成节点左边的链指针、位置和红色信息
Definition rbtree.h:184
xwlib_rbtree_gen_rr
#define xwlib_rbtree_gen_rr(n)
生成节点右边的链指针、位置和红色信息
Definition rbtree.h:198
xwlib_rbtree_get_parent
static struct xwlib_rbtree_node * xwlib_rbtree_get_parent(struct xwlib_rbtree_node *node)
返回节点的父节点指针
Definition rbtree.h:253
xwlib_rbtree_tst_right
#define xwlib_rbtree_tst_right(lpc)
测试当前lpc中的位置信息是否为右侧
Definition rbtree.h:150
xwlib_rbtree_tst_black
#define xwlib_rbtree_tst_black(lpc)
测试当前lpc中的颜色信息是否为黑色
Definition rbtree.h:220
函数调用图:
这是这个函数的调用关系图:

◆ xwlib_rbtree_link()

static void xwlib_rbtree_link ( struct xwlib_rbtree_node *  node,
xwptr_t  lpc 
)
inlinestatic

链接节点，并设置位置及颜色信息

参数
[in]node被链接的节点指针
[in]lpc链指针、位置和颜色的合并值

在文件 rbtree.h 第 350 行定义.

351{
352 node->lpc.v = lpc;
353 *xwlib_rbtree_get_link(lpc) = node;
354}
这是这个函数的调用关系图:

◆ xwlib_rbtree_link_nil()

static void xwlib_rbtree_link_nil ( struct xwlib_rbtree_node **  link)
inlinestatic

链接空（叶子）节点

参数
[in]link链接的位置

在文件 rbtree.h 第 361 行定义.

362{
363 *link = NULL;
364}

◆ xwlib_rbtree_remove()

void xwlib_rbtree_remove ( struct xwlib_rbtree *  tree,
struct xwlib_rbtree_node *  node 
)

删除一个节点，并修正红黑树的颜色

参数
[in]tree红黑树的指针
[in]node待删除的节点的指针
注解
  • 此函数假设不存在节点没有链接到红黑树的情形。

在文件 rbtree.c 第 320 行定义.

322{
323 struct xwlib_rbtree_node * parent;
324 struct xwlib_rbtree_node * sibling;
325 union {
326 struct xwlib_rbtree_node * same;
327 struct xwlib_rbtree_node * left;
328 } sl;
329 union {
330 struct xwlib_rbtree_node * reverse;
331 struct xwlib_rbtree_node * right;
332 } rr;
333 union {
334 struct xwlib_rbtree_node * child;
335 xwptr_t color;
336 } cc;
337 xwptr_t lpc;
338 xwptr_t rotation;
339
340 /* 步骤 1 删除节点 */
341 rr.right = node->right;
342 sl.left = node->left;
343 if (NULL == sl.left) {
344 parent = xwlib_rbtree_get_parent(node);
345 *xwlib_rbtree_get_link(node->lpc.v) = rr.right;
346 if (NULL == rr.right) {
347 /*
348 * 情况 1.1 待删除的节点(n)没有子节点
349 * ===================================
350 * 情况 1.1.1 节点(n)是红色
351 * 根据性质5，它的兄弟节点(s)不是叶子，就是红色节点，
352 * 且(s)没有子节点；
353 * *
354 * | * |
355 * p(*) * p(*)
356 * / \ * / \
357 * s(r) or NULL(B) n(r) * n(r) NULL(B) or s(r)
358 * *
359 * transplant_nil(n) * transplant_nil(n)
360 * --------------------> * -------------------->
361 * *
362 * | * |
363 * p(*) * p(*)
364 * / \ * / \
365 * s(r) or NULL(B) NULL(B) * NULL(B) NULL(B) or s(r)
366 * *
367 * =====================================================
368 * 情况 1.1.2 节点(n)是黑色
369 * 根据性质5，(n)的兄弟节点(s)一定不是叶子：
370 * + 如果兄弟节点(s)是红色，那么兄弟节点(s)有两个黑色子节点；
371 * + 如果兄弟节点(s)是黑色，那么兄弟节点(s)没子节点。
372 *
373 * |
374 * p(*)
375 * / \
376 * s(B) or s(r) n(B)
377 *
378 * transplant_nil(n)
379 * -------------------->
380 *
381 * | |
382 * p(*) p(*)
383 * / \ or / \
384 * s(B) NULL(BB) s(r) NULL(BB)
385 * / \ / \
386 * NULL(B) NULL(B) l(B) r(B)
387 *
388 * ******** ******** ******** OR ******** ******** ********
389 *
390 * |
391 * p(*)
392 * / \
393 * n(B) s(B) or s(r)
394 *
395 * transplant_nil(n)
396 * -------------------->
397 *
398 * | |
399 * p(*) p(*)
400 * / \ / \
401 * NULL(BB) s(B) or NULL(BB) s(r)
402 * / \ / \
403 * NULL(B) NULL(B) l(B) r(B)
404 */
405 if (NULL == tree->root) {
406 return; // cppcheck-suppress [misra-c2012-15.5]
407 }
408
409 lpc = node->lpc.v;
410 if (xwlib_rbtree_tst_black(lpc)) {
411 if (xwlib_rbtree_tst_right(lpc)) {
412 sibling = parent->left;
413 rotation = xwlib_rbtree_gen_rr(sibling);
414 } else {
415 sibling = parent->right;
416 rotation = xwlib_rbtree_gen_lr(sibling);
417 }
418 } else {
419 sibling = NULL;
420 }
421 } else {
422 /*
423 * 情况 1.2 待删除的节点(n)只有一个子节点
424 * ======================================
425 */
426 /*
427 * 情况 1.2.1 待删除的节点(n)没有左子节点
428 * ======================================
429 * |
430 * n(B)
431 * \
432 * r(r)
433 *
434 * transplant(n->right, n)
435 * ------------------------->
436 *
437 * |
438 * r(rB)
439 *
440 * set_black(r)
441 * ---------------->
442 *
443 * |
444 * r(B)
445 *
446 * + 根据性质5，右子节点(r)一定是红色；
447 * + 根据性质4，待删除的节点(n)一定是黑色；
448 */
449 rr.right->lpc.v = node->lpc.v; /* Inherit color */
450 sibling = NULL;
451 }
452 } else if (NULL == rr.right) {
453 /*
454 * 情况 1.2.2 待删除的节点(n)没有右子节点
455 * ======================================
456 *
457 * |
458 * n(B)
459 * /
460 * r(r)
461 *
462 * transplant(n->left, n)
463 * ------------------------->
464 *
465 * |
466 * r(rB)
467 *
468 * set_black(r)
469 * ---------------->
470 *
471 * |
472 * r(B)
473 *
474 * + 根据性质5，左子节点(r)一定是红色；
475 * + 根据性质4，待删除的节点(n)一定是黑色；
476 */
477 xwlib_rbtree_link(sl.left, node->lpc.v); /* Inherit color */
478 sibling = NULL;
479 } else {
480 /*
481 * 情况 1.3 待删除的节点(n)同时存在左右子节点
482 */
483 struct xwlib_rbtree_node * successor;
484
485 successor = xwlib_rbtree_get_successor(node);
486 if (successor == rr.right) {
487 /*
488 * 情况 1.3.1 待删除的节点(n)的后继节点(s)是它的右节点
489 * ====================================================
490 *
491 * |
492 * n(*)
493 * / \
494 * l(*) s(B)
495 * \
496 * c(r)_or_NULL(B)
497 *
498 * transplant(s, n)
499 * -------------------------------------------->
500 * s把自己的颜色留给了c，n把自己的颜色留给了s
501 *
502 * |
503 * s(*) n()
504 * \ /
505 * c(rB)_or_NULL(BB) l(*)
506 *
507 * link(l, ((&s->left) | (RBTREE_LEFT) | color(l)))
508 * -------------------------------------------------->
509 *
510 * |
511 * s(*) n()
512 * / \
513 * l(*) c(rB)_or_NULL(BB)
514 *
515 * ******** ******** ******** OR ******** ******** ********
516 *
517 * |
518 * n(*)
519 * / \
520 * l(*) s(r)
521 * \
522 * NULL(B)
523 *
524 * transplant(s, n)
525 * -------------------------------------------->
526 * s把自己的颜色留给了c，n把自己的颜色留给了s
527 *
528 * |
529 * s(*) n()
530 * \ /
531 * NULL(rB) l(*)
532 *
533 * link(l, ((&s->left) | (RBTREE_LEFT) | color(l)))
534 * -------------------------------------------------->
535 *
536 * |
537 * s(*) n()
538 * / \
539 * l(*) NULL(rB)
540 *
541 * ******** ******** ******** ******** ******** ********
542 * + 如果后继接点(s)是黑色，则只存在两种情况：
543 * - 后继节点(s)有红色右子节点（根据性质4和5），transplant
544 * 操作后，s把黑色留给右子节点，黑+红=黑；
545 * - 后继节点(s)没有右子节，(s)的兄弟节点(l)必然
546 * 存在（根据性质5），transplant操作后，会产生一个双黑的
547 * 叶子，需要修复颜色；
548 * + 如果后继节点(s)为红色，其不可能存在子节点（根据性质5），
549 * transplant操作后，不会产生双黑的叶子；
550 */
551
552 if (NULL != successor->right) {
553 xwlib_rbtree_set_black(successor->right);
554 sibling = NULL;
555 } else {
556 if (xwlib_rbtree_tst_black(successor->lpc.v)) {
557 sibling = sl.left;
558 parent = successor;
559 rotation = xwlib_rbtree_gen_rr(sibling);
560 } else {
561 sibling = NULL;
562 }
563 }
564 xwlib_rbtree_transplant(successor, node);
565 cc.color = xwlib_rbtree_get_color(sl.left->lpc.v);
566 xwlib_rbtree_link(sl.left,
567 xwlib_rbtree_gen_lc(successor, cc.color));
568 } else {
569 /*
570 * 情况 1.3.2 (n)的后继节点(s)是(n)的右子树上最左端的节点
571 * ======================================================
572 *
573 * |
574 * n(*)
575 * / \
576 * l r
577 * / \
578 * p
579 * / \
580 * s(*)
581 * \
582 * c(r)_or_NULL(B)
583 *
584 * transplant(s->right, s)
585 * ------------------------->
586 * s把自己的颜色留给了c
587 *
588 * |
589 * n(*) s()
590 * / \
591 * l r
592 * / \
593 * p
594 * / \
595 * c(rB)_or_NULL(BB)
596 *
597 * link(r, ((&s->right) | (RBTREE_RIGHT) | color(r)))
598 * ---------------------------------------------------->
599 *
600 * |
601 * n(*) s()
602 * / \
603 * l r
604 * / \
605 * p
606 * / \
607 * c(B)_or_NULL(BB)
608 *
609 * link(l, ((&s->left) | (RBTREE_LEFT) | color(l)))
610 * -------------------------------------------------->
611 *
612 * |
613 * n(*) s()
614 * / \
615 * l r
616 * / \
617 * p
618 * / \
619 * c(B)_or_NULL(BB)
620 *
621 * transplant(s, n)
622 * --------------------->
623 * n把自己的颜色留给了s
624 *
625 * |
626 * s(*)
627 * / \
628 * l r
629 * / \
630 * p
631 * / \
632 * C(B)_or_NULL(BB)
633 *
634 * + 如果后继节点(s)的右子节点(r)存在，根据性质5，
635 * (r)一定是红色，再根据性质4，(s)一定为黑色；
636 * + 根据性质5，如果后继节点(s)没有右子节点且(s)为黑色，
637 * (n)的左子节点(l)必然存在。
638 */
639 parent = xwlib_rbtree_get_parent(successor);
640 lpc = successor->lpc.v; /* cache */
641 cc.child = successor->right;
642
643 *xwlib_rbtree_get_link(lpc) = cc.child;
644 if (NULL != cc.child) {
645 cc.child->lpc.v = lpc; /* Inherit color */
646 sibling = NULL;
647 } else {
648 if (xwlib_rbtree_tst_black(successor->lpc.v)) {
649 sibling = parent->right;
650 rotation = xwlib_rbtree_gen_lr(sibling);
651 } else {
652 sibling = NULL;
653 }
654 }
655
656 /* link(r, ((&s->right) | (RBTREE_RIGHT) | color(r))) */
657 cc.color = xwlib_rbtree_get_color(rr.right->lpc.v);
658 xwlib_rbtree_link(rr.right,
659 xwlib_rbtree_gen_rc(successor, cc.color));
660
661 /* link(r, ((&s->right) | (RBTREE_RIGHT) | color(r))) */
662 cc.color = xwlib_rbtree_get_color(sl.left->lpc.v);
663 xwlib_rbtree_link(sl.left,
664 xwlib_rbtree_gen_lc(successor, cc.color));
665
666 /* transplant(s, n) */
667 xwlib_rbtree_transplant(successor, node);
668 }
669 }
670
671 /* 步骤 2：修复颜色 */
672 /* X有可能是NULL或节点(n) */
673 if (NULL == sibling) {
674 return; // cppcheck-suppress [misra-c2012-15.5]
675 }
676
677recursively_fix:
678 if (xwlib_rbtree_tst_red(sibling->lpc.v)) {
679 /*
680 * 情况 2.1 兄弟节点(s)是红色
681 * ===================================================
682 * *
683 * | * |
684 * p(B) * p(B)
685 * / \ * / \
686 * X(BB) s(r) * s(r) X(BB)
687 * / \ * / \
688 * l(B) r(B) * l(B) r(B)
689 * *
690 * left_rotate(p) * right_rotate(p)
691 * ----------------> * ----------------->
692 * *
693 * | * |
694 * s(r) * s(r)
695 * / \ * / \
696 * P(B) r(B) * l(B) P(B)
697 * / \ * / \
698 * X(BB) l(B) * r(B) X(BB)
699 * *
700 * flip_color(s); * flip_color(s);
701 * ----------------> * ---------------->
702 * flip_color(P); * flip_color(P);
703 * *
704 * | * |
705 * s(B) * s(B)
706 * / \ * / \
707 * p(r) r(B) * l(B) p(r)
708 * / \ * / \
709 * X(BB) l(B) * r(B) X(BB)
710 * *
711 * l是新的兄弟节点 * r是新的兄弟节点
712 * *
713 * + 根据性质4，父节点(p)一定为黑色；
714 * + 根据性质5，兄弟节点(s)有两个黑色的子节点。
715 */
716 lpc = sibling->lpc.v;
717 cc.child = *xwlib_rbtree_get_link(rotation);
718
719 *xwlib_rbtree_get_link(parent->lpc.v) = sibling;
720 sibling->lpc.v = parent->lpc.v; /* flip_color: 黑色 */
721
722 *xwlib_rbtree_get_link(lpc) = cc.child;
723 cc.child->lpc.v = lpc | (xwptr_t)XWLIB_RBTREE_COLOR_BLACK;
724
725 /* xwlib_rbtree_link(parent, rotation); */
726 *xwlib_rbtree_get_link(rotation) = parent;
727 parent->lpc.v = rotation; /* flip_color: 红色 */
728
729 /* parent = parent; */ /* omitted */
730 sibling = cc.child;
731 }
732
733black_sibling:
734 /*
735 * 情况 2.2 兄弟节点(s)是黑色
736 */
737 if (xwlib_rbtree_tst_right(sibling->lpc.v)) {
738 rotation = xwlib_rbtree_gen_lr(sibling); /* 用于情况2.2.3中左旋 */
739 rr.reverse = sibling->left;
740 sl.same = sibling->right;
741 if (NULL != rr.reverse) {
742 lpc = xwlib_rbtree_gen_rr(rr.reverse); /* 用于情况2.2.2中右旋 */
743 } else {
744 lpc = 0;
745 }
746 } else {
747 rotation = xwlib_rbtree_gen_rr(sibling); /* 用于情况2.2.3中右旋 */
748 rr.reverse = sibling->right;
749 sl.same = sibling->left;
750 if (NULL != rr.reverse) {
751 lpc = xwlib_rbtree_gen_lr(rr.reverse); /* 用于情况2.2.2中左旋 */
752 } else {
753 lpc = 0;
754 }
755 }
756
757 if ((NULL == sl.same) || xwlib_rbtree_tst_black(sl.same->lpc.v)) {
758 if ((NULL == rr.reverse) || xwlib_rbtree_tst_black(rr.reverse->lpc.v)) {
759 /*
760 * 情况 2.2.1 兄弟节点(s)没有红色的子节点
761 * =====================================
762 *
763 * |
764 * p(*)
765 * / \
766 * s(B) x(BB)
767 * / \
768 * same(B) reverse(B)
769 *
770 * flip_color(p); flip_color(s); flip_color(x);
771 * ---------------------------------------------->
772 *
773 * |
774 * p(rB_or_BB)
775 * / \
776 * s(r) X(B)
777 * / \
778 * same(B) reverse(B)
779 *
780 * 如果p是红色，就把p设置为黑色
781 * --------------------------------------->
782 * 如果p是黑色，p就作为新的X递归调整颜色
783 *
784 * ******** ******** ******** OR ******** ******** ********
785 *
786 * |
787 * p(*)
788 * / \
789 * X(BB) s(B)
790 * / \
791 * reverse(B) same(B)
792 *
793 * flip_color(p); flip_color(S); flip_color(X);
794 * ---------------------------------------------->
795 *
796 * |
797 * p(rB_or_BB)
798 * / \
799 * X(B) s(r)
800 * / \
801 * reverse(B) same(B)
802 *
803 * 如果p是红色，就把p设置为黑色
804 * --------------------------------------->
805 * 如果p是黑色，p就作为新的X递归调整颜色
806 */
807 xwlib_rbtree_flip_color(sibling);
808 if (xwlib_rbtree_tst_black(parent->lpc.v)) {
809 if (parent != tree->root) {
810 cc.child = parent;
811 parent = xwlib_rbtree_get_parent(cc.child);
812 if (xwlib_rbtree_tst_right(cc.child->lpc.v)) {
813 sibling = parent->left;
814 rotation = xwlib_rbtree_gen_rr(sibling);
815 } else {
816 sibling = parent->right;
817 rotation = xwlib_rbtree_gen_lr(sibling);
818 }
819 // cppcheck-suppress [misra-c2012-15.2]
820 goto recursively_fix;
821 }
822 } else {
823 xwlib_rbtree_flip_color(parent);
824 }
825 return; // cppcheck-suppress [misra-c2012-15.5]
826 }
827
828 /*
829 * 情况 2.2.2 与兄弟节点(s)位置相同的子节点为黑色，
830 * 位置相反的子节点为红色
831 *
832 * |
833 * p(*)
834 * / \
835 * s(B) X(BB)
836 * / \
837 * same(B) reverse(r)
838 * /
839 * z(B)
840 *
841 * left_rotate(s);
842 * ----------------->
843 *
844 * |
845 * p(*)
846 * / \
847 * reverse(r) X(BB)
848 * /
849 * s(B)
850 * / \
851 * same(B) z(B)
852 *
853 * flip_color(reverse); flip_color(s)
854 * ----------------------------------->
855 *
856 * |
857 * p(*)
858 * / \
859 * reverse(B) X(BB)
860 * /
861 * s(r)
862 * / \
863 * same(B) z(B)
864 *
865 * ******** ******** ******** OR ******** ******** ********
866 *
867 * |
868 * p(*)
869 * / \
870 * X(BB) s(B)
871 * / \
872 * reverse(r) same(B)
873 * \
874 * z(B)
875 *
876 * right_rotate(s);
877 * ------------------>
878 *
879 * |
880 * p(*)
881 * / \
882 * X(BB) reverse(r)
883 * \
884 * s(B)
885 * / \
886 * z(B) same(B)
887 *
888 * flip_color(reverse); flip_color(s)
889 * ----------------------------------->
890 *
891 * |
892 * p(*)
893 * / \
894 * X(BB) reverse(B)
895 * \
896 * s(r)
897 * / \
898 * z(B) same(B)
899 *
900 * 转换为情况 2.2.3
901 */
902 /* lpc 由black_sibling:处的条件语句赋值为
903 xwlib_rbtree_gen_lr(rr.reverse)
904 或 xwlib_rbtree_gen_rr(rr.reverse) */
905 rotation = sibling->lpc.v; /* rotation在此处作为临时变量
906 用于记录sibling的位置 */
907 cc.child = *xwlib_rbtree_get_link(lpc); /* child is z */
908
909 /* xwlib_rbtree_link(sibling, lpc); */
910 *xwlib_rbtree_get_link(lpc) = sibling;
911 sibling->lpc.v = lpc; /* flip_color(S): red */
912
913 /* omitted */
914 /* if (cc.child) { */
915 /* xwlib_rbtree_link(cc.child, */
916 /* rr.reverse->lpc.v | */
917 /* XWLIB_RBTREE_COLOR_BLACK); */
918 /* } else { */
919 /* xwlib_rbtree_link_nil(rr.reverse->lpc.v); */
920 /* } */
921 *xwlib_rbtree_get_link(rr.reverse->lpc.v) = cc.child;
922 if (NULL != cc.child) {
923 cc.child->lpc.v = rr.reverse->lpc.v |
924 (xwptr_t)XWLIB_RBTREE_COLOR_BLACK;
925 }
926
927 /* xwlib_rbtree_link(rr.reverse,
928 (rotation | XWLIB_RBTREE_COLOR_BLACK)); */
929 *xwlib_rbtree_get_link(rotation) = rr.reverse;
930 /* flip_color(cr) */
931 rr.reverse->lpc.v = rotation | (xwptr_t)XWLIB_RBTREE_COLOR_BLACK;
932
933 /* 转换为情况 2.2 */
934 sibling = rr.reverse;
935 goto black_sibling; // cppcheck-suppress [misra-c2012-15.2]
936 }
937
938 /*
939 * 情况 2.2.3 与兄弟节点(s)位置相同的子节点为红色
940 *
941 * |
942 * p(*)
943 * / \
944 * s(B) X(BB)
945 * / \
946 * same(r) reverse(*)
947 *
948 * right_rotate(p);
949 * ------------------>
950 * s, p, X留下颜色
951 *
952 * |
953 * s(*)
954 * / \
955 * same(rB) p(B)
956 * / \
957 * reverse(*) X(B)
958 *
959 * ******** ******** ******** ******** ******** ********
960 * OR
961 * ******** ******** ******** ******** ******** ********
962 *
963 * |
964 * p(*)
965 * / \
966 * X(BB) s(B)
967 * / \
968 * reverse(*) same(r)
969 *
970 * left_rotate(p);
971 * ------------------>
972 * s, p, X留下颜色
973 *
974 * |
975 * s(*)
976 * / \
977 * p(B) same(rB)
978 * / \
979 * X(B) reverse(*)
980 *
981 * + s把黑色留给same，然后继承p的颜色；
982 * + p留下颜色然后继承X的一份黑色，X带走另一份；
983 *
984 */
985 lpc = parent->lpc.v;
986
987 /* xwlib_rbtree_link(parent, rotation | XWLIB_RBTREE_COLOR_BLACK); */
988 *xwlib_rbtree_get_link(rotation) = parent;
989 parent->lpc.v = rotation | (xwptr_t)XWLIB_RBTREE_COLOR_BLACK;
990
991 /* cc.color = xwlib_rbtree_get_color(rr.reverse->lpc.v); */
992 /* xwlib_rbtree_link(rr.reverse,
993 xwlib_rbtree_get_lnpos(sibling->lpc.v) | cc.color); */
994 *xwlib_rbtree_get_link(sibling->lpc.v) = rr.reverse;
995 if (NULL != rr.reverse) {
996 cc.color = xwlib_rbtree_get_color(rr.reverse->lpc.v);
997 rr.reverse->lpc.v = xwlib_rbtree_get_lnpos(sibling->lpc.v) | cc.color;
998 }
999
1000 /* xwlib_rbtree_link(sibling, lpc); */
1001 sibling->lpc.v = lpc; /* Inherit color. */
1002 *xwlib_rbtree_get_link(lpc) = sibling;
1003 xwlib_rbtree_set_black(sl.same); /* Inherit color of sibling */
1004}
xwlib_rbtree_get_lnpos
#define xwlib_rbtree_get_lnpos(lpc)
获取lpc信息中的link指针和位置信息（屏蔽颜色信息）
Definition rbtree.h:134
xwlib_rbtree_get_successor
static struct xwlib_rbtree_node * xwlib_rbtree_get_successor(struct xwlib_rbtree_node *node)
返回节点的后继节点
Definition rbtree.h:393
xwlib_rbtree_gen_lc
#define xwlib_rbtree_gen_lc(n, color)
生成节点左边的链指针、位置和颜色信息
Definition rbtree.h:167
xwlib_rbtree_set_black
static void xwlib_rbtree_set_black(struct xwlib_rbtree_node *node)
将节点设置为黑色
Definition rbtree.h:329
xwlib_rbtree_get_color
#define xwlib_rbtree_get_color(lpc)
获取lpc信息中的颜色信息
Definition rbtree.h:212
xwlib_rbtree_transplant
static void xwlib_rbtree_transplant(struct xwlib_rbtree_node *newn, struct xwlib_rbtree_node *oldn)
用新节点代替旧节点并继承它的链指针、颜色和位置信息， 但新节点并不接管旧节点的子节点
Definition rbtree.h:413
xwlib_rbtree_link
static void xwlib_rbtree_link(struct xwlib_rbtree_node *node, xwptr_t lpc)
链接节点，并设置位置及颜色信息
Definition rbtree.h:350
xwlib_rbtree_gen_rc
#define xwlib_rbtree_gen_rc(n, color)
生成节点右边的链指针、位置和颜色信息
Definition rbtree.h:176
函数调用图:
这是这个函数的调用关系图:

◆ xwlib_rbtree_replace()

void xwlib_rbtree_replace ( struct xwlib_rbtree_node *  newn,
struct xwlib_rbtree_node *  oldn 
)

用一个新节点代替旧节点，继承它的颜色、位置信息并接管它的子树

参数
[in]newn新节点的指针
[in]oldn旧节点的指针

在文件 rbtree.c 第 1007 行定义.

1009{
1010 struct xwlib_rbtree_node * left = oldn->left;
1011 struct xwlib_rbtree_node * right = oldn->right;
1012
1013 xwlib_rbtree_transplant(newn, oldn);
1014 if (NULL != left) {
1015 xwptr_t lpc = xwlib_rbtree_get_color(left->lpc.v);
1016 lpc |= (xwptr_t)(&newn->left);
1017 xwlib_rbtree_link(left, lpc);
1018 }
1019
1020 if (NULL != right) {
1021 xwptr_t lpc = xwlib_rbtree_get_color(right->lpc.v);
1022 lpc |= ((xwptr_t)(&newn->right) | (xwptr_t)XWLIB_RBTREE_POS_RIGHT);
1023 xwlib_rbtree_link(right, lpc);
1024 }
1025}
函数调用图:

◆ xwlib_rbtree_set_black()

static void xwlib_rbtree_set_black ( struct xwlib_rbtree_node *  node)
inlinestatic

将节点设置为黑色

参数
[in]node红黑树节点指针

在文件 rbtree.h 第 329 行定义.

330{
331 node->lpc.color |= (xwptr_t)2UL;
332}
这是这个函数的调用关系图:

◆ xwlib_rbtree_set_red()

static void xwlib_rbtree_set_red ( struct xwlib_rbtree_node *  node)
inlinestatic

将节点设置为红色

参数
[in]node红黑树节点指针

在文件 rbtree.h 第 339 行定义.

340{
341 node->lpc.color &= ~((xwptr_t)(2UL));
342}

◆ xwlib_rbtree_transplant()

static void xwlib_rbtree_transplant ( struct xwlib_rbtree_node *  newn,
struct xwlib_rbtree_node *  oldn 
)
inlinestatic

用新节点代替旧节点并继承它的链指针、颜色和位置信息， 但新节点并不接管旧节点的子节点

参数
[in]newn新节点指针
[in]oldn旧节点指针

在文件 rbtree.h 第 413 行定义.

415{
416 newn->lpc.v = oldn->lpc.v;
417 *xwlib_rbtree_get_link(oldn->lpc.v) = newn;
418}
这是这个函数的调用关系图:

◆ xwlib_rbtree_transplant_nil()

static void xwlib_rbtree_transplant_nil ( struct xwlib_rbtree_node *  oldn)
inlinestatic

用叶子(NIL)替换一个旧节点

参数
[in]oldn旧节点指针

在文件 rbtree.h 第 425 行定义.

426{
427 *xwlib_rbtree_get_link(oldn->lpc.v) = NULL;
428}

◆ xwlib_rbtree_tst_empty()

static bool xwlib_rbtree_tst_empty ( struct xwlib_rbtree *  t)
inlinestatic

测试一棵红黑树是否为空树

参数
[in]t红黑树指针
返回值
false非空
true空

在文件 rbtree.h 第 437 行定义.

438{
439 return !!(NULL == t->root);
440}

◆ xwlib_rbtree_tst_link_root()

static bool xwlib_rbtree_tst_link_root ( struct xwlib_rbtree *  rbt,
struct xwlib_rbtree_node **  link 
)
inlinestatic

测试是否连接到根节点（是否为根节点的子节点）

参数
[in]rbt红黑树指针
[in]link链指针
返回
布尔值
返回值
true是
false否

在文件 rbtree.h 第 308 行定义.

310{
311 return !!(link == &rbt->root);
312}
这是这个函数的调用关系图:

◆ xwlib_rbtree_tst_node_unlinked()

static bool xwlib_rbtree_tst_node_unlinked ( struct xwlib_rbtree_node *  n)
inlinestatic

测试红黑树节点是否已经链接到红黑树中

参数
[in]n节点指针
返回值
false已链接
true未链接

在文件 rbtree.h 第 449 行定义.

450{
451 return !!((xwptr_t)0 == n->lpc.v);
452}
这是这个函数的调用关系图:

◆ xwlib_rbtree_tst_root()

static bool xwlib_rbtree_tst_root ( struct xwlib_rbtree *  rbt,
struct xwlib_rbtree_node *  node 
)
inlinestatic

测试当前节点是否为根节点

参数
[in]rbt红黑树指针
[in]node节点指针
返回
布尔值
返回值
true是
false否

在文件 rbtree.h 第 290 行定义.

292{
293 struct xwlib_rbtree_node * p;
294
295 p = xwlib_rbtree_get_parent(node);
296 return !!(p == (struct xwlib_rbtree_node *)&rbt->root);
297}
函数调用图: