1d60b2108SDamien Miller /*	$OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $	*/
29b481510SDamien Miller /*
39b481510SDamien Miller  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
49b481510SDamien Miller  * All rights reserved.
59b481510SDamien Miller  *
69b481510SDamien Miller  * Redistribution and use in source and binary forms, with or without
79b481510SDamien Miller  * modification, are permitted provided that the following conditions
89b481510SDamien Miller  * are met:
99b481510SDamien Miller  * 1. Redistributions of source code must retain the above copyright
109b481510SDamien Miller  *    notice, this list of conditions and the following disclaimer.
119b481510SDamien Miller  * 2. Redistributions in binary form must reproduce the above copyright
129b481510SDamien Miller  *    notice, this list of conditions and the following disclaimer in the
139b481510SDamien Miller  *    documentation and/or other materials provided with the distribution.
149b481510SDamien Miller  *
159b481510SDamien Miller  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
169b481510SDamien Miller  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
179b481510SDamien Miller  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
189b481510SDamien Miller  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
199b481510SDamien Miller  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
209b481510SDamien Miller  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
219b481510SDamien Miller  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
229b481510SDamien Miller  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
239b481510SDamien Miller  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
249b481510SDamien Miller  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
259b481510SDamien Miller  */
269b481510SDamien Miller 
277f24a0e6SDarren Tucker /* OPENBSD ORIGINAL: sys/sys/tree.h */
287f24a0e6SDarren Tucker 
29*951b53b1SDarren Tucker #include "config.h"
30*951b53b1SDarren Tucker #ifdef NO_ATTRIBUTE_ON_RETURN_TYPE
31*951b53b1SDarren Tucker # define __attribute__(x)
32*951b53b1SDarren Tucker #endif
33*951b53b1SDarren Tucker 
349b481510SDamien Miller #ifndef	_SYS_TREE_H_
359b481510SDamien Miller #define	_SYS_TREE_H_
369b481510SDamien Miller 
379b481510SDamien Miller /*
389b481510SDamien Miller  * This file defines data structures for different types of trees:
399b481510SDamien Miller  * splay trees and red-black trees.
409b481510SDamien Miller  *
419b481510SDamien Miller  * A splay tree is a self-organizing data structure.  Every operation
429b481510SDamien Miller  * on the tree causes a splay to happen.  The splay moves the requested
439b481510SDamien Miller  * node to the root of the tree and partly rebalances it.
449b481510SDamien Miller  *
459b481510SDamien Miller  * This has the benefit that request locality causes faster lookups as
469b481510SDamien Miller  * the requested nodes move to the top of the tree.  On the other hand,
479b481510SDamien Miller  * every lookup causes memory writes.
489b481510SDamien Miller  *
499b481510SDamien Miller  * The Balance Theorem bounds the total access time for m operations
509b481510SDamien Miller  * and n inserts on an initially empty tree as O((m + n)lg n).  The
519b481510SDamien Miller  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
529b481510SDamien Miller  *
539b481510SDamien Miller  * A red-black tree is a binary search tree with the node color as an
549b481510SDamien Miller  * extra attribute.  It fulfills a set of conditions:
559b481510SDamien Miller  *	- every search path from the root to a leaf consists of the
569b481510SDamien Miller  *	  same number of black nodes,
579b481510SDamien Miller  *	- each red node (except for the root) has a black parent,
589b481510SDamien Miller  *	- each leaf node is black.
599b481510SDamien Miller  *
609b481510SDamien Miller  * Every operation on a red-black tree is bounded as O(lg n).
619b481510SDamien Miller  * The maximum height of a red-black tree is 2lg (n+1).
629b481510SDamien Miller  */
639b481510SDamien Miller 
649b481510SDamien Miller #define SPLAY_HEAD(name, type)						\
659b481510SDamien Miller struct name {								\
669b481510SDamien Miller 	struct type *sph_root; /* root of the tree */			\
679b481510SDamien Miller }
689b481510SDamien Miller 
699b481510SDamien Miller #define SPLAY_INITIALIZER(root)						\
709b481510SDamien Miller 	{ NULL }
719b481510SDamien Miller 
729b481510SDamien Miller #define SPLAY_INIT(root) do {						\
739b481510SDamien Miller 	(root)->sph_root = NULL;					\
749b481510SDamien Miller } while (0)
759b481510SDamien Miller 
769b481510SDamien Miller #define SPLAY_ENTRY(type)						\
779b481510SDamien Miller struct {								\
789b481510SDamien Miller 	struct type *spe_left; /* left element */			\
799b481510SDamien Miller 	struct type *spe_right; /* right element */			\
809b481510SDamien Miller }
819b481510SDamien Miller 
829b481510SDamien Miller #define SPLAY_LEFT(elm, field)		(elm)->field.spe_left
839b481510SDamien Miller #define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right
849b481510SDamien Miller #define SPLAY_ROOT(head)		(head)->sph_root
859b481510SDamien Miller #define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)
869b481510SDamien Miller 
879b481510SDamien Miller /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
889b481510SDamien Miller #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
899b481510SDamien Miller 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
909b481510SDamien Miller 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
919b481510SDamien Miller 	(head)->sph_root = tmp;						\
929b481510SDamien Miller } while (0)
939b481510SDamien Miller 
949b481510SDamien Miller #define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
959b481510SDamien Miller 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
969b481510SDamien Miller 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
979b481510SDamien Miller 	(head)->sph_root = tmp;						\
989b481510SDamien Miller } while (0)
999b481510SDamien Miller 
1009b481510SDamien Miller #define SPLAY_LINKLEFT(head, tmp, field) do {				\
1019b481510SDamien Miller 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
1029b481510SDamien Miller 	tmp = (head)->sph_root;						\
1039b481510SDamien Miller 	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
1049b481510SDamien Miller } while (0)
1059b481510SDamien Miller 
1069b481510SDamien Miller #define SPLAY_LINKRIGHT(head, tmp, field) do {				\
1079b481510SDamien Miller 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
1089b481510SDamien Miller 	tmp = (head)->sph_root;						\
1099b481510SDamien Miller 	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
1109b481510SDamien Miller } while (0)
1119b481510SDamien Miller 
1129b481510SDamien Miller #define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
1139b481510SDamien Miller 	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
1149b481510SDamien Miller 	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
1159b481510SDamien Miller 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
1169b481510SDamien Miller 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
1179b481510SDamien Miller } while (0)
1189b481510SDamien Miller 
1199b481510SDamien Miller /* Generates prototypes and inline functions */
1209b481510SDamien Miller 
1219b481510SDamien Miller #define SPLAY_PROTOTYPE(name, type, field, cmp)				\
1229b481510SDamien Miller void name##_SPLAY(struct name *, struct type *);			\
1239b481510SDamien Miller void name##_SPLAY_MINMAX(struct name *, int);				\
1249b481510SDamien Miller struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
1259b481510SDamien Miller struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
1269b481510SDamien Miller 									\
1279b481510SDamien Miller /* Finds the node with the same key as elm */				\
1289b481510SDamien Miller static __inline struct type *						\
1299b481510SDamien Miller name##_SPLAY_FIND(struct name *head, struct type *elm)			\
1309b481510SDamien Miller {									\
1319b481510SDamien Miller 	if (SPLAY_EMPTY(head))						\
1329b481510SDamien Miller 		return(NULL);						\
1339b481510SDamien Miller 	name##_SPLAY(head, elm);					\
1349b481510SDamien Miller 	if ((cmp)(elm, (head)->sph_root) == 0)				\
1359b481510SDamien Miller 		return (head->sph_root);				\
1369b481510SDamien Miller 	return (NULL);							\
1379b481510SDamien Miller }									\
1389b481510SDamien Miller 									\
1399b481510SDamien Miller static __inline struct type *						\
1409b481510SDamien Miller name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
1419b481510SDamien Miller {									\
1429b481510SDamien Miller 	name##_SPLAY(head, elm);					\
1439b481510SDamien Miller 	if (SPLAY_RIGHT(elm, field) != NULL) {				\
1449b481510SDamien Miller 		elm = SPLAY_RIGHT(elm, field);				\
1459b481510SDamien Miller 		while (SPLAY_LEFT(elm, field) != NULL) {		\
1469b481510SDamien Miller 			elm = SPLAY_LEFT(elm, field);			\
1479b481510SDamien Miller 		}							\
1489b481510SDamien Miller 	} else								\
1499b481510SDamien Miller 		elm = NULL;						\
1509b481510SDamien Miller 	return (elm);							\
1519b481510SDamien Miller }									\
1529b481510SDamien Miller 									\
1539b481510SDamien Miller static __inline struct type *						\
1549b481510SDamien Miller name##_SPLAY_MIN_MAX(struct name *head, int val)			\
1559b481510SDamien Miller {									\
1569b481510SDamien Miller 	name##_SPLAY_MINMAX(head, val);					\
1579b481510SDamien Miller         return (SPLAY_ROOT(head));					\
1589b481510SDamien Miller }
1599b481510SDamien Miller 
1609b481510SDamien Miller /* Main splay operation.
1619b481510SDamien Miller  * Moves node close to the key of elm to top
1629b481510SDamien Miller  */
1639b481510SDamien Miller #define SPLAY_GENERATE(name, type, field, cmp)				\
1649b481510SDamien Miller struct type *								\
1659b481510SDamien Miller name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
1669b481510SDamien Miller {									\
1679b481510SDamien Miller     if (SPLAY_EMPTY(head)) {						\
1689b481510SDamien Miller 	    SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;	\
1699b481510SDamien Miller     } else {								\
1709b481510SDamien Miller 	    int __comp;							\
1719b481510SDamien Miller 	    name##_SPLAY(head, elm);					\
1729b481510SDamien Miller 	    __comp = (cmp)(elm, (head)->sph_root);			\
1739b481510SDamien Miller 	    if(__comp < 0) {						\
1749b481510SDamien Miller 		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
1759b481510SDamien Miller 		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
1769b481510SDamien Miller 		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
1779b481510SDamien Miller 	    } else if (__comp > 0) {					\
1789b481510SDamien Miller 		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
1799b481510SDamien Miller 		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
1809b481510SDamien Miller 		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
1819b481510SDamien Miller 	    } else							\
1829b481510SDamien Miller 		    return ((head)->sph_root);				\
1839b481510SDamien Miller     }									\
1849b481510SDamien Miller     (head)->sph_root = (elm);						\
1859b481510SDamien Miller     return (NULL);							\
1869b481510SDamien Miller }									\
1879b481510SDamien Miller 									\
1889b481510SDamien Miller struct type *								\
1899b481510SDamien Miller name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
1909b481510SDamien Miller {									\
1919b481510SDamien Miller 	struct type *__tmp;						\
1929b481510SDamien Miller 	if (SPLAY_EMPTY(head))						\
1939b481510SDamien Miller 		return (NULL);						\
1949b481510SDamien Miller 	name##_SPLAY(head, elm);					\
1959b481510SDamien Miller 	if ((cmp)(elm, (head)->sph_root) == 0) {			\
1969b481510SDamien Miller 		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
1979b481510SDamien Miller 			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
1989b481510SDamien Miller 		} else {						\
1999b481510SDamien Miller 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
2009b481510SDamien Miller 			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
2019b481510SDamien Miller 			name##_SPLAY(head, elm);			\
2029b481510SDamien Miller 			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
2039b481510SDamien Miller 		}							\
2049b481510SDamien Miller 		return (elm);						\
2059b481510SDamien Miller 	}								\
2069b481510SDamien Miller 	return (NULL);							\
2079b481510SDamien Miller }									\
2089b481510SDamien Miller 									\
2099b481510SDamien Miller void									\
2109b481510SDamien Miller name##_SPLAY(struct name *head, struct type *elm)			\
2119b481510SDamien Miller {									\
2129b481510SDamien Miller 	struct type __node, *__left, *__right, *__tmp;			\
2139b481510SDamien Miller 	int __comp;							\
2149b481510SDamien Miller \
2159b481510SDamien Miller 	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
2169b481510SDamien Miller 	__left = __right = &__node;					\
2179b481510SDamien Miller \
2189b481510SDamien Miller 	while ((__comp = (cmp)(elm, (head)->sph_root))) {		\
2199b481510SDamien Miller 		if (__comp < 0) {					\
2209b481510SDamien Miller 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
2219b481510SDamien Miller 			if (__tmp == NULL)				\
2229b481510SDamien Miller 				break;					\
2239b481510SDamien Miller 			if ((cmp)(elm, __tmp) < 0){			\
2249b481510SDamien Miller 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
2259b481510SDamien Miller 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
2269b481510SDamien Miller 					break;				\
2279b481510SDamien Miller 			}						\
2289b481510SDamien Miller 			SPLAY_LINKLEFT(head, __right, field);		\
2299b481510SDamien Miller 		} else if (__comp > 0) {				\
2309b481510SDamien Miller 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
2319b481510SDamien Miller 			if (__tmp == NULL)				\
2329b481510SDamien Miller 				break;					\
2339b481510SDamien Miller 			if ((cmp)(elm, __tmp) > 0){			\
2349b481510SDamien Miller 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
2359b481510SDamien Miller 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
2369b481510SDamien Miller 					break;				\
2379b481510SDamien Miller 			}						\
2389b481510SDamien Miller 			SPLAY_LINKRIGHT(head, __left, field);		\
2399b481510SDamien Miller 		}							\
2409b481510SDamien Miller 	}								\
2419b481510SDamien Miller 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
2429b481510SDamien Miller }									\
2439b481510SDamien Miller 									\
2449b481510SDamien Miller /* Splay with either the minimum or the maximum element			\
2459b481510SDamien Miller  * Used to find minimum or maximum element in tree.			\
2469b481510SDamien Miller  */									\
2479b481510SDamien Miller void name##_SPLAY_MINMAX(struct name *head, int __comp) \
2489b481510SDamien Miller {									\
2499b481510SDamien Miller 	struct type __node, *__left, *__right, *__tmp;			\
2509b481510SDamien Miller \
2519b481510SDamien Miller 	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
2529b481510SDamien Miller 	__left = __right = &__node;					\
2539b481510SDamien Miller \
2549b481510SDamien Miller 	while (1) {							\
2559b481510SDamien Miller 		if (__comp < 0) {					\
2569b481510SDamien Miller 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
2579b481510SDamien Miller 			if (__tmp == NULL)				\
2589b481510SDamien Miller 				break;					\
2599b481510SDamien Miller 			if (__comp < 0){				\
2609b481510SDamien Miller 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
2619b481510SDamien Miller 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
2629b481510SDamien Miller 					break;				\
2639b481510SDamien Miller 			}						\
2649b481510SDamien Miller 			SPLAY_LINKLEFT(head, __right, field);		\
2659b481510SDamien Miller 		} else if (__comp > 0) {				\
2669b481510SDamien Miller 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
2679b481510SDamien Miller 			if (__tmp == NULL)				\
2689b481510SDamien Miller 				break;					\
2699b481510SDamien Miller 			if (__comp > 0) {				\
2709b481510SDamien Miller 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
2719b481510SDamien Miller 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
2729b481510SDamien Miller 					break;				\
2739b481510SDamien Miller 			}						\
2749b481510SDamien Miller 			SPLAY_LINKRIGHT(head, __left, field);		\
2759b481510SDamien Miller 		}							\
2769b481510SDamien Miller 	}								\
2779b481510SDamien Miller 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
2789b481510SDamien Miller }
2799b481510SDamien Miller 
2809b481510SDamien Miller #define SPLAY_NEGINF	-1
2819b481510SDamien Miller #define SPLAY_INF	1
2829b481510SDamien Miller 
2839b481510SDamien Miller #define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)
2849b481510SDamien Miller #define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)
2859b481510SDamien Miller #define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)
2869b481510SDamien Miller #define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)
2879b481510SDamien Miller #define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\
2889b481510SDamien Miller 					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
2899b481510SDamien Miller #define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\
2909b481510SDamien Miller 					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
2919b481510SDamien Miller 
2929b481510SDamien Miller #define SPLAY_FOREACH(x, name, head)					\
2939b481510SDamien Miller 	for ((x) = SPLAY_MIN(name, head);				\
2949b481510SDamien Miller 	     (x) != NULL;						\
2959b481510SDamien Miller 	     (x) = SPLAY_NEXT(name, head, x))
2969b481510SDamien Miller 
2970afeae42SDamien Miller /* Macros that define a red-black tree */
2989b481510SDamien Miller #define RB_HEAD(name, type)						\
2999b481510SDamien Miller struct name {								\
3009b481510SDamien Miller 	struct type *rbh_root; /* root of the tree */			\
3019b481510SDamien Miller }
3029b481510SDamien Miller 
3039b481510SDamien Miller #define RB_INITIALIZER(root)						\
3049b481510SDamien Miller 	{ NULL }
3059b481510SDamien Miller 
3069b481510SDamien Miller #define RB_INIT(root) do {						\
3079b481510SDamien Miller 	(root)->rbh_root = NULL;					\
3089b481510SDamien Miller } while (0)
3099b481510SDamien Miller 
3109b481510SDamien Miller #define RB_BLACK	0
3119b481510SDamien Miller #define RB_RED		1
3129b481510SDamien Miller #define RB_ENTRY(type)							\
3139b481510SDamien Miller struct {								\
3149b481510SDamien Miller 	struct type *rbe_left;		/* left element */		\
3159b481510SDamien Miller 	struct type *rbe_right;		/* right element */		\
3169b481510SDamien Miller 	struct type *rbe_parent;	/* parent element */		\
3179b481510SDamien Miller 	int rbe_color;			/* node color */		\
3189b481510SDamien Miller }
3199b481510SDamien Miller 
3209b481510SDamien Miller #define RB_LEFT(elm, field)		(elm)->field.rbe_left
3219b481510SDamien Miller #define RB_RIGHT(elm, field)		(elm)->field.rbe_right
3229b481510SDamien Miller #define RB_PARENT(elm, field)		(elm)->field.rbe_parent
3239b481510SDamien Miller #define RB_COLOR(elm, field)		(elm)->field.rbe_color
3249b481510SDamien Miller #define RB_ROOT(head)			(head)->rbh_root
3259b481510SDamien Miller #define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
3269b481510SDamien Miller 
3279b481510SDamien Miller #define RB_SET(elm, parent, field) do {					\
3289b481510SDamien Miller 	RB_PARENT(elm, field) = parent;					\
3299b481510SDamien Miller 	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
3309b481510SDamien Miller 	RB_COLOR(elm, field) = RB_RED;					\
3319b481510SDamien Miller } while (0)
3329b481510SDamien Miller 
3339b481510SDamien Miller #define RB_SET_BLACKRED(black, red, field) do {				\
3349b481510SDamien Miller 	RB_COLOR(black, field) = RB_BLACK;				\
3359b481510SDamien Miller 	RB_COLOR(red, field) = RB_RED;					\
3369b481510SDamien Miller } while (0)
3379b481510SDamien Miller 
3389b481510SDamien Miller #ifndef RB_AUGMENT
339d60b2108SDamien Miller #define RB_AUGMENT(x)	do {} while (0)
3409b481510SDamien Miller #endif
3419b481510SDamien Miller 
3429b481510SDamien Miller #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
3439b481510SDamien Miller 	(tmp) = RB_RIGHT(elm, field);					\
3449b481510SDamien Miller 	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {		\
3459b481510SDamien Miller 		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
3469b481510SDamien Miller 	}								\
3479b481510SDamien Miller 	RB_AUGMENT(elm);						\
3489b481510SDamien Miller 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
3499b481510SDamien Miller 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
3509b481510SDamien Miller 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
3519b481510SDamien Miller 		else							\
3529b481510SDamien Miller 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
3539b481510SDamien Miller 	} else								\
3549b481510SDamien Miller 		(head)->rbh_root = (tmp);				\
3559b481510SDamien Miller 	RB_LEFT(tmp, field) = (elm);					\
3569b481510SDamien Miller 	RB_PARENT(elm, field) = (tmp);					\
3579b481510SDamien Miller 	RB_AUGMENT(tmp);						\
35813dd03a0SDamien Miller 	if ((RB_PARENT(tmp, field)))					\
35913dd03a0SDamien Miller 		RB_AUGMENT(RB_PARENT(tmp, field));			\
3609b481510SDamien Miller } while (0)
3619b481510SDamien Miller 
3629b481510SDamien Miller #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
3639b481510SDamien Miller 	(tmp) = RB_LEFT(elm, field);					\
3649b481510SDamien Miller 	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {		\
3659b481510SDamien Miller 		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
3669b481510SDamien Miller 	}								\
3679b481510SDamien Miller 	RB_AUGMENT(elm);						\
3689b481510SDamien Miller 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
3699b481510SDamien Miller 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
3709b481510SDamien Miller 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
3719b481510SDamien Miller 		else							\
3729b481510SDamien Miller 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
3739b481510SDamien Miller 	} else								\
3749b481510SDamien Miller 		(head)->rbh_root = (tmp);				\
3759b481510SDamien Miller 	RB_RIGHT(tmp, field) = (elm);					\
3769b481510SDamien Miller 	RB_PARENT(elm, field) = (tmp);					\
3779b481510SDamien Miller 	RB_AUGMENT(tmp);						\
37813dd03a0SDamien Miller 	if ((RB_PARENT(tmp, field)))					\
37913dd03a0SDamien Miller 		RB_AUGMENT(RB_PARENT(tmp, field));			\
3809b481510SDamien Miller } while (0)
3819b481510SDamien Miller 
3829b481510SDamien Miller /* Generates prototypes and inline functions */
3839b481510SDamien Miller #define	RB_PROTOTYPE(name, type, field, cmp)				\
384d60b2108SDamien Miller 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
385d60b2108SDamien Miller #define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
386d60b2108SDamien Miller 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
387d60b2108SDamien Miller #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
388d60b2108SDamien Miller attr void name##_RB_INSERT_COLOR(struct name *, struct type *);		\
389d60b2108SDamien Miller attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
390d60b2108SDamien Miller attr struct type *name##_RB_REMOVE(struct name *, struct type *);	\
391d60b2108SDamien Miller attr struct type *name##_RB_INSERT(struct name *, struct type *);	\
392d60b2108SDamien Miller attr struct type *name##_RB_FIND(struct name *, struct type *);		\
393d60b2108SDamien Miller attr struct type *name##_RB_NFIND(struct name *, struct type *);	\
394d60b2108SDamien Miller attr struct type *name##_RB_NEXT(struct type *);			\
395d60b2108SDamien Miller attr struct type *name##_RB_PREV(struct type *);			\
396d60b2108SDamien Miller attr struct type *name##_RB_MINMAX(struct name *, int);			\
397d60b2108SDamien Miller 									\
3989b481510SDamien Miller 
3999b481510SDamien Miller /* Main rb operation.
4009b481510SDamien Miller  * Moves node close to the key of elm to top
4019b481510SDamien Miller  */
4029b481510SDamien Miller #define	RB_GENERATE(name, type, field, cmp)				\
403d60b2108SDamien Miller 	RB_GENERATE_INTERNAL(name, type, field, cmp,)
404d60b2108SDamien Miller #define	RB_GENERATE_STATIC(name, type, field, cmp)			\
405d60b2108SDamien Miller 	RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
406d60b2108SDamien Miller #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
407d60b2108SDamien Miller attr void								\
4089b481510SDamien Miller name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
4099b481510SDamien Miller {									\
4109b481510SDamien Miller 	struct type *parent, *gparent, *tmp;				\
4119b481510SDamien Miller 	while ((parent = RB_PARENT(elm, field)) &&			\
4129b481510SDamien Miller 	    RB_COLOR(parent, field) == RB_RED) {			\
4139b481510SDamien Miller 		gparent = RB_PARENT(parent, field);			\
4149b481510SDamien Miller 		if (parent == RB_LEFT(gparent, field)) {		\
4159b481510SDamien Miller 			tmp = RB_RIGHT(gparent, field);			\
4169b481510SDamien Miller 			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
4179b481510SDamien Miller 				RB_COLOR(tmp, field) = RB_BLACK;	\
4189b481510SDamien Miller 				RB_SET_BLACKRED(parent, gparent, field);\
4199b481510SDamien Miller 				elm = gparent;				\
4209b481510SDamien Miller 				continue;				\
4219b481510SDamien Miller 			}						\
4229b481510SDamien Miller 			if (RB_RIGHT(parent, field) == elm) {		\
4239b481510SDamien Miller 				RB_ROTATE_LEFT(head, parent, tmp, field);\
4249b481510SDamien Miller 				tmp = parent;				\
4259b481510SDamien Miller 				parent = elm;				\
4269b481510SDamien Miller 				elm = tmp;				\
4279b481510SDamien Miller 			}						\
4289b481510SDamien Miller 			RB_SET_BLACKRED(parent, gparent, field);	\
4299b481510SDamien Miller 			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
4309b481510SDamien Miller 		} else {						\
4319b481510SDamien Miller 			tmp = RB_LEFT(gparent, field);			\
4329b481510SDamien Miller 			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
4339b481510SDamien Miller 				RB_COLOR(tmp, field) = RB_BLACK;	\
4349b481510SDamien Miller 				RB_SET_BLACKRED(parent, gparent, field);\
4359b481510SDamien Miller 				elm = gparent;				\
4369b481510SDamien Miller 				continue;				\
4379b481510SDamien Miller 			}						\
4389b481510SDamien Miller 			if (RB_LEFT(parent, field) == elm) {		\
4399b481510SDamien Miller 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
4409b481510SDamien Miller 				tmp = parent;				\
4419b481510SDamien Miller 				parent = elm;				\
4429b481510SDamien Miller 				elm = tmp;				\
4439b481510SDamien Miller 			}						\
4449b481510SDamien Miller 			RB_SET_BLACKRED(parent, gparent, field);	\
4459b481510SDamien Miller 			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
4469b481510SDamien Miller 		}							\
4479b481510SDamien Miller 	}								\
4489b481510SDamien Miller 	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
4499b481510SDamien Miller }									\
4509b481510SDamien Miller 									\
451d60b2108SDamien Miller attr void								\
4529b481510SDamien Miller name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
4539b481510SDamien Miller {									\
4549b481510SDamien Miller 	struct type *tmp;						\
4559b481510SDamien Miller 	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\
4569b481510SDamien Miller 	    elm != RB_ROOT(head)) {					\
4579b481510SDamien Miller 		if (RB_LEFT(parent, field) == elm) {			\
4589b481510SDamien Miller 			tmp = RB_RIGHT(parent, field);			\
4599b481510SDamien Miller 			if (RB_COLOR(tmp, field) == RB_RED) {		\
4609b481510SDamien Miller 				RB_SET_BLACKRED(tmp, parent, field);	\
4619b481510SDamien Miller 				RB_ROTATE_LEFT(head, parent, tmp, field);\
4629b481510SDamien Miller 				tmp = RB_RIGHT(parent, field);		\
4639b481510SDamien Miller 			}						\
4649b481510SDamien Miller 			if ((RB_LEFT(tmp, field) == NULL ||		\
4659b481510SDamien Miller 			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
4669b481510SDamien Miller 			    (RB_RIGHT(tmp, field) == NULL ||		\
4679b481510SDamien Miller 			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
4689b481510SDamien Miller 				RB_COLOR(tmp, field) = RB_RED;		\
4699b481510SDamien Miller 				elm = parent;				\
4709b481510SDamien Miller 				parent = RB_PARENT(elm, field);		\
4719b481510SDamien Miller 			} else {					\
4729b481510SDamien Miller 				if (RB_RIGHT(tmp, field) == NULL ||	\
4739b481510SDamien Miller 				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
4749b481510SDamien Miller 					struct type *oleft;		\
4759b481510SDamien Miller 					if ((oleft = RB_LEFT(tmp, field)))\
4769b481510SDamien Miller 						RB_COLOR(oleft, field) = RB_BLACK;\
4779b481510SDamien Miller 					RB_COLOR(tmp, field) = RB_RED;	\
4789b481510SDamien Miller 					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
4799b481510SDamien Miller 					tmp = RB_RIGHT(parent, field);	\
4809b481510SDamien Miller 				}					\
4819b481510SDamien Miller 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
4829b481510SDamien Miller 				RB_COLOR(parent, field) = RB_BLACK;	\
4839b481510SDamien Miller 				if (RB_RIGHT(tmp, field))		\
4849b481510SDamien Miller 					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
4859b481510SDamien Miller 				RB_ROTATE_LEFT(head, parent, tmp, field);\
4869b481510SDamien Miller 				elm = RB_ROOT(head);			\
4879b481510SDamien Miller 				break;					\
4889b481510SDamien Miller 			}						\
4899b481510SDamien Miller 		} else {						\
4909b481510SDamien Miller 			tmp = RB_LEFT(parent, field);			\
4919b481510SDamien Miller 			if (RB_COLOR(tmp, field) == RB_RED) {		\
4929b481510SDamien Miller 				RB_SET_BLACKRED(tmp, parent, field);	\
4939b481510SDamien Miller 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
4949b481510SDamien Miller 				tmp = RB_LEFT(parent, field);		\
4959b481510SDamien Miller 			}						\
4969b481510SDamien Miller 			if ((RB_LEFT(tmp, field) == NULL ||		\
4979b481510SDamien Miller 			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
4989b481510SDamien Miller 			    (RB_RIGHT(tmp, field) == NULL ||		\
4999b481510SDamien Miller 			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
5009b481510SDamien Miller 				RB_COLOR(tmp, field) = RB_RED;		\
5019b481510SDamien Miller 				elm = parent;				\
5029b481510SDamien Miller 				parent = RB_PARENT(elm, field);		\
5039b481510SDamien Miller 			} else {					\
5049b481510SDamien Miller 				if (RB_LEFT(tmp, field) == NULL ||	\
5059b481510SDamien Miller 				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
5069b481510SDamien Miller 					struct type *oright;		\
5079b481510SDamien Miller 					if ((oright = RB_RIGHT(tmp, field)))\
5089b481510SDamien Miller 						RB_COLOR(oright, field) = RB_BLACK;\
5099b481510SDamien Miller 					RB_COLOR(tmp, field) = RB_RED;	\
5109b481510SDamien Miller 					RB_ROTATE_LEFT(head, tmp, oright, field);\
5119b481510SDamien Miller 					tmp = RB_LEFT(parent, field);	\
5129b481510SDamien Miller 				}					\
5139b481510SDamien Miller 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
5149b481510SDamien Miller 				RB_COLOR(parent, field) = RB_BLACK;	\
5159b481510SDamien Miller 				if (RB_LEFT(tmp, field))		\
5169b481510SDamien Miller 					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
5179b481510SDamien Miller 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
5189b481510SDamien Miller 				elm = RB_ROOT(head);			\
5199b481510SDamien Miller 				break;					\
5209b481510SDamien Miller 			}						\
5219b481510SDamien Miller 		}							\
5229b481510SDamien Miller 	}								\
5239b481510SDamien Miller 	if (elm)							\
5249b481510SDamien Miller 		RB_COLOR(elm, field) = RB_BLACK;			\
5259b481510SDamien Miller }									\
5269b481510SDamien Miller 									\
527d60b2108SDamien Miller attr struct type *							\
5289b481510SDamien Miller name##_RB_REMOVE(struct name *head, struct type *elm)			\
5299b481510SDamien Miller {									\
5309b481510SDamien Miller 	struct type *child, *parent, *old = elm;			\
5319b481510SDamien Miller 	int color;							\
5329b481510SDamien Miller 	if (RB_LEFT(elm, field) == NULL)				\
5339b481510SDamien Miller 		child = RB_RIGHT(elm, field);				\
5349b481510SDamien Miller 	else if (RB_RIGHT(elm, field) == NULL)				\
5359b481510SDamien Miller 		child = RB_LEFT(elm, field);				\
5369b481510SDamien Miller 	else {								\
5379b481510SDamien Miller 		struct type *left;					\
5389b481510SDamien Miller 		elm = RB_RIGHT(elm, field);				\
5399b481510SDamien Miller 		while ((left = RB_LEFT(elm, field)))			\
5409b481510SDamien Miller 			elm = left;					\
5419b481510SDamien Miller 		child = RB_RIGHT(elm, field);				\
5429b481510SDamien Miller 		parent = RB_PARENT(elm, field);				\
5439b481510SDamien Miller 		color = RB_COLOR(elm, field);				\
5449b481510SDamien Miller 		if (child)						\
5459b481510SDamien Miller 			RB_PARENT(child, field) = parent;		\
5469b481510SDamien Miller 		if (parent) {						\
5479b481510SDamien Miller 			if (RB_LEFT(parent, field) == elm)		\
5489b481510SDamien Miller 				RB_LEFT(parent, field) = child;		\
5499b481510SDamien Miller 			else						\
5509b481510SDamien Miller 				RB_RIGHT(parent, field) = child;	\
5519b481510SDamien Miller 			RB_AUGMENT(parent);				\
5529b481510SDamien Miller 		} else							\
5539b481510SDamien Miller 			RB_ROOT(head) = child;				\
5549b481510SDamien Miller 		if (RB_PARENT(elm, field) == old)			\
5559b481510SDamien Miller 			parent = elm;					\
5569b481510SDamien Miller 		(elm)->field = (old)->field;				\
5579b481510SDamien Miller 		if (RB_PARENT(old, field)) {				\
5589b481510SDamien Miller 			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
5599b481510SDamien Miller 				RB_LEFT(RB_PARENT(old, field), field) = elm;\
5609b481510SDamien Miller 			else						\
5619b481510SDamien Miller 				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
5629b481510SDamien Miller 			RB_AUGMENT(RB_PARENT(old, field));		\
5639b481510SDamien Miller 		} else							\
5649b481510SDamien Miller 			RB_ROOT(head) = elm;				\
5659b481510SDamien Miller 		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
5669b481510SDamien Miller 		if (RB_RIGHT(old, field))				\
5679b481510SDamien Miller 			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
5689b481510SDamien Miller 		if (parent) {						\
5699b481510SDamien Miller 			left = parent;					\
5709b481510SDamien Miller 			do {						\
5719b481510SDamien Miller 				RB_AUGMENT(left);			\
5729b481510SDamien Miller 			} while ((left = RB_PARENT(left, field)));	\
5739b481510SDamien Miller 		}							\
5749b481510SDamien Miller 		goto color;						\
5759b481510SDamien Miller 	}								\
5769b481510SDamien Miller 	parent = RB_PARENT(elm, field);					\
5779b481510SDamien Miller 	color = RB_COLOR(elm, field);					\
5789b481510SDamien Miller 	if (child)							\
5799b481510SDamien Miller 		RB_PARENT(child, field) = parent;			\
5809b481510SDamien Miller 	if (parent) {							\
5819b481510SDamien Miller 		if (RB_LEFT(parent, field) == elm)			\
5829b481510SDamien Miller 			RB_LEFT(parent, field) = child;			\
5839b481510SDamien Miller 		else							\
5849b481510SDamien Miller 			RB_RIGHT(parent, field) = child;		\
5859b481510SDamien Miller 		RB_AUGMENT(parent);					\
5869b481510SDamien Miller 	} else								\
5879b481510SDamien Miller 		RB_ROOT(head) = child;					\
5889b481510SDamien Miller color:									\
5899b481510SDamien Miller 	if (color == RB_BLACK)						\
5909b481510SDamien Miller 		name##_RB_REMOVE_COLOR(head, parent, child);		\
5919b481510SDamien Miller 	return (old);							\
5929b481510SDamien Miller }									\
5939b481510SDamien Miller 									\
5949b481510SDamien Miller /* Inserts a node into the RB tree */					\
595d60b2108SDamien Miller attr struct type *							\
5969b481510SDamien Miller name##_RB_INSERT(struct name *head, struct type *elm)			\
5979b481510SDamien Miller {									\
5989b481510SDamien Miller 	struct type *tmp;						\
5999b481510SDamien Miller 	struct type *parent = NULL;					\
6009b481510SDamien Miller 	int comp = 0;							\
6019b481510SDamien Miller 	tmp = RB_ROOT(head);						\
6029b481510SDamien Miller 	while (tmp) {							\
6039b481510SDamien Miller 		parent = tmp;						\
6049b481510SDamien Miller 		comp = (cmp)(elm, parent);				\
6059b481510SDamien Miller 		if (comp < 0)						\
6069b481510SDamien Miller 			tmp = RB_LEFT(tmp, field);			\
6079b481510SDamien Miller 		else if (comp > 0)					\
6089b481510SDamien Miller 			tmp = RB_RIGHT(tmp, field);			\
6099b481510SDamien Miller 		else							\
6109b481510SDamien Miller 			return (tmp);					\
6119b481510SDamien Miller 	}								\
6129b481510SDamien Miller 	RB_SET(elm, parent, field);					\
6139b481510SDamien Miller 	if (parent != NULL) {						\
6149b481510SDamien Miller 		if (comp < 0)						\
6159b481510SDamien Miller 			RB_LEFT(parent, field) = elm;			\
6169b481510SDamien Miller 		else							\
6179b481510SDamien Miller 			RB_RIGHT(parent, field) = elm;			\
6189b481510SDamien Miller 		RB_AUGMENT(parent);					\
6199b481510SDamien Miller 	} else								\
6209b481510SDamien Miller 		RB_ROOT(head) = elm;					\
6219b481510SDamien Miller 	name##_RB_INSERT_COLOR(head, elm);				\
6229b481510SDamien Miller 	return (NULL);							\
6239b481510SDamien Miller }									\
6249b481510SDamien Miller 									\
6259b481510SDamien Miller /* Finds the node with the same key as elm */				\
626d60b2108SDamien Miller attr struct type *							\
6279b481510SDamien Miller name##_RB_FIND(struct name *head, struct type *elm)			\
6289b481510SDamien Miller {									\
6299b481510SDamien Miller 	struct type *tmp = RB_ROOT(head);				\
6309b481510SDamien Miller 	int comp;							\
6319b481510SDamien Miller 	while (tmp) {							\
6329b481510SDamien Miller 		comp = cmp(elm, tmp);					\
6339b481510SDamien Miller 		if (comp < 0)						\
6349b481510SDamien Miller 			tmp = RB_LEFT(tmp, field);			\
6359b481510SDamien Miller 		else if (comp > 0)					\
6369b481510SDamien Miller 			tmp = RB_RIGHT(tmp, field);			\
6379b481510SDamien Miller 		else							\
6389b481510SDamien Miller 			return (tmp);					\
6399b481510SDamien Miller 	}								\
6409b481510SDamien Miller 	return (NULL);							\
6419b481510SDamien Miller }									\
6429b481510SDamien Miller 									\
643d60b2108SDamien Miller /* Finds the first node greater than or equal to the search key */	\
644d60b2108SDamien Miller attr struct type *							\
645d60b2108SDamien Miller name##_RB_NFIND(struct name *head, struct type *elm)			\
646d60b2108SDamien Miller {									\
647d60b2108SDamien Miller 	struct type *tmp = RB_ROOT(head);				\
648d60b2108SDamien Miller 	struct type *res = NULL;					\
649d60b2108SDamien Miller 	int comp;							\
650d60b2108SDamien Miller 	while (tmp) {							\
651d60b2108SDamien Miller 		comp = cmp(elm, tmp);					\
652d60b2108SDamien Miller 		if (comp < 0) {						\
653d60b2108SDamien Miller 			res = tmp;					\
654d60b2108SDamien Miller 			tmp = RB_LEFT(tmp, field);			\
655d60b2108SDamien Miller 		}							\
656d60b2108SDamien Miller 		else if (comp > 0)					\
657d60b2108SDamien Miller 			tmp = RB_RIGHT(tmp, field);			\
658d60b2108SDamien Miller 		else							\
659d60b2108SDamien Miller 			return (tmp);					\
660d60b2108SDamien Miller 	}								\
661d60b2108SDamien Miller 	return (res);							\
662d60b2108SDamien Miller }									\
663d60b2108SDamien Miller 									\
664d60b2108SDamien Miller /* ARGSUSED */								\
665d60b2108SDamien Miller attr struct type *							\
66688aa4e3dSDamien Miller name##_RB_NEXT(struct type *elm)					\
6679b481510SDamien Miller {									\
6689b481510SDamien Miller 	if (RB_RIGHT(elm, field)) {					\
6699b481510SDamien Miller 		elm = RB_RIGHT(elm, field);				\
6709b481510SDamien Miller 		while (RB_LEFT(elm, field))				\
6719b481510SDamien Miller 			elm = RB_LEFT(elm, field);			\
6729b481510SDamien Miller 	} else {							\
6739b481510SDamien Miller 		if (RB_PARENT(elm, field) &&				\
6749b481510SDamien Miller 		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\
6759b481510SDamien Miller 			elm = RB_PARENT(elm, field);			\
6769b481510SDamien Miller 		else {							\
6779b481510SDamien Miller 			while (RB_PARENT(elm, field) &&			\
6789b481510SDamien Miller 			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
6799b481510SDamien Miller 				elm = RB_PARENT(elm, field);		\
6809b481510SDamien Miller 			elm = RB_PARENT(elm, field);			\
6819b481510SDamien Miller 		}							\
6829b481510SDamien Miller 	}								\
6839b481510SDamien Miller 	return (elm);							\
6849b481510SDamien Miller }									\
6859b481510SDamien Miller 									\
686d60b2108SDamien Miller /* ARGSUSED */								\
687d60b2108SDamien Miller attr struct type *							\
688d60b2108SDamien Miller name##_RB_PREV(struct type *elm)					\
689d60b2108SDamien Miller {									\
690d60b2108SDamien Miller 	if (RB_LEFT(elm, field)) {					\
691d60b2108SDamien Miller 		elm = RB_LEFT(elm, field);				\
692d60b2108SDamien Miller 		while (RB_RIGHT(elm, field))				\
693d60b2108SDamien Miller 			elm = RB_RIGHT(elm, field);			\
694d60b2108SDamien Miller 	} else {							\
695d60b2108SDamien Miller 		if (RB_PARENT(elm, field) &&				\
696d60b2108SDamien Miller 		    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))	\
697d60b2108SDamien Miller 			elm = RB_PARENT(elm, field);			\
698d60b2108SDamien Miller 		else {							\
699d60b2108SDamien Miller 			while (RB_PARENT(elm, field) &&			\
700d60b2108SDamien Miller 			    (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
701d60b2108SDamien Miller 				elm = RB_PARENT(elm, field);		\
702d60b2108SDamien Miller 			elm = RB_PARENT(elm, field);			\
703d60b2108SDamien Miller 		}							\
704d60b2108SDamien Miller 	}								\
705d60b2108SDamien Miller 	return (elm);							\
706d60b2108SDamien Miller }									\
707d60b2108SDamien Miller 									\
708d60b2108SDamien Miller attr struct type *							\
7099b481510SDamien Miller name##_RB_MINMAX(struct name *head, int val)				\
7109b481510SDamien Miller {									\
7119b481510SDamien Miller 	struct type *tmp = RB_ROOT(head);				\
7129b481510SDamien Miller 	struct type *parent = NULL;					\
7139b481510SDamien Miller 	while (tmp) {							\
7149b481510SDamien Miller 		parent = tmp;						\
7159b481510SDamien Miller 		if (val < 0)						\
7169b481510SDamien Miller 			tmp = RB_LEFT(tmp, field);			\
7179b481510SDamien Miller 		else							\
7189b481510SDamien Miller 			tmp = RB_RIGHT(tmp, field);			\
7199b481510SDamien Miller 	}								\
7209b481510SDamien Miller 	return (parent);						\
7219b481510SDamien Miller }
7229b481510SDamien Miller 
7239b481510SDamien Miller #define RB_NEGINF	-1
7249b481510SDamien Miller #define RB_INF	1
7259b481510SDamien Miller 
7269b481510SDamien Miller #define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
7279b481510SDamien Miller #define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
7289b481510SDamien Miller #define RB_FIND(name, x, y)	name##_RB_FIND(x, y)
729d60b2108SDamien Miller #define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)
73088aa4e3dSDamien Miller #define RB_NEXT(name, x, y)	name##_RB_NEXT(y)
731d60b2108SDamien Miller #define RB_PREV(name, x, y)	name##_RB_PREV(y)
7329b481510SDamien Miller #define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)
7339b481510SDamien Miller #define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)
7349b481510SDamien Miller 
7359b481510SDamien Miller #define RB_FOREACH(x, name, head)					\
7369b481510SDamien Miller 	for ((x) = RB_MIN(name, head);					\
7379b481510SDamien Miller 	     (x) != NULL;						\
73888aa4e3dSDamien Miller 	     (x) = name##_RB_NEXT(x))
7399b481510SDamien Miller 
740d60b2108SDamien Miller #define RB_FOREACH_SAFE(x, name, head, y)				\
741d60b2108SDamien Miller 	for ((x) = RB_MIN(name, head);					\
742d60b2108SDamien Miller 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1);		\
743d60b2108SDamien Miller 	     (x) = (y))
744d60b2108SDamien Miller 
745d60b2108SDamien Miller #define RB_FOREACH_REVERSE(x, name, head)				\
746d60b2108SDamien Miller 	for ((x) = RB_MAX(name, head);					\
747d60b2108SDamien Miller 	     (x) != NULL;						\
748d60b2108SDamien Miller 	     (x) = name##_RB_PREV(x))
749d60b2108SDamien Miller 
750d60b2108SDamien Miller #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\
751d60b2108SDamien Miller 	for ((x) = RB_MAX(name, head);					\
752d60b2108SDamien Miller 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), 1);		\
753d60b2108SDamien Miller 	     (x) = (y))
754d60b2108SDamien Miller 
7559b481510SDamien Miller #endif	/* _SYS_TREE_H_ */
756