Coverage Report

Created: 2025-06-13 07:15

/src/leptonica/src/rbtree.c
Line
Count
Source (jump to first uncovered line)
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
0
{
137
0
L_RBTREE  *t;
138
139
0
    if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
140
0
        keytype != L_FLOAT_TYPE && keytype)
141
0
        return (L_RBTREE *)ERROR_PTR("invalid keytype", __func__, NULL);
142
143
0
    t = (L_RBTREE *)LEPT_CALLOC(1, sizeof(L_RBTREE));
144
0
    t->keytype = keytype;
145
0
    verify_properties(t);
146
0
    return t;
147
0
}
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
0
{
160
0
node  *n;
161
162
0
    if (!t)
163
0
        return (RB_TYPE *)ERROR_PTR("tree is null\n", __func__, NULL);
164
165
0
    n = lookup_node(t, key);
166
0
    return n == NULL ? NULL : &n->value;
167
0
}
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
0
{
188
0
node  *n, *inserted_node;
189
190
0
    if (!t) {
191
0
        L_ERROR("tree is null\n", __func__);
192
0
        return;
193
0
    }
194
195
0
    inserted_node = new_node(key, value, L_RED_NODE, NULL, NULL);
196
0
    if (t->root == NULL) {
197
0
        t->root = inserted_node;
198
0
    } else {
199
0
        n = t->root;
200
0
        while (1) {
201
0
            int comp_result = compareKeys(t->keytype, key, n->key);
202
0
            if (comp_result == 0) {
203
0
                n->value = value;
204
0
                LEPT_FREE(inserted_node);
205
0
                return;
206
0
            } else if (comp_result < 0) {
207
0
                if (n->left == NULL) {
208
0
                    n->left = inserted_node;
209
0
                    break;
210
0
                } else {
211
0
                    n = n->left;
212
0
                }
213
0
            } else {  /* comp_result > 0 */
214
0
                if (n->right == NULL) {
215
0
                    n->right = inserted_node;
216
0
                    break;
217
0
                } else {
218
0
                    n = n->right;
219
0
                }
220
0
            }
221
0
        }
222
0
        inserted_node->parent = n;
223
0
    }
224
0
    insert_case1(t, inserted_node);
225
0
    verify_properties(t);
226
0
}
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
0
{
239
0
node  *n, *child;
240
241
0
    if (!t) {
242
0
        L_ERROR("tree is null\n", __func__);
243
0
        return;
244
0
    }
245
246
0
    n = lookup_node(t, key);
247
0
    if (n == NULL) return;  /* Key not found, do nothing */
248
0
    if (n->left != NULL && n->right != NULL) {
249
            /* Copy key/value from predecessor and then delete it instead */
250
0
        node *pred = maximum_node(n->left);
251
0
        n->key   = pred->key;
252
0
        n->value = pred->value;
253
0
        n = pred;
254
0
    }
255
256
        /* n->left == NULL || n->right == NULL */
257
0
    child = n->right == NULL ? n->left  : n->right;
258
0
    if (node_color(n) == L_BLACK_NODE) {
259
0
        n->color = node_color(child);
260
0
        delete_case1(t, n);
261
0
    }
262
0
    replace_node(t, n, child);
263
0
    if (n->parent == NULL && child != NULL)  /* root should be black */
264
0
        child->color = L_BLACK_NODE;
265
0
    LEPT_FREE(n);
266
267
0
    verify_properties(t);
268
0
}
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
0
{
284
0
node    *n;
285
286
0
    if (!pt) return;
287
0
    if (*pt == NULL) return;
288
0
    n = (*pt)->root;
289
0
    destroy_helper(n);
290
0
    LEPT_FREE(*pt);
291
0
    *pt = NULL;
292
0
}
293
294
    /* postorder DFS */
