xref: /openbsd-src/sbin/unwind/libunbound/util/rbtree.c (revision ae8c6e27550649e7a558381bdb90c7b5a9042405)
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