1 /*******************************************************************************
2 * Copyright (C) 2018 Cadence Design Systems, Inc.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to use this Software with Cadence processor cores only and
7 * not with any other processors and platforms, subject to
8 * the following conditions:
9 *
10 * The above copyright notice and this permission notice shall be included
11 * in all copies or substantial portions of the Software.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
14 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
15 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
16 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
17 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
18 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
19 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21 ******************************************************************************/
22
23 /*******************************************************************************
24 * rbtree.c
25 *
26 * Red-black tree library
27 ******************************************************************************/
28
29 #include "xf.h"
30
31 /*******************************************************************************
32 * Macros definitions
33 ******************************************************************************/
34
35 /* ...node color */
36 #define RB_RED (1)
37 #define RB_BLK (0)
38
39 /* ...pointer to parent node */
40 #define RB_PARENT(tree, node) ((node)->parent)
41
42 /* ...pointer to left child node */
43 #define RB_LEFT(tree, node) ((node)->left)
44
45 /* ...pointer to right child node */
46 #define RB_RIGHT(tree, node) ((node)->right)
47
48 /* ...pointer to right child node */
49 #define RB_COLOR(tree, node) ((node)->color & 1)
50
51 /* ...check if node is black */
52 #define RB_IS_BLACK(tree, node) (!((node)->color & RB_RED))
53
54 /* ...root node index of the tree - can be simplified? */
55 #define RB_ROOT(tree) RB_LEFT((tree), &(tree)->root)
56
57 /* ...empty node */
58 #define RB_NULL(tree) (&(tree)->root)
59
60 /*******************************************************************************
61 * Helpers
62 ******************************************************************************/
63
64 #define RB_SET_P(t, n, p) \
65 ({ (n)->parent = (p); })
66
67 #define RB_SET_L(t, n, l) \
68 ({ (n)->left = (l); })
69
70 #define RB_SET_R(t, n, r) \
71 ({ (n)->right = (r); })
72
73 #define RB_SET_C(t, n, c) \
74 RB_SET_C_##c((t), (n))
75
76 #define RB_SET_C_RB_BLK(t, n) \
77 ({ (n)->color &= ~1; })
78
79 #define RB_SET_C_RB_RED(t, n) \
80 ({ (n)->color |= 1; })
81
82 #define RB_SET_P_C(t, n, p, c) \
83 ({ (n)->parent = (p); RB_SET_C_##c(t, n); })
84
85 #define RB_SET_P_L(t, n, p, l) \
86 ({ (n)->parent = (p); (n)->left = (l); })
87
88 #define RB_SET_P_L_C(t, n, p, l, c) \
89 ({ (n)->parent = (p); (n)->left = (l); RB_SET_C_##c(t, n); })
90
91 #define RB_SET_P_R(t, n, p, r) \
92 ({ (n)->parent = (p); (n)->right = (r); })
93
94 #define RB_SET_P_R_C(t, n, p, r, c) \
95 ({ (n)->parent = (p); (n)->right = (r); RB_SET_C_##c(t, n); })
96
97 #define RB_SET_P_L_R(t, n, p, l, r) \
98 ({ (n)->parent = (p); (n)->left = (l); (n)->right = (r); })
99
100 #define RB_SET_P_L_R_C(t, n, p, l, r, c)\
101 ({ (n)->parent = (p); (n)->left = (l); (n)->right = (r); RB_SET_C_##c(t, n); })
102
103 #define RB_SET_ROOT(t, n) \
104 RB_SET_L((t), &(t)->root, (n))
105
106 /*******************************************************************************
107 * RB-tree functions
108 ******************************************************************************/
109
110 /*******************************************************************************
111 * rb_first, rb_last
112 *
113 * Return pointer to first/last item in the tree
114 ******************************************************************************/
115
rb_first(rb_tree_t * tree)116 rb_idx_t rb_first(rb_tree_t *tree)
117 {
118 rb_idx_t p_idx, t_idx;
119
120 if ((p_idx = RB_ROOT(tree)) != RB_NULL(tree))
121 {
122 /* ...find left-most item in non-empty tree */
123 while ((t_idx = RB_LEFT(tree, p_idx)) != RB_NULL(tree))
124 p_idx = t_idx;
125 }
126
127 return p_idx;
128 }
129
rb_last(rb_tree_t * tree)130 rb_idx_t rb_last(rb_tree_t *tree)
131 {
132 rb_idx_t p_idx, t_idx;
133
134 if ((p_idx = RB_ROOT(tree)) != RB_NULL(tree))
135 {
136 /* ...find right-most item in non-empty tree */
137 while ((t_idx = RB_RIGHT(tree, p_idx)) != RB_NULL(tree))
138 p_idx = t_idx;
139 }
140
141 return p_idx;
142 }
143
144 /*******************************************************************************
145 * rb_next, rb_prev
146 *
147 * Return next / previous in-order item in the tree
148 ******************************************************************************/
149
rb_next(rb_tree_t * tree,rb_idx_t n_idx)150 rb_idx_t rb_next(rb_tree_t *tree, rb_idx_t n_idx)
151 {
152 rb_idx_t p_idx, c_idx, t_idx;
153
154 /* ...if we have any right children, process them */
155 if ((c_idx = RB_RIGHT(tree, n_idx)) != RB_NULL(tree))
156 {
157 /* ...descent to the left-most node starting from right child */
158 while ((t_idx = RB_LEFT(tree, c_idx)) != RB_NULL(tree))
159 c_idx = t_idx;
160 return c_idx;
161 }
162
163 /* ...no right children; ascend to our parent while we are right child */
164 while ((p_idx = RB_PARENT(tree, n_idx)) != RB_NULL(tree))
165 {
166 /* ...as soon as "n" is a left child, return "p" */
167 if (n_idx == RB_RIGHT(tree, p_idx))
168 n_idx = p_idx;
169 else
170 return p_idx;
171 }
172
173 /* ...we were right-most child */
174 return p_idx;
175 }
176
rb_prev(rb_tree_t * tree,rb_idx_t n_idx)177 rb_idx_t rb_prev(rb_tree_t *tree, rb_idx_t n_idx)
178 {
179 rb_idx_t p_idx, c_idx, t_idx;
180
181 /* ...if we have any left children, process them */
182 if ((c_idx = RB_LEFT(tree, n_idx)) != RB_NULL(tree))
183 {
184 /* ...descent to the right-most node starting from left child */
185 while ((t_idx = RB_RIGHT(tree, c_idx)) != RB_NULL(tree))
186 c_idx = t_idx;
187 return c_idx;
188 }
189
190 /* ...no left children; ascend to our parent while we are left child */
191 while ((p_idx = RB_PARENT(tree, n_idx)) != RB_NULL(tree))
192 {
193 /* ...as soon as "n" is a right child, return "p" */
194 if (n_idx == RB_LEFT(tree, p_idx))
195 n_idx = p_idx;
196 else
197 return p_idx;
198 }
199
200 /* ...we were left-most child */
201 return p_idx;
202 }
203
204 /*******************************************************************************
205 * rb_init
206 *
207 * Initialize rb-tree structure
208 ******************************************************************************/
209
rb_init(rb_tree_t * tree)210 void rb_init(rb_tree_t *tree)
211 {
212 /* ...initialize sentinel node of the empty tree */
213 RB_SET_P_L_R_C(tree, &tree->root, RB_NULL(tree), RB_NULL(tree), RB_NULL(tree), RB_BLK);
214 }
215
216 /*******************************************************************************
217 * rb_insert
218 *
219 * Insert new item into RB-tree. Returns non-zero node index on success
220 ******************************************************************************/
221
222 /* ...internal tree balancing function */
__rb_insert_balance(rb_tree_t * tree,rb_idx_t n_idx,rb_idx_t p_idx)223 static void __rb_insert_balance(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t p_idx)
224 {
225 rb_idx_t u_idx, g_idx, t_idx, cl_idx, cr_idx;
226
227 rebalance:
228
229 /***************************************************************************
230 * Trivial case #1 - N (red) is a root
231 **************************************************************************/
232
233 if (p_idx == RB_NULL(tree))
234 {
235 RB_SET_C(tree, n_idx, RB_BLK);
236 goto root;
237 }
238
239 /***************************************************************************
240 * Trivial case #2 - P is black
241 **************************************************************************/
242
243 if (RB_IS_BLACK(tree, p_idx))
244 goto done;
245
246 /***************************************************************************
247 * Complex cases - P is red, N is red
248 **************************************************************************/
249
250 /* ...grandparent must exist and be black */
251 g_idx = RB_PARENT(tree, p_idx);
252 if (p_idx == RB_LEFT(tree, g_idx))
253 {
254 /* ...we are left grandchild; get uncle (if it exists) */
255 u_idx = RB_RIGHT(tree, g_idx);
256
257 /* ...if U is read, we have conditions of case #3 */
258 if (!RB_IS_BLACK(tree, u_idx))
259 goto case3;
260
261 /* ...we will need grand-grand-parent later */
262 t_idx = RB_PARENT(tree, g_idx);
263
264 /* ...U is black/null; if we are LL grandchild, we have case #5 */
265 if (n_idx == RB_LEFT(tree, p_idx))
266 goto case5_ll;
267
268 /* ...N is RL grandchild of G; case #4 */
269 goto case4_rl;
270 }
271 else
272 {
273 /* ...we are right grandchild; get uncle (if it exists) */
274 u_idx = RB_LEFT(tree, g_idx);
275
276 /* ...if U is read, we have conditions of case #3 */
277 if (!RB_IS_BLACK(tree, u_idx))
278 goto case3;
279
280 /* ...we will need grand-grand-parent later */
281 t_idx = RB_PARENT(tree, g_idx);
282
283 /* ...U is black/null; if we are RR grandchild, we have case #5 */
284 if (n_idx == RB_RIGHT(tree, p_idx))
285 goto case5_rr;
286
287 /* ...N is LR grandchild of G; case #4 */
288 goto case4_lr;
289 }
290
291 case4_rl:
292
293 /***************************************************************************
294 * Case #4 - P is red, U is black, N is red RL grandchild of G. We will do
295 * two tree rotations - first the one described in case #4, second is the
296 * one described in case #5 (as have conditions for case #5(LL) with P and
297 * N changing roles
298 **************************************************************************/
299
300 cl_idx = RB_LEFT(tree, n_idx), cr_idx = RB_RIGHT(tree, n_idx);
301 RB_SET_P_L_R_C(tree, n_idx, t_idx, p_idx, g_idx, RB_BLK);
302 RB_SET_P_R(tree, p_idx, n_idx, cl_idx);
303 RB_SET_P(tree, cl_idx, p_idx);
304 RB_SET_P_L_C(tree, g_idx, n_idx, cr_idx, RB_RED);
305 RB_SET_P(tree, cr_idx, g_idx);
306
307 /* ...new root of subtree is N; adjust T pointer */
308 goto case5_xx;
309
310 case4_lr:
311
312 /***************************************************************************
313 * Case #4 - P is red, U is black, N is red LR grandchild of G. We will do
314 * two tree rotations - first the one described in case #4, second is the
315 * one described in case #5 (as have conditions for case #5(RR) with P and
316 * N changing roles
317 **************************************************************************/
318
319 cl_idx = RB_LEFT(tree, n_idx), cr_idx = RB_RIGHT(tree, n_idx);
320 RB_SET_P_L_R_C(tree, n_idx, t_idx, g_idx, p_idx, RB_BLK);
321 RB_SET_P_L(tree, p_idx, n_idx, cr_idx);
322 RB_SET_P(tree, cr_idx, p_idx);
323 RB_SET_P_R_C(tree, g_idx, n_idx, cl_idx, RB_RED);
324 RB_SET_P(tree, cl_idx, g_idx);
325
326 /* ...new root of the subtree is N; adjust T pointer */
327 goto case5_xx;
328
329 case5_ll:
330
331 /***************************************************************************
332 * Case #5: N is LL grandchild of P; N and P red, G and U black
333 **************************************************************************/
334
335 cr_idx = RB_RIGHT(tree, p_idx);
336 RB_SET_P_L_C(tree, g_idx, p_idx, cr_idx, RB_RED);
337 RB_SET_P(tree, cr_idx, g_idx);
338 RB_SET_P_R_C(tree, p_idx, t_idx, g_idx, RB_BLK);
339
340 /* ...new root of the subtree is P; relabel and adjust T pointer */
341 n_idx = p_idx;
342 goto case5_xx;
343
344 case5_rr:
345
346 /***************************************************************************
347 * Case #5: N is RR grandchild of P; N and P red, G and U black
348 **************************************************************************/
349
350 cl_idx = RB_LEFT(tree, p_idx);
351 RB_SET_P_R_C(tree, g_idx, p_idx, cl_idx, RB_RED);
352 RB_SET_P(tree, cl_idx, g_idx);
353 RB_SET_P_L_C(tree, p_idx, t_idx, g_idx, RB_BLK);
354
355 /* ...new root of the subtree is P; relabel and adjust T pointer */
356 n_idx = p_idx;
357 goto case5_xx;
358
359 case5_xx:
360
361 /* ...N is a (black) root of subtree; check if it is a root of tree as well */
362 if (t_idx == RB_NULL(tree))
363 goto root;
364 else if (g_idx == RB_LEFT(tree, t_idx))
365 RB_SET_L(tree, t_idx, n_idx);
366 else
367 RB_SET_R(tree, t_idx, n_idx);
368
369 goto done;
370
371 case3:
372
373 /***************************************************************************
374 * Case #3 - P and U are red, G is black
375 **************************************************************************/
376
377 RB_SET_C(tree, p_idx, RB_BLK);
378 RB_SET_C(tree, u_idx, RB_BLK);
379 RB_SET_C(tree, g_idx, RB_RED);
380
381 /* ...rebalance the tree for a G */
382 n_idx = g_idx, p_idx = RB_PARENT(tree, g_idx);
383 goto rebalance;
384
385 root:
386 /* ...adjust root pointer of the tree */
387 RB_SET_ROOT(tree, n_idx);
388
389 done:
390 /* ...tree is balanced */
391 return;
392 }
393
394 /* ...high-level API function */
rb_insert(rb_tree_t * tree,rb_idx_t n_idx,rb_idx_t p_idx)395 void rb_insert(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t p_idx)
396 {
397 if (p_idx == RB_NULL(tree))
398 {
399 /* ...set black root node */
400 RB_SET_P_L_R_C(tree, n_idx, p_idx, p_idx, p_idx, RB_BLK);
401
402 /* ...tree consists of the only root node; is balanced */
403 RB_SET_ROOT(tree, n_idx);
404 }
405 else
406 {
407 /* ...create new node - set parent pointer and paint red */
408 RB_SET_P_L_R_C(tree, n_idx, p_idx, RB_NULL(tree), RB_NULL(tree), RB_RED);
409
410 /* ...and rebalance the tree */
411 __rb_insert_balance(tree, n_idx, p_idx);
412 }
413 }
414
415 /*******************************************************************************
416 * rb_delete
417 *
418 * Remove item from RB-key (by key). Returns zero on success
419 ******************************************************************************/
420
421 /* ...internal tree balancing function */
__rb_delete_rebalance(rb_tree_t * tree,rb_idx_t p_idx)422 static void __rb_delete_rebalance(rb_tree_t *tree, rb_idx_t p_idx)
423 {
424 rb_idx_t n_idx, s_idx, sl_idx, sr_idx, g_idx, c_idx, cl_idx, cr_idx;
425
426 /* ...initialize rebalancing procedure with null-child of P */
427 n_idx = RB_NULL(tree);
428
429 rebalance:
430
431 /* ...save grand-parent pointer (may be null) */
432 g_idx = RB_PARENT(tree, p_idx);
433
434 /***************************************************************************
435 * Check for complex cases
436 **************************************************************************/
437
438 if (n_idx == RB_LEFT(tree, p_idx))
439 {
440 /* ...N is left child; get sibling (must exist) and its children */
441 s_idx = RB_RIGHT(tree, p_idx);
442 sl_idx = RB_LEFT(tree, s_idx);
443 sr_idx = RB_RIGHT(tree, s_idx);
444
445 /* ...if S is black, test for conditions 3,4,5,6; otherwise - case 2 */
446 if (RB_IS_BLACK(tree, s_idx))
447 goto test3_l;
448 else
449 goto case2_l;
450 }
451 else
452 {
453 /* ...N is right child; get sibling (must exist) and its children */
454 s_idx = RB_LEFT(tree, p_idx);
455 sl_idx = RB_LEFT(tree, s_idx);
456 sr_idx = RB_RIGHT(tree, s_idx);
457
458 /* ...if S is black, test for conditions 3,4,5,6; otherwise - case 2 */
459 if (RB_IS_BLACK(tree, s_idx))
460 goto test3_r;
461 else
462 goto case2_r;
463 }
464
465 case2_l:
466
467 /***************************************************************************
468 * Case #2: N is a left child of P; S is red
469 **************************************************************************/
470
471 c_idx = sl_idx;
472 RB_SET_P_L_C(tree, s_idx, g_idx, p_idx, RB_BLK);
473 RB_SET_P_R_C(tree, p_idx, s_idx, c_idx, RB_RED);
474 RB_SET_P(tree, c_idx, p_idx);
475
476 /* ...S is new root of subtree, Sl(C) is new sibling of N; update G */
477 goto case2_x;
478
479 case2_r:
480
481 /***************************************************************************
482 * Case #2: N is a right child of P; S is red
483 **************************************************************************/
484
485 c_idx = sr_idx;
486 RB_SET_P_R_C(tree, s_idx, g_idx, p_idx, RB_BLK);
487 RB_SET_P_L_C(tree, p_idx, s_idx, c_idx, RB_RED);
488 RB_SET_P(tree, c_idx, p_idx);
489
490 /* ...S is new root of subtree, Sr(C) is new sibling of N; update G */
491 goto case2_x;
492
493 case2_x:
494
495 /* ...check if S is becoming new (black) root of the tree */
496 if (g_idx == RB_NULL(tree))
497 RB_SET_ROOT(tree, s_idx);
498 else if (p_idx == RB_LEFT(tree, g_idx))
499 RB_SET_L(tree, g_idx, s_idx);
500 else
501 RB_SET_R(tree, g_idx, s_idx);
502
503 /* ...relabel new N's grandparent (now S) as G and new sibling (now C) as S */
504 g_idx = s_idx, s_idx = c_idx;
505 sl_idx = RB_LEFT(tree, s_idx);
506 sr_idx = RB_RIGHT(tree, s_idx);
507
508 /* ...N is still one of P's children; select proper side */
509 if (n_idx == RB_LEFT(tree, p_idx))
510 goto test3_l;
511 else
512 goto test3_r;
513
514 test3_l:
515
516 /***************************************************************************
517 * Test for cases 3,4,5,6; P is any, S is black. N is left child of P
518 **************************************************************************/
519
520 if (!RB_IS_BLACK(tree, sr_idx))
521 /* ...Sr is red, Sl of any color; conditions for case #6 are met */
522 goto case6_l;
523 else if (!RB_IS_BLACK(tree, sl_idx))
524 /* ...Sr is black and Sl is red; conditions for case #5 are met */
525 goto case5_l;
526 else if (RB_IS_BLACK(tree, p_idx))
527 /* ...Sl and Sr are of the same (black) color and P is black */
528 goto case3;
529 else
530 /* ...Sl and Sr are of the same (black) color and P is red */
531 goto case4;
532
533 test3_r:
534
535 /***************************************************************************
536 * Test for cases 3,4,5,6; P is any, S is black. N is right child of P
537 **************************************************************************/
538
539 if (!RB_IS_BLACK(tree, sl_idx))
540 /* ...Sl is red, Sr of any color; conditions for case #6 are met */
541 goto case6_r;
542 else if (!RB_IS_BLACK(tree, sr_idx))
543 /* ...Sl is black and Sr is red; conditions for case #5 are met */
544 goto case5_r;
545 else if (RB_IS_BLACK(tree, p_idx))
546 /* ...Sl and Sr are of the same (black) color and P is black */
547 goto case3;
548 else
549 /* ...Sl and Sr are of the same (black) color and P is red */
550 goto case4;
551
552 case3:
553
554 /***************************************************************************
555 * Case #3: N, P, S, Sl and Sr are black
556 **************************************************************************/
557
558 RB_SET_C(tree, s_idx, RB_RED);
559
560 /* ...and rebalance the tree for parent */
561 n_idx = p_idx, p_idx = RB_PARENT(tree, p_idx);
562
563 if (p_idx == RB_NULL(tree))
564 goto done;
565 else
566 goto rebalance;
567
568 case4:
569
570 /***************************************************************************
571 * Case #4: N and S are black, P is red, Sl and Sr are all black
572 **************************************************************************/
573
574 RB_SET_C(tree, s_idx, RB_RED);
575 RB_SET_C(tree, p_idx, RB_BLK);
576
577 goto done;
578
579 case5_l:
580 /***************************************************************************
581 * Case #5: S is black, Sl is red, Sr is black; N is left child of P. We
582 * have two subsequent transformations (case #5 and case #6) combined
583 **************************************************************************/
584
585 cl_idx = RB_LEFT(tree, sl_idx);
586 cr_idx = RB_RIGHT(tree, sl_idx);
587
588 if (RB_IS_BLACK(tree, p_idx))
589 RB_SET_P_L_R_C(tree, sl_idx, g_idx, p_idx, s_idx, RB_BLK);
590 else
591 RB_SET_P_L_R_C(tree, sl_idx, g_idx, p_idx, s_idx, RB_RED);
592
593 RB_SET_P_R_C(tree, p_idx, sl_idx, cl_idx, RB_BLK);
594 RB_SET_P(tree, cl_idx, p_idx);
595 RB_SET_P_L(tree, s_idx, sl_idx, cr_idx);
596 RB_SET_P(tree, cr_idx, s_idx);
597
598 /* ...relabel new root as S (for common processing in case #6) */
599 s_idx = sl_idx;
600 goto case6_x;
601
602 case5_r:
603 /***************************************************************************
604 * Case #5: S is black, Sr is red, Sl is black; N is right child of P. We
605 * have two subsequent transformations (case #5 and case #6) combined
606 **************************************************************************/
607
608 cl_idx = RB_LEFT(tree, sr_idx);
609 cr_idx = RB_RIGHT(tree, sr_idx);
610
611 if (RB_IS_BLACK(tree, p_idx))
612 RB_SET_P_L_R_C(tree, sr_idx, g_idx, s_idx, p_idx, RB_BLK);
613 else
614 RB_SET_P_L_R_C(tree, sr_idx, g_idx, s_idx, p_idx, RB_RED);
615
616 RB_SET_P_L_C(tree, p_idx, sr_idx, cr_idx, RB_BLK);
617 RB_SET_P(tree, cr_idx, p_idx);
618 RB_SET_P_R(tree, s_idx, sr_idx, cl_idx);
619 RB_SET_P(tree, cl_idx, s_idx);
620
621 /* ...relabel new root as S (for common processing in case #6) */
622 s_idx = sr_idx;
623 goto case6_x;
624
625 case6_l:
626
627 /***************************************************************************
628 * Case #6: S is black, N is the left child of P, Sr is red
629 **************************************************************************/
630
631 if (RB_IS_BLACK(tree, p_idx))
632 RB_SET_P_L(tree, s_idx, g_idx, p_idx);
633 else
634 RB_SET_P_L_C(tree, s_idx, g_idx, p_idx, RB_RED);
635
636 RB_SET_P_R_C(tree, p_idx, s_idx, sl_idx, RB_BLK);
637 RB_SET_P(tree, sl_idx, p_idx);
638 RB_SET_C(tree, sr_idx, RB_BLK);
639
640 /* ...S is a new root of subtree; update G */
641 goto case6_x;
642
643 case6_r:
644
645 /***************************************************************************
646 * Case #6: S is black, N is the right child of P, Sl is red
647 **************************************************************************/
648
649 if (RB_IS_BLACK(tree, p_idx))
650 RB_SET_P_R(tree, s_idx, g_idx, p_idx);
651 else
652 RB_SET_P_R_C(tree, s_idx, g_idx, p_idx, RB_RED);
653
654 RB_SET_P_L_C(tree, p_idx, s_idx, sr_idx, RB_BLK);
655 RB_SET_P(tree, sr_idx, p_idx);
656 RB_SET_C(tree, sl_idx, RB_BLK);
657
658 /* ...S is a new root of subtree; update G */
659 goto case6_x;
660
661 case6_x:
662
663 /* ...S is a new root of subtree; update G's pointer */
664 if (g_idx == RB_NULL(tree))
665 RB_SET_ROOT(tree, s_idx);
666 else if (p_idx == RB_LEFT(tree, g_idx))
667 RB_SET_L(tree, g_idx, s_idx);
668 else
669 RB_SET_R(tree, g_idx, s_idx);
670
671 /* ...tree is balanced; pass through */
672
673 done:
674
675 return;
676 }
677
678 /* ...high-level API function */
rb_delete(rb_tree_t * tree,rb_idx_t n_idx)679 rb_idx_t rb_delete(rb_tree_t *tree, rb_idx_t n_idx)
680 {
681 rb_idx_t p_idx, t_idx, m_idx, c_idx, l_idx, r_idx, k_idx;
682 u32 color;
683
684 /* ...save parent of element N that we are going to remove */
685 p_idx = RB_PARENT(tree, n_idx);
686
687 /* ...get in-order predecessor/successor of n_idx, if possible */
688 if ((m_idx = RB_LEFT(tree, n_idx)) != RB_NULL(tree))
689 {
690 while ((t_idx = RB_RIGHT(tree, m_idx)) != RB_NULL(tree))
691 m_idx = t_idx;
692
693 /* ...set the child of in-order predecessor (may be null) */
694 c_idx = RB_LEFT(tree, m_idx);
695 }
696 else if ((m_idx = RB_RIGHT(tree, n_idx)) != RB_NULL(tree))
697 {
698 while ((t_idx = RB_LEFT(tree, m_idx)) != RB_NULL(tree))
699 m_idx = t_idx;
700
701 /* ...set the child of in-order successor (may be null) */
702 c_idx = RB_RIGHT(tree, m_idx);
703 }
704 else if (p_idx == RB_NULL(tree))
705 {
706 /* ...tree consists of the only root node N that we are removing */
707 RB_SET_ROOT(tree, m_idx);
708
709 /* ..return tree null pointer */
710 return m_idx;
711 }
712 else
713 {
714 /* ...N is a (non-root) leaf node; M and C are null */
715 c_idx = m_idx;
716
717 /* ...save the color of the node we are going to delete */
718 color = RB_COLOR(tree, n_idx);
719
720 /* ...set new parent of C */
721 t_idx = p_idx;
722
723 /* ...pointer that we return as in-order predecessor/successor */
724 k_idx = p_idx;
725
726 /* ...adjust only parent of the N */
727 goto adjust_parent;
728 }
729
730 /* ...node that replaces our component is M */
731 k_idx = m_idx;
732
733 /***************************************************************************
734 * Replace node N with M
735 **************************************************************************/
736
737 /* ...save original color of M (the node that we are deleting) */
738 color = RB_COLOR(tree, m_idx);
739
740 /* ...put M in place of N; get N's children */
741 l_idx = RB_LEFT(tree, n_idx);
742 r_idx = RB_RIGHT(tree, n_idx);
743
744 /* ...see if M is a child of N */
745 if ((t_idx = RB_PARENT(tree, m_idx)) != n_idx)
746 {
747 /* ...C becomes left or right child of M's original parent T */
748 if (c_idx == RB_LEFT(tree, m_idx))
749 RB_SET_R(tree, t_idx, c_idx);
750 else
751 RB_SET_L(tree, t_idx, c_idx);
752
753 /* ...adjust C parent pointer (okay if it's null) */
754 RB_SET_P(tree, c_idx, t_idx);
755
756 /* ...set all pointers of node M (it replaces N) */
757 RB_SET_P_L_R(tree, m_idx, p_idx, l_idx, r_idx);
758 RB_SET_P(tree, l_idx, m_idx);
759 RB_SET_P(tree, r_idx, m_idx);
760 }
761 else
762 {
763 /* ...M is a left or right child of N; it gets to N's place, and C remains intact */
764 if (m_idx == l_idx)
765 {
766 RB_SET_P_R(tree, m_idx, p_idx, r_idx);
767 RB_SET_P(tree, r_idx, m_idx);
768 }
769 else
770 {
771 RB_SET_P_L(tree, m_idx, p_idx, l_idx);
772 RB_SET_P(tree, l_idx, m_idx);
773 }
774
775 /* ...parent of C is still M (we label it as T) */
776 t_idx = m_idx;
777 }
778
779 /* ...paint M in the same color as N which it replaced */
780 if (RB_IS_BLACK(tree, n_idx))
781 RB_SET_C(tree, m_idx, RB_BLK);
782 else
783 RB_SET_C(tree, m_idx, RB_RED);
784
785 adjust_parent:
786
787 /* ...adjust N's parent node to point to M */
788 if (p_idx == RB_NULL(tree))
789 RB_SET_ROOT(tree, m_idx);
790 else if (n_idx == RB_LEFT(tree, p_idx))
791 RB_SET_L(tree, p_idx, m_idx);
792 else
793 RB_SET_R(tree, p_idx, m_idx);
794
795 /* ...check for a color of deleted item (M or N in case it is a leaf) */
796 if (color == RB_BLK)
797 {
798 if (c_idx == RB_NULL(tree))
799 /* ...rebalance the tree for a T node (it is never a null)*/
800 __rb_delete_rebalance(tree, t_idx);
801 else
802 /* ...C node exists and is necessarily red; repaint it black */
803 RB_SET_C(tree, c_idx, RB_BLK);
804 }
805
806 /* ....return the node K which replaced deleted node N */
807 return k_idx;
808 }
809
810 /*******************************************************************************
811 * rb_replace
812 *
813 * Replace the node with the same-key node - adjust tree pointers
814 ******************************************************************************/
815
rb_replace(rb_tree_t * tree,rb_idx_t n_idx,rb_idx_t t_idx)816 void rb_replace(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t t_idx)
817 {
818 rb_idx_t p_idx, l_idx, r_idx;
819
820 /* ...get node pointers */
821 p_idx = RB_PARENT(tree, n_idx), l_idx = RB_LEFT(tree, n_idx), r_idx = RB_RIGHT(tree, n_idx);
822
823 /* ...set new node pointers */
824 RB_SET_P_L_R(tree, t_idx, p_idx, l_idx, r_idx);
825
826 /* ...set node color */
827 if (RB_IS_BLACK(tree, n_idx))
828 RB_SET_C(tree, t_idx, RB_BLK);
829 else
830 RB_SET_C(tree, t_idx, RB_RED);
831
832 /* ...update parent node */
833 if (p_idx == RB_NULL(tree))
834 RB_SET_ROOT(tree, t_idx);
835 else if (n_idx == RB_LEFT(tree, p_idx))
836 RB_SET_L(tree, p_idx, t_idx);
837 else
838 RB_SET_R(tree, p_idx, t_idx);
839
840 /* ...update children's parent node (okay if null) */
841 RB_SET_P(tree, l_idx, t_idx), RB_SET_P(tree, r_idx, t_idx);
842 }
843