295
static void
296
destroy_helper(node  *n)
297
0
{
298
0
    if (!n) return;
299
0
    destroy_helper(n->left);
300
0
    destroy_helper(n->right);
301
0
    LEPT_FREE(n);
302
0
}
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
0
{
318
0
node  *n;
319
320
0
    if (!t)
321
0
        return (L_RBTREE_NODE *)ERROR_PTR("tree is null", __func__, NULL);
322
0
    if (t->root == NULL) {
323
0
        L_INFO("tree is empty\n", __func__);
324
0
        return NULL;
325
0
    }
326
327
        /* Just go down the left side as far as possible */
328
0
    n = t->root;
329
0
    while (n && n->left)
330
0
        n = n->left;
331
0
    return n;
332
0
}
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
0
{
351
0
    if (!n)
352
0
        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
0
    if (n->right) {
359
0
        n = n->right;
360
0
        while (n->left)
361
0
            n = n->left;
362
0
        return n;
363
0
    } else {
364
0
        while (n->parent && n->parent->right == n)
365
0
            n = n->parent;
366
0
        return n->parent;
367
0
    }
368
0
}
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
0
{
384
0
node  *n;
385
386
0
    if (!t)
387
0
        return (L_RBTREE_NODE *)ERROR_PTR("tree is null", __func__, NULL);
388
0
    if (t->root == NULL) {
389
0
        L_INFO("tree is empty\n", __func__);
390
0
        return NULL;
391
0
    }
392
393
        /* Just go down the right side as far as possible */
394
0
    n = t->root;
395
0
    while (n && n->right)
396
0
        n = n->right;
397
0
    return n;
398
0
}
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
0
{
417
0
    if (!n)
418
0
        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
0
    if (n->left) {
425
0
        n = n->left;
426
0
        while (n->right)
427
0
            n = n->right;
428
0
        return n;
429
0
    } else {
430
0
        while (n->parent && n->parent->left == n)
431
0
            n = n->parent;
432
0
        return n->parent;
433
0
    }
434
0
}
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
0
{
445
0
l_int32  count = 0;
446
0
node    *n;
447
448
0
    if (!t) return 0;
449
0
    n = t->root;
450
0
    count_helper(n, &count);
451
0
    return count;
452
0
}
453
454
    /* preorder DFS */
455
static void
456
count_helper(node  *n, l_int32  *pcount)
457
0
{
458
0
    if (n)
459
0
        (*pcount)++;
460
0
    else
461
0
        return;
462
463
0
    count_helper(n->left, pcount);
464
0
    count_helper(n->right, pcount);
465
0
}
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
0
{
479
0
    if (!fp) {
480
0
        L_ERROR("stream not defined\n", __func__);
481
0
        return;
482
0
    }
483
0
    if (!t) {
484
0
        L_ERROR("tree not defined\n", __func__);
485
0
        return;
486
0
    }
487
488
0
    print_tree_helper(fp, t->root, t->keytype, 0);
489
0
    fprintf(fp, "\n");
490
0
}
491
492
0
#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
0
{
500
0
l_int32  i;
501
502
0
    if (n == NULL) {
503
0
        fprintf(fp, "<empty tree>");
504
0
        return;
505
0
    }
506
0
    if (n->right != NULL) {
507
0
        print_tree_helper(fp, n->right, keytype, indent + INDENT_STEP);
508
0
    }
509
0
    for (i = 0; i < indent; i++)
510
0
        fprintf(fp, " ");
511
0
    if (n->color == L_BLACK_NODE) {
512
0
        if (keytype == L_INT_TYPE)
513
0
            fprintf(fp, "%lld\n", n->key.itype);
514
0
        else if (keytype == L_UINT_TYPE)
515
0
            fprintf(fp, "%llx\n", n->key.utype);
516
0
        else if (keytype == L_FLOAT_TYPE)
517
0
            fprintf(fp, "%f\n", n->key.ftype);
518
0
    } else {
519
0
        if (keytype == L_INT_TYPE)
520
0
            fprintf(fp, "<%lld>\n", n->key.itype);
521
0
        else if (keytype == L_UINT_TYPE)
522
0
            fprintf(fp, "<%llx>\n", n->key.utype);
523
0
        else if (keytype == L_FLOAT_TYPE)
524
0
            fprintf(fp, "<%f>\n", n->key.ftype);
525
0
    }
526
0
    if (n->left != NULL) {
527
0
        print_tree_helper(fp, n->left, keytype, indent + INDENT_STEP);
528
0
    }
529
0
}
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
0
{
540
0
    if (keytype == L_INT_TYPE) {
541
0
        if (left.itype < right.itype)
542
0
            return -1;
543
0
        else if (left.itype > right.itype)
544
0
            return 1;
545
0
        else {  /* equality */
546
0
            return 0;
547
0
        }
548
0
    } else if (keytype == L_UINT_TYPE) {
549
0
        if (left.utype < right.utype)
550
0
            return -1;
551
0
        else if (left.utype > right.utype)
552
0
            return 1;
553
0
        else {  /* equality */
554
0
            return 0;
555
0
        }
556
0
    } else if (keytype == L_FLOAT_TYPE) {
557
0
        if (left.ftype < right.ftype)
558
0
            return -1;
559
0
        else if (left.ftype > right.ftype)
560
0
            return 1;
561
0
        else {  /* equality */
562
0
            return 0;
563
0
        }
564
0
    } else {
565
0
        L_ERROR("unknown keytype %d\n", __func__, keytype);
566
0
        return 0;
567
0
    }
568
0
}
569
570
571
/* ------------------------------------------------------------- *
572
 *                  Static red-black tree helpers                *
573
 * ------------------------------------------------------------- */
