• file
• revisions
• annotate
• diff
• comparison
• raw

ipc/chromium/src/third_party/libevent/WIN32-Code/tree.h@6474c204b198 (annotated)

ipc/chromium/src/third_party/libevent/WIN32-Code/tree.h

Wed, 31 Dec 2014 06:09:35 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Wed, 31 Dec 2014 06:09:35 +0100

changeset 0

6474c204b198

permissions

-rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

michael@0	1	/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
michael@0	2	/*
michael@0	3	* Copyright 2002 Niels Provos <provos@citi.umich.edu>
michael@0	4	* All rights reserved.
michael@0	5	*
michael@0	6	* Redistribution and use in source and binary forms, with or without
michael@0	7	* modification, are permitted provided that the following conditions
michael@0	8	* are met:
michael@0	9	* 1. Redistributions of source code must retain the above copyright
michael@0	10	* notice, this list of conditions and the following disclaimer.
michael@0	11	* 2. Redistributions in binary form must reproduce the above copyright
michael@0	12	* notice, this list of conditions and the following disclaimer in the
michael@0	13	* documentation and/or other materials provided with the distribution.
michael@0	14	*
michael@0	15	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
michael@0	16	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
michael@0	17	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
michael@0	18	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
michael@0	19	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
michael@0	20	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
michael@0	21	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
michael@0	22	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
michael@0	23	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
michael@0	24	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0	25	*/
michael@0	26
michael@0	27	#ifndef _SYS_TREE_H_
michael@0	28	#define _SYS_TREE_H_
michael@0	29
michael@0	30	/*
michael@0	31	* This file defines data structures for different types of trees:
michael@0	32	* splay trees and red-black trees.
michael@0	33	*
michael@0	34	* A splay tree is a self-organizing data structure. Every operation
michael@0	35	* on the tree causes a splay to happen. The splay moves the requested
michael@0	36	* node to the root of the tree and partly rebalances it.
michael@0	37	*
michael@0	38	* This has the benefit that request locality causes faster lookups as
michael@0	39	* the requested nodes move to the top of the tree. On the other hand,
michael@0	40	* every lookup causes memory writes.
michael@0	41	*
michael@0	42	* The Balance Theorem bounds the total access time for m operations
michael@0	43	* and n inserts on an initially empty tree as O((m + n)lg n). The
michael@0	44	* amortized cost for a sequence of m accesses to a splay tree is O(lg n);
michael@0	45	*
michael@0	46	* A red-black tree is a binary search tree with the node color as an
michael@0	47	* extra attribute. It fulfills a set of conditions:
michael@0	48	* - every search path from the root to a leaf consists of the
michael@0	49	* same number of black nodes,
michael@0	50	* - each red node (except for the root) has a black parent,
michael@0	51	* - each leaf node is black.
michael@0	52	*
michael@0	53	* Every operation on a red-black tree is bounded as O(lg n).
michael@0	54	* The maximum height of a red-black tree is 2lg (n+1).
michael@0	55	*/
michael@0	56
michael@0	57	#define SPLAY_HEAD(name, type) \
michael@0	58	struct name { \
michael@0	59	struct type *sph_root; /* root of the tree */ \
michael@0	60	}
michael@0	61
michael@0	62	#define SPLAY_INITIALIZER(root) \
michael@0	63	{ NULL }
michael@0	64
michael@0	65	#define SPLAY_INIT(root) do { \
michael@0	66	(root)->sph_root = NULL; \
michael@0	67	} while (0)
michael@0	68
michael@0	69	#define SPLAY_ENTRY(type) \
michael@0	70	struct { \
michael@0	71	struct type *spe_left; /* left element */ \
michael@0	72	struct type *spe_right; /* right element */ \
michael@0	73	}
michael@0	74
michael@0	75	#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
michael@0	76	#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
michael@0	77	#define SPLAY_ROOT(head) (head)->sph_root
michael@0	78	#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
michael@0	79
michael@0	80	/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
michael@0	81	#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
michael@0	82	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
michael@0	83	SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
michael@0	84	(head)->sph_root = tmp; \
michael@0	85	} while (0)
michael@0	86
michael@0	87	#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
michael@0	88	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
michael@0	89	SPLAY_LEFT(tmp, field) = (head)->sph_root; \
michael@0	90	(head)->sph_root = tmp; \
michael@0	91	} while (0)
michael@0	92
michael@0	93	#define SPLAY_LINKLEFT(head, tmp, field) do { \
michael@0	94	SPLAY_LEFT(tmp, field) = (head)->sph_root; \
michael@0	95	tmp = (head)->sph_root; \
michael@0	96	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
michael@0	97	} while (0)
michael@0	98
michael@0	99	#define SPLAY_LINKRIGHT(head, tmp, field) do { \
michael@0	100	SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
michael@0	101	tmp = (head)->sph_root; \
michael@0	102	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
michael@0	103	} while (0)
michael@0	104
michael@0	105	#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
michael@0	106	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
michael@0	107	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
michael@0	108	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
michael@0	109	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
michael@0	110	} while (0)
michael@0	111
michael@0	112	/* Generates prototypes and inline functions */
michael@0	113
michael@0	114	#define SPLAY_PROTOTYPE(name, type, field, cmp) \
michael@0	115	void name##_SPLAY(struct name *, struct type *); \
michael@0	116	void name##_SPLAY_MINMAX(struct name *, int); \
michael@0	117	struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
michael@0	118	struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
michael@0	119	\
michael@0	120	/* Finds the node with the same key as elm */ \
michael@0	121	static __inline struct type * \
michael@0	122	name##_SPLAY_FIND(struct name *head, struct type *elm) \
michael@0	123	{ \
michael@0	124	if (SPLAY_EMPTY(head)) \
michael@0	125	return(NULL); \
michael@0	126	name##_SPLAY(head, elm); \
michael@0	127	if ((cmp)(elm, (head)->sph_root) == 0) \
michael@0	128	return (head->sph_root); \
michael@0	129	return (NULL); \
michael@0	130	} \
michael@0	131	\
michael@0	132	static __inline struct type * \
michael@0	133	name##_SPLAY_NEXT(struct name *head, struct type *elm) \
michael@0	134	{ \
michael@0	135	name##_SPLAY(head, elm); \
michael@0	136	if (SPLAY_RIGHT(elm, field) != NULL) { \
michael@0	137	elm = SPLAY_RIGHT(elm, field); \
michael@0	138	while (SPLAY_LEFT(elm, field) != NULL) { \
michael@0	139	elm = SPLAY_LEFT(elm, field); \
michael@0	140	} \
michael@0	141	} else \
michael@0	142	elm = NULL; \
michael@0	143	return (elm); \
michael@0	144	} \
michael@0	145	\
michael@0	146	static __inline struct type * \
michael@0	147	name##_SPLAY_MIN_MAX(struct name *head, int val) \
michael@0	148	{ \
michael@0	149	name##_SPLAY_MINMAX(head, val); \
michael@0	150	return (SPLAY_ROOT(head)); \
michael@0	151	}
michael@0	152
michael@0	153	/* Main splay operation.
michael@0	154	* Moves node close to the key of elm to top
michael@0	155	*/
michael@0	156	#define SPLAY_GENERATE(name, type, field, cmp) \
michael@0	157	struct type * \
michael@0	158	name##_SPLAY_INSERT(struct name *head, struct type *elm) \
michael@0	159	{ \
michael@0	160	if (SPLAY_EMPTY(head)) { \
michael@0	161	SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
michael@0	162	} else { \
michael@0	163	int __comp; \
michael@0	164	name##_SPLAY(head, elm); \
michael@0	165	__comp = (cmp)(elm, (head)->sph_root); \
michael@0	166	if(__comp < 0) { \
michael@0	167	SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
michael@0	168	SPLAY_RIGHT(elm, field) = (head)->sph_root; \
michael@0	169	SPLAY_LEFT((head)->sph_root, field) = NULL; \
michael@0	170	} else if (__comp > 0) { \
michael@0	171	SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
michael@0	172	SPLAY_LEFT(elm, field) = (head)->sph_root; \
michael@0	173	SPLAY_RIGHT((head)->sph_root, field) = NULL; \
michael@0	174	} else \
michael@0	175	return ((head)->sph_root); \
michael@0	176	} \
michael@0	177	(head)->sph_root = (elm); \
michael@0	178	return (NULL); \
michael@0	179	} \
michael@0	180	\
michael@0	181	struct type * \
michael@0	182	name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
michael@0	183	{ \
michael@0	184	struct type *__tmp; \
michael@0	185	if (SPLAY_EMPTY(head)) \
michael@0	186	return (NULL); \
michael@0	187	name##_SPLAY(head, elm); \
michael@0	188	if ((cmp)(elm, (head)->sph_root) == 0) { \
michael@0	189	if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
michael@0	190	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
michael@0	191	} else { \
michael@0	192	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
michael@0	193	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
michael@0	194	name##_SPLAY(head, elm); \
michael@0	195	SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
michael@0	196	} \
michael@0	197	return (elm); \
michael@0	198	} \
michael@0	199	return (NULL); \
michael@0	200	} \
michael@0	201	\
michael@0	202	void \
michael@0	203	name##_SPLAY(struct name *head, struct type *elm) \
michael@0	204	{ \
michael@0	205	struct type __node, *__left, *__right, *__tmp; \
michael@0	206	int __comp; \
michael@0	207	\
michael@0	208	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
michael@0	209	__left = __right = &__node; \
michael@0	210	\
michael@0	211	while ((__comp = (cmp)(elm, (head)->sph_root))) { \
michael@0	212	if (__comp < 0) { \
michael@0	213	__tmp = SPLAY_LEFT((head)->sph_root, field); \
michael@0	214	if (__tmp == NULL) \
michael@0	215	break; \
michael@0	216	if ((cmp)(elm, __tmp) < 0){ \
michael@0	217	SPLAY_ROTATE_RIGHT(head, __tmp, field); \
michael@0	218	if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
michael@0	219	break; \
michael@0	220	} \
michael@0	221	SPLAY_LINKLEFT(head, __right, field); \
michael@0	222	} else if (__comp > 0) { \
michael@0	223	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
michael@0	224	if (__tmp == NULL) \
michael@0	225	break; \
michael@0	226	if ((cmp)(elm, __tmp) > 0){ \
michael@0	227	SPLAY_ROTATE_LEFT(head, __tmp, field); \
michael@0	228	if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
michael@0	229	break; \
michael@0	230	} \
michael@0	231	SPLAY_LINKRIGHT(head, __left, field); \
michael@0	232	} \
michael@0	233	} \
michael@0	234	SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
michael@0	235	} \
michael@0	236	\
michael@0	237	/* Splay with either the minimum or the maximum element \
michael@0	238	* Used to find minimum or maximum element in tree. \
michael@0	239	*/ \
michael@0	240	void name##_SPLAY_MINMAX(struct name *head, int __comp) \
michael@0	241	{ \
michael@0	242	struct type __node, *__left, *__right, *__tmp; \
michael@0	243	\
michael@0	244	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
michael@0	245	__left = __right = &__node; \
michael@0	246	\
michael@0	247	while (1) { \
michael@0	248	if (__comp < 0) { \
michael@0	249	__tmp = SPLAY_LEFT((head)->sph_root, field); \
michael@0	250	if (__tmp == NULL) \
michael@0	251	break; \
michael@0	252	if (__comp < 0){ \
michael@0	253	SPLAY_ROTATE_RIGHT(head, __tmp, field); \
michael@0	254	if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
michael@0	255	break; \
michael@0	256	} \
michael@0	257	SPLAY_LINKLEFT(head, __right, field); \
michael@0	258	} else if (__comp > 0) { \
michael@0	259	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
michael@0	260	if (__tmp == NULL) \
michael@0	261	break; \
michael@0	262	if (__comp > 0) { \
michael@0	263	SPLAY_ROTATE_LEFT(head, __tmp, field); \
michael@0	264	if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
michael@0	265	break; \
michael@0	266	} \
michael@0	267	SPLAY_LINKRIGHT(head, __left, field); \
michael@0	268	} \
michael@0	269	} \
michael@0	270	SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
michael@0	271	}
michael@0	272
michael@0	273	#define SPLAY_NEGINF -1
michael@0	274	#define SPLAY_INF 1
michael@0	275
michael@0	276	#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
michael@0	277	#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
michael@0	278	#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
michael@0	279	#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
michael@0	280	#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
michael@0	281	: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
michael@0	282	#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
michael@0	283	: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
michael@0	284
michael@0	285	#define SPLAY_FOREACH(x, name, head) \
michael@0	286	for ((x) = SPLAY_MIN(name, head); \
michael@0	287	(x) != NULL; \
michael@0	288	(x) = SPLAY_NEXT(name, head, x))
michael@0	289
michael@0	290	/* Macros that define a red-back tree */
michael@0	291	#define RB_HEAD(name, type) \
michael@0	292	struct name { \
michael@0	293	struct type *rbh_root; /* root of the tree */ \
michael@0	294	}
michael@0	295
michael@0	296	#define RB_INITIALIZER(root) \
michael@0	297	{ NULL }
michael@0	298
michael@0	299	#define RB_INIT(root) do { \
michael@0	300	(root)->rbh_root = NULL; \
michael@0	301	} while (0)
michael@0	302
michael@0	303	#define RB_BLACK 0
michael@0	304	#define RB_RED 1
michael@0	305	#define RB_ENTRY(type) \
michael@0	306	struct { \
michael@0	307	struct type *rbe_left; /* left element */ \
michael@0	308	struct type *rbe_right; /* right element */ \
michael@0	309	struct type *rbe_parent; /* parent element */ \
michael@0	310	int rbe_color; /* node color */ \
michael@0	311	}
michael@0	312
michael@0	313	#define RB_LEFT(elm, field) (elm)->field.rbe_left
michael@0	314	#define RB_RIGHT(elm, field) (elm)->field.rbe_right
michael@0	315	#define RB_PARENT(elm, field) (elm)->field.rbe_parent
michael@0	316	#define RB_COLOR(elm, field) (elm)->field.rbe_color
michael@0	317	#define RB_ROOT(head) (head)->rbh_root
michael@0	318	#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
michael@0	319
michael@0	320	#define RB_SET(elm, parent, field) do { \
michael@0	321	RB_PARENT(elm, field) = parent; \
michael@0	322	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
michael@0	323	RB_COLOR(elm, field) = RB_RED; \
michael@0	324	} while (0)
michael@0	325
michael@0	326	#define RB_SET_BLACKRED(black, red, field) do { \
michael@0	327	RB_COLOR(black, field) = RB_BLACK; \
michael@0	328	RB_COLOR(red, field) = RB_RED; \
michael@0	329	} while (0)
michael@0	330
michael@0	331	#ifndef RB_AUGMENT
michael@0	332	#define RB_AUGMENT(x)
michael@0	333	#endif
michael@0	334
michael@0	335	#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
michael@0	336	(tmp) = RB_RIGHT(elm, field); \
michael@0	337	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
michael@0	338	RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
michael@0	339	} \
michael@0	340	RB_AUGMENT(elm); \
michael@0	341	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
michael@0	342	if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
michael@0	343	RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
michael@0	344	else \
michael@0	345	RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
michael@0	346	} else \
michael@0	347	(head)->rbh_root = (tmp); \
michael@0	348	RB_LEFT(tmp, field) = (elm); \
michael@0	349	RB_PARENT(elm, field) = (tmp); \
michael@0	350	RB_AUGMENT(tmp); \
michael@0	351	if ((RB_PARENT(tmp, field))) \
michael@0	352	RB_AUGMENT(RB_PARENT(tmp, field)); \
michael@0	353	} while (0)
michael@0	354
michael@0	355	#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
michael@0	356	(tmp) = RB_LEFT(elm, field); \
michael@0	357	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
michael@0	358	RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
michael@0	359	} \
michael@0	360	RB_AUGMENT(elm); \
michael@0	361	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
michael@0	362	if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
michael@0	363	RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
michael@0	364	else \
michael@0	365	RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
michael@0	366	} else \
michael@0	367	(head)->rbh_root = (tmp); \
michael@0	368	RB_RIGHT(tmp, field) = (elm); \
michael@0	369	RB_PARENT(elm, field) = (tmp); \
michael@0	370	RB_AUGMENT(tmp); \
michael@0	371	if ((RB_PARENT(tmp, field))) \
michael@0	372	RB_AUGMENT(RB_PARENT(tmp, field)); \
michael@0	373	} while (0)
michael@0	374
michael@0	375	/* Generates prototypes and inline functions */
michael@0	376	#define RB_PROTOTYPE(name, type, field, cmp) \
michael@0	377	void name##_RB_INSERT_COLOR(struct name *, struct type *); \
michael@0	378	void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
michael@0	379	struct type *name##_RB_REMOVE(struct name *, struct type *); \
michael@0	380	struct type *name##_RB_INSERT(struct name *, struct type *); \
michael@0	381	struct type *name##_RB_FIND(struct name *, struct type *); \
michael@0	382	struct type *name##_RB_NEXT(struct type *); \
michael@0	383	struct type *name##_RB_MINMAX(struct name *, int); \
michael@0	384	\
michael@0	385
michael@0	386	/* Main rb operation.
michael@0	387	* Moves node close to the key of elm to top
michael@0	388	*/
michael@0	389	#define RB_GENERATE(name, type, field, cmp) \
michael@0	390	void \
michael@0	391	name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
michael@0	392	{ \
michael@0	393	struct type *parent, *gparent, *tmp; \
michael@0	394	while ((parent = RB_PARENT(elm, field)) && \
michael@0	395	RB_COLOR(parent, field) == RB_RED) { \
michael@0	396	gparent = RB_PARENT(parent, field); \
michael@0	397	if (parent == RB_LEFT(gparent, field)) { \
michael@0	398	tmp = RB_RIGHT(gparent, field); \
michael@0	399	if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
michael@0	400	RB_COLOR(tmp, field) = RB_BLACK; \
michael@0	401	RB_SET_BLACKRED(parent, gparent, field);\
michael@0	402	elm = gparent; \
michael@0	403	continue; \
michael@0	404	} \
michael@0	405	if (RB_RIGHT(parent, field) == elm) { \
michael@0	406	RB_ROTATE_LEFT(head, parent, tmp, field);\
michael@0	407	tmp = parent; \
michael@0	408	parent = elm; \
michael@0	409	elm = tmp; \
michael@0	410	} \
michael@0	411	RB_SET_BLACKRED(parent, gparent, field); \
michael@0	412	RB_ROTATE_RIGHT(head, gparent, tmp, field); \
michael@0	413	} else { \
michael@0	414	tmp = RB_LEFT(gparent, field); \
michael@0	415	if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
michael@0	416	RB_COLOR(tmp, field) = RB_BLACK; \
michael@0	417	RB_SET_BLACKRED(parent, gparent, field);\
michael@0	418	elm = gparent; \
michael@0	419	continue; \
michael@0	420	} \
michael@0	421	if (RB_LEFT(parent, field) == elm) { \
michael@0	422	RB_ROTATE_RIGHT(head, parent, tmp, field);\
michael@0	423	tmp = parent; \
michael@0	424	parent = elm; \
michael@0	425	elm = tmp; \
michael@0	426	} \
michael@0	427	RB_SET_BLACKRED(parent, gparent, field); \
michael@0	428	RB_ROTATE_LEFT(head, gparent, tmp, field); \
michael@0	429	} \
michael@0	430	} \
michael@0	431	RB_COLOR(head->rbh_root, field) = RB_BLACK; \
michael@0	432	} \
michael@0	433	\
michael@0	434	void \
michael@0	435	name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
michael@0	436	{ \
michael@0	437	struct type *tmp; \
michael@0	438	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
michael@0	439	elm != RB_ROOT(head)) { \
michael@0	440	if (RB_LEFT(parent, field) == elm) { \
michael@0	441	tmp = RB_RIGHT(parent, field); \
michael@0	442	if (RB_COLOR(tmp, field) == RB_RED) { \
michael@0	443	RB_SET_BLACKRED(tmp, parent, field); \
michael@0	444	RB_ROTATE_LEFT(head, parent, tmp, field);\
michael@0	445	tmp = RB_RIGHT(parent, field); \
michael@0	446	} \
michael@0	447	if ((RB_LEFT(tmp, field) == NULL || \
michael@0	448	RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
michael@0	449	(RB_RIGHT(tmp, field) == NULL || \
michael@0	450	RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
michael@0	451	RB_COLOR(tmp, field) = RB_RED; \
michael@0	452	elm = parent; \
michael@0	453	parent = RB_PARENT(elm, field); \
michael@0	454	} else { \
michael@0	455	if (RB_RIGHT(tmp, field) == NULL || \
michael@0	456	RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
michael@0	457	struct type *oleft; \
michael@0	458	if ((oleft = RB_LEFT(tmp, field)))\
michael@0	459	RB_COLOR(oleft, field) = RB_BLACK;\
michael@0	460	RB_COLOR(tmp, field) = RB_RED; \
michael@0	461	RB_ROTATE_RIGHT(head, tmp, oleft, field);\
michael@0	462	tmp = RB_RIGHT(parent, field); \
michael@0	463	} \
michael@0	464	RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
michael@0	465	RB_COLOR(parent, field) = RB_BLACK; \
michael@0	466	if (RB_RIGHT(tmp, field)) \
michael@0	467	RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
michael@0	468	RB_ROTATE_LEFT(head, parent, tmp, field);\
michael@0	469	elm = RB_ROOT(head); \
michael@0	470	break; \
michael@0	471	} \
michael@0	472	} else { \
michael@0	473	tmp = RB_LEFT(parent, field); \
michael@0	474	if (RB_COLOR(tmp, field) == RB_RED) { \
michael@0	475	RB_SET_BLACKRED(tmp, parent, field); \
michael@0	476	RB_ROTATE_RIGHT(head, parent, tmp, field);\
michael@0	477	tmp = RB_LEFT(parent, field); \
michael@0	478	} \
michael@0	479	if ((RB_LEFT(tmp, field) == NULL || \
michael@0	480	RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
michael@0	481	(RB_RIGHT(tmp, field) == NULL || \
michael@0	482	RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
michael@0	483	RB_COLOR(tmp, field) = RB_RED; \
michael@0	484	elm = parent; \
michael@0	485	parent = RB_PARENT(elm, field); \
michael@0	486	} else { \
michael@0	487	if (RB_LEFT(tmp, field) == NULL || \
michael@0	488	RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
michael@0	489	struct type *oright; \
michael@0	490	if ((oright = RB_RIGHT(tmp, field)))\
michael@0	491	RB_COLOR(oright, field) = RB_BLACK;\
michael@0	492	RB_COLOR(tmp, field) = RB_RED; \
michael@0	493	RB_ROTATE_LEFT(head, tmp, oright, field);\
michael@0	494	tmp = RB_LEFT(parent, field); \
michael@0	495	} \
michael@0	496	RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
michael@0	497	RB_COLOR(parent, field) = RB_BLACK; \
michael@0	498	if (RB_LEFT(tmp, field)) \
michael@0	499	RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
michael@0	500	RB_ROTATE_RIGHT(head, parent, tmp, field);\
michael@0	501	elm = RB_ROOT(head); \
michael@0	502	break; \
michael@0	503	} \
michael@0	504	} \
michael@0	505	} \
michael@0	506	if (elm) \
michael@0	507	RB_COLOR(elm, field) = RB_BLACK; \
michael@0	508	} \
michael@0	509	\
michael@0	510	struct type * \
michael@0	511	name##_RB_REMOVE(struct name *head, struct type *elm) \
michael@0	512	{ \
michael@0	513	struct type *child, *parent, *old = elm; \
michael@0	514	int color; \
michael@0	515	if (RB_LEFT(elm, field) == NULL) \
michael@0	516	child = RB_RIGHT(elm, field); \
michael@0	517	else if (RB_RIGHT(elm, field) == NULL) \
michael@0	518	child = RB_LEFT(elm, field); \
michael@0	519	else { \
michael@0	520	struct type *left; \
michael@0	521	elm = RB_RIGHT(elm, field); \
michael@0	522	while ((left = RB_LEFT(elm, field))) \
michael@0	523	elm = left; \
michael@0	524	child = RB_RIGHT(elm, field); \
michael@0	525	parent = RB_PARENT(elm, field); \
michael@0	526	color = RB_COLOR(elm, field); \
michael@0	527	if (child) \
michael@0	528	RB_PARENT(child, field) = parent; \
michael@0	529	if (parent) { \
michael@0	530	if (RB_LEFT(parent, field) == elm) \
michael@0	531	RB_LEFT(parent, field) = child; \
michael@0	532	else \
michael@0	533	RB_RIGHT(parent, field) = child; \
michael@0	534	RB_AUGMENT(parent); \
michael@0	535	} else \
michael@0	536	RB_ROOT(head) = child; \
michael@0	537	if (RB_PARENT(elm, field) == old) \
michael@0	538	parent = elm; \
michael@0	539	(elm)->field = (old)->field; \
michael@0	540	if (RB_PARENT(old, field)) { \
michael@0	541	if (RB_LEFT(RB_PARENT(old, field), field) == old)\
michael@0	542	RB_LEFT(RB_PARENT(old, field), field) = elm;\
michael@0	543	else \
michael@0	544	RB_RIGHT(RB_PARENT(old, field), field) = elm;\
michael@0	545	RB_AUGMENT(RB_PARENT(old, field)); \
michael@0	546	} else \
michael@0	547	RB_ROOT(head) = elm; \
michael@0	548	RB_PARENT(RB_LEFT(old, field), field) = elm; \
michael@0	549	if (RB_RIGHT(old, field)) \
michael@0	550	RB_PARENT(RB_RIGHT(old, field), field) = elm; \
michael@0	551	if (parent) { \
michael@0	552	left = parent; \
michael@0	553	do { \
michael@0	554	RB_AUGMENT(left); \
michael@0	555	} while ((left = RB_PARENT(left, field))); \
michael@0	556	} \
michael@0	557	goto color; \
michael@0	558	} \
michael@0	559	parent = RB_PARENT(elm, field); \
michael@0	560	color = RB_COLOR(elm, field); \
michael@0	561	if (child) \
michael@0	562	RB_PARENT(child, field) = parent; \
michael@0	563	if (parent) { \
michael@0	564	if (RB_LEFT(parent, field) == elm) \
michael@0	565	RB_LEFT(parent, field) = child; \
michael@0	566	else \
michael@0	567	RB_RIGHT(parent, field) = child; \
michael@0	568	RB_AUGMENT(parent); \
michael@0	569	} else \
michael@0	570	RB_ROOT(head) = child; \
michael@0	571	color: \
michael@0	572	if (color == RB_BLACK) \
michael@0	573	name##_RB_REMOVE_COLOR(head, parent, child); \
michael@0	574	return (old); \
michael@0	575	} \
michael@0	576	\
michael@0	577	/* Inserts a node into the RB tree */ \
michael@0	578	struct type * \
michael@0	579	name##_RB_INSERT(struct name *head, struct type *elm) \
michael@0	580	{ \
michael@0	581	struct type *tmp; \
michael@0	582	struct type *parent = NULL; \
michael@0	583	int comp = 0; \
michael@0	584	tmp = RB_ROOT(head); \
michael@0	585	while (tmp) { \
michael@0	586	parent = tmp; \
michael@0	587	comp = (cmp)(elm, parent); \
michael@0	588	if (comp < 0) \
michael@0	589	tmp = RB_LEFT(tmp, field); \
michael@0	590	else if (comp > 0) \
michael@0	591	tmp = RB_RIGHT(tmp, field); \
michael@0	592	else \
michael@0	593	return (tmp); \
michael@0	594	} \
michael@0	595	RB_SET(elm, parent, field); \
michael@0	596	if (parent != NULL) { \
michael@0	597	if (comp < 0) \
michael@0	598	RB_LEFT(parent, field) = elm; \
michael@0	599	else \
michael@0	600	RB_RIGHT(parent, field) = elm; \
michael@0	601	RB_AUGMENT(parent); \
michael@0	602	} else \
michael@0	603	RB_ROOT(head) = elm; \
michael@0	604	name##_RB_INSERT_COLOR(head, elm); \
michael@0	605	return (NULL); \
michael@0	606	} \
michael@0	607	\
michael@0	608	/* Finds the node with the same key as elm */ \
michael@0	609	struct type * \
michael@0	610	name##_RB_FIND(struct name *head, struct type *elm) \
michael@0	611	{ \
michael@0	612	struct type *tmp = RB_ROOT(head); \
michael@0	613	int comp; \
michael@0	614	while (tmp) { \
michael@0	615	comp = cmp(elm, tmp); \
michael@0	616	if (comp < 0) \
michael@0	617	tmp = RB_LEFT(tmp, field); \
michael@0	618	else if (comp > 0) \
michael@0	619	tmp = RB_RIGHT(tmp, field); \
michael@0	620	else \
michael@0	621	return (tmp); \
michael@0	622	} \
michael@0	623	return (NULL); \
michael@0	624	} \
michael@0	625	\
michael@0	626	struct type * \
michael@0	627	name##_RB_NEXT(struct type *elm) \
michael@0	628	{ \
michael@0	629	if (RB_RIGHT(elm, field)) { \
michael@0	630	elm = RB_RIGHT(elm, field); \
michael@0	631	while (RB_LEFT(elm, field)) \
michael@0	632	elm = RB_LEFT(elm, field); \
michael@0	633	} else { \
michael@0	634	if (RB_PARENT(elm, field) && \
michael@0	635	(elm == RB_LEFT(RB_PARENT(elm, field), field))) \
michael@0	636	elm = RB_PARENT(elm, field); \
michael@0	637	else { \
michael@0	638	while (RB_PARENT(elm, field) && \
michael@0	639	(elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
michael@0	640	elm = RB_PARENT(elm, field); \
michael@0	641	elm = RB_PARENT(elm, field); \
michael@0	642	} \
michael@0	643	} \
michael@0	644	return (elm); \
michael@0	645	} \
michael@0	646	\
michael@0	647	struct type * \
michael@0	648	name##_RB_MINMAX(struct name *head, int val) \
michael@0	649	{ \
michael@0	650	struct type *tmp = RB_ROOT(head); \
michael@0	651	struct type *parent = NULL; \
michael@0	652	while (tmp) { \
michael@0	653	parent = tmp; \
michael@0	654	if (val < 0) \
michael@0	655	tmp = RB_LEFT(tmp, field); \
michael@0	656	else \
michael@0	657	tmp = RB_RIGHT(tmp, field); \
michael@0	658	} \
michael@0	659	return (parent); \
michael@0	660	}
michael@0	661
michael@0	662	#define RB_NEGINF -1
michael@0	663	#define RB_INF 1
michael@0	664
michael@0	665	#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
michael@0	666	#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
michael@0	667	#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
michael@0	668	#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
michael@0	669	#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
michael@0	670	#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
michael@0	671
michael@0	672	#define RB_FOREACH(x, name, head) \
michael@0	673	for ((x) = RB_MIN(name, head); \
michael@0	674	(x) != NULL; \
michael@0	675	(x) = name##_RB_NEXT(x))
michael@0	676
michael@0	677	#endif /* _SYS_TREE_H_ */
michael@0	678	/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
michael@0	679	/*
michael@0	680	* Copyright 2002 Niels Provos <provos@citi.umich.edu>
michael@0	681	* All rights reserved.
michael@0	682	*
michael@0	683	* Redistribution and use in source and binary forms, with or without
michael@0	684	* modification, are permitted provided that the following conditions
michael@0	685	* are met:
michael@0	686	* 1. Redistributions of source code must retain the above copyright
michael@0	687	* notice, this list of conditions and the following disclaimer.
michael@0	688	* 2. Redistributions in binary form must reproduce the above copyright
michael@0	689	* notice, this list of conditions and the following disclaimer in the
michael@0	690	* documentation and/or other materials provided with the distribution.
michael@0	691	*
michael@0	692	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
michael@0	693	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
michael@0	694	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
michael@0	695	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
michael@0	696	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
michael@0	697	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
michael@0	698	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
michael@0	699	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
michael@0	700	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
michael@0	701	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0	702	*/
michael@0	703
michael@0	704	#ifndef _SYS_TREE_H_
michael@0	705	#define _SYS_TREE_H_
michael@0	706
michael@0	707	/*
michael@0	708	* This file defines data structures for different types of trees:
michael@0	709	* splay trees and red-black trees.
michael@0	710	*
michael@0	711	* A splay tree is a self-organizing data structure. Every operation
michael@0	712	* on the tree causes a splay to happen. The splay moves the requested
michael@0	713	* node to the root of the tree and partly rebalances it.
michael@0	714	*
michael@0	715	* This has the benefit that request locality causes faster lookups as
michael@0	716	* the requested nodes move to the top of the tree. On the other hand,
michael@0	717	* every lookup causes memory writes.
michael@0	718	*
michael@0	719	* The Balance Theorem bounds the total access time for m operations
michael@0	720	* and n inserts on an initially empty tree as O((m + n)lg n). The
michael@0	721	* amortized cost for a sequence of m accesses to a splay tree is O(lg n);
michael@0	722	*
michael@0	723	* A red-black tree is a binary search tree with the node color as an
michael@0	724	* extra attribute. It fulfills a set of conditions:
michael@0	725	* - every search path from the root to a leaf consists of the
michael@0	726	* same number of black nodes,
michael@0	727	* - each red node (except for the root) has a black parent,
michael@0	728	* - each leaf node is black.
michael@0	729	*
michael@0	730	* Every operation on a red-black tree is bounded as O(lg n).
michael@0	731	* The maximum height of a red-black tree is 2lg (n+1).
michael@0	732	*/
michael@0	733
michael@0	734	#define SPLAY_HEAD(name, type) \
michael@0	735	struct name { \
michael@0	736	struct type *sph_root; /* root of the tree */ \
michael@0	737	}
michael@0	738
michael@0	739	#define SPLAY_INITIALIZER(root) \
michael@0	740	{ NULL }
michael@0	741
michael@0	742	#define SPLAY_INIT(root) do { \
michael@0	743	(root)->sph_root = NULL; \
michael@0	744	} while (0)
michael@0	745
michael@0	746	#define SPLAY_ENTRY(type) \
michael@0	747	struct { \
michael@0	748	struct type *spe_left; /* left element */ \
michael@0	749	struct type *spe_right; /* right element */ \
michael@0	750	}
michael@0	751
michael@0	752	#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
michael@0	753	#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
michael@0	754	#define SPLAY_ROOT(head) (head)->sph_root
michael@0	755	#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
michael@0	756
michael@0	757	/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
michael@0	758	#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
michael@0	759	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
michael@0	760	SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
michael@0	761	(head)->sph_root = tmp; \
michael@0	762	} while (0)
michael@0	763
michael@0	764	#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
michael@0	765	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
michael@0	766	SPLAY_LEFT(tmp, field) = (head)->sph_root; \
michael@0	767	(head)->sph_root = tmp; \
michael@0	768	} while (0)
michael@0	769
michael@0	770	#define SPLAY_LINKLEFT(head, tmp, field) do { \
michael@0	771	SPLAY_LEFT(tmp, field) = (head)->sph_root; \
michael@0	772	tmp = (head)->sph_root; \
michael@0	773	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
michael@0	774	} while (0)
michael@0	775
michael@0	776	#define SPLAY_LINKRIGHT(head, tmp, field) do { \
michael@0	777	SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
michael@0	778	tmp = (head)->sph_root; \
michael@0	779	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
michael@0	780	} while (0)
michael@0	781
michael@0	782	#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
michael@0	783	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
michael@0	784	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
michael@0	785	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
michael@0	786	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
michael@0	787	} while (0)
michael@0	788
michael@0	789	/* Generates prototypes and inline functions */
michael@0	790
michael@0	791	#define SPLAY_PROTOTYPE(name, type, field, cmp) \
michael@0	792	void name##_SPLAY(struct name *, struct type *); \
michael@0	793	void name##_SPLAY_MINMAX(struct name *, int); \
michael@0	794	struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
michael@0	795	struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
michael@0	796	\
michael@0	797	/* Finds the node with the same key as elm */ \
michael@0	798	static __inline struct type * \
michael@0	799	name##_SPLAY_FIND(struct name *head, struct type *elm) \
michael@0	800	{ \
michael@0	801	if (SPLAY_EMPTY(head)) \
michael@0	802	return(NULL); \
michael@0	803	name##_SPLAY(head, elm); \
michael@0	804	if ((cmp)(elm, (head)->sph_root) == 0) \
michael@0	805	return (head->sph_root); \
michael@0	806	return (NULL); \
michael@0	807	} \
michael@0	808	\
michael@0	809	static __inline struct type * \
michael@0	810	name##_SPLAY_NEXT(struct name *head, struct type *elm) \
michael@0	811	{ \
michael@0	812	name##_SPLAY(head, elm); \
michael@0	813	if (SPLAY_RIGHT(elm, field) != NULL) { \
michael@0	814	elm = SPLAY_RIGHT(elm, field); \
michael@0	815	while (SPLAY_LEFT(elm, field) != NULL) { \
michael@0	816	elm = SPLAY_LEFT(elm, field); \
michael@0	817	} \
michael@0	818	} else \
michael@0	819	elm = NULL; \
michael@0	820	return (elm); \
michael@0	821	} \
michael@0	822	\
michael@0	823	static __inline struct type * \
michael@0	824	name##_SPLAY_MIN_MAX(struct name *head, int val) \
michael@0	825	{ \
michael@0	826	name##_SPLAY_MINMAX(head, val); \
michael@0	827	return (SPLAY_ROOT(head)); \
michael@0	828	}
michael@0	829
michael@0	830	/* Main splay operation.
michael@0	831	* Moves node close to the key of elm to top
michael@0	832	*/
michael@0	833	#define SPLAY_GENERATE(name, type, field, cmp) \
michael@0	834	struct type * \
michael@0	835	name##_SPLAY_INSERT(struct name *head, struct type *elm) \
michael@0	836	{ \
michael@0	837	if (SPLAY_EMPTY(head)) { \
michael@0	838	SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
michael@0	839	} else { \
michael@0	840	int __comp; \
michael@0	841	name##_SPLAY(head, elm); \
michael@0	842	__comp = (cmp)(elm, (head)->sph_root); \
michael@0	843	if(__comp < 0) { \
michael@0	844	SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
michael@0	845	SPLAY_RIGHT(elm, field) = (head)->sph_root; \
michael@0	846	SPLAY_LEFT((head)->sph_root, field) = NULL; \
michael@0	847	} else if (__comp > 0) { \
michael@0	848	SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
michael@0	849	SPLAY_LEFT(elm, field) = (head)->sph_root; \
michael@0	850	SPLAY_RIGHT((head)->sph_root, field) = NULL; \
michael@0	851	} else \
michael@0	852	return ((head)->sph_root); \
michael@0	853	} \
michael@0	854	(head)->sph_root = (elm); \
michael@0	855	return (NULL); \
michael@0	856	} \
michael@0	857	\
michael@0	858	struct type * \
michael@0	859	name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
michael@0	860	{ \
michael@0	861	struct type *__tmp; \
michael@0	862	if (SPLAY_EMPTY(head)) \
michael@0	863	return (NULL); \
michael@0	864	name##_SPLAY(head, elm); \
michael@0	865	if ((cmp)(elm, (head)->sph_root) == 0) { \
michael@0	866	if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
michael@0	867	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
michael@0	868	} else { \
michael@0	869	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
michael@0	870	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
michael@0	871	name##_SPLAY(head, elm); \
michael@0	872	SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
michael@0	873	} \
michael@0	874	return (elm); \
michael@0	875	} \
michael@0	876	return (NULL); \
michael@0	877	} \
michael@0	878	\
michael@0	879	void \
michael@0	880	name##_SPLAY(struct name *head, struct type *elm) \
michael@0	881	{ \
michael@0	882	struct type __node, *__left, *__right, *__tmp; \
michael@0	883	int __comp; \
michael@0	884	\
michael@0	885	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
michael@0	886	__left = __right = &__node; \
michael@0	887	\
michael@0	888	while ((__comp = (cmp)(elm, (head)->sph_root))) { \
michael@0	889	if (__comp < 0) { \
michael@0	890	__tmp = SPLAY_LEFT((head)->sph_root, field); \
michael@0	891	if (__tmp == NULL) \
michael@0	892	break; \
michael@0	893	if ((cmp)(elm, __tmp) < 0){ \
michael@0	894	SPLAY_ROTATE_RIGHT(head, __tmp, field); \
michael@0	895	if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
michael@0	896	break; \
michael@0	897	} \
michael@0	898	SPLAY_LINKLEFT(head, __right, field); \
michael@0	899	} else if (__comp > 0) { \
michael@0	900	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
michael@0	901	if (__tmp == NULL) \
michael@0	902	break; \
michael@0	903	if ((cmp)(elm, __tmp) > 0){ \
michael@0	904	SPLAY_ROTATE_LEFT(head, __tmp, field); \
michael@0	905	if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
michael@0	906	break; \
michael@0	907	} \
michael@0	908	SPLAY_LINKRIGHT(head, __left, field); \
michael@0	909	} \
michael@0	910	} \
michael@0	911	SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
michael@0	912	} \
michael@0	913	\
michael@0	914	/* Splay with either the minimum or the maximum element \
michael@0	915	* Used to find minimum or maximum element in tree. \
michael@0	916	*/ \
michael@0	917	void name##_SPLAY_MINMAX(struct name *head, int __comp) \
michael@0	918	{ \
michael@0	919	struct type __node, *__left, *__right, *__tmp; \
michael@0	920	\
michael@0	921	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
michael@0	922	__left = __right = &__node; \
michael@0	923	\
michael@0	924	while (1) { \
michael@0	925	if (__comp < 0) { \
michael@0	926	__tmp = SPLAY_LEFT((head)->sph_root, field); \
michael@0	927	if (__tmp == NULL) \
michael@0	928	break; \
michael@0	929	if (__comp < 0){ \
michael@0	930	SPLAY_ROTATE_RIGHT(head, __tmp, field); \
michael@0	931	if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
michael@0	932	break; \
michael@0	933	} \
michael@0	934	SPLAY_LINKLEFT(head, __right, field); \
michael@0	935	} else if (__comp > 0) { \
michael@0	936	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
michael@0	937	if (__tmp == NULL) \
michael@0	938	break; \
michael@0	939	if (__comp > 0) { \
michael@0	940	SPLAY_ROTATE_LEFT(head, __tmp, field); \
michael@0	941	if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
michael@0	942	break; \
michael@0	943	} \
michael@0	944	SPLAY_LINKRIGHT(head, __left, field); \
michael@0	945	} \
michael@0	946	} \
michael@0	947	SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
michael@0	948	}
michael@0	949
michael@0	950	#define SPLAY_NEGINF -1
michael@0	951	#define SPLAY_INF 1
michael@0	952
michael@0	953	#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
michael@0	954	#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
michael@0	955	#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
michael@0	956	#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
michael@0	957	#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
michael@0	958	: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
michael@0	959	#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
michael@0	960	: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
michael@0	961
michael@0	962	#define SPLAY_FOREACH(x, name, head) \
michael@0	963	for ((x) = SPLAY_MIN(name, head); \
michael@0	964	(x) != NULL; \
michael@0	965	(x) = SPLAY_NEXT(name, head, x))
michael@0	966
michael@0	967	/* Macros that define a red-back tree */
michael@0	968	#define RB_HEAD(name, type) \
michael@0	969	struct name { \
michael@0	970	struct type *rbh_root; /* root of the tree */ \
michael@0	971	}
michael@0	972
michael@0	973	#define RB_INITIALIZER(root) \
michael@0	974	{ NULL }
michael@0	975
michael@0	976	#define RB_INIT(root) do { \
michael@0	977	(root)->rbh_root = NULL; \
michael@0	978	} while (0)
michael@0	979
michael@0	980	#define RB_BLACK 0
michael@0	981	#define RB_RED 1
michael@0	982	#define RB_ENTRY(type) \
michael@0	983	struct { \
michael@0	984	struct type *rbe_left; /* left element */ \
michael@0	985	struct type *rbe_right; /* right element */ \
michael@0	986	struct type *rbe_parent; /* parent element */ \
michael@0	987	int rbe_color; /* node color */ \
michael@0	988	}
michael@0	989
michael@0	990	#define RB_LEFT(elm, field) (elm)->field.rbe_left
michael@0	991	#define RB_RIGHT(elm, field) (elm)->field.rbe_right
michael@0	992	#define RB_PARENT(elm, field) (elm)->field.rbe_parent
michael@0	993	#define RB_COLOR(elm, field) (elm)->field.rbe_color
michael@0	994	#define RB_ROOT(head) (head)->rbh_root
michael@0	995	#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
michael@0	996
michael@0	997	#define RB_SET(elm, parent, field) do { \
michael@0	998	RB_PARENT(elm, field) = parent; \
michael@0	999	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
michael@0	1000	RB_COLOR(elm, field) = RB_RED; \
michael@0	1001	} while (0)
michael@0	1002
michael@0	1003	#define RB_SET_BLACKRED(black, red, field) do { \
michael@0	1004	RB_COLOR(black, field) = RB_BLACK; \
michael@0	1005	RB_COLOR(red, field) = RB_RED; \
michael@0	1006	} while (0)
michael@0	1007
michael@0	1008	#ifndef RB_AUGMENT
michael@0	1009	#define RB_AUGMENT(x)
michael@0	1010	#endif
michael@0	1011
michael@0	1012	#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
michael@0	1013	(tmp) = RB_RIGHT(elm, field); \
michael@0	1014	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
michael@0	1015	RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
michael@0	1016	} \
michael@0	1017	RB_AUGMENT(elm); \
michael@0	1018	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
michael@0	1019	if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
michael@0	1020	RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
michael@0	1021	else \
michael@0	1022	RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
michael@0	1023	} else \
michael@0	1024	(head)->rbh_root = (tmp); \
michael@0	1025	RB_LEFT(tmp, field) = (elm); \
michael@0	1026	RB_PARENT(elm, field) = (tmp); \
michael@0	1027	RB_AUGMENT(tmp); \
michael@0	1028	if ((RB_PARENT(tmp, field))) \
michael@0	1029	RB_AUGMENT(RB_PARENT(tmp, field)); \
michael@0	1030	} while (0)
michael@0	1031
michael@0	1032	#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
michael@0	1033	(tmp) = RB_LEFT(elm, field); \
michael@0	1034	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
michael@0	1035	RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
michael@0	1036	} \
michael@0	1037	RB_AUGMENT(elm); \
michael@0	1038	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
michael@0	1039	if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
michael@0	1040	RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
michael@0	1041	else \
michael@0	1042	RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
michael@0	1043	} else \
michael@0	1044	(head)->rbh_root = (tmp); \
michael@0	1045	RB_RIGHT(tmp, field) = (elm); \
michael@0	1046	RB_PARENT(elm, field) = (tmp); \
michael@0	1047	RB_AUGMENT(tmp); \
michael@0	1048	if ((RB_PARENT(tmp, field))) \
michael@0	1049	RB_AUGMENT(RB_PARENT(tmp, field)); \
michael@0	1050	} while (0)
michael@0	1051
michael@0	1052	/* Generates prototypes and inline functions */
michael@0	1053	#define RB_PROTOTYPE(name, type, field, cmp) \
michael@0	1054	void name##_RB_INSERT_COLOR(struct name *, struct type *); \
michael@0	1055	void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
michael@0	1056	struct type *name##_RB_REMOVE(struct name *, struct type *); \
michael@0	1057	struct type *name##_RB_INSERT(struct name *, struct type *); \
michael@0	1058	struct type *name##_RB_FIND(struct name *, struct type *); \
michael@0	1059	struct type *name##_RB_NEXT(struct type *); \
michael@0	1060	struct type *name##_RB_MINMAX(struct name *, int); \
michael@0	1061	\
michael@0	1062
michael@0	1063	/* Main rb operation.
michael@0	1064	* Moves node close to the key of elm to top
michael@0	1065	*/
michael@0	1066	#define RB_GENERATE(name, type, field, cmp) \
michael@0	1067	void \
michael@0	1068	name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
michael@0	1069	{ \
michael@0	1070	struct type *parent, *gparent, *tmp; \
michael@0	1071	while ((parent = RB_PARENT(elm, field)) && \
michael@0	1072	RB_COLOR(parent, field) == RB_RED) { \
michael@0	1073	gparent = RB_PARENT(parent, field); \
michael@0	1074	if (parent == RB_LEFT(gparent, field)) { \
michael@0	1075	tmp = RB_RIGHT(gparent, field); \
michael@0	1076	if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
michael@0	1077	RB_COLOR(tmp, field) = RB_BLACK; \
michael@0	1078	RB_SET_BLACKRED(parent, gparent, field);\
michael@0	1079	elm = gparent; \
michael@0	1080	continue; \
michael@0	1081	} \
michael@0	1082	if (RB_RIGHT(parent, field) == elm) { \
michael@0	1083	RB_ROTATE_LEFT(head, parent, tmp, field);\
michael@0	1084	tmp = parent; \
michael@0	1085	parent = elm; \
michael@0	1086	elm = tmp; \
michael@0	1087	} \
michael@0	1088	RB_SET_BLACKRED(parent, gparent, field); \
michael@0	1089	RB_ROTATE_RIGHT(head, gparent, tmp, field); \
michael@0	1090	} else { \
michael@0	1091	tmp = RB_LEFT(gparent, field); \
michael@0	1092	if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
michael@0	1093	RB_COLOR(tmp, field) = RB_BLACK; \
michael@0	1094	RB_SET_BLACKRED(parent, gparent, field);\
michael@0	1095	elm = gparent; \
michael@0	1096	continue; \
michael@0	1097	} \
michael@0	1098	if (RB_LEFT(parent, field) == elm) { \
michael@0	1099	RB_ROTATE_RIGHT(head, parent, tmp, field);\
michael@0	1100	tmp = parent; \
michael@0	1101	parent = elm; \
michael@0	1102	elm = tmp; \
michael@0	1103	} \
michael@0	1104	RB_SET_BLACKRED(parent, gparent, field); \
michael@0	1105	RB_ROTATE_LEFT(head, gparent, tmp, field); \
michael@0	1106	} \
michael@0	1107	} \
michael@0	1108	RB_COLOR(head->rbh_root, field) = RB_BLACK; \
michael@0	1109	} \
michael@0	1110	\
michael@0	1111	void \
michael@0	1112	name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
michael@0	1113	{ \
michael@0	1114	struct type *tmp; \
michael@0	1115	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
michael@0	1116	elm != RB_ROOT(head)) { \
michael@0	1117	if (RB_LEFT(parent, field) == elm) { \
michael@0	1118	tmp = RB_RIGHT(parent, field); \
michael@0	1119	if (RB_COLOR(tmp, field) == RB_RED) { \
michael@0	1120	RB_SET_BLACKRED(tmp, parent, field); \
michael@0	1121	RB_ROTATE_LEFT(head, parent, tmp, field);\
michael@0	1122	tmp = RB_RIGHT(parent, field); \
michael@0	1123	} \
michael@0	1124	if ((RB_LEFT(tmp, field) == NULL || \
michael@0	1125	RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
michael@0	1126	(RB_RIGHT(tmp, field) == NULL || \
michael@0	1127	RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
michael@0	1128	RB_COLOR(tmp, field) = RB_RED; \
michael@0	1129	elm = parent; \
michael@0	1130	parent = RB_PARENT(elm, field); \
michael@0	1131	} else { \
michael@0	1132	if (RB_RIGHT(tmp, field) == NULL || \
michael@0	1133	RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
michael@0	1134	struct type *oleft; \
michael@0	1135	if ((oleft = RB_LEFT(tmp, field)))\
michael@0	1136	RB_COLOR(oleft, field) = RB_BLACK;\
michael@0	1137	RB_COLOR(tmp, field) = RB_RED; \
michael@0	1138	RB_ROTATE_RIGHT(head, tmp, oleft, field);\
michael@0	1139	tmp = RB_RIGHT(parent, field); \
michael@0	1140	} \
michael@0	1141	RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
michael@0	1142	RB_COLOR(parent, field) = RB_BLACK; \
michael@0	1143	if (RB_RIGHT(tmp, field)) \
michael@0	1144	RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
michael@0	1145	RB_ROTATE_LEFT(head, parent, tmp, field);\
michael@0	1146	elm = RB_ROOT(head); \
michael@0	1147	break; \
michael@0	1148	} \
michael@0	1149	} else { \
michael@0	1150	tmp = RB_LEFT(parent, field); \
michael@0	1151	if (RB_COLOR(tmp, field) == RB_RED) { \
michael@0	1152	RB_SET_BLACKRED(tmp, parent, field); \
michael@0	1153	RB_ROTATE_RIGHT(head, parent, tmp, field);\
michael@0	1154	tmp = RB_LEFT(parent, field); \
michael@0	1155	} \
michael@0	1156	if ((RB_LEFT(tmp, field) == NULL || \
michael@0	1157	RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
michael@0	1158	(RB_RIGHT(tmp, field) == NULL || \
michael@0	1159	RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
michael@0	1160	RB_COLOR(tmp, field) = RB_RED; \
michael@0	1161	elm = parent; \
michael@0	1162	parent = RB_PARENT(elm, field); \
michael@0	1163	} else { \
michael@0	1164	if (RB_LEFT(tmp, field) == NULL || \
michael@0	1165	RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
michael@0	1166	struct type *oright; \
michael@0	1167	if ((oright = RB_RIGHT(tmp, field)))\
michael@0	1168	RB_COLOR(oright, field) = RB_BLACK;\
michael@0	1169	RB_COLOR(tmp, field) = RB_RED; \
michael@0	1170	RB_ROTATE_LEFT(head, tmp, oright, field);\
michael@0	1171	tmp = RB_LEFT(parent, field); \
michael@0	1172	} \
michael@0	1173	RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
michael@0	1174	RB_COLOR(parent, field) = RB_BLACK; \
michael@0	1175	if (RB_LEFT(tmp, field)) \
michael@0	1176	RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
michael@0	1177	RB_ROTATE_RIGHT(head, parent, tmp, field);\
michael@0	1178	elm = RB_ROOT(head); \
michael@0	1179	break; \
michael@0	1180	} \
michael@0	1181	} \
michael@0	1182	} \
michael@0	1183	if (elm) \
michael@0	1184	RB_COLOR(elm, field) = RB_BLACK; \
michael@0	1185	} \
michael@0	1186	\
michael@0	1187	struct type * \
michael@0	1188	name##_RB_REMOVE(struct name *head, struct type *elm) \
michael@0	1189	{ \
michael@0	1190	struct type *child, *parent, *old = elm; \
michael@0	1191	int color; \
michael@0	1192	if (RB_LEFT(elm, field) == NULL) \
michael@0	1193	child = RB_RIGHT(elm, field); \
michael@0	1194	else if (RB_RIGHT(elm, field) == NULL) \
michael@0	1195	child = RB_LEFT(elm, field); \
michael@0	1196	else { \
michael@0	1197	struct type *left; \
michael@0	1198	elm = RB_RIGHT(elm, field); \
michael@0	1199	while ((left = RB_LEFT(elm, field))) \
michael@0	1200	elm = left; \
michael@0	1201	child = RB_RIGHT(elm, field); \
michael@0	1202	parent = RB_PARENT(elm, field); \
michael@0	1203	color = RB_COLOR(elm, field); \
michael@0	1204	if (child) \
michael@0	1205	RB_PARENT(child, field) = parent; \
michael@0	1206	if (parent) { \
michael@0	1207	if (RB_LEFT(parent, field) == elm) \
michael@0	1208	RB_LEFT(parent, field) = child; \
michael@0	1209	else \
michael@0	1210	RB_RIGHT(parent, field) = child; \
michael@0	1211	RB_AUGMENT(parent); \
michael@0	1212	} else \
michael@0	1213	RB_ROOT(head) = child; \
michael@0	1214	if (RB_PARENT(elm, field) == old) \
michael@0	1215	parent = elm; \
michael@0	1216	(elm)->field = (old)->field; \
michael@0	1217	if (RB_PARENT(old, field)) { \
michael@0	1218	if (RB_LEFT(RB_PARENT(old, field), field) == old)\
michael@0	1219	RB_LEFT(RB_PARENT(old, field), field) = elm;\
michael@0	1220	else \
michael@0	1221	RB_RIGHT(RB_PARENT(old, field), field) = elm;\
michael@0	1222	RB_AUGMENT(RB_PARENT(old, field)); \
michael@0	1223	} else \
michael@0	1224	RB_ROOT(head) = elm; \
michael@0	1225	RB_PARENT(RB_LEFT(old, field), field) = elm; \
michael@0	1226	if (RB_RIGHT(old, field)) \
michael@0	1227	RB_PARENT(RB_RIGHT(old, field), field) = elm; \
michael@0	1228	if (parent) { \
michael@0	1229	left = parent; \
michael@0	1230	do { \
michael@0	1231	RB_AUGMENT(left); \
michael@0	1232	} while ((left = RB_PARENT(left, field))); \
michael@0	1233	} \
michael@0	1234	goto color; \
michael@0	1235	} \
michael@0	1236	parent = RB_PARENT(elm, field); \
michael@0	1237	color = RB_COLOR(elm, field); \
michael@0	1238	if (child) \
michael@0	1239	RB_PARENT(child, field) = parent; \
michael@0	1240	if (parent) { \
michael@0	1241	if (RB_LEFT(parent, field) == elm) \
michael@0	1242	RB_LEFT(parent, field) = child; \
michael@0	1243	else \
michael@0	1244	RB_RIGHT(parent, field) = child; \
michael@0	1245	RB_AUGMENT(parent); \
michael@0	1246	} else \
michael@0	1247	RB_ROOT(head) = child; \
michael@0	1248	color: \
michael@0	1249	if (color == RB_BLACK) \
michael@0	1250	name##_RB_REMOVE_COLOR(head, parent, child); \
michael@0	1251	return (old); \
michael@0	1252	} \
michael@0	1253	\
michael@0	1254	/* Inserts a node into the RB tree */ \
michael@0	1255	struct type * \
michael@0	1256	name##_RB_INSERT(struct name *head, struct type *elm) \
michael@0	1257	{ \
michael@0	1258	struct type *tmp; \
michael@0	1259	struct type *parent = NULL; \
michael@0	1260	int comp = 0; \
michael@0	1261	tmp = RB_ROOT(head); \
michael@0	1262	while (tmp) { \
michael@0	1263	parent = tmp; \
michael@0	1264	comp = (cmp)(elm, parent); \
michael@0	1265	if (comp < 0) \
michael@0	1266	tmp = RB_LEFT(tmp, field); \
michael@0	1267	else if (comp > 0) \
michael@0	1268	tmp = RB_RIGHT(tmp, field); \
michael@0	1269	else \
michael@0	1270	return (tmp); \
michael@0	1271	} \
michael@0	1272	RB_SET(elm, parent, field); \
michael@0	1273	if (parent != NULL) { \
michael@0	1274	if (comp < 0) \
michael@0	1275	RB_LEFT(parent, field) = elm; \
michael@0	1276	else \
michael@0	1277	RB_RIGHT(parent, field) = elm; \
michael@0	1278	RB_AUGMENT(parent); \
michael@0	1279	} else \
michael@0	1280	RB_ROOT(head) = elm; \
michael@0	1281	name##_RB_INSERT_COLOR(head, elm); \
michael@0	1282	return (NULL); \
michael@0	1283	} \
michael@0	1284	\
michael@0	1285	/* Finds the node with the same key as elm */ \
michael@0	1286	struct type * \
michael@0	1287	name##_RB_FIND(struct name *head, struct type *elm) \
michael@0	1288	{ \
michael@0	1289	struct type *tmp = RB_ROOT(head); \
michael@0	1290	int comp; \
michael@0	1291	while (tmp) { \
michael@0	1292	comp = cmp(elm, tmp); \
michael@0	1293	if (comp < 0) \
michael@0	1294	tmp = RB_LEFT(tmp, field); \
michael@0	1295	else if (comp > 0) \
michael@0	1296	tmp = RB_RIGHT(tmp, field); \
michael@0	1297	else \
michael@0	1298	return (tmp); \
michael@0	1299	} \
michael@0	1300	return (NULL); \
michael@0	1301	} \
michael@0	1302	\
michael@0	1303	struct type * \
michael@0	1304	name##_RB_NEXT(struct type *elm) \
michael@0	1305	{ \
michael@0	1306	if (RB_RIGHT(elm, field)) { \
michael@0	1307	elm = RB_RIGHT(elm, field); \
michael@0	1308	while (RB_LEFT(elm, field)) \
michael@0	1309	elm = RB_LEFT(elm, field); \
michael@0	1310	} else { \
michael@0	1311	if (RB_PARENT(elm, field) && \
michael@0	1312	(elm == RB_LEFT(RB_PARENT(elm, field), field))) \
michael@0	1313	elm = RB_PARENT(elm, field); \
michael@0	1314	else { \
michael@0	1315	while (RB_PARENT(elm, field) && \
michael@0	1316	(elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
michael@0	1317	elm = RB_PARENT(elm, field); \
michael@0	1318	elm = RB_PARENT(elm, field); \
michael@0	1319	} \
michael@0	1320	} \
michael@0	1321	return (elm); \
michael@0	1322	} \
michael@0	1323	\
michael@0	1324	struct type * \
michael@0	1325	name##_RB_MINMAX(struct name *head, int val) \
michael@0	1326	{ \
michael@0	1327	struct type *tmp = RB_ROOT(head); \
michael@0	1328	struct type *parent = NULL; \
michael@0	1329	while (tmp) { \
michael@0	1330	parent = tmp; \
michael@0	1331	if (val < 0) \
michael@0	1332	tmp = RB_LEFT(tmp, field); \
michael@0	1333	else \
michael@0	1334	tmp = RB_RIGHT(tmp, field); \
michael@0	1335	} \
michael@0	1336	return (parent); \
michael@0	1337	}
michael@0	1338
michael@0	1339	#define RB_NEGINF -1
michael@0	1340	#define RB_INF 1
michael@0	1341
michael@0	1342	#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
michael@0	1343	#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
michael@0	1344	#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
michael@0	1345	#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
michael@0	1346	#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
michael@0	1347	#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
michael@0	1348
michael@0	1349	#define RB_FOREACH(x, name, head) \
michael@0	1350	for ((x) = RB_MIN(name, head); \
michael@0	1351	(x) != NULL; \
michael@0	1352	(x) = name##_RB_NEXT(x))
michael@0	1353
michael@0	1354	#endif /* _SYS_TREE_H_ */