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