1 /* Ordered {set,map} data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2021 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
4
5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation; either version 2.1 of the
8 License, or (at your option) any later version.
9
10 This file is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 /* A red-black tree is a binary tree where every node is colored black or
19 red such that
20 1. The root is black.
21 2. No red node has a red parent.
22 Or equivalently: No red node has a red child.
23 3. All paths from the root down to any NULL endpoint contain the same
24 number of black nodes.
25 Let's call this the "black-height" bh of the tree. It follows that every
26 such path contains exactly bh black and between 0 and bh red nodes. (The
27 extreme cases are a path containing only black nodes, and a path colored
28 alternately black-red-black-red-...-black-red.) The height of the tree
29 therefore is >= bh, <= 2*bh.
30 */
31
32 /* Color of a node. */
33 typedef enum color { BLACK, RED } color_t;
34
35 /* Tree node implementation, valid for this file only. */
36 struct NODE_IMPL
37 {
38 struct NODE_IMPL *left; /* left branch, or NULL */
39 struct NODE_IMPL *right; /* right branch, or NULL */
40 /* Parent pointer, or NULL. The parent pointer is not needed for most
41 operations. It is needed so that a NODE_T can be returned without
42 memory allocation, on which the functions <container>_remove_node,
43 <container>_add_before, <container>_add_after can be implemented. */
44 struct NODE_IMPL *parent;
45 color_t color; /* node's color */
46 NODE_PAYLOAD_FIELDS
47 };
48 typedef struct NODE_IMPL * NODE_T;
49
50 /* Concrete CONTAINER_IMPL type, valid for this file only. */
51 struct CONTAINER_IMPL
52 {
53 struct CONTAINER_IMPL_BASE base;
54 struct NODE_IMPL *root; /* root node or NULL */
55 size_t count; /* number of nodes */
56 };
57
58 /* A red-black tree of height h has a black-height bh >= ceil(h/2) and
59 therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree
60 of height h >= 117 would have at least 2^59 - 1 elements, and because even
61 on 64-bit machines,
62 sizeof (NODE_IMPL) * (2^59 - 1) > 2^64
63 this would exceed the address space of the machine. */
64 #define MAXHEIGHT 116
65
66 /* Rotates left a subtree.
67
68 B D
69 / \ / \
70 A D --> B E
71 / \ / \
72 C E A C
73
74 Changes the tree structure, updates the branch sizes.
75 The caller must update the colors and register D as child of its parent. */
76 static NODE_T
77 rotate_left (NODE_T b_node, NODE_T d_node)
78 {
79 NODE_T c_node = d_node->left;
80
81 b_node->right = c_node;
82 d_node->left = b_node;
83
84 d_node->parent = b_node->parent;
85 b_node->parent = d_node;
86 if (c_node != NULL)
87 c_node->parent = b_node;
88
89 return d_node;
90 }
91
92 /* Rotates right a subtree.
93
94 D B
95 / \ / \
96 B E --> A D
97 / \ / \
98 A C C E
99
100 Changes the tree structure, updates the branch sizes.
101 The caller must update the colors and register B as child of its parent. */
102 static NODE_T
103 rotate_right (NODE_T b_node, NODE_T d_node)
104 {
105 NODE_T c_node = b_node->right;
106
107 d_node->left = c_node;
108 b_node->right = d_node;
109
110 b_node->parent = d_node->parent;
111 d_node->parent = b_node;
112 if (c_node != NULL)
113 c_node->parent = d_node;
114
115 return b_node;
116 }
117
118 /* Ensures the tree is balanced, after an insertion operation.
119 Also assigns node->color.
120 parent is the given node's parent, known to be non-NULL. */
121 static void
122 rebalance_after_add (CONTAINER_T container, NODE_T node, NODE_T parent)
123 {
124 for (;;)
125 {
126 /* At this point, parent = node->parent != NULL.
127 Think of node->color being RED (although node->color is not yet
128 assigned.) */
129 NODE_T grandparent;
130 NODE_T uncle;
131
132 if (parent->color == BLACK)
133 {
134 /* A RED color for node is acceptable. */
135 node->color = RED;
136 return;
137 }
138
139 grandparent = parent->parent;
140 /* Since parent is RED, we know that
141 grandparent is != NULL and colored BLACK. */
142
143 if (grandparent->left == parent)
144 uncle = grandparent->right;
145 else if (grandparent->right == parent)
146 uncle = grandparent->left;
147 else
148 abort ();
149
150 if (uncle != NULL && uncle->color == RED)
151 {
152 /* Change grandparent from BLACK to RED, and
153 change parent and uncle from RED to BLACK.
154 This makes it acceptable for node to be RED. */
155 node->color = RED;
156 parent->color = uncle->color = BLACK;
157 node = grandparent;
158 }
159 else
160 {
161 /* grandparent and uncle are BLACK. parent is RED. node wants
162 to be RED too.
163 In this case, recoloring is not sufficient. Need to perform
164 one or two rotations. */
165 NODE_T *grandparentp;
166
167 if (grandparent->parent == NULL)
168 grandparentp = &container->root;
169 else if (grandparent->parent->left == grandparent)
170 grandparentp = &grandparent->parent->left;
171 else if (grandparent->parent->right == grandparent)
172 grandparentp = &grandparent->parent->right;
173 else
174 abort ();
175
176 if (grandparent->left == parent)
177 {
178 if (parent->right == node)
179 {
180 /* Rotation between node and parent. */
181 grandparent->left = rotate_left (parent, node);
182 node = parent;
183 parent = grandparent->left;
184 }
185 /* grandparent and uncle are BLACK. parent and node want to be
186 RED. parent = grandparent->left. node = parent->left.
187
188 grandparent parent
189 bh+1 bh+1
190 / \ / \
191 parent uncle --> node grandparent
192 bh bh bh bh
193 / \ / \
194 node C C uncle
195 bh bh bh bh
196 */
197 *grandparentp = rotate_right (parent, grandparent);
198 parent->color = BLACK;
199 node->color = grandparent->color = RED;
200 }
201 else /* grandparent->right == parent */
202 {
203 if (parent->left == node)
204 {
205 /* Rotation between node and parent. */
206 grandparent->right = rotate_right (node, parent);
207 node = parent;
208 parent = grandparent->right;
209 }
210 /* grandparent and uncle are BLACK. parent and node want to be
211 RED. parent = grandparent->right. node = parent->right.
212
213 grandparent parent
214 bh+1 bh+1
215 / \ / \
216 uncle parent --> grandparent node
217 bh bh bh bh
218 / \ / \
219 C node uncle C
220 bh bh bh bh
221 */
222 *grandparentp = rotate_left (grandparent, parent);
223 parent->color = BLACK;
224 node->color = grandparent->color = RED;
225 }
226 return;
227 }
228
229 /* Start again with a new (node, parent) pair. */
230 parent = node->parent;
231
232 if (parent == NULL)
233 {
234 /* Change node's color from RED to BLACK. This increases the
235 tree's black-height. */
236 node->color = BLACK;
237 return;
238 }
239 }
240 }
241
242 /* Ensures the tree is balanced, after a deletion operation.
243 CHILD was a grandchild of PARENT and is now its child. Between them,
244 a black node was removed. CHILD is also black, or NULL.
245 (CHILD can also be NULL. But PARENT is non-NULL.) */
246 static void
247 rebalance_after_remove (CONTAINER_T container, NODE_T child, NODE_T parent)
248 {
249 for (;;)
250 {
251 /* At this point, we reduced the black-height of the CHILD subtree by 1.
252 To make up, either look for a possibility to turn a RED to a BLACK
253 node, or try to reduce the black-height tree of CHILD's sibling
254 subtree as well. */
255 NODE_T *parentp;
256
257 if (parent->parent == NULL)
258 parentp = &container->root;
259 else if (parent->parent->left == parent)
260 parentp = &parent->parent->left;
261 else if (parent->parent->right == parent)
262 parentp = &parent->parent->right;
263 else
264 abort ();
265
266 if (parent->left == child)
267 {
268 NODE_T sibling = parent->right;
269 /* sibling's black-height is >= 1. In particular,
270 sibling != NULL.
271
272 parent
273 / \
274 child sibling
275 bh bh+1
276 */
277
278 if (sibling->color == RED)
279 {
280 /* sibling is RED, hence parent is BLACK and sibling's children
281 are non-NULL and BLACK.
282
283 parent sibling
284 bh+2 bh+2
285 / \ / \
286 child sibling --> parent SR
287 bh bh+1 bh+1 bh+1
288 / \ / \
289 SL SR child SL
290 bh+1 bh+1 bh bh+1
291 */
292 *parentp = rotate_left (parent, sibling);
293 parent->color = RED;
294 sibling->color = BLACK;
295
296 /* Concentrate on the subtree of parent. The new sibling is
297 one of the old sibling's children, and known to be BLACK. */
298 parentp = &sibling->left;
299 sibling = parent->right;
300 }
301 /* Now we know that sibling is BLACK.
302
303 parent
304 / \
305 child sibling
306 bh bh+1
307 */
308 if (sibling->right != NULL && sibling->right->color == RED)
309 {
310 /*
311 parent sibling
312 bh+1|bh+2 bh+1|bh+2
313 / \ / \
314 child sibling --> parent SR
315 bh bh+1 bh+1 bh+1
316 / \ / \
317 SL SR child SL
318 bh bh bh bh
319 */
320 *parentp = rotate_left (parent, sibling);
321 sibling->color = parent->color;
322 parent->color = BLACK;
323 sibling->right->color = BLACK;
324 return;
325 }
326 else if (sibling->left != NULL && sibling->left->color == RED)
327 {
328 /*
329 parent parent
330 bh+1|bh+2 bh+1|bh+2
331 / \ / \
332 child sibling --> child SL
333 bh bh+1 bh bh+1
334 / \ / \
335 SL SR SLL sibling
336 bh bh bh bh
337 / \ / \
338 SLL SLR SLR SR
339 bh bh bh bh
340
341 where SLL, SLR, SR are all black.
342 */
343 parent->right = rotate_right (sibling->left, sibling);
344 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
345 sibling->color = RED;
346 sibling = parent->right;
347 sibling->color = BLACK;
348
349 /* Now do as in the previous case. */
350 *parentp = rotate_left (parent, sibling);
351 sibling->color = parent->color;
352 parent->color = BLACK;
353 sibling->right->color = BLACK;
354 return;
355 }
356 else
357 {
358 if (parent->color == BLACK)
359 {
360 /* Change sibling from BLACK to RED. Then the entire
361 subtree at parent has decreased its black-height.
362 parent parent
363 bh+2 bh+1
364 / \ / \
365 child sibling --> child sibling
366 bh bh+1 bh bh
367 */
368 sibling->color = RED;
369
370 child = parent;
371 }
372 else
373 {
374 /* Change parent from RED to BLACK, but compensate by
375 changing sibling from BLACK to RED.
376 parent parent
377 bh+1 bh+1
378 / \ / \
379 child sibling --> child sibling
380 bh bh+1 bh bh
381 */
382 parent->color = BLACK;
383 sibling->color = RED;
384 return;
385 }
386 }
387 }
388 else if (parent->right == child)
389 {
390 NODE_T sibling = parent->left;
391 /* sibling's black-height is >= 1. In particular,
392 sibling != NULL.
393
394 parent
395 / \
396 sibling child
397 bh+1 bh
398 */
399
400 if (sibling->color == RED)
401 {
402 /* sibling is RED, hence parent is BLACK and sibling's children
403 are non-NULL and BLACK.
404
405 parent sibling
406 bh+2 bh+2
407 / \ / \
408 sibling child --> SR parent
409 bh+1 ch bh+1 bh+1
410 / \ / \
411 SL SR SL child
412 bh+1 bh+1 bh+1 bh
413 */
414 *parentp = rotate_right (sibling, parent);
415 parent->color = RED;
416 sibling->color = BLACK;
417
418 /* Concentrate on the subtree of parent. The new sibling is
419 one of the old sibling's children, and known to be BLACK. */
420 parentp = &sibling->right;
421 sibling = parent->left;
422 }
423 /* Now we know that sibling is BLACK.
424
425 parent
426 / \
427 sibling child
428 bh+1 bh
429 */
430 if (sibling->left != NULL && sibling->left->color == RED)
431 {
432 /*
433 parent sibling
434 bh+1|bh+2 bh+1|bh+2
435 / \ / \
436 sibling child --> SL parent
437 bh+1 bh bh+1 bh+1
438 / \ / \
439 SL SR SR child
440 bh bh bh bh
441 */
442 *parentp = rotate_right (sibling, parent);
443 sibling->color = parent->color;
444 parent->color = BLACK;
445 sibling->left->color = BLACK;
446 return;
447 }
448 else if (sibling->right != NULL && sibling->right->color == RED)
449 {
450 /*
451 parent parent
452 bh+1|bh+2 bh+1|bh+2
453 / \ / \
454 sibling child --> SR child
455 bh+1 bh bh+1 bh
456 / \ / \
457 SL SR sibling SRR
458 bh bh bh bh
459 / \ / \
460 SRL SRR SL SRL
461 bh bh bh bh
462
463 where SL, SRL, SRR are all black.
464 */
465 parent->left = rotate_left (sibling, sibling->right);
466 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
467 sibling->color = RED;
468 sibling = parent->left;
469 sibling->color = BLACK;
470
471 /* Now do as in the previous case. */
472 *parentp = rotate_right (sibling, parent);
473 sibling->color = parent->color;
474 parent->color = BLACK;
475 sibling->left->color = BLACK;
476 return;
477 }
478 else
479 {
480 if (parent->color == BLACK)
481 {
482 /* Change sibling from BLACK to RED. Then the entire
483 subtree at parent has decreased its black-height.
484 parent parent
485 bh+2 bh+1
486 / \ / \
487 sibling child --> sibling child
488 bh+1 bh bh bh
489 */
490 sibling->color = RED;
491
492 child = parent;
493 }
494 else
495 {
496 /* Change parent from RED to BLACK, but compensate by
497 changing sibling from BLACK to RED.
498 parent parent
499 bh+1 bh+1
500 / \ / \
501 sibling child --> sibling child
502 bh+1 bh bh bh
503 */
504 parent->color = BLACK;
505 sibling->color = RED;
506 return;
507 }
508 }
509 }
510 else
511 abort ();
512
513 /* Start again with a new (child, parent) pair. */
514 parent = child->parent;
515
516 #if 0 /* Already handled. */
517 if (child != NULL && child->color == RED)
518 {
519 child->color = BLACK;
520 return;
521 }
522 #endif
523
524 if (parent == NULL)
525 return;
526 }
527 }
528
529 static NODE_T
530 gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS)
531 {
532 /* Create new node. */
533 NODE_T new_node =
534 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
535
536 if (new_node == NULL)
537 return NULL;
538
539 new_node->left = NULL;
540 new_node->right = NULL;
541 NODE_PAYLOAD_ASSIGN(new_node)
542
543 /* Add it to the tree. */
544 if (container->root == NULL)
545 {
546 new_node->color = BLACK;
547 container->root = new_node;
548 new_node->parent = NULL;
549 }
550 else
551 {
552 NODE_T node;
553
554 for (node = container->root; node->left != NULL; )
555 node = node->left;
556
557 node->left = new_node;
558 new_node->parent = node;
559
560 /* Color and rebalance. */
561 rebalance_after_add (container, new_node, node);
562 }
563
564 container->count++;
565 return new_node;
566 }
567
568 /* Adds the already allocated NEW_NODE to the tree, right before NODE. */
569 static void
570 gl_tree_add_node_before (CONTAINER_T container, NODE_T node, NODE_T new_node)
571 {
572 new_node->left = NULL;
573 new_node->right = NULL;
574
575 /* Add it to the tree. */
576 if (node->left == NULL)
577 node->left = new_node;
578 else
579 {
580 for (node = node->left; node->right != NULL; )
581 node = node->right;
582 node->right = new_node;
583 }
584 new_node->parent = node;
585
586 /* Color and rebalance. */
587 rebalance_after_add (container, new_node, node);
588
589 container->count++;
590 }
591
592 static NODE_T
593 gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
594 {
595 /* Create new node. */
596 NODE_T new_node =
597 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
598
599 if (new_node == NULL)
600 return NULL;
601
602 NODE_PAYLOAD_ASSIGN(new_node)
603
604 gl_tree_add_node_before (container, node, new_node);
605 return new_node;
606 }
607
608 /* Adds the already allocated NEW_NODE to the tree, right after NODE. */
609 static void
610 gl_tree_add_node_after (CONTAINER_T container, NODE_T node, NODE_T new_node)
611 {
612 new_node->left = NULL;
613 new_node->right = NULL;
614
615 /* Add it to the tree. */
616 if (node->right == NULL)
617 node->right = new_node;
618 else
619 {
620 for (node = node->right; node->left != NULL; )
621 node = node->left;
622 node->left = new_node;
623 }
624 new_node->parent = node;
625
626 /* Color and rebalance. */
627 rebalance_after_add (container, new_node, node);
628
629 container->count++;
630 }
631
632 static NODE_T
633 gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
634 {
635 /* Create new node. */
636 NODE_T new_node =
637 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
638
639 if (new_node == NULL)
640 return NULL;
641
642 NODE_PAYLOAD_ASSIGN(new_node)
643
644 gl_tree_add_node_after (container, node, new_node);
645 return new_node;
646 }
647
648 static void
649 gl_tree_remove_node_no_free (CONTAINER_T container, NODE_T node)
650 {
651 NODE_T parent = node->parent;
652
653 if (node->left == NULL)
654 {
655 /* Replace node with node->right. */
656 NODE_T child = node->right;
657
658 if (child != NULL)
659 {
660 child->parent = parent;
661 /* Since node->left == NULL, child must be RED and of height 1,
662 hence node must have been BLACK. Recolor the child. */
663 child->color = BLACK;
664 }
665 if (parent == NULL)
666 container->root = child;
667 else
668 {
669 if (parent->left == node)
670 parent->left = child;
671 else /* parent->right == node */
672 parent->right = child;
673
674 if (child == NULL && node->color == BLACK)
675 rebalance_after_remove (container, child, parent);
676 }
677 }
678 else if (node->right == NULL)
679 {
680 /* It is not absolutely necessary to treat this case. But the more
681 general case below is more complicated, hence slower. */
682 /* Replace node with node->left. */
683 NODE_T child = node->left;
684
685 child->parent = parent;
686 /* Since node->right == NULL, child must be RED and of height 1,
687 hence node must have been BLACK. Recolor the child. */
688 child->color = BLACK;
689 if (parent == NULL)
690 container->root = child;
691 else
692 {
693 if (parent->left == node)
694 parent->left = child;
695 else /* parent->right == node */
696 parent->right = child;
697 }
698 }
699 else
700 {
701 /* Replace node with the rightmost element of the node->left subtree. */
702 NODE_T subst;
703 NODE_T subst_parent;
704 NODE_T child;
705 color_t removed_color;
706
707 for (subst = node->left; subst->right != NULL; )
708 subst = subst->right;
709
710 subst_parent = subst->parent;
711
712 child = subst->left;
713
714 removed_color = subst->color;
715
716 /* The case subst_parent == node is special: If we do nothing special,
717 we get confusion about node->left, subst->left and child->parent.
718 subst_parent == node
719 <==> The 'for' loop above terminated immediately.
720 <==> subst == subst_parent->left
721 [otherwise subst == subst_parent->right]
722 In this case, we would need to first set
723 child->parent = node; node->left = child;
724 and later - when we copy subst into node's position - again
725 child->parent = subst; subst->left = child;
726 Altogether a no-op. */
727 if (subst_parent != node)
728 {
729 if (child != NULL)
730 child->parent = subst_parent;
731 subst_parent->right = child;
732 }
733
734 /* Copy subst into node's position.
735 (This is safer than to copy subst's value into node, keep node in
736 place, and free subst.) */
737 if (subst_parent != node)
738 {
739 subst->left = node->left;
740 subst->left->parent = subst;
741 }
742 subst->right = node->right;
743 subst->right->parent = subst;
744 subst->color = node->color;
745 subst->parent = parent;
746 if (parent == NULL)
747 container->root = subst;
748 else if (parent->left == node)
749 parent->left = subst;
750 else /* parent->right == node */
751 parent->right = subst;
752
753 if (removed_color == BLACK)
754 {
755 if (child != NULL && child->color == RED)
756 /* Recolor the child. */
757 child->color = BLACK;
758 else
759 /* Rebalancing starts at child's parent, that is subst_parent -
760 except when subst_parent == node. In this case, we need to use
761 its replacement, subst. */
762 rebalance_after_remove (container, child,
763 subst_parent != node ? subst_parent : subst);
764 }
765 }
766
767 container->count--;
768 }
769
770 static bool
771 gl_tree_remove_node (CONTAINER_T container, NODE_T node)
772 {
773 gl_tree_remove_node_no_free (container, node);
774 NODE_PAYLOAD_DISPOSE (container, node)
775 free (node);
776 return true;
777 }
778
779 /* For debugging. */
780 static unsigned int
781 check_invariants (NODE_T node, NODE_T parent, size_t *counterp)
782 {
783 unsigned int left_blackheight =
784 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
785 unsigned int right_blackheight =
786 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
787
788 if (!(node->parent == parent))
789 abort ();
790 if (!(node->color == BLACK || node->color == RED))
791 abort ();
792 if (parent == NULL && !(node->color == BLACK))
793 abort ();
794 if (!(left_blackheight == right_blackheight))
795 abort ();
796
797 (*counterp)++;
798
799 return left_blackheight + (node->color == BLACK ? 1 : 0);
800 }