Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/rbtree.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 /*
28 * Modified from the excellent code here:
29 * http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
30 * which has been placed in the public domain under the Creative Commons
31 * CC0 1.0 waiver (http://creativecommons.org/publicdomain/zero/1.0/).
32 */
33
34 /*!
35 * \file rbtree.c
36 * <pre>
37 *
38 * Basic functions for using red-black trees. These are "nearly" balanced
39 * sorted trees with ordering by key that allows insertion, lookup and
40 * deletion of key/value pairs in log(n) time.
41 *
42 * We use red-black trees to implement our version of:
43 * * a map: a function that maps keys to values (e.g., int64 --> int64).
44 * * a set: a collection that is sorted by unique keys (without
45 * associated values)
46 *
47 * There are 5 invariant properties of RB trees:
48 * (1) Each node is either red or black.
49 * (2) The root node is black.
50 * (3) All leaves are black and contain no data (null).
51 * (4) Every red node has two children and both are black. This is
52 * equivalent to requiring the parent of every red node to be black.
53 * (5) All paths from any given node to its leaf nodes contain the
54 * same number of black nodes.
55 *
56 * Interface to red-black tree
57 * L_RBTREE *l_rbtreeCreate()
58 * RB_TYPE *l_rbtreeLookup()
59 * void l_rbtreeInsert()
60 * void l_rbtreeDelete()
61 * void l_rbtreeDestroy()
62 * L_RBTREE_NODE *l_rbtreeGetFirst()
63 * L_RBTREE_NODE *l_rbtreeGetNext()
64 * L_RBTREE_NODE *l_rbtreeGetLast()
65 * L_RBTREE_NODE *l_rbtreeGetPrev()
66 * l_int32 l_rbtreeGetCount()
67 * void l_rbtreePrint()
68 *
69 * General comparison function
70 * static l_int32 compareKeys()
71 * </pre>
72 */
73
74 #ifdef HAVE_CONFIG_H
75 #include <config_auto.h>
76 #endif /* HAVE_CONFIG_H */
77
78 #include "allheaders.h"
79
80 /* The node color enum is only needed in the rbtree implementation */
81 enum {
82 L_RED_NODE = 1,
83 L_BLACK_NODE = 2
84 };
85
86 /* This makes it simpler to read the code */
87 typedef L_RBTREE_NODE node;
88
89 /* Lots of static helper functions */
90 static void destroy_helper(node *n);
91 static void count_helper(node *n, l_int32 *pcount);
92 static void print_tree_helper(FILE *fp, node *n, l_int32 keytype,
93 l_int32 indent);
94
95 static l_int32 compareKeys(l_int32 keytype, RB_TYPE left, RB_TYPE right);
96
97 static node *grandparent(node *n);
98 static node *sibling(node *n);
99 static node *uncle(node *n);
100 static l_int32 node_color(node *n);
101 static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color,
102 node *left, node *right);
103 static node *lookup_node(L_RBTREE *t, RB_TYPE key);
104 static void rotate_left(L_RBTREE *t, node *n);
105 static void rotate_right(L_RBTREE *t, node *n);
106 static void replace_node(L_RBTREE *t, node *oldn, node *newn);
107 static void insert_case1(L_RBTREE *t, node *n);
108 static void insert_case2(L_RBTREE *t, node *n);
109 static void insert_case3(L_RBTREE *t, node *n);
110 static void insert_case4(L_RBTREE *t, node *n);
111 static void insert_case5(L_RBTREE *t, node *n);
112 static node *maximum_node(node *root);
113 static void delete_case1(L_RBTREE *t, node *n);
114 static void delete_case2(L_RBTREE *t, node *n);
115 static void delete_case3(L_RBTREE *t, node *n);
116 static void delete_case4(L_RBTREE *t, node *n);
117 static void delete_case5(L_RBTREE *t, node *n);
118 static void delete_case6(L_RBTREE *t, node *n);
119 static void verify_properties(L_RBTREE *t);
120
121 #ifndef NO_CONSOLE_IO
122 #define VERIFY_RBTREE 0 /* only for debugging */
123 #endif /* ~NO_CONSOLE_IO */
124
125 /* ------------------------------------------------------------- *
126 * Interface to Red-black Tree *
127 * ------------------------------------------------------------- */
128 /*!
129 * \brief l_rbtreeCreate()
130 *
131 * \param[in] keytype defined by an enum for an RB_TYPE union
132 * \return rbtree container with empty ptr to the root
133 */
134 L_RBTREE *
135 l_rbtreeCreate(l_int32 keytype)
136 {
137 L_RBTREE *t;
138
139 if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
140 keytype != L_FLOAT_TYPE && keytype)
141 return (L_RBTREE *)ERROR_PTR("invalid keytype", __func__, NULL);
142
143 t = (L_RBTREE *)LEPT_CALLOC(1, sizeof(L_RBTREE));
144 t->keytype = keytype;
145 verify_properties(t);
146 return t;
147 }
148
149 /*!
150 * \brief l_rbtreeLookup()
151 *
152 * \param[in] t rbtree, including root node
153 * \param[in] key find a node with this key
154 * \return &value a pointer to a union, if the node exists; else NULL
155 */
156 RB_TYPE *
157 l_rbtreeLookup(L_RBTREE *t,
158 RB_TYPE key)
159 {
160 node *n;
161
162 if (!t)
163 return (RB_TYPE *)ERROR_PTR("tree is null\n", __func__, NULL);
164
165 n = lookup_node(t, key);
166 return n == NULL ? NULL : &n->value;
167 }
168
169 /*!
170 * \brief l_rbtreeInsert()
171 *
172 * \param[in] t rbtree, including root node
173 * \param[in] key insert a node with this key, if the key does not
174 * already exist in the tree
175 * \param[in] value typically an int, used for an index
176 * \return void
177 *
178 * <pre>
179 * Notes:
180 * (1) If a node with the key already exists, this just updates the value.
181 * </pre>
182 */
183 void
184 l_rbtreeInsert(L_RBTREE *t,
185 RB_TYPE key,
186 RB_TYPE value)
187 {
188 node *n, *inserted_node;
189
190 if (!t) {
191 L_ERROR("tree is null\n", __func__);
192 return;
193 }
194
195 inserted_node = new_node(key, value, L_RED_NODE, NULL, NULL);
196 if (t->root == NULL) {
197 t->root = inserted_node;
198 } else {
199 n = t->root;
200 while (1) {
201 int comp_result = compareKeys(t->keytype, key, n->key);
202 if (comp_result == 0) {
203 n->value = value;
204 LEPT_FREE(inserted_node);
205 return;
206 } else if (comp_result < 0) {
207 if (n->left == NULL) {
208 n->left = inserted_node;
209 break;
210 } else {
211 n = n->left;
212 }
213 } else { /* comp_result > 0 */
214 if (n->right == NULL) {
215 n->right = inserted_node;
216 break;
217 } else {
218 n = n->right;
219 }
220 }
221 }
222 inserted_node->parent = n;
223 }
224 insert_case1(t, inserted_node);
225 verify_properties(t);
226 }
227
228 /*!
229 * \brief l_rbtreeDelete()
230 *
231 * \param[in] t rbtree, including root node
232 * \param[in] key delete the node with this key
233 * \return void
234 */
235 void
236 l_rbtreeDelete(L_RBTREE *t,
237 RB_TYPE key)
238 {
239 node *n, *child;
240
241 if (!t) {
242 L_ERROR("tree is null\n", __func__);
243 return;
244 }
245
246 n = lookup_node(t, key);
247 if (n == NULL) return; /* Key not found, do nothing */
248 if (n->left != NULL && n->right != NULL) {
249 /* Copy key/value from predecessor and then delete it instead */
250 node *pred = maximum_node(n->left);
251 n->key = pred->key;
252 n->value = pred->value;
253 n = pred;
254 }
255
256 /* n->left == NULL || n->right == NULL */
257 child = n->right == NULL ? n->left : n->right;
258 if (node_color(n) == L_BLACK_NODE) {
259 n->color = node_color(child);
260 delete_case1(t, n);
261 }
262 replace_node(t, n, child);
263 if (n->parent == NULL && child != NULL) /* root should be black */
264 child->color = L_BLACK_NODE;
265 LEPT_FREE(n);
266
267 verify_properties(t);
268 }
269
270 /*!
271 * \brief l_rbtreeDestroy()
272 *
273 * \param[in] pt pointer to tree; will be wet to null before returning
274 * \return void
275 *
276 * <pre>
277 * Notes:
278 * (1) Destroys the tree and nulls the input tree ptr.
279 * </pre>
280 */
281 void
282 l_rbtreeDestroy(L_RBTREE **pt)
283 {
284 node *n;
285
286 if (!pt) return;
287 if (*pt == NULL) return;
288 n = (*pt)->root;
289 destroy_helper(n);
290 LEPT_FREE(*pt);
291 *pt = NULL;
292 }
293
294 /* postorder DFS */
295 static void
296 destroy_helper(node *n)
297 {
298 if (!n) return;
299 destroy_helper(n->left);
300 destroy_helper(n->right);
301 LEPT_FREE(n);
302 }
303
304 /*!
305 * \brief l_rbtreeGetFirst()
306 *
307 * \param[in] t rbtree, including root node
308 * \return first node, or NULL on error or if the tree is empty
309 *
310 * <pre>
311 * Notes:
312 * (1) This is the first node in an in-order traversal.
313 * </pre>
314 */
315 L_RBTREE_NODE *
316 l_rbtreeGetFirst(L_RBTREE *t)
317 {
318 node *n;
319
320 if (!t)
321 return (L_RBTREE_NODE *)ERROR_PTR("tree is null", __func__, NULL);
322 if (t->root == NULL) {
323 L_INFO("tree is empty\n", __func__);
324 return NULL;
325 }
326
327 /* Just go down the left side as far as possible */
328 n = t->root;
329 while (n && n->left)
330 n = n->left;
331 return n;
332 }
333
334 /*!
335 * \brief l_rbtreeGetNext()
336 *
337 * \param[in] n current node
338 * \return next node, or NULL if it's the last node
339 *
340 * <pre>
341 * Notes:
342 * (1) This finds the next node, in an in-order traversal, from
343 * the current node.
344 * (2) It is useful as an iterator for a map.
345 * (3) Call l_rbtreeGetFirst() to get the first node.
346 * </pre>
347 */
348 L_RBTREE_NODE *
349 l_rbtreeGetNext(L_RBTREE_NODE *n)
350 {
351 if (!n)
352 return (L_RBTREE_NODE *)ERROR_PTR("n not defined", __func__, NULL);
353
354 /* If there is a right child, go to it, and then go left all the
355 * way to the end. Otherwise go up to the parent; continue upward
356 * as long as you're on the right branch, but stop at the parent
357 * when you hit it from the left branch. */
358 if (n->right) {
359 n = n->right;
360 while (n->left)
361 n = n->left;
362 return n;
363 } else {
364 while (n->parent && n->parent->right == n)
365 n = n->parent;
366 return n->parent;
367 }
368 }
369
370 /*!
371 * \brief l_rbtreeGetLast()
372 *
373 * \param[in] t rbtree, including root node
374 * \return last node, or NULL on error or if the tree is empty
375 *
376 * <pre>
377 * Notes:
378 * (1) This is the last node in an in-order traversal.
379 * </pre>
380 */
381 L_RBTREE_NODE *
382 l_rbtreeGetLast(L_RBTREE *t)
383 {
384 node *n;
385
386 if (!t)
387 return (L_RBTREE_NODE *)ERROR_PTR("tree is null", __func__, NULL);
388 if (t->root == NULL) {
389 L_INFO("tree is empty\n", __func__);
390 return NULL;
391 }
392
393 /* Just go down the right side as far as possible */
394 n = t->root;
395 while (n && n->right)
396 n = n->right;
397 return n;
398 }
399
400 /*!
401 * \brief l_rbtreeGetPrev()
402 *
403 * \param[in] n current node
404 * \return next node, or NULL if it's the first node
405 *
406 * <pre>
407 * Notes:
408 * (1) This finds the previous node, in an in-order traversal, from
409 * the current node.
410 * (2) It is useful as an iterator for a map.
411 * (3) Call l_rbtreeGetLast() to get the last node.
412 * </pre>
413 */
414 L_RBTREE_NODE *
415 l_rbtreeGetPrev(L_RBTREE_NODE *n)
416 {
417 if (!n)
418 return (L_RBTREE_NODE *)ERROR_PTR("n not defined", __func__, NULL);
419
420 /* If there is a left child, go to it, and then go right all the
421 * way to the end. Otherwise go up to the parent; continue upward
422 * as long as you're on the left branch, but stop at the parent
423 * when you hit it from the right branch. */
424 if (n->left) {
425 n = n->left;
426 while (n->right)
427 n = n->right;
428 return n;
429 } else {
430 while (n->parent && n->parent->left == n)
431 n = n->parent;
432 return n->parent;
433 }
434 }
435
436 /*!
437 * \brief l_rbtreeGetCount()
438 *
439 * \param[in] t rbtree
440 * \return count the number of nodes in the tree, or 0 on error
441 */
442 l_int32
443 l_rbtreeGetCount(L_RBTREE *t)
444 {
445 l_int32 count = 0;
446 node *n;
447
448 if (!t) return 0;
449 n = t->root;
450 count_helper(n, &count);
451 return count;
452 }
453
454 /* preorder DFS */
455 static void
456 count_helper(node *n, l_int32 *pcount)
457 {
458 if (n)
459 (*pcount)++;
460 else
461 return;
462
463 count_helper(n->left, pcount);
464 count_helper(n->right, pcount);
465 }
466
467
468 /*!
469 * \brief l_rbtreePrint()
470 *
471 * \param[in] fp file stream
472 * \param[in] t rbtree
473 * \return void
474 */
475 void
476 l_rbtreePrint(FILE *fp,
477 L_RBTREE *t)
478 {
479 if (!fp) {
480 L_ERROR("stream not defined\n", __func__);
481 return;
482 }
483 if (!t) {
484 L_ERROR("tree not defined\n", __func__);
485 return;
486 }
487
488 print_tree_helper(fp, t->root, t->keytype, 0);
489 fprintf(fp, "\n");
490 }
491
492 #define INDENT_STEP 4
493
494 static void
495 print_tree_helper(FILE *fp,
496 node *n,
497 l_int32 keytype,
498 l_int32 indent)
499 {
500 l_int32 i;
501
502 if (n == NULL) {
503 fprintf(fp, "<empty tree>");
504 return;
505 }
506 if (n->right != NULL) {
507 print_tree_helper(fp, n->right, keytype, indent + INDENT_STEP);
508 }
509 for (i = 0; i < indent; i++)
510 fprintf(fp, " ");
511 if (n->color == L_BLACK_NODE) {
512 if (keytype == L_INT_TYPE)
513 fprintf(fp, "%lld\n", n->key.itype);
514 else if (keytype == L_UINT_TYPE)
515 fprintf(fp, "%llx\n", n->key.utype);
516 else if (keytype == L_FLOAT_TYPE)
517 fprintf(fp, "%f\n", n->key.ftype);
518 } else {
519 if (keytype == L_INT_TYPE)
520 fprintf(fp, "<%lld>\n", n->key.itype);
521 else if (keytype == L_UINT_TYPE)
522 fprintf(fp, "<%llx>\n", n->key.utype);
523 else if (keytype == L_FLOAT_TYPE)
524 fprintf(fp, "<%f>\n", n->key.ftype);
525 }
526 if (n->left != NULL) {
527 print_tree_helper(fp, n->left, keytype, indent + INDENT_STEP);
528 }
529 }
530
531
532 /* ------------------------------------------------------------- *
533 * Static key comparison function *
534 * ------------------------------------------------------------- */
535 static l_int32
536 compareKeys(l_int32 keytype,
537 RB_TYPE left,
538 RB_TYPE right)
539 {
540 if (keytype == L_INT_TYPE) {
541 if (left.itype < right.itype)
542 return -1;
543 else if (left.itype > right.itype)
544 return 1;
545 else { /* equality */
546 return 0;
547 }
548 } else if (keytype == L_UINT_TYPE) {
549 if (left.utype < right.utype)
550 return -1;
551 else if (left.utype > right.utype)
552 return 1;
553 else { /* equality */
554 return 0;
555 }
556 } else if (keytype == L_FLOAT_TYPE) {
557 if (left.ftype < right.ftype)
558 return -1;
559 else if (left.ftype > right.ftype)
560 return 1;
561 else { /* equality */
562 return 0;
563 }
564 } else {
565 L_ERROR("unknown keytype %d\n", __func__, keytype);
566 return 0;
567 }
568 }
569
570
571 /* ------------------------------------------------------------- *
572 * Static red-black tree helpers *
573 * ------------------------------------------------------------- */
574 static node *grandparent(node *n) {
575 if (!n || !n->parent || !n->parent->parent) {
576 L_ERROR("root and child of root have no grandparent\n", "grandparent");
577 return NULL;
578 }
579 return n->parent->parent;
580 }
581
582 static node *sibling(node *n) {
583 if (!n || !n->parent) {
584 L_ERROR("root has no sibling\n", "sibling");
585 return NULL;
586 }
587 if (n == n->parent->left)
588 return n->parent->right;
589 else
590 return n->parent->left;
591 }
592
593 static node *uncle(node *n) {
594 if (!n || !n->parent || !n->parent->parent) {
595 L_ERROR("root and child of root have no uncle\n", "uncle");
596 return NULL;
597 }
598 return sibling(n->parent);
599 }
600
601 static l_int32 node_color(node *n) {
602 return n == NULL ? L_BLACK_NODE : n->color;
603 }
604
605
606 static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color,
607 node *left, node *right) {
608 node *result = (node *)LEPT_CALLOC(1, sizeof(node));
609 result->key = key;
610 result->value = value;
611 result->color = node_color;
612 result->left = left;
613 result->right = right;
614 if (left != NULL) left->parent = result;
615 if (right != NULL) right->parent = result;
616 result->parent = NULL;
617 return result;
618 }
619
620 static node *lookup_node(L_RBTREE *t, RB_TYPE key) {
621 node *n = t->root;
622 while (n != NULL) {
623 int comp_result = compareKeys(t->keytype, key, n->key);
624 if (comp_result == 0) {
625 return n;
626 } else if (comp_result < 0) {
627 n = n->left;
628 } else { /* comp_result > 0 */
629 n = n->right;
630 }
631 }
632 return n;
633 }
634
635 static void rotate_left(L_RBTREE *t, node *n) {
636 node *r = n->right;
637 replace_node(t, n, r);
638 n->right = r->left;
639 if (r->left != NULL) {
640 r->left->parent = n;
641 }
642 r->left = n;
643 n->parent = r;
644 }
645
646 static void rotate_right(L_RBTREE *t, node *n) {
647 node *L = n->left;
648 replace_node(t, n, L);
649 n->left = L->right;
650 if (L->right != NULL) {
651 L->right->parent = n;
652 }
653 L->right = n;
654 n->parent = L;
655 }
656
657 static void replace_node(L_RBTREE *t, node *oldn, node *newn) {
658 if (oldn->parent == NULL) {
659 t->root = newn;
660 } else {
661 if (oldn == oldn->parent->left)
662 oldn->parent->left = newn;
663 else
664 oldn->parent->right = newn;
665 }
666 if (newn != NULL) {
667 newn->parent = oldn->parent;
668 }
669 }
670
671 static void insert_case1(L_RBTREE *t, node *n) {
672 if (n->parent == NULL)
673 n->color = L_BLACK_NODE;
674 else
675 insert_case2(t, n);
676 }
677
678 static void insert_case2(L_RBTREE *t, node *n) {
679 if (node_color(n->parent) == L_BLACK_NODE)
680 return; /* Tree is still valid */
681 else
682 insert_case3(t, n);
683 }
684
685 static void insert_case3(L_RBTREE *t, node *n) {
686 if (node_color(uncle(n)) == L_RED_NODE) {
687 n->parent->color = L_BLACK_NODE;
688 uncle(n)->color = L_BLACK_NODE;
689 grandparent(n)->color = L_RED_NODE;
690 insert_case1(t, grandparent(n));
691 } else {
692 insert_case4(t, n);
693 }
694 }
695
696 static void insert_case4(L_RBTREE *t, node *n) {
697 if (n == n->parent->right && n->parent == grandparent(n)->left) {
698 rotate_left(t, n->parent);
699 n = n->left;
700 } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
701 rotate_right(t, n->parent);
702 n = n->right;
703 }
704 insert_case5(t, n);
705 }
706
707 static void insert_case5(L_RBTREE *t, node *n) {
708 n->parent->color = L_BLACK_NODE;
709 grandparent(n)->color = L_RED_NODE;
710 if (n == n->parent->left && n->parent == grandparent(n)->left) {
711 rotate_right(t, grandparent(n));
712 } else if (n == n->parent->right && n->parent == grandparent(n)->right) {
713 rotate_left(t, grandparent(n));
714 } else {
715 L_ERROR("identity confusion\n", "insert_case5");
716 }
717 }
718
719 static node *maximum_node(node *n) {
720 if (!n) {
721 L_ERROR("n not defined\n", "maximum_node");
722 return NULL;
723 }
724 while (n->right != NULL) {
725 n = n->right;
726 }
727 return n;
728 }
729
730 static void delete_case1(L_RBTREE *t, node *n) {
731 if (n->parent == NULL)
732 return;
733 else
734 delete_case2(t, n);
735 }
736
737 static void delete_case2(L_RBTREE *t, node *n) {
738 if (node_color(sibling(n)) == L_RED_NODE) {
739 n->parent->color = L_RED_NODE;
740 sibling(n)->color = L_BLACK_NODE;
741 if (n == n->parent->left)
742 rotate_left(t, n->parent);
743 else
744 rotate_right(t, n->parent);
745 }
746 delete_case3(t, n);
747 }
748
749 static void delete_case3(L_RBTREE *t, node *n) {
750 if (node_color(n->parent) == L_BLACK_NODE &&
751 node_color(sibling(n)) == L_BLACK_NODE &&
752 node_color(sibling(n)->left) == L_BLACK_NODE &&
753 node_color(sibling(n)->right) == L_BLACK_NODE) {
754 sibling(n)->color = L_RED_NODE;
755 delete_case1(t, n->parent);
756 } else {
757 delete_case4(t, n);
758 }
759 }
760
761 static void delete_case4(L_RBTREE *t, node *n) {
762 if (node_color(n->parent) == L_RED_NODE &&
763 node_color(sibling(n)) == L_BLACK_NODE &&
764 node_color(sibling(n)->left) == L_BLACK_NODE &&
765 node_color(sibling(n)->right) == L_BLACK_NODE) {
766 sibling(n)->color = L_RED_NODE;
767 n->parent->color = L_BLACK_NODE;
768 } else {
769 delete_case5(t, n);
770 }
771 }
772
773 static void delete_case5(L_RBTREE *t, node *n) {
774 if (n == n->parent->left &&
775 node_color(sibling(n)) == L_BLACK_NODE &&
776 node_color(sibling(n)->left) == L_RED_NODE &&
777 node_color(sibling(n)->right) == L_BLACK_NODE) {
778 sibling(n)->color = L_RED_NODE;
779 sibling(n)->left->color = L_BLACK_NODE;
780 rotate_right(t, sibling(n));
781 } else if (n == n->parent->right &&
782 node_color(sibling(n)) == L_BLACK_NODE &&
783 node_color(sibling(n)->right) == L_RED_NODE &&
784 node_color(sibling(n)->left) == L_BLACK_NODE) {
785 sibling(n)->color = L_RED_NODE;
786 sibling(n)->right->color = L_BLACK_NODE;
787 rotate_left(t, sibling(n));
788 }
789 delete_case6(t, n);
790 }
791
792 static void delete_case6(L_RBTREE *t, node *n) {
793 sibling(n)->color = node_color(n->parent);
794 n->parent->color = L_BLACK_NODE;
795 if (n == n->parent->left) {
796 if (node_color(sibling(n)->right) != L_RED_NODE) {
797 L_ERROR("right sibling is not RED", "delete_case6");
798 return;
799 }
800 sibling(n)->right->color = L_BLACK_NODE;
801 rotate_left(t, n->parent);
802 } else {
803 if (node_color(sibling(n)->left) != L_RED_NODE) {
804 L_ERROR("left sibling is not RED", "delete_case6");
805 return;
806 }
807 sibling(n)->left->color = L_BLACK_NODE;
808 rotate_right(t, n->parent);
809 }
810 }
811
812
813 /* ------------------------------------------------------------- *
814 * Debugging: verify if tree is valid *
815 * ------------------------------------------------------------- */
816 #if VERIFY_RBTREE
817 static void verify_property_1(node *root);
818 static void verify_property_2(node *root);
819 static void verify_property_4(node *root);
820 static void verify_property_5(node *root);
821 static void verify_property_5_helper(node *n, int black_count,
822 int* black_count_path);
823 #endif
824
825 static void verify_properties(L_RBTREE *t) {
826 #if VERIFY_RBTREE
827 verify_property_1(t->root);
828 verify_property_2(t->root);
829 /* Property 3 is implicit */
830 verify_property_4(t->root);
831 verify_property_5(t->root);
832 #endif
833 }
834
835 #if VERIFY_RBTREE
836 static void verify_property_1(node *n) {
837 if (node_color(n) != L_RED_NODE && node_color(n) != L_BLACK_NODE) {
838 L_ERROR("color neither RED nor BLACK\n", "verify_property_1");
839 return;
840 }
841 if (n == NULL) return;
842 verify_property_1(n->left);
843 verify_property_1(n->right);
844 }
845
846 static void verify_property_2(node *root) {
847 if (node_color(root) != L_BLACK_NODE)
848 L_ERROR("root is not black!\n", "verify_property_2");
849 }
850
851 static void verify_property_4(node *n) {
852 if (node_color(n) == L_RED_NODE) {
853 if (node_color(n->left) != L_BLACK_NODE ||
854 node_color(n->right) != L_BLACK_NODE ||
855 node_color(n->parent) != L_BLACK_NODE) {
856 L_ERROR("children & parent not all BLACK", "verify_property_4");
857 return;
858 }
859 }
860 if (n == NULL) return;
861 verify_property_4(n->left);
862 verify_property_4(n->right);
863 }
864
865 static void verify_property_5(node *root) {
866 int black_count_path = -1;
867 verify_property_5_helper(root, 0, &black_count_path);
868 }
869
870 static void verify_property_5_helper(node *n, int black_count,
871 int* path_black_count) {
872 if (node_color(n) == L_BLACK_NODE) {
873 black_count++;
874 }
875 if (n == NULL) {
876 if (*path_black_count == -1) {
877 *path_black_count = black_count;
878 } else if (*path_black_count != black_count) {
879 L_ERROR("incorrect black count", "verify_property_5_helper");
880 }
881 return;
882 }
883 verify_property_5_helper(n->left, black_count, path_black_count);
884 verify_property_5_helper(n->right, black_count, path_black_count);
885 }
886 #endif