XWOS API  4.0
XWOS C/C++ API参考手册
载入中...
搜索中...
未找到
rbtree.c
浏览该文件的文档.
1
13#include <xwos/standard.h>
14#include <xwos/lib/rbtree.h>
15
16__xwlib_code __xwcc_hot
17void xwlib_rbtree_insert_color(struct xwlib_rbtree * tree,
18 struct xwlib_rbtree_node * node)
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}
318
319__xwlib_code __xwcc_hot
320void xwlib_rbtree_remove(struct xwlib_rbtree * tree,
321 struct xwlib_rbtree_node * node)
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}
1005
1006__xwlib_code __xwcc_hot
1007void xwlib_rbtree_replace(struct xwlib_rbtree_node * newn,
1008 struct xwlib_rbtree_node * oldn)
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}
__xwcc_hot
#define __xwcc_hot
Definition compiler.h:98
__xwlib_code
#define __xwlib_code
Definition compiler.h:199
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_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_get_link
#define xwlib_rbtree_get_link(lpc)
获取lpc信息中的link指针
Definition rbtree.h:126
xwlib_rbtree_gen_rr
#define xwlib_rbtree_gen_rr(n)
生成节点右边的链指针、位置和红色信息
Definition rbtree.h:198
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_get_pos
#define xwlib_rbtree_get_pos(lpc)
获取lpc信息中的位置信息
Definition rbtree.h:141
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_insert_color
void xwlib_rbtree_insert_color(struct xwlib_rbtree *tree, struct xwlib_rbtree_node *node)
插入一个红色节点后修正红黑树的颜色
Definition rbtree.c:17
xwlib_rbtree_remove
void xwlib_rbtree_remove(struct xwlib_rbtree *tree, struct xwlib_rbtree_node *node)
删除一个节点，并修正红黑树的颜色
Definition rbtree.c:320
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)
链接节点，并设置位置及颜色信息
Definition rbtree.h:350
xwlib_rbtree_replace
void xwlib_rbtree_replace(struct xwlib_rbtree_node *newn, struct xwlib_rbtree_node *oldn)
用一个新节点代替旧节点，继承它的颜色、位置信息并接管它的子树
Definition rbtree.c:1007
xwlib_rbtree_gen_rc
#define xwlib_rbtree_gen_rc(n, color)
生成节点右边的链指针、位置和颜色信息
Definition rbtree.h:176
XWLIB_RBTREE_POS_RIGHT
@ XWLIB_RBTREE_POS_RIGHT
Definition rbtree.h:67
XWLIB_RBTREE_COLOR_BLACK
@ XWLIB_RBTREE_COLOR_BLACK
Definition rbtree.h:75
NULL
#define NULL
Definition type.h:28
xwptr_t
unsigned long xwptr_t
Definition type.h:375
rbtree.h
XWOS通用库：红黑树
xwlib_rbtree_node
红黑树节点
Definition rbtree.h:81
xwlib_rbtree_node::left
struct xwlib_rbtree_node * left
Definition rbtree.h:82
xwlib_rbtree_node::color
xwptr_t color
Definition rbtree.h:87
xwlib_rbtree_node::right
struct xwlib_rbtree_node * right
Definition rbtree.h:83
xwlib_rbtree_node::v
xwptr_t v
Definition rbtree.h:88
xwlib_rbtree_node::lpc
union xwlib_rbtree_node::@5 lpc
xwlib_rbtree
红黑树
Definition rbtree.h:95
xwlib_rbtree::root
struct xwlib_rbtree_node * root
Definition rbtree.h:96
standard.h
XWOS的标准头文件