574
0
static node *grandparent(node *n) {
575
0
    if (!n || !n->parent || !n->parent->parent) {
576
0
        L_ERROR("root and child of root have no grandparent\n", "grandparent");
577
0
        return NULL;
578
0
    }
579
0
    return n->parent->parent;
580
0
}
581
582
0
static node *sibling(node *n) {
583
0
    if (!n || !n->parent) {
584
0
        L_ERROR("root has no sibling\n", "sibling");
585
0
        return NULL;
586
0
    }
587
0
    if (n == n->parent->left)
588
0
        return n->parent->right;
589
0
    else
590
0
        return n->parent->left;
591
0
}
592
593
0
static node *uncle(node *n) {
594
0
    if (!n || !n->parent || !n->parent->parent) {
595
0
        L_ERROR("root and child of root have no uncle\n", "uncle");
596
0
        return NULL;
597
0
    }
598
0
    return sibling(n->parent);
599
0
}
600
601
0
static l_int32 node_color(node *n) {
602
0
    return n == NULL ? L_BLACK_NODE : n->color;
603
0
}
604
605
606
static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color,
607
0
                      node *left, node *right) {
608
0
    node *result = (node *)LEPT_CALLOC(1, sizeof(node));
609
0
    result->key = key;
610
0
    result->value = value;
611
0
    result->color = node_color;
612
0
    result->left = left;
613
0
    result->right = right;
614
0
    if (left != NULL) left->parent = result;
615
0
    if (right != NULL) right->parent = result;
616
0
    result->parent = NULL;
617
0
    return result;
618
0
}
619
620
0
static node *lookup_node(L_RBTREE *t, RB_TYPE key) {
621
0
    node *n = t->root;
622
0
    while (n != NULL) {
623
0
        int comp_result = compareKeys(t->keytype, key, n->key);
624
0
        if (comp_result == 0) {
625
0
            return n;
626
0
        } else if (comp_result < 0) {
627
0
            n = n->left;
628
0
        } else {  /* comp_result > 0 */
629
0
            n = n->right;
630
0
        }
631
0
    }
632
0
    return n;
633
0
}
634
635
0
static void rotate_left(L_RBTREE *t, node *n) {
636
0
    node *r = n->right;
637
0
    replace_node(t, n, r);
638
0
    n->right = r->left;
639
0
    if (r->left != NULL) {
640
0
        r->left->parent = n;
641
0
    }
642
0
    r->left = n;
643
0
    n->parent = r;
644
0
}
645
646
0
static void rotate_right(L_RBTREE *t, node *n) {
647
0
    node *L = n->left;
648
0
    replace_node(t, n, L);
649
0
    n->left = L->right;
650
0
    if (L->right != NULL) {
651
0
        L->right->parent = n;
652
0
    }
653
0
    L->right = n;
654
0
    n->parent = L;
655
0
}
656
657
0
static void replace_node(L_RBTREE *t, node *oldn, node *newn) {
658
0
    if (oldn->parent == NULL) {
659
0
        t->root = newn;
660
0
    } else {
661
0
        if (oldn == oldn->parent->left)
662
0
            oldn->parent->left = newn;
663
0
        else
664
0
            oldn->parent->right = newn;
665
0
    }
666
0
    if (newn != NULL) {
667
0
        newn->parent = oldn->parent;
668
0
    }
669
0
}
670
671
0
static void insert_case1(L_RBTREE *t, node *n) {
672
0
    if (n->parent == NULL)
673
0
        n->color = L_BLACK_NODE;
674
0
    else
675
0
        insert_case2(t, n);
676
0
}
677
678
0
static void insert_case2(L_RBTREE *t, node *n) {
679
0
    if (node_color(n->parent) == L_BLACK_NODE)
680
0
        return; /* Tree is still valid */
681
0
    else
682
0
        insert_case3(t, n);
683
0
}
684
685
0
static void insert_case3(L_RBTREE *t, node *n) {
686
0
    if (node_color(uncle(n)) == L_RED_NODE) {
687
0
        n->parent->color = L_BLACK_NODE;
688
0
        uncle(n)->color = L_BLACK_NODE;
689
0
        grandparent(n)->color = L_RED_NODE;
690
0
        insert_case1(t, grandparent(n));
691
0
    } else {
692
0
        insert_case4(t, n);
693
0
    }
694
0
}
695
696
0
static void insert_case4(L_RBTREE *t, node *n) {
697
0
    if (n == n->parent->right && n->parent == grandparent(n)->left) {
698
0
        rotate_left(t, n->parent);
699
0
        n = n->left;
700
0
    } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
701
0
        rotate_right(t, n->parent);
702
0
        n = n->right;
703
0
    }
704
0
    insert_case5(t, n);
