[mirror_frr.git] / lib / typerb.c

/* RB-tree */

/*
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include "typerb.h"

#define RB_BLACK	0
#define RB_RED		1

#define rb_entry		typed_rb_entry
#define rbt_tree		typed_rb_root

#define RBE_LEFT(_rbe)		(_rbe)->rbt_left
#define RBE_RIGHT(_rbe)		(_rbe)->rbt_right
#define RBE_PARENT(_rbe)	(_rbe)->rbt_parent
#define RBE_COLOR(_rbe)		(_rbe)->rbt_color

#define RBH_ROOT(_rbt)		(_rbt)->rbt_root

static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
{
	RBE_PARENT(rbe) = parent;
	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
	RBE_COLOR(rbe) = RB_RED;
}

static inline void rbe_set_blackred(struct rb_entry *black,
				    struct rb_entry *red)
{
	RBE_COLOR(black) = RB_BLACK;
	RBE_COLOR(red) = RB_RED;
}

static inline void rbe_rotate_left(struct rbt_tree *rbt, struct rb_entry *rbe)
{
	struct rb_entry *parent;
	struct rb_entry *tmp;

	tmp = RBE_RIGHT(rbe);
	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
	if (RBE_RIGHT(rbe) != NULL)
		RBE_PARENT(RBE_LEFT(tmp)) = rbe;

	parent = RBE_PARENT(rbe);
	RBE_PARENT(tmp) = parent;
	if (parent != NULL) {
		if (rbe == RBE_LEFT(parent))
			RBE_LEFT(parent) = tmp;
		else
			RBE_RIGHT(parent) = tmp;
	} else
		RBH_ROOT(rbt) = tmp;

	RBE_LEFT(tmp) = rbe;
	RBE_PARENT(rbe) = tmp;
}

static inline void rbe_rotate_right(struct rbt_tree *rbt, struct rb_entry *rbe)
{
	struct rb_entry *parent;
	struct rb_entry *tmp;

	tmp = RBE_LEFT(rbe);
	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
	if (RBE_LEFT(rbe) != NULL)
		RBE_PARENT(RBE_RIGHT(tmp)) = rbe;

	parent = RBE_PARENT(rbe);
	RBE_PARENT(tmp) = parent;
	if (parent != NULL) {
		if (rbe == RBE_LEFT(parent))
			RBE_LEFT(parent) = tmp;
		else
			RBE_RIGHT(parent) = tmp;
	} else
		RBH_ROOT(rbt) = tmp;

	RBE_RIGHT(tmp) = rbe;
	RBE_PARENT(rbe) = tmp;
}

static inline void rbe_insert_color(struct rbt_tree *rbt, struct rb_entry *rbe)
{
	struct rb_entry *parent, *gparent, *tmp;

	rbt->count++;

	while ((parent = RBE_PARENT(rbe)) != NULL
	       && RBE_COLOR(parent) == RB_RED) {
		gparent = RBE_PARENT(parent);

		if (parent == RBE_LEFT(gparent)) {
			tmp = RBE_RIGHT(gparent);
			if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
				RBE_COLOR(tmp) = RB_BLACK;
				rbe_set_blackred(parent, gparent);
				rbe = gparent;
				continue;
			}

			if (RBE_RIGHT(parent) == rbe) {
				rbe_rotate_left(rbt, parent);
				tmp = parent;
				parent = rbe;
				rbe = tmp;
			}

			rbe_set_blackred(parent, gparent);
			rbe_rotate_right(rbt, gparent);
		} else {
			tmp = RBE_LEFT(gparent);
			if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
				RBE_COLOR(tmp) = RB_BLACK;
				rbe_set_blackred(parent, gparent);
				rbe = gparent;
				continue;
			}

			if (RBE_LEFT(parent) == rbe) {
				rbe_rotate_right(rbt, parent);
				tmp = parent;
				parent = rbe;
				rbe = tmp;
			}

			rbe_set_blackred(parent, gparent);
			rbe_rotate_left(rbt, gparent);
		}
	}

	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
}

static inline void rbe_remove_color(struct rbt_tree *rbt,
				    struct rb_entry *parent,
				    struct rb_entry *rbe)
{
	struct rb_entry *tmp;

	while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
	       && rbe != RBH_ROOT(rbt) && parent) {
		if (RBE_LEFT(parent) == rbe) {
			tmp = RBE_RIGHT(parent);
			if (RBE_COLOR(tmp) == RB_RED) {
				rbe_set_blackred(tmp, parent);
				rbe_rotate_left(rbt, parent);
				tmp = RBE_RIGHT(parent);
			}
			if ((RBE_LEFT(tmp) == NULL
			     || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
			    && (RBE_RIGHT(tmp) == NULL
				|| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
				RBE_COLOR(tmp) = RB_RED;
				rbe = parent;
				parent = RBE_PARENT(rbe);
			} else {
				if (RBE_RIGHT(tmp) == NULL
				    || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
					struct rb_entry *oleft;

					oleft = RBE_LEFT(tmp);
					if (oleft != NULL)
						RBE_COLOR(oleft) = RB_BLACK;

					RBE_COLOR(tmp) = RB_RED;
					rbe_rotate_right(rbt, tmp);
					tmp = RBE_RIGHT(parent);
				}

				RBE_COLOR(tmp) = RBE_COLOR(parent);
				RBE_COLOR(parent) = RB_BLACK;
				if (RBE_RIGHT(tmp))
					RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;

				rbe_rotate_left(rbt, parent);
				rbe = RBH_ROOT(rbt);
				break;
			}
		} else {
			tmp = RBE_LEFT(parent);
			if (RBE_COLOR(tmp) == RB_RED) {
				rbe_set_blackred(tmp, parent);
				rbe_rotate_right(rbt, parent);
				tmp = RBE_LEFT(parent);
			}

			if ((RBE_LEFT(tmp) == NULL
			     || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
			    && (RBE_RIGHT(tmp) == NULL
				|| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
				RBE_COLOR(tmp) = RB_RED;
				rbe = parent;
				parent = RBE_PARENT(rbe);
			} else {
				if (RBE_LEFT(tmp) == NULL
				    || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
					struct rb_entry *oright;

					oright = RBE_RIGHT(tmp);
					if (oright != NULL)
						RBE_COLOR(oright) = RB_BLACK;

					RBE_COLOR(tmp) = RB_RED;
					rbe_rotate_left(rbt, tmp);
					tmp = RBE_LEFT(parent);
				}

				RBE_COLOR(tmp) = RBE_COLOR(parent);
				RBE_COLOR(parent) = RB_BLACK;
				if (RBE_LEFT(tmp) != NULL)
					RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;

				rbe_rotate_right(rbt, parent);
				rbe = RBH_ROOT(rbt);
				break;
			}
		}
	}

	if (rbe != NULL)
		RBE_COLOR(rbe) = RB_BLACK;
}

static inline struct rb_entry *
rbe_remove(struct rbt_tree *rbt, struct rb_entry *rbe)
{
	struct rb_entry *child, *parent, *old = rbe;
	unsigned int color;

	if (RBE_LEFT(rbe) == NULL)
		child = RBE_RIGHT(rbe);
	else if (RBE_RIGHT(rbe) == NULL)
		child = RBE_LEFT(rbe);
	else {
		struct rb_entry *tmp;

		rbe = RBE_RIGHT(rbe);
		while ((tmp = RBE_LEFT(rbe)) != NULL)
			rbe = tmp;

		child = RBE_RIGHT(rbe);
		parent = RBE_PARENT(rbe);
		color = RBE_COLOR(rbe);
		if (child != NULL)
			RBE_PARENT(child) = parent;
		if (parent != NULL) {
			if (RBE_LEFT(parent) == rbe)
				RBE_LEFT(parent) = child;
			else
				RBE_RIGHT(parent) = child;
		} else
			RBH_ROOT(rbt) = child;
		if (RBE_PARENT(rbe) == old)
			parent = rbe;
		*rbe = *old;

		tmp = RBE_PARENT(old);
		if (tmp != NULL) {
			if (RBE_LEFT(tmp) == old)
				RBE_LEFT(tmp) = rbe;
			else
				RBE_RIGHT(tmp) = rbe;
		} else
			RBH_ROOT(rbt) = rbe;

		RBE_PARENT(RBE_LEFT(old)) = rbe;
		if (RBE_RIGHT(old))
			RBE_PARENT(RBE_RIGHT(old)) = rbe;

		goto color;
	}

	parent = RBE_PARENT(rbe);
	color = RBE_COLOR(rbe);

	if (child != NULL)
		RBE_PARENT(child) = parent;
	if (parent != NULL) {
		if (RBE_LEFT(parent) == rbe)
			RBE_LEFT(parent) = child;
		else
			RBE_RIGHT(parent) = child;
	} else
		RBH_ROOT(rbt) = child;
color:
	if (color == RB_BLACK)
		rbe_remove_color(rbt, parent, child);

	rbt->count--;
	return (old);
}

void typed_rb_remove(struct rbt_tree *rbt, struct rb_entry *rbe)
{
	rbe_remove(rbt, rbe);
}

struct typed_rb_entry *typed_rb_insert(struct rbt_tree *rbt,
		struct rb_entry *rbe, int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b))
{
	struct rb_entry *tmp;
	struct rb_entry *parent = NULL;
	int comp = 0;

	tmp = RBH_ROOT(rbt);
	while (tmp != NULL) {
		parent = tmp;

		comp = cmpfn(rbe, tmp);
		if (comp < 0)
			tmp = RBE_LEFT(tmp);
		else if (comp > 0)
			tmp = RBE_RIGHT(tmp);
		else
			return tmp;
	}

	rbe_set(rbe, parent);

	if (parent != NULL) {
		if (comp < 0)
			RBE_LEFT(parent) = rbe;
		else
			RBE_RIGHT(parent) = rbe;
	} else
		RBH_ROOT(rbt) = rbe;

	rbe_insert_color(rbt, rbe);

	return NULL;
}

/* Finds the node with the same key as elm */
struct rb_entry *typed_rb_find(struct rbt_tree *rbt, const struct rb_entry *key,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b))
{
	struct rb_entry *tmp = RBH_ROOT(rbt);
	int comp;

