File Coverage

rbtree.c
Criterion Covered Total %
statement 354 389 91.0
branch 227 288 78.8
condition n/a
subroutine n/a
pod n/a
total 581 677 85.8


line stmt bran cond sub pod time code
1             /* Auto-Generated by RBGen version 0.1 on 2022-05-04T14:58:52Z */
2              
3             /*
4             Credits:
5              
6             Intrest in red/black trees was inspired by Dr. John Franco, and his animated
7             red/black tree java applet.
8             http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html
9              
10             The node insertion code was written in a joint effort with Anthony Deeter,
11             as a class project.
12              
13             The red/black deletion algorithm was derived from the deletion patterns in
14             "Fundamentals of Sequential and Parallel Algorithms",
15             by Dr. Kenneth A. Berman and Dr. Jerome L. Paul
16              
17             I also got the sentinel node idea from this book.
18              
19             */
20              
21             #include "/root/.cpan/build/Tree-RB-XS-0.07-0/rbtree.h"
22             #include
23              
24             #define IS_BLACK(node) (!(node)->color)
25             #define IS_RED(node) ((node)->color)
26             #define NODE_IS_IN_TREE(node) ((node)->count != 0)
27             #define SET_COLOR_BLACK(node) ((node)->color= 0)
28             #define SET_COLOR_RED(node) ((node)->color= 1)
29             #define COPY_COLOR(dest,src) ((dest)->color= (src)->color)
30             #define GET_COUNT(node) ((node)->count)
31             #define SET_COUNT(node,val) ((node)->count= (val))
32             #define ADD_COUNT(node,val) ((node)->count+= (val))
33             #define IS_SENTINEL(node) (!(bool) (node)->count)
34             #define IS_ROOTSENTINEL(node) (!(bool) (node)->parent)
35             #define NOT_SENTINEL(node) ((bool) (node)->count)
36             #define NOT_ROOTSENTINEL(node) ((bool) (node)->parent)
37             #define PTR_OFS(node,ofs) ((void*)(((char*)(void*)(node))+ofs))
38              
39             static void Balance( rbtree_node_t *current );
40             static void RotateRight( rbtree_node_t *node );
41             static void RotateLeft( rbtree_node_t *node );
42             static void PruneLeaf( rbtree_node_t *node );
43             static void InsertAtLeaf( rbtree_node_t *leaf, rbtree_node_t *new_node, bool on_left);
44              
45 45           void rbtree_init_tree( rbtree_node_t *root_sentinel, rbtree_node_t *leaf_sentinel ) {
46 45           SET_COUNT(root_sentinel, 0);
47 45           SET_COLOR_BLACK(leaf_sentinel);
48 45           root_sentinel->parent= NULL;
49 45           root_sentinel->left= leaf_sentinel;
50 45           root_sentinel->right= leaf_sentinel;
51 45           SET_COUNT(leaf_sentinel, 0);
52 45           SET_COLOR_BLACK(leaf_sentinel);
53 45           leaf_sentinel->left= leaf_sentinel;
54 45           leaf_sentinel->right= leaf_sentinel;
55 45           leaf_sentinel->parent= leaf_sentinel;
56 45           }
57              
58 150           rbtree_node_t *rbtree_node_left_leaf( rbtree_node_t *node ) {
59 150 100         if (IS_SENTINEL(node)) return NULL;
60 529 100         while (NOT_SENTINEL(node->left))
61 380           node= node->left;
62 149           return node;
63             }
64              
65 109           rbtree_node_t *rbtree_node_right_leaf( rbtree_node_t *node ) {
66 109 100         if (IS_SENTINEL(node)) return NULL;
67 524 100         while (NOT_SENTINEL(node->right))
68 416           node= node->right;
69 108           return node;
70             }
71              
72 23           rbtree_node_t *rbtree_node_rootsentinel( rbtree_node_t *node ) {
73 77 50         while (node && node->parent)
    100          
74 54           node= node->parent;
75             // The node might not have been part of the tree, so make extra checks that
76             // this is really a sentinel
77 23 50         return node && node->right && node->right->right == node->right? node : NULL;
    100          
    50          
78             }
79              
80 25397           rbtree_node_t *rbtree_node_prev( rbtree_node_t *node ) {
81 25397 100         if (IS_SENTINEL(node)) return NULL;
82             // If we are not at a leaf, move to the right-most node
83             // in the tree to the left of this node.
84 25395 100         if (NOT_SENTINEL(node->left)) {
85 158           node= node->left;
86 184 100         while (NOT_SENTINEL(node->right))
87 26           node= node->right;
88 158           return node;
89             }
90             // Else walk up the tree until we see a parent node to the left
91             else {
92 25237           rbtree_node_t *parent= node->parent;
93 30085 100         while (parent->left == node) {
94 4902           node= parent;
95 4902           parent= parent->parent;
96             // Check for root_sentinel
97 4902 100         if (!parent) return NULL;
98             }
99 25183           return parent;
100             }
101             }
102              
103 845697           rbtree_node_t *rbtree_node_next( rbtree_node_t *node ) {
104 845697 100         if (IS_SENTINEL(node)) return NULL;
105             // If we are not at a leaf, move to the left-most node
106             // in the tree to the right of this node.
107 845696 100         if (NOT_SENTINEL(node->right)) {
108 235242           node= node->right;
109 470228 100         while (NOT_SENTINEL(node->left))
110 234986           node= node->left;
111 235242           return node;
112             }
113             // Else walk up the tree until we see a parent node to the right
114             else {
115 610454           rbtree_node_t *parent= node->parent;
116 610454 50         assert(parent);
117 9020106 100         while (parent->right == node) {
118 8409652 50         assert(parent != parent->parent);
119 8409652           node= parent;
120 8409652           parent= node->parent;
121             }
122             // Check for the root_sentinel
123 610454 100         if (!parent->parent) return NULL;
124 310231           return parent;
125             }
126             }
127              
128             /** Simple find algorithm.
129             * This function looks for the nearest node to the requested key, returning the node and
130             * the final value of the compare function which indicates whether this is the node equal to,
131             * before, or after the requested key.
132             */
133 70000           rbtree_node_t * rbtree_find_nearest(rbtree_node_t *node, void *goal,
134             int(*compare)(void *ctx, void *a,void *b), void *ctx, int cmp_ptr_ofs,
135             int *last_cmp_out
136             ) {
137 70000           rbtree_node_t *nearest= NULL, *test;
138 70000           int count, cmp= 0;
139            
140 70000 50         if (IS_ROOTSENTINEL(node))
141 70000           node= node->left;
142              
143 1436585 100         while (NOT_SENTINEL(node)) {
144 1366585           nearest= node;
145 1366585           cmp= compare( ctx, goal, PTR_OFS(node,cmp_ptr_ofs) );
146 1366585 100         if (cmp<0) node= node->left;
147 1193105 50         else if (cmp>0) node= node->right;
148 0           else break;
149             }
150 70000 100         if (nearest && last_cmp_out)
    50          
151 69993           *last_cmp_out= cmp;
152 70000           return nearest;
153             }
154              
155             /** Find-all algorithm.
156             * This function not only finds a node, but can find the nearest node to the one requested, finds the number of
157             * matching nodes, and gets the first and last node so the matches can be iterated.
158             */
159 400399           bool rbtree_find_all(rbtree_node_t *node, void* goal,
160             int(*compare)(void *ctx, void *a,void *b), void *ctx, int cmp_ptr_ofs,
161             rbtree_node_t **result_first, rbtree_node_t **result_last, size_t *result_count
162             ) {
163 400399           rbtree_node_t *nearest= NULL, *first, *last, *test;
164             size_t count;
165             int cmp;
166            
167 400399 50         if (IS_ROOTSENTINEL(node))
168 400399           node= node->left;
169              
170 11105157 100         while (NOT_SENTINEL(node)) {
171 10705025           nearest= node;
172 10705025           cmp= compare( ctx, goal, PTR_OFS(node,cmp_ptr_ofs) );
173 10705025 100         if (cmp<0) node= node->left;
174 10127661 100         else if (cmp>0) node= node->right;
175 267           else break;
176             }
177 400399 100         if (IS_SENTINEL(node)) {
178             /* no matches. Look up neighbor node if requested. */
179 400132 50         if (result_first)
180 400132 100         *result_first= nearest && cmp < 0? rbtree_node_prev(nearest) : nearest;
    100          
181 400132 50         if (result_last)
182 400132 100         *result_last= nearest && cmp > 0? rbtree_node_next(nearest) : nearest;
    100          
183 400132 100         if (result_count) *result_count= 0;
184 400132           return false;
185             }
186             // we've found the head of the tree the matches will be found in
187 267           count= 1;
188 267 50         if (result_first || result_count) {
    0          
189             // Search the left tree for the first match
190 267           first= node;
191 267           test= first->left;
192 476 100         while (NOT_SENTINEL(test)) {
193 209           cmp= compare( ctx, goal, PTR_OFS(test,cmp_ptr_ofs) );
194 209 100         if (cmp == 0) {
195 4           first= test;
196 4           count+= 1 + GET_COUNT(test->right);
197 4           test= test->left;
198             }
199             else /* cmp > 0 */
200 205           test= test->right;
201             }
202 267 50         if (result_first) *result_first= first;
203             }
204 267 100         if (result_last || result_count) {
    50          
205             // Search the right tree for the last match
206 267           last= node;
207 267           test= last->right;
208 485 100         while (NOT_SENTINEL(test)) {
209 218           cmp= compare( ctx, goal, PTR_OFS(test,cmp_ptr_ofs) );
210 218 100         if (cmp == 0) {
211 4           last= test;
212 4           count+= 1 + GET_COUNT(test->left);
213 4           test= test->right;
214             }
215             else /* cmp < 0 */
216 214           test= test->left;
217             }
218 267 100         if (result_last) *result_last= last;
219 267 100         if (result_count) *result_count= count;
220             }
221 267           return true;
222             }
223              
224             /* Insert a new object into the tree. The initial node is called 'hint' because if the new node
225             * isn't a child of hint, this will backtrack up the tree to find the actual insertion point.
226             */
227 470212           bool rbtree_node_insert( rbtree_node_t *hint, rbtree_node_t *node, int(*compare)(void *ctx, void *a, void *b), void *ctx, int cmp_ptr_ofs) {
228             // Can't insert node if it is already in the tree
229 470212 50         if (NODE_IS_IN_TREE(node))
230 0           return false;
231             // check for first node scenario
232 470212 100         if (IS_ROOTSENTINEL(hint)) {
233 127 100         if (IS_SENTINEL(hint->left)) {
234 38           hint->left= node;
235 38           node->parent= hint;
236 38           node->left= hint->right; // tree's leaf sentinel
237 38           node->right= hint->right;
238 38           SET_COUNT(node, 1);
239 38           SET_COLOR_BLACK(node);
240 38           return true;
241             }
242             else
243 89           hint= hint->left;
244             }
245             // else traverse hint until leaf
246             int cmp;
247 470174           bool leftmost= true, rightmost= true;
248 470174           rbtree_node_t *pos= hint, *next, *parent;
249             while (1) {
250 500056           cmp= compare(ctx, PTR_OFS(node,cmp_ptr_ofs), PTR_OFS(pos,cmp_ptr_ofs) );
251 500056 100         if (cmp < 0) {
252 39734           rightmost= false;
253 39734           next= pos->left;
254             } else {
255 460322           leftmost= false;
256 460322           next= pos->right;
257             }
258 500056 100         if (IS_SENTINEL(next))
259 470174           break;
260 29882           pos= next;
261 29882           }
262             // If the original hint was not the root of the tree, and cmp indicate the same direction
263             // as leftmost or rightmost, then backtrack and see if we're completely in the wrong spot.
264 470174 100         if (NOT_ROOTSENTINEL(hint->parent) && (cmp < 0? leftmost : rightmost)) {
    100          
    100          
265             // we are the leftmost child of hint, so if there is a parent to the left,
266             // key needs to not compare less else we have to start over.
267 445071           parent= hint->parent;
268             while (1) {
269 10178241 100         if ((cmp < 0? parent->right : parent->left) == hint) {
    100          
270 44525 50         if ((cmp < 0) == (compare(ctx, PTR_OFS(node,cmp_ptr_ofs), PTR_OFS(parent,cmp_ptr_ofs)) < 0)) {
271             // Whoops. Hint was wrong. Should start over from root.
272 0 0         while (NOT_ROOTSENTINEL(parent->parent))
273 0           parent= parent->parent;
274 0           return rbtree_node_insert(parent, node, compare, ctx, cmp_ptr_ofs);
275             }
276 44525           else break; // we're fine afterall
277             }
278 10133716 100         else if (IS_ROOTSENTINEL(parent->parent))
279 400546           break; // we're fine afterall
280 9733170           parent= parent->parent;
281 9733170           }
282             }
283 470174 100         if (cmp < 0)
284 34987           pos->left= node;
285             else
286 435187           pos->right= node;
287 470174           node->parent= pos;
288             // next is pointing to the leaf-sentinel for this tree after exiting loop above
289 470174           node->left= next;
290 470174           node->right= next;
291 470174           SET_COUNT(node, 1);
292 470174           SET_COLOR_RED(node);
293 12538688 100         for (parent= pos; NOT_ROOTSENTINEL(parent); parent= parent->parent)
294 12068514           ADD_COUNT(parent, 1);
295 470174           Balance(pos);
296             // We've iterated to the root sentinel- so node->left is the head of the tree.
297             // Set the tree's root to black
298 470174           SET_COLOR_BLACK(parent->left);
299 470174           return true;
300             }
301              
302 62232           void RotateRight( rbtree_node_t *node ) {
303 62232           rbtree_node_t *new_head= node->left;
304 62232           rbtree_node_t *parent= node->parent;
305              
306 62232 100         if (parent->right == node) parent->right= new_head;
307 17915           else parent->left= new_head;
308 62232           new_head->parent= parent;
309              
310 62232           ADD_COUNT(node, -1 - GET_COUNT(new_head->left));
311 62232           ADD_COUNT(new_head, 1 + GET_COUNT(node->right));
312 62232           node->left= new_head->right;
313 62232           new_head->right->parent= node;
314              
315 62232           new_head->right= node;
316 62232           node->parent= new_head;
317 62232           }
318              
319 451314           void RotateLeft( rbtree_node_t *node ) {
320 451314           rbtree_node_t *new_head= node->right;
321 451314           rbtree_node_t *parent= node->parent;
322              
323 451314 100         if (parent->right == node) parent->right= new_head;
324 76415           else parent->left= new_head;
325 451314           new_head->parent= parent;
326              
327 451314           ADD_COUNT(node, -1 - GET_COUNT(new_head->right));
328 451314           ADD_COUNT(new_head, 1 + GET_COUNT(node->left));
329 451314           node->right= new_head->left;
330 451314           new_head->left->parent= node;
331              
332 451314           new_head->left= node;
333 451314           node->parent= new_head;
334 451314           }
335              
336             /** Re-balance a tree which has just had one element added.
337             * current is the parent node of the node just added. The child is red.
338             *
339             * node counts are *not* updated by this method.
340             */
341 470174           void Balance( rbtree_node_t *current ) {
342             // if current is a black node, no rotations needed
343 916025 100         while (IS_RED(current)) {
344             // current is red, the imbalanced child is red, and parent is black.
345              
346 897563           rbtree_node_t *parent= current->parent;
347              
348             // if the current is on the right of the parent, the parent is to the left
349 897563 100         if (parent->right == current) {
350             // if the sibling is also red, we can pull down the color black from the parent
351 833842 100         if (IS_RED(parent->left)) {
352 443960           SET_COLOR_BLACK(parent->left);
353 443960           SET_COLOR_BLACK(current);
354 443960           SET_COLOR_RED(parent);
355             // jump twice up the tree. if current reaches the HeadSentinel (black node), the loop will stop
356 443960           current= parent->parent;
357 443960           continue;
358             }
359             // if the imbalance (red node) is on the left, and the parent is on the left,
360             // a "prep-slide" is needed. (see diagram)
361 389882 100         if (IS_RED(current->left))
362 402           RotateRight( current );
363              
364             // Now we can do our left rotation to balance the tree.
365 389882           RotateLeft( parent );
366 389882           SET_COLOR_RED(parent);
367 389882           SET_COLOR_BLACK(parent->parent);
368 389882           return;
369             }
370             // else the parent is to the right
371             else {
372             // if the sibling is also red, we can pull down the color black from the parent
373 63721 100         if (IS_RED(parent->right)) {
374 1891           SET_COLOR_BLACK(parent->right);
375 1891           SET_COLOR_BLACK(current);
376 1891           SET_COLOR_RED(parent);
377             // jump twice up the tree. if current reaches the HeadSentinel (black node), the loop will stop
378 1891           current= parent->parent;
379 1891           continue;
380             }
381             // if the imbalance (red node) is on the right, and the parent is on the right,
382             // a "prep-slide" is needed. (see diagram)
383 61830 100         if (IS_RED(current->right))
384 61427           RotateLeft( current );
385              
386             // Now we can do our right rotation to balance the tree.
387 61830           RotateRight( parent );
388 61830           SET_COLOR_RED(parent);
389 61830           SET_COLOR_BLACK(parent->parent);
390 61830           return;
391             }
392             }
393             // note that we should now set the root node to be black.
394             // but the caller does this anyway.
395 18462           return;
396             }
397              
398              
399 70848           size_t rbtree_node_index( rbtree_node_t *node ) {
400 70848           int left_count= GET_COUNT(node->left);
401 70848           rbtree_node_t *prev= node;
402 70848           node= node->parent;
403 1364667 100         while (NOT_SENTINEL(node)) {
404 1293819 100         if (node->right == prev)
405 1129788           left_count += GET_COUNT(node->left)+1;
406 1293819           prev= node;
407 1293819           node= node->parent;
408             }
409 70848           return left_count;
410             }
411              
412             /** Find the Nth node in the tree, indexed from 0, from the left to right.
413             * This operates by looking at the count of the left subtree, to descend down to the Nth element.
414             */
415 766           rbtree_node_t *rbtree_node_child_at_index( rbtree_node_t *node, size_t index ) {
416 766 100         if (index >= GET_COUNT(node))
417 143           return NULL;
418 1995 100         while (index != GET_COUNT(node->left)) {
419 1372 100         if (index < GET_COUNT(node->left))
420 414           node= node->left;
421             else {
422 958           index -= GET_COUNT(node->left)+1;
423 958           node= node->right;
424             }
425             }
426 623           return node;
427             }
428              
429             /** Prune a node from anywhere in the tree.
430             * If the node is a leaf, it can be removed easily. Otherwise we must swap the node for a leaf node
431             * with an adjacent key value, and then remove from the position of that leaf.
432             *
433             * This function *does* update node counts.
434             */
435 26           void rbtree_node_prune( rbtree_node_t *current ) {
436             rbtree_node_t *temp, *successor;
437 26 50         if (GET_COUNT(current) == 0)
438 0           return;
439              
440             // If this is a leaf node (or almost a leaf) we can just prune it
441 26 100         if (IS_SENTINEL(current->left) || IS_SENTINEL(current->right))
    100          
442 20           PruneLeaf(current);
443              
444             // Otherwise we need a successor. We are guaranteed to have one because
445             // the current node has 2 children.
446             else {
447             // pick from the largest subtree
448 12           successor= (GET_COUNT(current->left) > GET_COUNT(current->right))?
449             rbtree_node_prev( current )
450 6 100         : rbtree_node_next( current );
451 6           PruneLeaf( successor );
452              
453             // now exchange the successor for the current node
454 6           temp= current->right;
455 6           successor->right= temp;
456 6           temp->parent= successor;
457              
458 6           temp= current->left;
459 6           successor->left= temp;
460 6           temp->parent= successor;
461              
462 6           temp= current->parent;
463 6           successor->parent= temp;
464 6 100         if (temp->left == current) temp->left= successor; else temp->right= successor;
465 6           COPY_COLOR(successor, current);
466 6           SET_COUNT(successor, GET_COUNT(current));
467             }
468 26           current->left= current->right= current->parent= NULL;
469 26           SET_COLOR_BLACK(current);
470 26           SET_COUNT(current, 0);
471             }
472              
473             /** PruneLeaf performs pruning of nodes with at most one child node.
474             * This is the real heart of node deletion.
475             * The first operation is to decrease the node count from node to root_sentinel.
476             */
477 26           void PruneLeaf( rbtree_node_t *node ) {
478 26           rbtree_node_t *parent= node->parent, *current, *sibling, *sentinel;
479 26           bool leftside= (parent->left == node);
480 26 100         sentinel= IS_SENTINEL(node->left)? node->left : node->right;
481            
482             // first, decrement the count from here to root_sentinel
483 95 100         for (current= node; NOT_ROOTSENTINEL(current); current= current->parent)
484 69           ADD_COUNT(current, -1);
485              
486             // if the node is red and has at most one child, then it has no child.
487             // Prune it.
488 26 100         if (IS_RED(node)) {
489 9 100         if (leftside) parent->left= sentinel;
490 8           else parent->right= sentinel;
491 9           return;
492             }
493              
494             // node is black here. If it has a child, the child will be red.
495 17 100         if (node->left != sentinel) {
496             // swap with child
497 1           SET_COLOR_BLACK(node->left);
498 1           node->left->parent= parent;
499 1 50         if (leftside) parent->left= node->left;
500 0           else parent->right= node->left;
501 1           return;
502             }
503 16 100         if (node->right != sentinel) {
504             // swap with child
505 4           SET_COLOR_BLACK(node->right);
506 4           node->right->parent= parent;
507 4 100         if (leftside) parent->left= node->right;
508 1           else parent->right= node->right;
509 4           return;
510             }
511              
512             // Now, we have determined that node is a black leaf node with no children.
513             // The tree must have the same number of black nodes along any path from root
514             // to leaf. We want to remove a black node, disrupting the number of black
515             // nodes along the path from the root to the current leaf. To correct this,
516             // we must either shorten all other paths, or add a black node to the current
517             // path. Then we can freely remove our black leaf.
518             //
519             // While we are pointing to it, we will go ahead and delete the leaf and
520             // replace it with the sentinel (which is also black, so it won't affect
521             // the algorithm).
522              
523 12 100         if (leftside) parent->left= sentinel; else parent->right= sentinel;
524              
525 12 100         sibling= (leftside)? parent->right : parent->left;
526 12           current= node;
527              
528             // Loop until the current node is red, or until we get to the root node.
529             // (The root node's parent is the root_sentinel, which will have a NULL parent.)
530 23 100         while (IS_BLACK(current) && NOT_ROOTSENTINEL(parent)) {
    100          
531             // If the sibling is red, we are unable to reduce the number of black
532             // nodes in the sibling tree, and we can't increase the number of black
533             // nodes in our tree.. Thus we must do a rotation from the sibling
534             // tree to our tree to give us some extra (red) nodes to play with.
535             // This is Case 1 from the text
536 14 100         if (IS_RED(sibling)) {
537 2           SET_COLOR_RED(parent);
538 2           SET_COLOR_BLACK(sibling);
539 2 50         if (leftside) {
540 2           RotateLeft(parent);
541 2           sibling= parent->right;
542             }
543             else {
544 0           RotateRight(parent);
545 0           sibling= parent->left;
546             }
547 2           continue;
548             }
549             // sibling will be black here
550              
551             // If the sibling is black and both children are black, we have to
552             // reduce the black node count in the sibling's tree to match ours.
553             // This is Case 2a from the text.
554 12 100         if (IS_BLACK(sibling->right) && IS_BLACK(sibling->left)) {
    50          
555 9 50         assert(NOT_SENTINEL(sibling));
556 9           SET_COLOR_RED(sibling);
557             // Now we move one level up the tree to continue fixing the
558             // other branches.
559 9           current= parent;
560 9           parent= current->parent;
561 9           leftside= (parent->left == current);
562 9 100         sibling= (leftside)? parent->right : parent->left;
563 9           continue;
564             }
565             // sibling will be black with 1 or 2 red children here
566              
567             // << Case 2b is handled by the while loop. >>
568              
569             // If one of the sibling's children are red, we again can't make the
570             // sibling red to balance the tree at the parent, so we have to do a
571             // rotation. If the "near" nephew is red and the "far" nephew is
572             // black, we need to rotate that tree rightward before rotating the
573             // parent leftward.
574             // After doing a rotation and rearranging a few colors, the effect is
575             // that we maintain the same number of black nodes per path on the far
576             // side of the parent, and we gain a black node on the current side,
577             // so we are done.
578             // This is Case 4 from the text. (Case 3 is the double rotation)
579 3 50         if (leftside) {
580 3 50         if (IS_BLACK(sibling->right)) { // Case 3 from the text
581 0           RotateRight( sibling );
582 0           sibling= parent->right;
583             }
584             // now Case 4 from the text
585 3           SET_COLOR_BLACK(sibling->right);
586 3 50         assert(NOT_SENTINEL(sibling));
587 3           COPY_COLOR(sibling, parent);
588 3           SET_COLOR_BLACK(parent);
589              
590 3           current= parent;
591 3           parent= current->parent;
592 3           RotateLeft( current );
593 3           return;
594             }
595             else {
596 0 0         if (IS_BLACK(sibling->left)) { // Case 3 from the text
597 0           RotateLeft( sibling );
598 0           sibling= parent->left;
599             }
600             // now Case 4 from the text
601 0           SET_COLOR_BLACK(sibling->left);
602 0 0         assert(NOT_SENTINEL(sibling));
603 0           COPY_COLOR(sibling, parent);
604 0           SET_COLOR_BLACK(parent);
605              
606 0           current= parent;
607 0           parent= current->parent;
608 0           RotateRight( current );
609 0           return;
610             }
611             }
612              
613             // Now, make the current node black (to fulfill Case 2b)
614             // Case 4 will have exited directly out of the function.
615             // If we stopped because we reached the top of the tree,
616             // the head is black anyway so don't worry about it.
617 9           SET_COLOR_BLACK(current);
618             }
619              
620             /** Mark all nodes as being not-in-tree, and possibly delete the objects that contain them.
621             * DeleteProc is optional. If given, it will be called on the 'Object' which contains the rbtree_node_t.
622             * obj_ofs is a negative (or zero) number of bytes offset from the rbtree_node_t pointer to the containing
623             * object pointer. `ctx` is a user-defined context pointer to pass to the destructor.
624             */
625 45           void rbtree_clear( rbtree_node_t *root_sentinel, void (*destructor)(void *obj, void *ctx), int obj_ofs, void *ctx ) {
626             rbtree_node_t *current, *next;
627             int from_left;
628             // Delete in a depth-first post-traversal, because the node might not exist after
629             // calling the destructor.
630 45 50         if (!IS_ROOTSENTINEL(root_sentinel))
631 0           return; /* this is API usage bug, but no way to report it */
632 45 100         if (IS_SENTINEL(root_sentinel->left))
633 8           return; /* tree already empty */
634 37           current= root_sentinel->left;
635             while (1) {
636             check_left: // came from above, go down-left
637 470186 100         if (NOT_SENTINEL(current->left)) {
638 235067           current= current->left;
639 235067           goto check_left;
640             }
641             check_right: // came up from the left, go down-right
642 470186 100         if (NOT_SENTINEL(current->right)) {
643 235082           current= current->right;
644 235082           goto check_left;
645             }
646             zap_current: // came up from the right, kill the current node and proceed up
647 470186           next= current->parent;
648 470186           from_left= (next->left == current)? 1 : 0;
649 470186           SET_COUNT(current, 0);
650 470186           current->left= current->right= current->parent= NULL;
651 470186 50         if (destructor) destructor(PTR_OFS(current,obj_ofs), ctx);
652 470186           current= next;
653 470186 100         if (current == root_sentinel)
654 37           break;
655 470149 100         else if (from_left)
656 235067           goto check_right;
657             else
658 235082           goto zap_current;
659             }
660 37           root_sentinel->left= root_sentinel->right;
661 37           SET_COLOR_BLACK(root_sentinel);
662 37           SET_COUNT(root_sentinel, 0);
663             }
664              
665              
666             static int CheckSubtree(rbtree_node_t *node, rbtree_compare_fn, void *ctx, int, int *);
667              
668 15           int rbtree_check_structure(rbtree_node_t *node, rbtree_compare_fn compare, void *ctx, int cmp_pointer_ofs) {
669             // If at root, check for root sentinel details
670 15 50         if (node && !node->parent) {
    50          
671 15 50         if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right))
    50          
    50          
    50          
