1eaad808eSchristos /*
2eaad808eSchristos * rbtree.c -- generic red black tree
3eaad808eSchristos *
4eaad808eSchristos * Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
5eaad808eSchristos *
6eaad808eSchristos * This software is open source.
7eaad808eSchristos *
8eaad808eSchristos * Redistribution and use in source and binary forms, with or without
9eaad808eSchristos * modification, are permitted provided that the following conditions
10eaad808eSchristos * are met:
11eaad808eSchristos *
12eaad808eSchristos * Redistributions of source code must retain the above copyright notice,
13eaad808eSchristos * this list of conditions and the following disclaimer.
14eaad808eSchristos *
15eaad808eSchristos * Redistributions in binary form must reproduce the above copyright notice,
16eaad808eSchristos * this list of conditions and the following disclaimer in the documentation
17eaad808eSchristos * and/or other materials provided with the distribution.
18eaad808eSchristos *
19eaad808eSchristos * Neither the name of the NLNET LABS nor the names of its contributors may
20eaad808eSchristos * be used to endorse or promote products derived from this software without
21eaad808eSchristos * specific prior written permission.
22eaad808eSchristos *
23eaad808eSchristos * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24eaad808eSchristos * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25eaad808eSchristos * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26eaad808eSchristos * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27eaad808eSchristos * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28eaad808eSchristos * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29eaad808eSchristos * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30eaad808eSchristos * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31eaad808eSchristos * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32eaad808eSchristos * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33eaad808eSchristos * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34eaad808eSchristos *
35eaad808eSchristos */
36eaad808eSchristos
37eaad808eSchristos /**
38eaad808eSchristos * \file
39eaad808eSchristos * Implementation of a redblack tree.
40eaad808eSchristos */
41eaad808eSchristos
42eaad808eSchristos #include "config.h"
43eaad808eSchristos #include "log.h"
44eaad808eSchristos #include "fptr_wlist.h"
45eaad808eSchristos #include "util/rbtree.h"
46eaad808eSchristos
47eaad808eSchristos /** Node colour black */
48eaad808eSchristos #define BLACK 0
49eaad808eSchristos /** Node colour red */
50eaad808eSchristos #define RED 1
51eaad808eSchristos
52eaad808eSchristos /** the NULL node, global alloc */
53*762909a6Schristos rbnode_type rbtree_null_node = {
54eaad808eSchristos RBTREE_NULL, /* Parent. */
55eaad808eSchristos RBTREE_NULL, /* Left. */
56eaad808eSchristos RBTREE_NULL, /* Right. */
57eaad808eSchristos NULL, /* Key. */
58eaad808eSchristos BLACK /* Color. */
59eaad808eSchristos };
60eaad808eSchristos
61eaad808eSchristos /** rotate subtree left (to preserve redblack property) */
62*762909a6Schristos static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
63eaad808eSchristos /** rotate subtree right (to preserve redblack property) */
64*762909a6Schristos static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
65eaad808eSchristos /** Fixup node colours when insert happened */
66*762909a6Schristos static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
67eaad808eSchristos /** Fixup node colours when delete happened */
68*762909a6Schristos static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
69*762909a6Schristos rbnode_type* child_parent);
70eaad808eSchristos
71eaad808eSchristos /*
72eaad808eSchristos * Creates a new red black tree, initializes and returns a pointer to it.
73eaad808eSchristos *
74eaad808eSchristos * Return NULL on failure.
75eaad808eSchristos *
76eaad808eSchristos */
77*762909a6Schristos rbtree_type *
rbtree_create(int (* cmpf)(const void *,const void *))78eaad808eSchristos rbtree_create (int (*cmpf)(const void *, const void *))
79eaad808eSchristos {
80*762909a6Schristos rbtree_type *rbtree;
81eaad808eSchristos
82eaad808eSchristos /* Allocate memory for it */
83*762909a6Schristos rbtree = (rbtree_type *) malloc(sizeof(rbtree_type));
84eaad808eSchristos if (!rbtree) {
85eaad808eSchristos return NULL;
86eaad808eSchristos }
87eaad808eSchristos
88eaad808eSchristos /* Initialize it */
89eaad808eSchristos rbtree_init(rbtree, cmpf);
90eaad808eSchristos
91eaad808eSchristos return rbtree;
92eaad808eSchristos }
93eaad808eSchristos
94eaad808eSchristos void
rbtree_init(rbtree_type * rbtree,int (* cmpf)(const void *,const void *))95*762909a6Schristos rbtree_init(rbtree_type *rbtree, int (*cmpf)(const void *, const void *))
96eaad808eSchristos {
97eaad808eSchristos /* Initialize it */
98eaad808eSchristos rbtree->root = RBTREE_NULL;
99eaad808eSchristos rbtree->count = 0;
100eaad808eSchristos rbtree->cmp = cmpf;
101eaad808eSchristos }
102eaad808eSchristos
103eaad808eSchristos /*
104eaad808eSchristos * Rotates the node to the left.
105eaad808eSchristos *
106eaad808eSchristos */
107eaad808eSchristos static void
rbtree_rotate_left(rbtree_type * rbtree,rbnode_type * node)108*762909a6Schristos rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)
109eaad808eSchristos {
110*762909a6Schristos rbnode_type *right = node->right;
111eaad808eSchristos node->right = right->left;
112eaad808eSchristos if (right->left != RBTREE_NULL)
113eaad808eSchristos right->left->parent = node;
114eaad808eSchristos
115eaad808eSchristos right->parent = node->parent;
116eaad808eSchristos
117eaad808eSchristos if (node->parent != RBTREE_NULL) {
118eaad808eSchristos if (node == node->parent->left) {
119eaad808eSchristos node->parent->left = right;
120eaad808eSchristos } else {
121eaad808eSchristos node->parent->right = right;
122eaad808eSchristos }
123eaad808eSchristos } else {
124eaad808eSchristos rbtree->root = right;
125eaad808eSchristos }
126eaad808eSchristos right->left = node;
127eaad808eSchristos node->parent = right;
128eaad808eSchristos }
129eaad808eSchristos
130eaad808eSchristos /*
131eaad808eSchristos * Rotates the node to the right.
132eaad808eSchristos *
133eaad808eSchristos */
134eaad808eSchristos static void
rbtree_rotate_right(rbtree_type * rbtree,rbnode_type * node)135*762909a6Schristos rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)
136eaad808eSchristos {
137*762909a6Schristos rbnode_type *left = node->left;
138eaad808eSchristos node->left = left->right;
139eaad808eSchristos if (left->right != RBTREE_NULL)
140eaad808eSchristos left->right->parent = node;
141eaad808eSchristos
142eaad808eSchristos left->parent = node->parent;
143eaad808eSchristos
144eaad808eSchristos if (node->parent != RBTREE_NULL) {
145eaad808eSchristos if (node == node->parent->right) {
146eaad808eSchristos node->parent->right = left;
147eaad808eSchristos } else {
148eaad808eSchristos node->parent->left = left;
149eaad808eSchristos }
150eaad808eSchristos } else {
151eaad808eSchristos rbtree->root = left;
152eaad808eSchristos }
153eaad808eSchristos left->right = node;
154eaad808eSchristos node->parent = left;
155eaad808eSchristos }
156eaad808eSchristos
157eaad808eSchristos static void
rbtree_insert_fixup(rbtree_type * rbtree,rbnode_type * node)158*762909a6Schristos rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)
159eaad808eSchristos {
160*762909a6Schristos rbnode_type *uncle;
161eaad808eSchristos
162eaad808eSchristos /* While not at the root and need fixing... */
163eaad808eSchristos while (node != rbtree->root && node->parent->color == RED) {
164eaad808eSchristos /* If our parent is left child of our grandparent... */
165eaad808eSchristos if (node->parent == node->parent->parent->left) {
166eaad808eSchristos uncle = node->parent->parent->right;
167eaad808eSchristos
168eaad808eSchristos /* If our uncle is red... */
169eaad808eSchristos if (uncle->color == RED) {
170eaad808eSchristos /* Paint the parent and the uncle black... */
171eaad808eSchristos node->parent->color = BLACK;
172eaad808eSchristos uncle->color = BLACK;
173eaad808eSchristos
174eaad808eSchristos /* And the grandparent red... */
175eaad808eSchristos node->parent->parent->color = RED;
176eaad808eSchristos
177eaad808eSchristos /* And continue fixing the grandparent */
178eaad808eSchristos node = node->parent->parent;
179eaad808eSchristos } else { /* Our uncle is black... */
180eaad808eSchristos /* Are we the right child? */
181eaad808eSchristos if (node == node->parent->right) {
182eaad808eSchristos node = node->parent;
183eaad808eSchristos rbtree_rotate_left(rbtree, node);
184eaad808eSchristos }
185eaad808eSchristos /* Now we're the left child, repaint and rotate... */
186eaad808eSchristos node->parent->color = BLACK;
187eaad808eSchristos node->parent->parent->color = RED;
188eaad808eSchristos rbtree_rotate_right(rbtree, node->parent->parent);
189eaad808eSchristos }
190eaad808eSchristos } else {
191eaad808eSchristos uncle = node->parent->parent->left;
192eaad808eSchristos
193eaad808eSchristos /* If our uncle is red... */
194eaad808eSchristos if (uncle->color == RED) {
195eaad808eSchristos /* Paint the parent and the uncle black... */
196eaad808eSchristos node->parent->color = BLACK;
197eaad808eSchristos uncle->color = BLACK;
198eaad808eSchristos
199eaad808eSchristos /* And the grandparent red... */
200eaad808eSchristos node->parent->parent->color = RED;
201eaad808eSchristos
202eaad808eSchristos /* And continue fixing the grandparent */
203eaad808eSchristos node = node->parent->parent;
204eaad808eSchristos } else { /* Our uncle is black... */
205eaad808eSchristos /* Are we the right child? */
206eaad808eSchristos if (node == node->parent->left) {
207eaad808eSchristos node = node->parent;
208eaad808eSchristos rbtree_rotate_right(rbtree, node);
209eaad808eSchristos }
210eaad808eSchristos /* Now we're the right child, repaint and rotate... */
211eaad808eSchristos node->parent->color = BLACK;
212eaad808eSchristos node->parent->parent->color = RED;
213eaad808eSchristos rbtree_rotate_left(rbtree, node->parent->parent);
214eaad808eSchristos }
215eaad808eSchristos }
216eaad808eSchristos }
217eaad808eSchristos rbtree->root->color = BLACK;
218eaad808eSchristos }
219eaad808eSchristos
220eaad808eSchristos
221eaad808eSchristos /*
222eaad808eSchristos * Inserts a node into a red black tree.
223eaad808eSchristos *
224eaad808eSchristos * Returns NULL on failure or the pointer to the newly added node
225eaad808eSchristos * otherwise.
226eaad808eSchristos */
227*762909a6Schristos rbnode_type *
rbtree_insert(rbtree_type * rbtree,rbnode_type * data)228*762909a6Schristos rbtree_insert (rbtree_type *rbtree, rbnode_type *data)
229eaad808eSchristos {
230eaad808eSchristos /* XXX Not necessary, but keeps compiler quiet... */
231eaad808eSchristos int r = 0;
232eaad808eSchristos
233eaad808eSchristos /* We start at the root of the tree */
234*762909a6Schristos rbnode_type *node = rbtree->root;
235*762909a6Schristos rbnode_type *parent = RBTREE_NULL;
236eaad808eSchristos
237eaad808eSchristos fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
238eaad808eSchristos /* Lets find the new parent... */
239eaad808eSchristos while (node != RBTREE_NULL) {
240eaad808eSchristos /* Compare two keys, do we have a duplicate? */
241eaad808eSchristos if ((r = rbtree->cmp(data->key, node->key)) == 0) {
242eaad808eSchristos return NULL;
243eaad808eSchristos }
244eaad808eSchristos parent = node;
245eaad808eSchristos
246eaad808eSchristos if (r < 0) {
247eaad808eSchristos node = node->left;
248eaad808eSchristos } else {
249eaad808eSchristos node = node->right;
250eaad808eSchristos }
251eaad808eSchristos }
252eaad808eSchristos
253eaad808eSchristos /* Initialize the new node */
254eaad808eSchristos data->parent = parent;
255eaad808eSchristos data->left = data->right = RBTREE_NULL;
256eaad808eSchristos data->color = RED;
257eaad808eSchristos rbtree->count++;
258eaad808eSchristos
259eaad808eSchristos /* Insert it into the tree... */
260eaad808eSchristos if (parent != RBTREE_NULL) {
261eaad808eSchristos if (r < 0) {
262eaad808eSchristos parent->left = data;
263eaad808eSchristos } else {
264eaad808eSchristos parent->right = data;
265eaad808eSchristos }
266eaad808eSchristos } else {
267eaad808eSchristos rbtree->root = data;
268eaad808eSchristos }
269eaad808eSchristos
270eaad808eSchristos /* Fix up the red-black properties... */
271eaad808eSchristos rbtree_insert_fixup(rbtree, data);
272eaad808eSchristos
273eaad808eSchristos return data;
274eaad808eSchristos }
275eaad808eSchristos
276eaad808eSchristos /*
277eaad808eSchristos * Searches the red black tree, returns the data if key is found or NULL otherwise.
278eaad808eSchristos *
279eaad808eSchristos */
280*762909a6Schristos rbnode_type *
rbtree_search(rbtree_type * rbtree,const void * key)281*762909a6Schristos rbtree_search (rbtree_type *rbtree, const void *key)
282eaad808eSchristos {
283*762909a6Schristos rbnode_type *node;
284eaad808eSchristos
285eaad808eSchristos if (rbtree_find_less_equal(rbtree, key, &node)) {
286eaad808eSchristos return node;
287eaad808eSchristos } else {
288eaad808eSchristos return NULL;
289eaad808eSchristos }
290eaad808eSchristos }
291eaad808eSchristos
292eaad808eSchristos /** helpers for delete: swap node colours */
swap_int8(uint8_t * x,uint8_t * y)293eaad808eSchristos static void swap_int8(uint8_t* x, uint8_t* y)
294eaad808eSchristos {
295eaad808eSchristos uint8_t t = *x; *x = *y; *y = t;
296eaad808eSchristos }
297eaad808eSchristos
298eaad808eSchristos /** helpers for delete: swap node pointers */
swap_np(rbnode_type ** x,rbnode_type ** y)299*762909a6Schristos static void swap_np(rbnode_type** x, rbnode_type** y)
300eaad808eSchristos {
301*762909a6Schristos rbnode_type* t = *x; *x = *y; *y = t;
302eaad808eSchristos }
303eaad808eSchristos
304eaad808eSchristos /** Update parent pointers of child trees of 'parent' */
change_parent_ptr(rbtree_type * rbtree,rbnode_type * parent,rbnode_type * old,rbnode_type * new)305*762909a6Schristos static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,
306*762909a6Schristos rbnode_type* old, rbnode_type* new)
307eaad808eSchristos {
308eaad808eSchristos if(parent == RBTREE_NULL)
309eaad808eSchristos {
310eaad808eSchristos log_assert(rbtree->root == old);
311eaad808eSchristos if(rbtree->root == old) rbtree->root = new;
312eaad808eSchristos return;
313eaad808eSchristos }
314eaad808eSchristos log_assert(parent->left == old || parent->right == old
315eaad808eSchristos || parent->left == new || parent->right == new);
316eaad808eSchristos if(parent->left == old) parent->left = new;
317eaad808eSchristos if(parent->right == old) parent->right = new;
318eaad808eSchristos }
319eaad808eSchristos /** Update parent pointer of a node 'child' */
change_child_ptr(rbnode_type * child,rbnode_type * old,rbnode_type * new)320*762909a6Schristos static void change_child_ptr(rbnode_type* child, rbnode_type* old,
321*762909a6Schristos rbnode_type* new)
322eaad808eSchristos {
323eaad808eSchristos if(child == RBTREE_NULL) return;
324eaad808eSchristos log_assert(child->parent == old || child->parent == new);
325eaad808eSchristos if(child->parent == old) child->parent = new;
326eaad808eSchristos }
327eaad808eSchristos
328*762909a6Schristos rbnode_type*
rbtree_delete(rbtree_type * rbtree,const void * key)329*762909a6Schristos rbtree_delete(rbtree_type *rbtree, const void *key)
330eaad808eSchristos {
331*762909a6Schristos rbnode_type *to_delete;
332*762909a6Schristos rbnode_type *child;
333eaad808eSchristos if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
334eaad808eSchristos rbtree->count--;
335eaad808eSchristos
336eaad808eSchristos /* make sure we have at most one non-leaf child */
337eaad808eSchristos if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
338eaad808eSchristos {
339eaad808eSchristos /* swap with smallest from right subtree (or largest from left) */
340*762909a6Schristos rbnode_type *smright = to_delete->right;
341eaad808eSchristos while(smright->left != RBTREE_NULL)
342eaad808eSchristos smright = smright->left;
343eaad808eSchristos /* swap the smright and to_delete elements in the tree,
344*762909a6Schristos * but the rbnode_type is first part of user data struct
345eaad808eSchristos * so cannot just swap the keys and data pointers. Instead
346eaad808eSchristos * readjust the pointers left,right,parent */
347eaad808eSchristos
348eaad808eSchristos /* swap colors - colors are tied to the position in the tree */
349eaad808eSchristos swap_int8(&to_delete->color, &smright->color);
350eaad808eSchristos
351eaad808eSchristos /* swap child pointers in parents of smright/to_delete */
352eaad808eSchristos change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
353eaad808eSchristos if(to_delete->right != smright)
354eaad808eSchristos change_parent_ptr(rbtree, smright->parent, smright, to_delete);
355eaad808eSchristos
356eaad808eSchristos /* swap parent pointers in children of smright/to_delete */
357eaad808eSchristos change_child_ptr(smright->left, smright, to_delete);
358eaad808eSchristos change_child_ptr(smright->left, smright, to_delete);
359eaad808eSchristos change_child_ptr(smright->right, smright, to_delete);
360eaad808eSchristos change_child_ptr(smright->right, smright, to_delete);
361eaad808eSchristos change_child_ptr(to_delete->left, to_delete, smright);
362eaad808eSchristos if(to_delete->right != smright)
363eaad808eSchristos change_child_ptr(to_delete->right, to_delete, smright);
364eaad808eSchristos if(to_delete->right == smright)
365eaad808eSchristos {
366eaad808eSchristos /* set up so after swap they work */
367eaad808eSchristos to_delete->right = to_delete;
368eaad808eSchristos smright->parent = smright;
369eaad808eSchristos }
370eaad808eSchristos
371eaad808eSchristos /* swap pointers in to_delete/smright nodes */
372eaad808eSchristos swap_np(&to_delete->parent, &smright->parent);
373eaad808eSchristos swap_np(&to_delete->left, &smright->left);
374eaad808eSchristos swap_np(&to_delete->right, &smright->right);
375eaad808eSchristos
376eaad808eSchristos /* now delete to_delete (which is at the location where the smright previously was) */
377eaad808eSchristos }
378eaad808eSchristos log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);
379eaad808eSchristos
380eaad808eSchristos if(to_delete->left != RBTREE_NULL) child = to_delete->left;
381eaad808eSchristos else child = to_delete->right;
382eaad808eSchristos
383eaad808eSchristos /* unlink to_delete from the tree, replace to_delete with child */
384eaad808eSchristos change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
385eaad808eSchristos change_child_ptr(child, to_delete, to_delete->parent);
386eaad808eSchristos
387eaad808eSchristos if(to_delete->color == RED)
388eaad808eSchristos {
389eaad808eSchristos /* if node is red then the child (black) can be swapped in */
390eaad808eSchristos }
391eaad808eSchristos else if(child->color == RED)
392eaad808eSchristos {
393eaad808eSchristos /* change child to BLACK, removing a RED node is no problem */
394eaad808eSchristos if(child!=RBTREE_NULL) child->color = BLACK;
395eaad808eSchristos }
396eaad808eSchristos else rbtree_delete_fixup(rbtree, child, to_delete->parent);
397eaad808eSchristos
398eaad808eSchristos /* unlink completely */
399eaad808eSchristos to_delete->parent = RBTREE_NULL;
400eaad808eSchristos to_delete->left = RBTREE_NULL;
401eaad808eSchristos to_delete->right = RBTREE_NULL;
402eaad808eSchristos to_delete->color = BLACK;
403eaad808eSchristos return to_delete;
404eaad808eSchristos }
405eaad808eSchristos
rbtree_delete_fixup(rbtree_type * rbtree,rbnode_type * child,rbnode_type * child_parent)406*762909a6Schristos static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
407*762909a6Schristos rbnode_type* child_parent)
408eaad808eSchristos {
409*762909a6Schristos rbnode_type* sibling;
410eaad808eSchristos int go_up = 1;
411eaad808eSchristos
412eaad808eSchristos /* determine sibling to the node that is one-black short */
413eaad808eSchristos if(child_parent->right == child) sibling = child_parent->left;
414eaad808eSchristos else sibling = child_parent->right;
415eaad808eSchristos
416eaad808eSchristos while(go_up)
417eaad808eSchristos {
418eaad808eSchristos if(child_parent == RBTREE_NULL)
419eaad808eSchristos {
420eaad808eSchristos /* removed parent==black from root, every path, so ok */
421eaad808eSchristos return;
422eaad808eSchristos }
423eaad808eSchristos
424eaad808eSchristos if(sibling->color == RED)
425eaad808eSchristos { /* rotate to get a black sibling */
426eaad808eSchristos child_parent->color = RED;
427eaad808eSchristos sibling->color = BLACK;
428eaad808eSchristos if(child_parent->right == child)
429eaad808eSchristos rbtree_rotate_right(rbtree, child_parent);
430eaad808eSchristos else rbtree_rotate_left(rbtree, child_parent);
431eaad808eSchristos /* new sibling after rotation */
432eaad808eSchristos if(child_parent->right == child) sibling = child_parent->left;
433eaad808eSchristos else sibling = child_parent->right;
434eaad808eSchristos }
435eaad808eSchristos
436eaad808eSchristos if(child_parent->color == BLACK
437eaad808eSchristos && sibling->color == BLACK
438eaad808eSchristos && sibling->left->color == BLACK
439eaad808eSchristos && sibling->right->color == BLACK)
440eaad808eSchristos { /* fixup local with recolor of sibling */
441eaad808eSchristos if(sibling != RBTREE_NULL)
442eaad808eSchristos sibling->color = RED;
443eaad808eSchristos
444eaad808eSchristos child = child_parent;
445eaad808eSchristos child_parent = child_parent->parent;
446eaad808eSchristos /* prepare to go up, new sibling */
447eaad808eSchristos if(child_parent->right == child) sibling = child_parent->left;
448eaad808eSchristos else sibling = child_parent->right;
449eaad808eSchristos }
450eaad808eSchristos else go_up = 0;
451eaad808eSchristos }
452eaad808eSchristos
453eaad808eSchristos if(child_parent->color == RED
454eaad808eSchristos && sibling->color == BLACK
455eaad808eSchristos && sibling->left->color == BLACK
456eaad808eSchristos && sibling->right->color == BLACK)
457eaad808eSchristos {
458eaad808eSchristos /* move red to sibling to rebalance */
459eaad808eSchristos if(sibling != RBTREE_NULL)
460eaad808eSchristos sibling->color = RED;
461eaad808eSchristos child_parent->color = BLACK;
462eaad808eSchristos return;
463eaad808eSchristos }
464eaad808eSchristos log_assert(sibling != RBTREE_NULL);
465eaad808eSchristos
466eaad808eSchristos /* get a new sibling, by rotating at sibling. See which child
467eaad808eSchristos of sibling is red */
468eaad808eSchristos if(child_parent->right == child
469eaad808eSchristos && sibling->color == BLACK
470eaad808eSchristos && sibling->right->color == RED
471eaad808eSchristos && sibling->left->color == BLACK)
472eaad808eSchristos {
473eaad808eSchristos sibling->color = RED;
474eaad808eSchristos sibling->right->color = BLACK;
475eaad808eSchristos rbtree_rotate_left(rbtree, sibling);
476eaad808eSchristos /* new sibling after rotation */
477eaad808eSchristos if(child_parent->right == child) sibling = child_parent->left;
478eaad808eSchristos else sibling = child_parent->right;
479eaad808eSchristos }
480eaad808eSchristos else if(child_parent->left == child
481eaad808eSchristos && sibling->color == BLACK
482eaad808eSchristos && sibling->left->color == RED
483eaad808eSchristos && sibling->right->color == BLACK)
484eaad808eSchristos {
485eaad808eSchristos sibling->color = RED;
486eaad808eSchristos sibling->left->color = BLACK;
487eaad808eSchristos rbtree_rotate_right(rbtree, sibling);
488eaad808eSchristos /* new sibling after rotation */
489eaad808eSchristos if(child_parent->right == child) sibling = child_parent->left;
490eaad808eSchristos else sibling = child_parent->right;
491eaad808eSchristos }
492eaad808eSchristos
493eaad808eSchristos /* now we have a black sibling with a red child. rotate and exchange colors. */
494eaad808eSchristos sibling->color = child_parent->color;
495eaad808eSchristos child_parent->color = BLACK;
496eaad808eSchristos if(child_parent->right == child)
497eaad808eSchristos {
498eaad808eSchristos log_assert(sibling->left->color == RED);
499eaad808eSchristos sibling->left->color = BLACK;
500eaad808eSchristos rbtree_rotate_right(rbtree, child_parent);
501eaad808eSchristos }
502eaad808eSchristos else
503eaad808eSchristos {
504eaad808eSchristos log_assert(sibling->right->color == RED);
505eaad808eSchristos sibling->right->color = BLACK;
506eaad808eSchristos rbtree_rotate_left(rbtree, child_parent);
507eaad808eSchristos }
508eaad808eSchristos }
509eaad808eSchristos
510eaad808eSchristos int
rbtree_find_less_equal(rbtree_type * rbtree,const void * key,rbnode_type ** result)511*762909a6Schristos rbtree_find_less_equal(rbtree_type *rbtree, const void *key,
512*762909a6Schristos rbnode_type **result)
513eaad808eSchristos {
514eaad808eSchristos int r;
515*762909a6Schristos rbnode_type *node;
516eaad808eSchristos
517eaad808eSchristos log_assert(result);
518eaad808eSchristos
519eaad808eSchristos /* We start at root... */
520eaad808eSchristos node = rbtree->root;
521eaad808eSchristos
522eaad808eSchristos *result = NULL;
523eaad808eSchristos fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
524eaad808eSchristos
525eaad808eSchristos /* While there are children... */
526eaad808eSchristos while (node != RBTREE_NULL) {
527eaad808eSchristos r = rbtree->cmp(key, node->key);
528eaad808eSchristos if (r == 0) {
529eaad808eSchristos /* Exact match */
530eaad808eSchristos *result = node;
531eaad808eSchristos return 1;
532eaad808eSchristos }
533eaad808eSchristos if (r < 0) {
534eaad808eSchristos node = node->left;
535eaad808eSchristos } else {
536eaad808eSchristos /* Temporary match */
537eaad808eSchristos *result = node;
538eaad808eSchristos node = node->right;
539eaad808eSchristos }
540eaad808eSchristos }
541eaad808eSchristos return 0;
542eaad808eSchristos }
543eaad808eSchristos
544eaad808eSchristos /*
545eaad808eSchristos * Finds the first element in the red black tree
546eaad808eSchristos *
547eaad808eSchristos */
548*762909a6Schristos rbnode_type *
rbtree_first(rbtree_type * rbtree)549*762909a6Schristos rbtree_first (rbtree_type *rbtree)
550eaad808eSchristos {
551*762909a6Schristos rbnode_type *node;
552eaad808eSchristos
553eaad808eSchristos for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
554eaad808eSchristos return node;
555eaad808eSchristos }
556eaad808eSchristos
557*762909a6Schristos rbnode_type *
rbtree_last(rbtree_type * rbtree)558*762909a6Schristos rbtree_last (rbtree_type *rbtree)
559eaad808eSchristos {
560*762909a6Schristos rbnode_type *node;
561eaad808eSchristos
562eaad808eSchristos for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
563eaad808eSchristos return node;
564eaad808eSchristos }
565eaad808eSchristos
566eaad808eSchristos /*
567eaad808eSchristos * Returns the next node...
568eaad808eSchristos *
569eaad808eSchristos */
570*762909a6Schristos rbnode_type *
rbtree_next(rbnode_type * node)571*762909a6Schristos rbtree_next (rbnode_type *node)
572eaad808eSchristos {
573*762909a6Schristos rbnode_type *parent;
574eaad808eSchristos
575eaad808eSchristos if (node->right != RBTREE_NULL) {
576eaad808eSchristos /* One right, then keep on going left... */
577eaad808eSchristos for (node = node->right; node->left != RBTREE_NULL; node = node->left);
578eaad808eSchristos } else {
579eaad808eSchristos parent = node->parent;
580eaad808eSchristos while (parent != RBTREE_NULL && node == parent->right) {
581eaad808eSchristos node = parent;
582eaad808eSchristos parent = parent->parent;
583eaad808eSchristos }
584eaad808eSchristos node = parent;
585eaad808eSchristos }
586eaad808eSchristos return node;
587eaad808eSchristos }
588eaad808eSchristos
589*762909a6Schristos rbnode_type *
rbtree_previous(rbnode_type * node)590*762909a6Schristos rbtree_previous(rbnode_type *node)
591eaad808eSchristos {
592*762909a6Schristos rbnode_type *parent;
593eaad808eSchristos
594eaad808eSchristos if (node->left != RBTREE_NULL) {
595eaad808eSchristos /* One left, then keep on going right... */
596eaad808eSchristos for (node = node->left; node->right != RBTREE_NULL; node = node->right);
597eaad808eSchristos } else {
598eaad808eSchristos parent = node->parent;
599eaad808eSchristos while (parent != RBTREE_NULL && node == parent->left) {
600eaad808eSchristos node = parent;
601eaad808eSchristos parent = parent->parent;
602eaad808eSchristos }
603eaad808eSchristos node = parent;
604eaad808eSchristos }
605eaad808eSchristos return node;
606eaad808eSchristos }
607eaad808eSchristos
608eaad808eSchristos /** recursive descent traverse */
609eaad808eSchristos static void
traverse_post(void (* func)(rbnode_type *,void *),void * arg,rbnode_type * node)610*762909a6Schristos traverse_post(void (*func)(rbnode_type*, void*), void* arg, rbnode_type* node)
611eaad808eSchristos {
612eaad808eSchristos if(!node || node == RBTREE_NULL)
613eaad808eSchristos return;
614eaad808eSchristos /* recurse */
615eaad808eSchristos traverse_post(func, arg, node->left);
616eaad808eSchristos traverse_post(func, arg, node->right);
617eaad808eSchristos /* call user func */
618eaad808eSchristos (*func)(node, arg);
619eaad808eSchristos }
620eaad808eSchristos
621eaad808eSchristos void
traverse_postorder(rbtree_type * tree,void (* func)(rbnode_type *,void *),void * arg)622*762909a6Schristos traverse_postorder(rbtree_type* tree, void (*func)(rbnode_type*, void*),
623*762909a6Schristos void* arg)
624eaad808eSchristos {
625eaad808eSchristos traverse_post(func, arg, tree->root);
626eaad808eSchristos }
627