	while (tmp != NULL) {
		comp = cmpfn(key, tmp);
		if (comp < 0)
			tmp = RBE_LEFT(tmp);
		else if (comp > 0)
			tmp = RBE_RIGHT(tmp);
		else
			return tmp;
	}

	return (NULL);
}

struct rb_entry *typed_rb_find_gteq(struct rbt_tree *rbt,
		const struct rb_entry *key,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b))
{
	struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
	int comp;

	while (tmp != NULL) {
		comp = cmpfn(key, tmp);
		if (comp < 0) {
			best = tmp;
			tmp = RBE_LEFT(tmp);
		} else if (comp > 0)
			tmp = RBE_RIGHT(tmp);
		else
			return tmp;
	}

	return best;
}

struct rb_entry *typed_rb_find_lt(struct rbt_tree *rbt,
		const struct rb_entry *key,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b))
{
	struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
	int comp;

	while (tmp != NULL) {
		comp = cmpfn(key, tmp);
		if (comp <= 0)
			tmp = RBE_LEFT(tmp);
		else {
			best = tmp;
			tmp = RBE_RIGHT(tmp);
		}
	}

	return best;
}

struct rb_entry *typed_rb_next(struct rb_entry *rbe)
{
	if (RBE_RIGHT(rbe) != NULL) {
		rbe = RBE_RIGHT(rbe);
		while (RBE_LEFT(rbe) != NULL)
			rbe = RBE_LEFT(rbe);
	} else {
		if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
			rbe = RBE_PARENT(rbe);
		else {
			while (RBE_PARENT(rbe)
			       && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
				rbe = RBE_PARENT(rbe);
			rbe = RBE_PARENT(rbe);
		}
	}

	return rbe;
}

struct rb_entry *typed_rb_min(struct rbt_tree *rbt)
{
	struct rb_entry *rbe = RBH_ROOT(rbt);
	struct rb_entry *parent = NULL;

