This source file includes following definitions.
- rotate_left
- rotate_right
- rebalance_after_add
- rebalance_after_remove
- gl_tree_nx_add_first
- gl_tree_add_node_before
- gl_tree_nx_add_before
- gl_tree_add_node_after
- gl_tree_nx_add_after
- gl_tree_remove_node_no_free
- gl_tree_remove_node
- check_invariants
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 typedef enum color { BLACK, RED } color_t;
34
35
36 struct NODE_IMPL
37 {
38 struct NODE_IMPL *left;
39 struct NODE_IMPL *right;
40
41
42
43
44 struct NODE_IMPL *parent;
45 color_t color;
46 NODE_PAYLOAD_FIELDS
47 };
48 typedef struct NODE_IMPL * NODE_T;
49
50
51 struct CONTAINER_IMPL
52 {
53 struct CONTAINER_IMPL_BASE base;
54 struct NODE_IMPL *root;
55 size_t count;
56 };
57
58
59
60
61
62
63
64 #define MAXHEIGHT 116
65
66
67
68
69
70
71
72
73
74
75
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
93
94
95
96
97
98
99
100
101
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
119
120
121 static void
122 rebalance_after_add (CONTAINER_T container, NODE_T node, NODE_T parent)
123 {
124 for (;;)
125 {
126
127
128
129 NODE_T grandparent;
130 NODE_T uncle;
131
132 if (parent->color == BLACK)
133 {
134
135 node->color = RED;
136 return;
137 }
138
139 grandparent = parent->parent;
140
141
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
153
154
155 node->color = RED;
156 parent->color = uncle->color = BLACK;
157 node = grandparent;
158 }
159 else
160 {
161
162
163
164
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
181 grandparent->left = rotate_left (parent, node);
182 node = parent;
183 parent = grandparent->left;
184 }
185
186
187
188
189
190
191
192
193
194
195
196
197 *grandparentp = rotate_right (parent, grandparent);
198 parent->color = BLACK;
199 node->color = grandparent->color = RED;
200 }
201 else
202 {
203 if (parent->left == node)
204 {
205
206 grandparent->right = rotate_right (node, parent);
207 node = parent;
208 parent = grandparent->right;
209 }
210
211
212
213
214
215
216
217
218
219
220
221
222 *grandparentp = rotate_left (grandparent, parent);
223 parent->color = BLACK;
224 node->color = grandparent->color = RED;
225 }
226 return;
227 }
228
229
230 parent = node->parent;
231
232 if (parent == NULL)
233 {
234
235
236 node->color = BLACK;
237 return;
238 }
239 }
240 }
241
242
243
244
245
246 static void
247 rebalance_after_remove (CONTAINER_T container, NODE_T child, NODE_T parent)
248 {
249 for (;;)
250 {
251
252
253
254
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
270
271
272
273
274
275
276
277
278 if (sibling->color == RED)
279 {
280
281
282
283
284
285
286
287
288
289
290
291
292 *parentp = rotate_left (parent, sibling);
293 parent->color = RED;
294 sibling->color = BLACK;
295
296
297
298 parentp = &sibling->left;
299 sibling = parent->right;
300 }
301
302
303
304
305
306
307
308 if (sibling->right != NULL && sibling->right->color == RED)
309 {
310
311
312
313
314
315
316
317
318
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
330
331
332
333
334
335
336
337
338
339
340
341
342
343 parent->right = rotate_right (sibling->left, sibling);
344
345 sibling->color = RED;
346 sibling = parent->right;
347 sibling->color = BLACK;
348
349
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
361
362
363
364
365
366
367
368 sibling->color = RED;
369
370 child = parent;
371 }
372 else
373 {
374
375
376
377
378
379
380
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
392
393
394
395
396
397
398
399
400 if (sibling->color == RED)
401 {
402
403
404
405
406
407
408
409
410
411
412
413
414 *parentp = rotate_right (sibling, parent);
415 parent->color = RED;
416 sibling->color = BLACK;
417
418
419
420 parentp = &sibling->right;
421 sibling = parent->left;
422 }
423
424
425
426
427
428
429
430 if (sibling->left != NULL && sibling->left->color == RED)
431 {
432
433
434
435
436
437
438
439
440
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
452
453
454
455
456
457
458
459
460
461
462
463
464
465 parent->left = rotate_left (sibling, sibling->right);
466
467 sibling->color = RED;
468 sibling = parent->left;
469 sibling->color = BLACK;
470
471
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
483
484
485
486
487
488
489
490 sibling->color = RED;
491
492 child = parent;
493 }
494 else
495 {
496
497
498
499
500
501
502
503
504 parent->color = BLACK;
505 sibling->color = RED;
506 return;
507 }
508 }
509 }
510 else
511 abort ();
512
513
514 parent = child->parent;
515
516 #if 0
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
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
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
561 rebalance_after_add (container, new_node, node);
562 }
563
564 container->count++;
565 return new_node;
566 }
567
568
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
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
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
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
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
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
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
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
656 NODE_T child = node->right;
657
658 if (child != NULL)
659 {
660 child->parent = parent;
661
662
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
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
681
682
683 NODE_T child = node->left;
684
685 child->parent = parent;
686
687
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
696 parent->right = child;
697 }
698 }
699 else
700 {
701
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
717
718
719
720
721
722
723
724
725
726
727 if (subst_parent != node)
728 {
729 if (child != NULL)
730 child->parent = subst_parent;
731 subst_parent->right = child;
732 }
733
734
735
736
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
751 parent->right = subst;
752
753 if (removed_color == BLACK)
754 {
755 if (child != NULL && child->color == RED)
756
757 child->color = BLACK;
758 else
759
760
761
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
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 }