705
0
}
706
707
0
static void insert_case5(L_RBTREE *t, node *n) {
708
0
    n->parent->color = L_BLACK_NODE;
709
0
    grandparent(n)->color = L_RED_NODE;
710
0
    if (n == n->parent->left && n->parent == grandparent(n)->left) {
711
0
        rotate_right(t, grandparent(n));
712
0
    } else if (n == n->parent->right && n->parent == grandparent(n)->right) {
713
0
        rotate_left(t, grandparent(n));
714
0
    } else {
715
0
        L_ERROR("identity confusion\n", "insert_case5");
716
0
    }
717
0
}
718
719
0
static node *maximum_node(node *n) {
720
0
    if (!n) {
721
0
        L_ERROR("n not defined\n", "maximum_node");
722
0
        return NULL;
723
0
    }
724
0
    while (n->right != NULL) {
725
0
        n = n->right;
726
0
    }
727
0
    return n;
728
0
}
729
730
0
static void delete_case1(L_RBTREE *t, node *n) {
731
0
    if (n->parent == NULL)
732
0
        return;
733
0
    else
734
0
        delete_case2(t, n);
735
0
}
736
737
0
static void delete_case2(L_RBTREE *t, node *n) {
738
0
    if (node_color(sibling(n)) == L_RED_NODE) {
739
0
        n->parent->color = L_RED_NODE;
740
0
        sibling(n)->color = L_BLACK_NODE;
741
0
        if (n == n->parent->left)
742
0
            rotate_left(t, n->parent);
743
0
        else
744
0
            rotate_right(t, n->parent);
745
0
    }
746
0
    delete_case3(t, n);
747
0
}
748
749
0
static void delete_case3(L_RBTREE *t, node *n) {
750
0
    if (node_color(n->parent) == L_BLACK_NODE &&
751
0
        node_color(sibling(n)) == L_BLACK_NODE &&
752
0
        node_color(sibling(n)->left) == L_BLACK_NODE &&
753
0
        node_color(sibling(n)->right) == L_BLACK_NODE) {
754
0
        sibling(n)->color = L_RED_NODE;
755
0
        delete_case1(t, n->parent);
756
0
    } else {
757
0
        delete_case4(t, n);
758
0
    }
759
0
}
760
761
0
static void delete_case4(L_RBTREE *t, node *n) {
762
0
    if (node_color(n->parent) == L_RED_NODE &&
763
0
        node_color(sibling(n)) == L_BLACK_NODE &&
764
0
        node_color(sibling(n)->left) == L_BLACK_NODE &&
765
0
        node_color(sibling(n)->right) == L_BLACK_NODE) {
766
0
        sibling(n)->color = L_RED_NODE;
767
0
        n->parent->color = L_BLACK_NODE;
768
0
    } else {
769
0
        delete_case5(t, n);
770
0
    }
771
0
}
772
773
0
static void delete_case5(L_RBTREE *t, node *n) {
774
0
    if (n == n->parent->left &&
775
0
        node_color(sibling(n)) == L_BLACK_NODE &&
776
0
        node_color(sibling(n)->left) == L_RED_NODE &&
777
0
        node_color(sibling(n)->right) == L_BLACK_NODE) {
778
0
        sibling(n)->color = L_RED_NODE;
779
0
        sibling(n)->left->color = L_BLACK_NODE;
780
0
        rotate_right(t, sibling(n));
781
0
    } else if (n == n->parent->right &&
782
0
               node_color(sibling(n)) == L_BLACK_NODE &&
783
0
               node_color(sibling(n)->right) == L_RED_NODE &&
784
0
               node_color(sibling(n)->left) == L_BLACK_NODE) {
785
0
        sibling(n)->color = L_RED_NODE;
786
0
        sibling(n)->right->color = L_BLACK_NODE;
787
0
        rotate_left(t, sibling(n));
788
0
    }
789
0
    delete_case6(t, n);
790
0
}
791
792
0
static void delete_case6(L_RBTREE *t, node *n) {
793
0
    sibling(n)->color = node_color(n->parent);
794
0
    n->parent->color = L_BLACK_NODE;
795
0
    if (n == n->parent->left) {
796
0
        if (node_color(sibling(n)->right) != L_RED_NODE) {
797
0
            L_ERROR("right sibling is not RED", "delete_case6");
798
0
            return;
799
0
        }
800
0
        sibling(n)->right->color = L_BLACK_NODE;
801
0
        rotate_left(t, n->parent);
802
0
    } else {
803
0
        if (node_color(sibling(n)->left) != L_RED_NODE) {
804
0
            L_ERROR("left sibling is not RED", "delete_case6");
805
0
            return;
806
0
        }
807
0
        sibling(n)->left->color = L_BLACK_NODE;
808
0
        rotate_right(t, n->parent);
809
0
    }
810
0
}
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
0
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
0
}
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