672 0           return RBTREE_INVALID_ROOT;
673 15 50         if (GET_COUNT(node->right) || IS_RED(node->right) || node->right->left != node->right
    50          
    50          
674 15 50         || node->right->right != node->right)
675 0           return RBTREE_INVALID_SENTINEL;
676 15 50         if (node->left == node->right) return 0; /* empty tree, nothing more to check */
677 15 50         if (node->left->parent != node)
678 0           return RBTREE_INVALID_ROOT;
679 15           node= node->left; /* else start checking at first real node */
680             }
681             int black_count;
682 15           return CheckSubtree(node, compare, ctx, cmp_pointer_ofs, &black_count);
683             }
684              
685 470008           int CheckSubtree(rbtree_node_t *node, rbtree_compare_fn compare, void *ctx, int cmp_pointer_ofs, int *black_count) {
686             // This node should be fully attached to the tree
687 470008 50         if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node))
    50          
    50          
    50          
    50          
688 0           return RBTREE_INVALID_NODE;
689             // Check counts. This is an easy way to validate the relation to sentinels too
690 470008 50         if (GET_COUNT(node) != GET_COUNT(node->left) + GET_COUNT(node->right) + 1)
691 0           return RBTREE_INVALID_COUNT;
692             // Check node key order
693 470008           int left_black_count= 0, right_black_count= 0;
694 470008 100         if (NOT_SENTINEL(node->left)) {
695 234993 50         if (node->left->parent != node)
696 0           return RBTREE_INVALID_NODE;
697 234993 100         if (IS_RED(node) && IS_RED(node->left))
    50          
698 0           return RBTREE_INVALID_COLOR;
699 234993 50         if (compare(ctx, PTR_OFS(node->left, cmp_pointer_ofs), PTR_OFS(node, cmp_pointer_ofs)) > 0)
700 0           return RBTREE_INVALID_ORDER;
701 234993           int err= CheckSubtree(node->left, compare, ctx, cmp_pointer_ofs, &left_black_count);
702 234993 50         if (err) return err;
703             }
704 470008 100         if (NOT_SENTINEL(node->right)) {
705 235000 50         if (node->right->parent != node)
706 0           return RBTREE_INVALID_NODE;
707 235000 100         if (IS_RED(node) && IS_RED(node->right))
    50          
708 0           return RBTREE_INVALID_COLOR;
709 235000 50         if (compare(ctx, PTR_OFS(node->right, cmp_pointer_ofs), PTR_OFS(node, cmp_pointer_ofs)) < 0)
710 0           return RBTREE_INVALID_ORDER;
711 235000           int err= CheckSubtree(node->right, compare, ctx, cmp_pointer_ofs, &right_black_count);
712 235000 50         if (err) return err;
713             }
714 470008 50         if (left_black_count != right_black_count)
715 0           return RBTREE_INVALID_COLOR;
716 470008           *black_count= left_black_count + (IS_BLACK(node)? 1 : 0);
717 470008           return 0;
718             }