	while (rbe != NULL) {
		parent = rbe;
		rbe = RBE_LEFT(rbe);
	}

	return parent;
}
Commit	Line	Data
80911bc2 DL	1	/* RB-tree */
	2
	3	/*
	4	* Copyright 2002 Niels Provos <provos@citi.umich.edu>
	5	* All rights reserved.
	6	*
	7	* Redistribution and use in source and binary forms, with or without
	8	* modification, are permitted provided that the following conditions
	9	* are met:
	10	* 1. Redistributions of source code must retain the above copyright
	11	* notice, this list of conditions and the following disclaimer.
	12	* 2. Redistributions in binary form must reproduce the above copyright
	13	* notice, this list of conditions and the following disclaimer in the
	14	* documentation and/or other materials provided with the distribution.
	15	*
	16	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
	17	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
	18	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
	19	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
	20	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
	21	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	22	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	23	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	24	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
	25	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	26	*/
	27
	28	/*
	29	* Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
	30	*
	31	* Permission to use, copy, modify, and distribute this software for any
	32	* purpose with or without fee is hereby granted, provided that the above
	33	* copyright notice and this permission notice appear in all copies.
	34	*
	35	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	36	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	37	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
	38	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	39	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	40	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	41	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
	42	*/
	43
	44	#include "typerb.h"
	45
	46	#define RB_BLACK 0
	47	#define RB_RED 1
	48
	49	#define rb_entry typed_rb_entry
	50	#define rbt_tree typed_rb_root
	51
	52	#define RBE_LEFT(_rbe) (_rbe)->rbt_left
	53	#define RBE_RIGHT(_rbe) (_rbe)->rbt_right
	54	#define RBE_PARENT(_rbe) (_rbe)->rbt_parent
	55	#define RBE_COLOR(_rbe) (_rbe)->rbt_color
	56
	57	#define RBH_ROOT(_rbt) (_rbt)->rbt_root
	58
	59	static inline void rbe_set(struct rb_entry rbe, struct rb_entry parent)
	60	{
	61	RBE_PARENT(rbe) = parent;
	62	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
	63	RBE_COLOR(rbe) = RB_RED;
	64	}
65
66	static inline void rbe_set_blackred(struct rb_entry *black,
67	struct rb_entry *red)
68	{
69	RBE_COLOR(black) = RB_BLACK;
70	RBE_COLOR(red) = RB_RED;
71	}
72
73	static inline void rbe_rotate_left(struct rbt_tree rbt, struct rb_entry rbe)
74	{
75	struct rb_entry *parent;
76	struct rb_entry *tmp;
77
78	tmp = RBE_RIGHT(rbe);
79	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
80	if (RBE_RIGHT(rbe) != NULL)
81	RBE_PARENT(RBE_LEFT(tmp)) = rbe;
82
83	parent = RBE_PARENT(rbe);
84	RBE_PARENT(tmp) = parent;
85	if (parent != NULL) {
86	if (rbe == RBE_LEFT(parent))
87	RBE_LEFT(parent) = tmp;
88	else
89	RBE_RIGHT(parent) = tmp;
90	} else
91	RBH_ROOT(rbt) = tmp;
92
93	RBE_LEFT(tmp) = rbe;
94	RBE_PARENT(rbe) = tmp;
95	}
96
97	static inline void rbe_rotate_right(struct rbt_tree rbt, struct rb_entry rbe)
98	{
99	struct rb_entry *parent;
100	struct rb_entry *tmp;
101
102	tmp = RBE_LEFT(rbe);
103	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
104	if (RBE_LEFT(rbe) != NULL)
105	RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
106
107	parent = RBE_PARENT(rbe);
108	RBE_PARENT(tmp) = parent;
109	if (parent != NULL) {
110	if (rbe == RBE_LEFT(parent))
111	RBE_LEFT(parent) = tmp;
112	else
113	RBE_RIGHT(parent) = tmp;
114	} else
115	RBH_ROOT(rbt) = tmp;
116
117	RBE_RIGHT(tmp) = rbe;
118	RBE_PARENT(rbe) = tmp;
119	}
120
121	static inline void rbe_insert_color(struct rbt_tree rbt, struct rb_entry rbe)
122	{
123	struct rb_entry parent, gparent, *tmp;
124
125	rbt->count++;
126
127	while ((parent = RBE_PARENT(rbe)) != NULL
128	&& RBE_COLOR(parent) == RB_RED) {
129	gparent = RBE_PARENT(parent);
130
131	if (parent == RBE_LEFT(gparent)) {
132	tmp = RBE_RIGHT(gparent);
133	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
134	RBE_COLOR(tmp) = RB_BLACK;
135	rbe_set_blackred(parent, gparent);
136	rbe = gparent;
137	continue;
138	}
139
140	if (RBE_RIGHT(parent) == rbe) {
141	rbe_rotate_left(rbt, parent);
142	tmp = parent;
143	parent = rbe;
144	rbe = tmp;
145	}
146
147	rbe_set_blackred(parent, gparent);
148	rbe_rotate_right(rbt, gparent);
149	} else {
150	tmp = RBE_LEFT(gparent);
151	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
152	RBE_COLOR(tmp) = RB_BLACK;
153	rbe_set_blackred(parent, gparent);
154	rbe = gparent;
155	continue;
156	}
157
158	if (RBE_LEFT(parent) == rbe) {
159	rbe_rotate_right(rbt, parent);
160	tmp = parent;
161	parent = rbe;
162	rbe = tmp;
163	}
164
165	rbe_set_blackred(parent, gparent);
166	rbe_rotate_left(rbt, gparent);
167	}
168	}
169
170	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
171	}
172
173	static inline void rbe_remove_color(struct rbt_tree *rbt,
174	struct rb_entry *parent,
175	struct rb_entry *rbe)
176	{
177	struct rb_entry *tmp;
178
179	while ((rbe == NULL \|\| RBE_COLOR(rbe) == RB_BLACK)
180	&& rbe != RBH_ROOT(rbt) && parent) {
181	if (RBE_LEFT(parent) == rbe) {
182	tmp = RBE_RIGHT(parent);
183	if (RBE_COLOR(tmp) == RB_RED) {
184	rbe_set_blackred(tmp, parent);
185	rbe_rotate_left(rbt, parent);
186	tmp = RBE_RIGHT(parent);
187	}
188	if ((RBE_LEFT(tmp) == NULL
189	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
190	&& (RBE_RIGHT(tmp) == NULL
191	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
192	RBE_COLOR(tmp) = RB_RED;
193	rbe = parent;
194	parent = RBE_PARENT(rbe);
195	} else {
196	if (RBE_RIGHT(tmp) == NULL
197	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
198	struct rb_entry *oleft;
199
200	oleft = RBE_LEFT(tmp);
201	if (oleft != NULL)
202	RBE_COLOR(oleft) = RB_BLACK;
203
204	RBE_COLOR(tmp) = RB_RED;
205	rbe_rotate_right(rbt, tmp);
206	tmp = RBE_RIGHT(parent);
207	}
208
209	RBE_COLOR(tmp) = RBE_COLOR(parent);
210	RBE_COLOR(parent) = RB_BLACK;
211	if (RBE_RIGHT(tmp))
212	RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
213
214	rbe_rotate_left(rbt, parent);
215	rbe = RBH_ROOT(rbt);
216	break;
217	}
218	} else {
219	tmp = RBE_LEFT(parent);
220	if (RBE_COLOR(tmp) == RB_RED) {
221	rbe_set_blackred(tmp, parent);
222	rbe_rotate_right(rbt, parent);
223	tmp = RBE_LEFT(parent);
224	}
225
226	if ((RBE_LEFT(tmp) == NULL
227	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
228	&& (RBE_RIGHT(tmp) == NULL
229	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
230	RBE_COLOR(tmp) = RB_RED;
231	rbe = parent;
232	parent = RBE_PARENT(rbe);
233	} else {
234	if (RBE_LEFT(tmp) == NULL
235	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
236	struct rb_entry *oright;
237
238	oright = RBE_RIGHT(tmp);
239	if (oright != NULL)
240	RBE_COLOR(oright) = RB_BLACK;
241
242	RBE_COLOR(tmp) = RB_RED;
243	rbe_rotate_left(rbt, tmp);
244	tmp = RBE_LEFT(parent);
245	}
246
247	RBE_COLOR(tmp) = RBE_COLOR(parent);
248	RBE_COLOR(parent) = RB_BLACK;
249	if (RBE_LEFT(tmp) != NULL)
250	RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
251
252	rbe_rotate_right(rbt, parent);
253	rbe = RBH_ROOT(rbt);
254	break;
255	}
256	}
257	}
258
259	if (rbe != NULL)
260	RBE_COLOR(rbe) = RB_BLACK;
261	}
262
263	static inline struct rb_entry *
264	rbe_remove(struct rbt_tree rbt, struct rb_entry rbe)
265	{
266	struct rb_entry child, parent, *old = rbe;
267	unsigned int color;
268
269	if (RBE_LEFT(rbe) == NULL)
270	child = RBE_RIGHT(rbe);
271	else if (RBE_RIGHT(rbe) == NULL)
272	child = RBE_LEFT(rbe);
273	else {
274	struct rb_entry *tmp;
275
276	rbe = RBE_RIGHT(rbe);
277	while ((tmp = RBE_LEFT(rbe)) != NULL)
278	rbe = tmp;
279
280	child = RBE_RIGHT(rbe);
281	parent = RBE_PARENT(rbe);
282	color = RBE_COLOR(rbe);
283	if (child != NULL)
284	RBE_PARENT(child) = parent;
285	if (parent != NULL) {
286	if (RBE_LEFT(parent) == rbe)
287	RBE_LEFT(parent) = child;
288	else
289	RBE_RIGHT(parent) = child;
290	} else
291	RBH_ROOT(rbt) = child;
292	if (RBE_PARENT(rbe) == old)
293	parent = rbe;
294	rbe = old;
295
296	tmp = RBE_PARENT(old);
297	if (tmp != NULL) {
298	if (RBE_LEFT(tmp) == old)
299	RBE_LEFT(tmp) = rbe;
300	else
301	RBE_RIGHT(tmp) = rbe;
302	} else
303	RBH_ROOT(rbt) = rbe;
304
305	RBE_PARENT(RBE_LEFT(old)) = rbe;
306	if (RBE_RIGHT(old))
307	RBE_PARENT(RBE_RIGHT(old)) = rbe;
308
309	goto color;
310	}
311
312	parent = RBE_PARENT(rbe);
313	color = RBE_COLOR(rbe);
314
315	if (child != NULL)
316	RBE_PARENT(child) = parent;
317	if (parent != NULL) {
318	if (RBE_LEFT(parent) == rbe)
319	RBE_LEFT(parent) = child;
320	else
321	RBE_RIGHT(parent) = child;
322	} else
323	RBH_ROOT(rbt) = child;
324	color:
325	if (color == RB_BLACK)
326	rbe_remove_color(rbt, parent, child);
327
328	rbt->count--;
329	return (old);
330	}
331
332	void typed_rb_remove(struct rbt_tree rbt, struct rb_entry rbe)
333	{
334	rbe_remove(rbt, rbe);
335	}
336
337	struct typed_rb_entry typed_rb_insert(struct rbt_tree rbt,
338	struct rb_entry rbe, int (cmpfn)(
339	const struct typed_rb_entry *a,
340	const struct typed_rb_entry *b))
341	{
342	struct rb_entry *tmp;
343	struct rb_entry *parent = NULL;
344	int comp = 0;
345
346	tmp = RBH_ROOT(rbt);
347	while (tmp != NULL) {
348	parent = tmp;
349
350	comp = cmpfn(rbe, tmp);
351	if (comp < 0)
352	tmp = RBE_LEFT(tmp);
353	else if (comp > 0)
354	tmp = RBE_RIGHT(tmp);
355	else
356	return tmp;
357	}
358
359	rbe_set(rbe, parent);
360
361	if (parent != NULL) {
362	if (comp < 0)
363	RBE_LEFT(parent) = rbe;
364	else
365	RBE_RIGHT(parent) = rbe;
366	} else
367	RBH_ROOT(rbt) = rbe;
368
369	rbe_insert_color(rbt, rbe);
370
371	return NULL;
372	}
373
374	/* Finds the node with the same key as elm */
375	struct rb_entry typed_rb_find(struct rbt_tree rbt, const struct rb_entry *key,
376	int (*cmpfn)(
377	const struct typed_rb_entry *a,
378	const struct typed_rb_entry *b))
379	{
380	struct rb_entry *tmp = RBH_ROOT(rbt);
381	int comp;
382
383	while (tmp != NULL) {
384	comp = cmpfn(key, tmp);
385	if (comp < 0)
386	tmp = RBE_LEFT(tmp);
387	else if (comp > 0)
388	tmp = RBE_RIGHT(tmp);
389	else
390	return tmp;
391	}
392
393	return (NULL);
394	}
395
396	struct rb_entry typed_rb_find_gteq(struct rbt_tree rbt,
397	const struct rb_entry *key,
398	int (*cmpfn)(
399	const struct typed_rb_entry *a,
400	const struct typed_rb_entry *b))
401	{
402	struct rb_entry tmp = RBH_ROOT(rbt), best = NULL;
403	int comp;
404
405	while (tmp != NULL) {
406	comp = cmpfn(key, tmp);
407	if (comp < 0) {
408	best = tmp;
409	tmp = RBE_LEFT(tmp);
410	} else if (comp > 0)
411	tmp = RBE_RIGHT(tmp);
412	else
413	return tmp;
414	}
415
416	return best;
417	}
418
419	struct rb_entry typed_rb_find_lt(struct rbt_tree rbt,
420	const struct rb_entry *key,
421	int (*cmpfn)(
422	const struct typed_rb_entry *a,
423	const struct typed_rb_entry *b))
424	{
425	struct rb_entry tmp = RBH_ROOT(rbt), best = NULL;
426	int comp;
427
428	while (tmp != NULL) {
429	comp = cmpfn(key, tmp);
430	if (comp <= 0)
431	tmp = RBE_LEFT(tmp);
432	else {
433	best = tmp;
434	tmp = RBE_RIGHT(tmp);
435	}
436	}
437
438	return best;
439	}
440
441	struct rb_entry typed_rb_next(struct rb_entry rbe)
442	{
443	if (RBE_RIGHT(rbe) != NULL) {
444	rbe = RBE_RIGHT(rbe);
445	while (RBE_LEFT(rbe) != NULL)
446	rbe = RBE_LEFT(rbe);
447	} else {
448	if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
449	rbe = RBE_PARENT(rbe);
450	else {
451	while (RBE_PARENT(rbe)
452	&& (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
453	rbe = RBE_PARENT(rbe);
454	rbe = RBE_PARENT(rbe);
455	}
456	}
457
458	return rbe;
459	}
460
461	struct rb_entry typed_rb_min(struct rbt_tree rbt)
462	{
463	struct rb_entry *rbe = RBH_ROOT(rbt);
464	struct rb_entry *parent = NULL;
465
466	while (rbe != NULL) {
467	parent = rbe;
468	rbe = RBE_LEFT(rbe);
469	}
470
471	return parent;
472	}