xref: /freebsd/crypto/openssh/openbsd-compat/sys-tree.h (revision 4b17dab0ba7675679933f9f3d4aed1cd28dd0393)
14b17dab0SDag-Erling Smørgrav /*	$OpenBSD: tree.h,v 1.6 2002/06/11 22:09:52 provos Exp $	*/
24b17dab0SDag-Erling Smørgrav /*
34b17dab0SDag-Erling Smørgrav  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
44b17dab0SDag-Erling Smørgrav  * All rights reserved.
54b17dab0SDag-Erling Smørgrav  *
64b17dab0SDag-Erling Smørgrav  * Redistribution and use in source and binary forms, with or without
74b17dab0SDag-Erling Smørgrav  * modification, are permitted provided that the following conditions
84b17dab0SDag-Erling Smørgrav  * are met:
94b17dab0SDag-Erling Smørgrav  * 1. Redistributions of source code must retain the above copyright
104b17dab0SDag-Erling Smørgrav  *    notice, this list of conditions and the following disclaimer.
114b17dab0SDag-Erling Smørgrav  * 2. Redistributions in binary form must reproduce the above copyright
124b17dab0SDag-Erling Smørgrav  *    notice, this list of conditions and the following disclaimer in the
134b17dab0SDag-Erling Smørgrav  *    documentation and/or other materials provided with the distribution.
144b17dab0SDag-Erling Smørgrav  *
154b17dab0SDag-Erling Smørgrav  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
164b17dab0SDag-Erling Smørgrav  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
174b17dab0SDag-Erling Smørgrav  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
184b17dab0SDag-Erling Smørgrav  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
194b17dab0SDag-Erling Smørgrav  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
204b17dab0SDag-Erling Smørgrav  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
214b17dab0SDag-Erling Smørgrav  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
224b17dab0SDag-Erling Smørgrav  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
234b17dab0SDag-Erling Smørgrav  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
244b17dab0SDag-Erling Smørgrav  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
254b17dab0SDag-Erling Smørgrav  */
264b17dab0SDag-Erling Smørgrav 
274b17dab0SDag-Erling Smørgrav #ifndef	_SYS_TREE_H_
284b17dab0SDag-Erling Smørgrav #define	_SYS_TREE_H_
294b17dab0SDag-Erling Smørgrav 
304b17dab0SDag-Erling Smørgrav /*
314b17dab0SDag-Erling Smørgrav  * This file defines data structures for different types of trees:
324b17dab0SDag-Erling Smørgrav  * splay trees and red-black trees.
334b17dab0SDag-Erling Smørgrav  *
344b17dab0SDag-Erling Smørgrav  * A splay tree is a self-organizing data structure.  Every operation
354b17dab0SDag-Erling Smørgrav  * on the tree causes a splay to happen.  The splay moves the requested
364b17dab0SDag-Erling Smørgrav  * node to the root of the tree and partly rebalances it.
374b17dab0SDag-Erling Smørgrav  *
384b17dab0SDag-Erling Smørgrav  * This has the benefit that request locality causes faster lookups as
394b17dab0SDag-Erling Smørgrav  * the requested nodes move to the top of the tree.  On the other hand,
404b17dab0SDag-Erling Smørgrav  * every lookup causes memory writes.
414b17dab0SDag-Erling Smørgrav  *
424b17dab0SDag-Erling Smørgrav  * The Balance Theorem bounds the total access time for m operations
434b17dab0SDag-Erling Smørgrav  * and n inserts on an initially empty tree as O((m + n)lg n).  The
444b17dab0SDag-Erling Smørgrav  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
454b17dab0SDag-Erling Smørgrav  *
464b17dab0SDag-Erling Smørgrav  * A red-black tree is a binary search tree with the node color as an
474b17dab0SDag-Erling Smørgrav  * extra attribute.  It fulfills a set of conditions:
484b17dab0SDag-Erling Smørgrav  *	- every search path from the root to a leaf consists of the
494b17dab0SDag-Erling Smørgrav  *	  same number of black nodes,
504b17dab0SDag-Erling Smørgrav  *	- each red node (except for the root) has a black parent,
514b17dab0SDag-Erling Smørgrav  *	- each leaf node is black.
524b17dab0SDag-Erling Smørgrav  *
534b17dab0SDag-Erling Smørgrav  * Every operation on a red-black tree is bounded as O(lg n).
544b17dab0SDag-Erling Smørgrav  * The maximum height of a red-black tree is 2lg (n+1).
554b17dab0SDag-Erling Smørgrav  */
564b17dab0SDag-Erling Smørgrav 
574b17dab0SDag-Erling Smørgrav #define SPLAY_HEAD(name, type)						\
584b17dab0SDag-Erling Smørgrav struct name {								\
594b17dab0SDag-Erling Smørgrav 	struct type *sph_root; /* root of the tree */			\
604b17dab0SDag-Erling Smørgrav }
614b17dab0SDag-Erling Smørgrav 
624b17dab0SDag-Erling Smørgrav #define SPLAY_INITIALIZER(root)						\
634b17dab0SDag-Erling Smørgrav 	{ NULL }
644b17dab0SDag-Erling Smørgrav 
654b17dab0SDag-Erling Smørgrav #define SPLAY_INIT(root) do {						\
664b17dab0SDag-Erling Smørgrav 	(root)->sph_root = NULL;					\
674b17dab0SDag-Erling Smørgrav } while (0)
684b17dab0SDag-Erling Smørgrav 
694b17dab0SDag-Erling Smørgrav #define SPLAY_ENTRY(type)						\
704b17dab0SDag-Erling Smørgrav struct {								\
714b17dab0SDag-Erling Smørgrav 	struct type *spe_left; /* left element */			\
724b17dab0SDag-Erling Smørgrav 	struct type *spe_right; /* right element */			\
734b17dab0SDag-Erling Smørgrav }
744b17dab0SDag-Erling Smørgrav 
754b17dab0SDag-Erling Smørgrav #define SPLAY_LEFT(elm, field)		(elm)->field.spe_left
764b17dab0SDag-Erling Smørgrav #define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right
774b17dab0SDag-Erling Smørgrav #define SPLAY_ROOT(head)		(head)->sph_root
784b17dab0SDag-Erling Smørgrav #define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)
794b17dab0SDag-Erling Smørgrav 
804b17dab0SDag-Erling Smørgrav /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
814b17dab0SDag-Erling Smørgrav #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
824b17dab0SDag-Erling Smørgrav 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
834b17dab0SDag-Erling Smørgrav 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
844b17dab0SDag-Erling Smørgrav 	(head)->sph_root = tmp;						\
854b17dab0SDag-Erling Smørgrav } while (0)
864b17dab0SDag-Erling Smørgrav 
874b17dab0SDag-Erling Smørgrav #define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
884b17dab0SDag-Erling Smørgrav 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
894b17dab0SDag-Erling Smørgrav 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
904b17dab0SDag-Erling Smørgrav 	(head)->sph_root = tmp;						\
914b17dab0SDag-Erling Smørgrav } while (0)
924b17dab0SDag-Erling Smørgrav 
934b17dab0SDag-Erling Smørgrav #define SPLAY_LINKLEFT(head, tmp, field) do {				\
944b17dab0SDag-Erling Smørgrav 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
954b17dab0SDag-Erling Smørgrav 	tmp = (head)->sph_root;						\
964b17dab0SDag-Erling Smørgrav 	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
974b17dab0SDag-Erling Smørgrav } while (0)
984b17dab0SDag-Erling Smørgrav 
994b17dab0SDag-Erling Smørgrav #define SPLAY_LINKRIGHT(head, tmp, field) do {				\
1004b17dab0SDag-Erling Smørgrav 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
1014b17dab0SDag-Erling Smørgrav 	tmp = (head)->sph_root;						\
1024b17dab0SDag-Erling Smørgrav 	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
1034b17dab0SDag-Erling Smørgrav } while (0)
1044b17dab0SDag-Erling Smørgrav 
1054b17dab0SDag-Erling Smørgrav #define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
1064b17dab0SDag-Erling Smørgrav 	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
1074b17dab0SDag-Erling Smørgrav 	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
1084b17dab0SDag-Erling Smørgrav 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
1094b17dab0SDag-Erling Smørgrav 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
1104b17dab0SDag-Erling Smørgrav } while (0)
1114b17dab0SDag-Erling Smørgrav 
1124b17dab0SDag-Erling Smørgrav /* Generates prototypes and inline functions */
1134b17dab0SDag-Erling Smørgrav 
1144b17dab0SDag-Erling Smørgrav #define SPLAY_PROTOTYPE(name, type, field, cmp)				\
1154b17dab0SDag-Erling Smørgrav void name##_SPLAY(struct name *, struct type *);			\
1164b17dab0SDag-Erling Smørgrav void name##_SPLAY_MINMAX(struct name *, int);				\
1174b17dab0SDag-Erling Smørgrav struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
1184b17dab0SDag-Erling Smørgrav struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
1194b17dab0SDag-Erling Smørgrav 									\
1204b17dab0SDag-Erling Smørgrav /* Finds the node with the same key as elm */				\
1214b17dab0SDag-Erling Smørgrav static __inline struct type *						\
1224b17dab0SDag-Erling Smørgrav name##_SPLAY_FIND(struct name *head, struct type *elm)			\
1234b17dab0SDag-Erling Smørgrav {									\
1244b17dab0SDag-Erling Smørgrav 	if (SPLAY_EMPTY(head))						\
1254b17dab0SDag-Erling Smørgrav 		return(NULL);						\
1264b17dab0SDag-Erling Smørgrav 	name##_SPLAY(head, elm);					\
1274b17dab0SDag-Erling Smørgrav 	if ((cmp)(elm, (head)->sph_root) == 0)				\
1284b17dab0SDag-Erling Smørgrav 		return (head->sph_root);				\
1294b17dab0SDag-Erling Smørgrav 	return (NULL);							\
1304b17dab0SDag-Erling Smørgrav }									\
1314b17dab0SDag-Erling Smørgrav 									\
1324b17dab0SDag-Erling Smørgrav static __inline struct type *						\
1334b17dab0SDag-Erling Smørgrav name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
1344b17dab0SDag-Erling Smørgrav {									\
1354b17dab0SDag-Erling Smørgrav 	name##_SPLAY(head, elm);					\
1364b17dab0SDag-Erling Smørgrav 	if (SPLAY_RIGHT(elm, field) != NULL) {				\
1374b17dab0SDag-Erling Smørgrav 		elm = SPLAY_RIGHT(elm, field);				\
1384b17dab0SDag-Erling Smørgrav 		while (SPLAY_LEFT(elm, field) != NULL) {		\
1394b17dab0SDag-Erling Smørgrav 			elm = SPLAY_LEFT(elm, field);			\
1404b17dab0SDag-Erling Smørgrav 		}							\
1414b17dab0SDag-Erling Smørgrav 	} else								\
1424b17dab0SDag-Erling Smørgrav 		elm = NULL;						\
1434b17dab0SDag-Erling Smørgrav 	return (elm);							\
1444b17dab0SDag-Erling Smørgrav }									\
1454b17dab0SDag-Erling Smørgrav 									\
1464b17dab0SDag-Erling Smørgrav static __inline struct type *						\
1474b17dab0SDag-Erling Smørgrav name##_SPLAY_MIN_MAX(struct name *head, int val)			\
1484b17dab0SDag-Erling Smørgrav {									\
1494b17dab0SDag-Erling Smørgrav 	name##_SPLAY_MINMAX(head, val);					\
1504b17dab0SDag-Erling Smørgrav         return (SPLAY_ROOT(head));					\
1514b17dab0SDag-Erling Smørgrav }
1524b17dab0SDag-Erling Smørgrav 
1534b17dab0SDag-Erling Smørgrav /* Main splay operation.
1544b17dab0SDag-Erling Smørgrav  * Moves node close to the key of elm to top
1554b17dab0SDag-Erling Smørgrav  */
1564b17dab0SDag-Erling Smørgrav #define SPLAY_GENERATE(name, type, field, cmp)				\
1574b17dab0SDag-Erling Smørgrav struct type *								\
1584b17dab0SDag-Erling Smørgrav name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
1594b17dab0SDag-Erling Smørgrav {									\
1604b17dab0SDag-Erling Smørgrav     if (SPLAY_EMPTY(head)) {						\
1614b17dab0SDag-Erling Smørgrav 	    SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;	\
1624b17dab0SDag-Erling Smørgrav     } else {								\
1634b17dab0SDag-Erling Smørgrav 	    int __comp;							\
1644b17dab0SDag-Erling Smørgrav 	    name##_SPLAY(head, elm);					\
1654b17dab0SDag-Erling Smørgrav 	    __comp = (cmp)(elm, (head)->sph_root);			\
1664b17dab0SDag-Erling Smørgrav 	    if(__comp < 0) {						\
1674b17dab0SDag-Erling Smørgrav 		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
1684b17dab0SDag-Erling Smørgrav 		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
1694b17dab0SDag-Erling Smørgrav 		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
1704b17dab0SDag-Erling Smørgrav 	    } else if (__comp > 0) {					\
1714b17dab0SDag-Erling Smørgrav 		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
1724b17dab0SDag-Erling Smørgrav 		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
1734b17dab0SDag-Erling Smørgrav 		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
1744b17dab0SDag-Erling Smørgrav 	    } else							\
1754b17dab0SDag-Erling Smørgrav 		    return ((head)->sph_root);				\
1764b17dab0SDag-Erling Smørgrav     }									\
1774b17dab0SDag-Erling Smørgrav     (head)->sph_root = (elm);						\
1784b17dab0SDag-Erling Smørgrav     return (NULL);							\
1794b17dab0SDag-Erling Smørgrav }									\
1804b17dab0SDag-Erling Smørgrav 									\
1814b17dab0SDag-Erling Smørgrav struct type *								\
1824b17dab0SDag-Erling Smørgrav name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
1834b17dab0SDag-Erling Smørgrav {									\
1844b17dab0SDag-Erling Smørgrav 	struct type *__tmp;						\
1854b17dab0SDag-Erling Smørgrav 	if (SPLAY_EMPTY(head))						\
1864b17dab0SDag-Erling Smørgrav 		return (NULL);						\
1874b17dab0SDag-Erling Smørgrav 	name##_SPLAY(head, elm);					\
1884b17dab0SDag-Erling Smørgrav 	if ((cmp)(elm, (head)->sph_root) == 0) {			\
1894b17dab0SDag-Erling Smørgrav 		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
1904b17dab0SDag-Erling Smørgrav 			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
1914b17dab0SDag-Erling Smørgrav 		} else {						\
1924b17dab0SDag-Erling Smørgrav 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
1934b17dab0SDag-Erling Smørgrav 			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
1944b17dab0SDag-Erling Smørgrav 			name##_SPLAY(head, elm);			\
1954b17dab0SDag-Erling Smørgrav 			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
1964b17dab0SDag-Erling Smørgrav 		}							\
1974b17dab0SDag-Erling Smørgrav 		return (elm);						\
1984b17dab0SDag-Erling Smørgrav 	}								\
1994b17dab0SDag-Erling Smørgrav 	return (NULL);							\
2004b17dab0SDag-Erling Smørgrav }									\
2014b17dab0SDag-Erling Smørgrav 									\
2024b17dab0SDag-Erling Smørgrav void									\
2034b17dab0SDag-Erling Smørgrav name##_SPLAY(struct name *head, struct type *elm)			\
2044b17dab0SDag-Erling Smørgrav {									\
2054b17dab0SDag-Erling Smørgrav 	struct type __node, *__left, *__right, *__tmp;			\
2064b17dab0SDag-Erling Smørgrav 	int __comp;							\
2074b17dab0SDag-Erling Smørgrav \
2084b17dab0SDag-Erling Smørgrav 	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
2094b17dab0SDag-Erling Smørgrav 	__left = __right = &__node;					\
2104b17dab0SDag-Erling Smørgrav \
2114b17dab0SDag-Erling Smørgrav 	while ((__comp = (cmp)(elm, (head)->sph_root))) {		\
2124b17dab0SDag-Erling Smørgrav 		if (__comp < 0) {					\
2134b17dab0SDag-Erling Smørgrav 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
2144b17dab0SDag-Erling Smørgrav 			if (__tmp == NULL)				\
2154b17dab0SDag-Erling Smørgrav 				break;					\
2164b17dab0SDag-Erling Smørgrav 			if ((cmp)(elm, __tmp) < 0){			\
2174b17dab0SDag-Erling Smørgrav 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
2184b17dab0SDag-Erling Smørgrav 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
2194b17dab0SDag-Erling Smørgrav 					break;				\
2204b17dab0SDag-Erling Smørgrav 			}						\
2214b17dab0SDag-Erling Smørgrav 			SPLAY_LINKLEFT(head, __right, field);		\
2224b17dab0SDag-Erling Smørgrav 		} else if (__comp > 0) {				\
2234b17dab0SDag-Erling Smørgrav 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
2244b17dab0SDag-Erling Smørgrav 			if (__tmp == NULL)				\
2254b17dab0SDag-Erling Smørgrav 				break;					\
2264b17dab0SDag-Erling Smørgrav 			if ((cmp)(elm, __tmp) > 0){			\
2274b17dab0SDag-Erling Smørgrav 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
2284b17dab0SDag-Erling Smørgrav 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
2294b17dab0SDag-Erling Smørgrav 					break;				\
2304b17dab0SDag-Erling Smørgrav 			}						\
2314b17dab0SDag-Erling Smørgrav 			SPLAY_LINKRIGHT(head, __left, field);		\
2324b17dab0SDag-Erling Smørgrav 		}							\
2334b17dab0SDag-Erling Smørgrav 	}								\
2344b17dab0SDag-Erling Smørgrav 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
2354b17dab0SDag-Erling Smørgrav }									\
2364b17dab0SDag-Erling Smørgrav 									\
2374b17dab0SDag-Erling Smørgrav /* Splay with either the minimum or the maximum element			\
2384b17dab0SDag-Erling Smørgrav  * Used to find minimum or maximum element in tree.			\
2394b17dab0SDag-Erling Smørgrav  */									\
2404b17dab0SDag-Erling Smørgrav void name##_SPLAY_MINMAX(struct name *head, int __comp) \
2414b17dab0SDag-Erling Smørgrav {									\
2424b17dab0SDag-Erling Smørgrav 	struct type __node, *__left, *__right, *__tmp;			\
2434b17dab0SDag-Erling Smørgrav \
2444b17dab0SDag-Erling Smørgrav 	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
2454b17dab0SDag-Erling Smørgrav 	__left = __right = &__node;					\
2464b17dab0SDag-Erling Smørgrav \
2474b17dab0SDag-Erling Smørgrav 	while (1) {							\
2484b17dab0SDag-Erling Smørgrav 		if (__comp < 0) {					\
2494b17dab0SDag-Erling Smørgrav 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
2504b17dab0SDag-Erling Smørgrav 			if (__tmp == NULL)				\
2514b17dab0SDag-Erling Smørgrav 				break;					\
2524b17dab0SDag-Erling Smørgrav 			if (__comp < 0){				\
2534b17dab0SDag-Erling Smørgrav 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
2544b17dab0SDag-Erling Smørgrav 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
2554b17dab0SDag-Erling Smørgrav 					break;				\
2564b17dab0SDag-Erling Smørgrav 			}						\
2574b17dab0SDag-Erling Smørgrav 			SPLAY_LINKLEFT(head, __right, field);		\
2584b17dab0SDag-Erling Smørgrav 		} else if (__comp > 0) {				\
2594b17dab0SDag-Erling Smørgrav 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
2604b17dab0SDag-Erling Smørgrav 			if (__tmp == NULL)				\
2614b17dab0SDag-Erling Smørgrav 				break;					\
2624b17dab0SDag-Erling Smørgrav 			if (__comp > 0) {				\
2634b17dab0SDag-Erling Smørgrav 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
2644b17dab0SDag-Erling Smørgrav 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
2654b17dab0SDag-Erling Smørgrav 					break;				\
2664b17dab0SDag-Erling Smørgrav 			}						\
2674b17dab0SDag-Erling Smørgrav 			SPLAY_LINKRIGHT(head, __left, field);		\
2684b17dab0SDag-Erling Smørgrav 		}							\
2694b17dab0SDag-Erling Smørgrav 	}								\
2704b17dab0SDag-Erling Smørgrav 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
2714b17dab0SDag-Erling Smørgrav }
2724b17dab0SDag-Erling Smørgrav 
2734b17dab0SDag-Erling Smørgrav #define SPLAY_NEGINF	-1
2744b17dab0SDag-Erling Smørgrav #define SPLAY_INF	1
2754b17dab0SDag-Erling Smørgrav 
2764b17dab0SDag-Erling Smørgrav #define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)
2774b17dab0SDag-Erling Smørgrav #define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)
2784b17dab0SDag-Erling Smørgrav #define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)
2794b17dab0SDag-Erling Smørgrav #define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)
2804b17dab0SDag-Erling Smørgrav #define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\
2814b17dab0SDag-Erling Smørgrav 					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
2824b17dab0SDag-Erling Smørgrav #define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\
2834b17dab0SDag-Erling Smørgrav 					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
2844b17dab0SDag-Erling Smørgrav 
2854b17dab0SDag-Erling Smørgrav #define SPLAY_FOREACH(x, name, head)					\
2864b17dab0SDag-Erling Smørgrav 	for ((x) = SPLAY_MIN(name, head);				\
2874b17dab0SDag-Erling Smørgrav 	     (x) != NULL;						\
2884b17dab0SDag-Erling Smørgrav 	     (x) = SPLAY_NEXT(name, head, x))
2894b17dab0SDag-Erling Smørgrav 
2904b17dab0SDag-Erling Smørgrav /* Macros that define a red-back tree */
2914b17dab0SDag-Erling Smørgrav #define RB_HEAD(name, type)						\
2924b17dab0SDag-Erling Smørgrav struct name {								\
2934b17dab0SDag-Erling Smørgrav 	struct type *rbh_root; /* root of the tree */			\
2944b17dab0SDag-Erling Smørgrav }
2954b17dab0SDag-Erling Smørgrav 
2964b17dab0SDag-Erling Smørgrav #define RB_INITIALIZER(root)						\
2974b17dab0SDag-Erling Smørgrav 	{ NULL }
2984b17dab0SDag-Erling Smørgrav 
2994b17dab0SDag-Erling Smørgrav #define RB_INIT(root) do {						\
3004b17dab0SDag-Erling Smørgrav 	(root)->rbh_root = NULL;					\
3014b17dab0SDag-Erling Smørgrav } while (0)
3024b17dab0SDag-Erling Smørgrav 
3034b17dab0SDag-Erling Smørgrav #define RB_BLACK	0
3044b17dab0SDag-Erling Smørgrav #define RB_RED		1
3054b17dab0SDag-Erling Smørgrav #define RB_ENTRY(type)							\
3064b17dab0SDag-Erling Smørgrav struct {								\
3074b17dab0SDag-Erling Smørgrav 	struct type *rbe_left;		/* left element */		\
3084b17dab0SDag-Erling Smørgrav 	struct type *rbe_right;		/* right element */		\
3094b17dab0SDag-Erling Smørgrav 	struct type *rbe_parent;	/* parent element */		\
3104b17dab0SDag-Erling Smørgrav 	int rbe_color;			/* node color */		\
3114b17dab0SDag-Erling Smørgrav }
3124b17dab0SDag-Erling Smørgrav 
3134b17dab0SDag-Erling Smørgrav #define RB_LEFT(elm, field)		(elm)->field.rbe_left
3144b17dab0SDag-Erling Smørgrav #define RB_RIGHT(elm, field)		(elm)->field.rbe_right
3154b17dab0SDag-Erling Smørgrav #define RB_PARENT(elm, field)		(elm)->field.rbe_parent
3164b17dab0SDag-Erling Smørgrav #define RB_COLOR(elm, field)		(elm)->field.rbe_color
3174b17dab0SDag-Erling Smørgrav #define RB_ROOT(head)			(head)->rbh_root
3184b17dab0SDag-Erling Smørgrav #define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
3194b17dab0SDag-Erling Smørgrav 
3204b17dab0SDag-Erling Smørgrav #define RB_SET(elm, parent, field) do {					\
3214b17dab0SDag-Erling Smørgrav 	RB_PARENT(elm, field) = parent;					\
3224b17dab0SDag-Erling Smørgrav 	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
3234b17dab0SDag-Erling Smørgrav 	RB_COLOR(elm, field) = RB_RED;					\
3244b17dab0SDag-Erling Smørgrav } while (0)
3254b17dab0SDag-Erling Smørgrav 
3264b17dab0SDag-Erling Smørgrav #define RB_SET_BLACKRED(black, red, field) do {				\
3274b17dab0SDag-Erling Smørgrav 	RB_COLOR(black, field) = RB_BLACK;				\
3284b17dab0SDag-Erling Smørgrav 	RB_COLOR(red, field) = RB_RED;					\
3294b17dab0SDag-Erling Smørgrav } while (0)
3304b17dab0SDag-Erling Smørgrav 
3314b17dab0SDag-Erling Smørgrav #ifndef RB_AUGMENT
3324b17dab0SDag-Erling Smørgrav #define RB_AUGMENT(x)
3334b17dab0SDag-Erling Smørgrav #endif
3344b17dab0SDag-Erling Smørgrav 
3354b17dab0SDag-Erling Smørgrav #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
3364b17dab0SDag-Erling Smørgrav 	(tmp) = RB_RIGHT(elm, field);					\
3374b17dab0SDag-Erling Smørgrav 	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {		\
3384b17dab0SDag-Erling Smørgrav 		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
3394b17dab0SDag-Erling Smørgrav 	}								\
3404b17dab0SDag-Erling Smørgrav 	RB_AUGMENT(elm);						\
3414b17dab0SDag-Erling Smørgrav 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
3424b17dab0SDag-Erling Smørgrav 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
3434b17dab0SDag-Erling Smørgrav 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
3444b17dab0SDag-Erling Smørgrav 		else							\
3454b17dab0SDag-Erling Smørgrav 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
3464b17dab0SDag-Erling Smørgrav 		RB_AUGMENT(RB_PARENT(elm, field));			\
3474b17dab0SDag-Erling Smørgrav 	} else								\
3484b17dab0SDag-Erling Smørgrav 		(head)->rbh_root = (tmp);				\
3494b17dab0SDag-Erling Smørgrav 	RB_LEFT(tmp, field) = (elm);					\
3504b17dab0SDag-Erling Smørgrav 	RB_PARENT(elm, field) = (tmp);					\
3514b17dab0SDag-Erling Smørgrav 	RB_AUGMENT(tmp);						\
3524b17dab0SDag-Erling Smørgrav } while (0)
3534b17dab0SDag-Erling Smørgrav 
3544b17dab0SDag-Erling Smørgrav #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
3554b17dab0SDag-Erling Smørgrav 	(tmp) = RB_LEFT(elm, field);					\
3564b17dab0SDag-Erling Smørgrav 	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {		\
3574b17dab0SDag-Erling Smørgrav 		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
3584b17dab0SDag-Erling Smørgrav 	}								\
3594b17dab0SDag-Erling Smørgrav 	RB_AUGMENT(elm);						\
3604b17dab0SDag-Erling Smørgrav 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
3614b17dab0SDag-Erling Smørgrav 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
3624b17dab0SDag-Erling Smørgrav 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
3634b17dab0SDag-Erling Smørgrav 		else							\
3644b17dab0SDag-Erling Smørgrav 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
3654b17dab0SDag-Erling Smørgrav 		RB_AUGMENT(RB_PARENT(elm, field));			\
3664b17dab0SDag-Erling Smørgrav 	} else								\
3674b17dab0SDag-Erling Smørgrav 		(head)->rbh_root = (tmp);				\
3684b17dab0SDag-Erling Smørgrav 	RB_RIGHT(tmp, field) = (elm);					\
3694b17dab0SDag-Erling Smørgrav 	RB_PARENT(elm, field) = (tmp);					\
3704b17dab0SDag-Erling Smørgrav 	RB_AUGMENT(tmp);						\
3714b17dab0SDag-Erling Smørgrav } while (0)
3724b17dab0SDag-Erling Smørgrav 
3734b17dab0SDag-Erling Smørgrav /* Generates prototypes and inline functions */
3744b17dab0SDag-Erling Smørgrav #define RB_PROTOTYPE(name, type, field, cmp)				\
3754b17dab0SDag-Erling Smørgrav void name##_RB_INSERT_COLOR(struct name *, struct type *);	\
3764b17dab0SDag-Erling Smørgrav void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
3774b17dab0SDag-Erling Smørgrav struct type *name##_RB_REMOVE(struct name *, struct type *);		\
3784b17dab0SDag-Erling Smørgrav struct type *name##_RB_INSERT(struct name *, struct type *);		\
3794b17dab0SDag-Erling Smørgrav struct type *name##_RB_FIND(struct name *, struct type *);		\
3804b17dab0SDag-Erling Smørgrav struct type *name##_RB_NEXT(struct name *, struct type *);		\
3814b17dab0SDag-Erling Smørgrav struct type *name##_RB_MINMAX(struct name *, int);			\
3824b17dab0SDag-Erling Smørgrav 									\
3834b17dab0SDag-Erling Smørgrav 
3844b17dab0SDag-Erling Smørgrav /* Main rb operation.
3854b17dab0SDag-Erling Smørgrav  * Moves node close to the key of elm to top
3864b17dab0SDag-Erling Smørgrav  */
3874b17dab0SDag-Erling Smørgrav #define RB_GENERATE(name, type, field, cmp)				\
3884b17dab0SDag-Erling Smørgrav void									\
3894b17dab0SDag-Erling Smørgrav name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
3904b17dab0SDag-Erling Smørgrav {									\
3914b17dab0SDag-Erling Smørgrav 	struct type *parent, *gparent, *tmp;				\
3924b17dab0SDag-Erling Smørgrav 	while ((parent = RB_PARENT(elm, field)) &&			\
3934b17dab0SDag-Erling Smørgrav 	    RB_COLOR(parent, field) == RB_RED) {			\
3944b17dab0SDag-Erling Smørgrav 		gparent = RB_PARENT(parent, field);			\
3954b17dab0SDag-Erling Smørgrav 		if (parent == RB_LEFT(gparent, field)) {		\
3964b17dab0SDag-Erling Smørgrav 			tmp = RB_RIGHT(gparent, field);			\
3974b17dab0SDag-Erling Smørgrav 			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
3984b17dab0SDag-Erling Smørgrav 				RB_COLOR(tmp, field) = RB_BLACK;	\
3994b17dab0SDag-Erling Smørgrav 				RB_SET_BLACKRED(parent, gparent, field);\
4004b17dab0SDag-Erling Smørgrav 				elm = gparent;				\
4014b17dab0SDag-Erling Smørgrav 				continue;				\
4024b17dab0SDag-Erling Smørgrav 			}						\
4034b17dab0SDag-Erling Smørgrav 			if (RB_RIGHT(parent, field) == elm) {		\
4044b17dab0SDag-Erling Smørgrav 				RB_ROTATE_LEFT(head, parent, tmp, field);\
4054b17dab0SDag-Erling Smørgrav 				tmp = parent;				\
4064b17dab0SDag-Erling Smørgrav 				parent = elm;				\
4074b17dab0SDag-Erling Smørgrav 				elm = tmp;				\
4084b17dab0SDag-Erling Smørgrav 			}						\
4094b17dab0SDag-Erling Smørgrav 			RB_SET_BLACKRED(parent, gparent, field);	\
4104b17dab0SDag-Erling Smørgrav 			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
4114b17dab0SDag-Erling Smørgrav 		} else {						\
4124b17dab0SDag-Erling Smørgrav 			tmp = RB_LEFT(gparent, field);			\
4134b17dab0SDag-Erling Smørgrav 			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
4144b17dab0SDag-Erling Smørgrav 				RB_COLOR(tmp, field) = RB_BLACK;	\
4154b17dab0SDag-Erling Smørgrav 				RB_SET_BLACKRED(parent, gparent, field);\
4164b17dab0SDag-Erling Smørgrav 				elm = gparent;				\
4174b17dab0SDag-Erling Smørgrav 				continue;				\
4184b17dab0SDag-Erling Smørgrav 			}						\
4194b17dab0SDag-Erling Smørgrav 			if (RB_LEFT(parent, field) == elm) {		\
4204b17dab0SDag-Erling Smørgrav 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
4214b17dab0SDag-Erling Smørgrav 				tmp = parent;				\
4224b17dab0SDag-Erling Smørgrav 				parent = elm;				\
4234b17dab0SDag-Erling Smørgrav 				elm = tmp;				\
4244b17dab0SDag-Erling Smørgrav 			}						\
4254b17dab0SDag-Erling Smørgrav 			RB_SET_BLACKRED(parent, gparent, field);	\
4264b17dab0SDag-Erling Smørgrav 			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
4274b17dab0SDag-Erling Smørgrav 		}							\
4284b17dab0SDag-Erling Smørgrav 	}								\
4294b17dab0SDag-Erling Smørgrav 	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
4304b17dab0SDag-Erling Smørgrav }									\
4314b17dab0SDag-Erling Smørgrav 									\
4324b17dab0SDag-Erling Smørgrav void									\
4334b17dab0SDag-Erling Smørgrav name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
4344b17dab0SDag-Erling Smørgrav {									\
4354b17dab0SDag-Erling Smørgrav 	struct type *tmp;						\
4364b17dab0SDag-Erling Smørgrav 	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\
4374b17dab0SDag-Erling Smørgrav 	    elm != RB_ROOT(head)) {					\
4384b17dab0SDag-Erling Smørgrav 		if (RB_LEFT(parent, field) == elm) {			\
4394b17dab0SDag-Erling Smørgrav 			tmp = RB_RIGHT(parent, field);			\
4404b17dab0SDag-Erling Smørgrav 			if (RB_COLOR(tmp, field) == RB_RED) {		\
4414b17dab0SDag-Erling Smørgrav 				RB_SET_BLACKRED(tmp, parent, field);	\
4424b17dab0SDag-Erling Smørgrav 				RB_ROTATE_LEFT(head, parent, tmp, field);\
4434b17dab0SDag-Erling Smørgrav 				tmp = RB_RIGHT(parent, field);		\
4444b17dab0SDag-Erling Smørgrav 			}						\
4454b17dab0SDag-Erling Smørgrav 			if ((RB_LEFT(tmp, field) == NULL ||		\
4464b17dab0SDag-Erling Smørgrav 			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
4474b17dab0SDag-Erling Smørgrav 			    (RB_RIGHT(tmp, field) == NULL ||		\
4484b17dab0SDag-Erling Smørgrav 			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
4494b17dab0SDag-Erling Smørgrav 				RB_COLOR(tmp, field) = RB_RED;		\
4504b17dab0SDag-Erling Smørgrav 				elm = parent;				\
4514b17dab0SDag-Erling Smørgrav 				parent = RB_PARENT(elm, field);		\
4524b17dab0SDag-Erling Smørgrav 			} else {					\
4534b17dab0SDag-Erling Smørgrav 				if (RB_RIGHT(tmp, field) == NULL ||	\
4544b17dab0SDag-Erling Smørgrav 				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
4554b17dab0SDag-Erling Smørgrav 					struct type *oleft;		\
4564b17dab0SDag-Erling Smørgrav 					if ((oleft = RB_LEFT(tmp, field)))\
4574b17dab0SDag-Erling Smørgrav 						RB_COLOR(oleft, field) = RB_BLACK;\
4584b17dab0SDag-Erling Smørgrav 					RB_COLOR(tmp, field) = RB_RED;	\
4594b17dab0SDag-Erling Smørgrav 					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
4604b17dab0SDag-Erling Smørgrav 					tmp = RB_RIGHT(parent, field);	\
4614b17dab0SDag-Erling Smørgrav 				}					\
4624b17dab0SDag-Erling Smørgrav 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
4634b17dab0SDag-Erling Smørgrav 				RB_COLOR(parent, field) = RB_BLACK;	\
4644b17dab0SDag-Erling Smørgrav 				if (RB_RIGHT(tmp, field))		\
4654b17dab0SDag-Erling Smørgrav 					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
4664b17dab0SDag-Erling Smørgrav 				RB_ROTATE_LEFT(head, parent, tmp, field);\
4674b17dab0SDag-Erling Smørgrav 				elm = RB_ROOT(head);			\
4684b17dab0SDag-Erling Smørgrav 				break;					\
4694b17dab0SDag-Erling Smørgrav 			}						\
4704b17dab0SDag-Erling Smørgrav 		} else {						\
4714b17dab0SDag-Erling Smørgrav 			tmp = RB_LEFT(parent, field);			\
4724b17dab0SDag-Erling Smørgrav 			if (RB_COLOR(tmp, field) == RB_RED) {		\
4734b17dab0SDag-Erling Smørgrav 				RB_SET_BLACKRED(tmp, parent, field);	\
4744b17dab0SDag-Erling Smørgrav 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
4754b17dab0SDag-Erling Smørgrav 				tmp = RB_LEFT(parent, field);		\
4764b17dab0SDag-Erling Smørgrav 			}						\
4774b17dab0SDag-Erling Smørgrav 			if ((RB_LEFT(tmp, field) == NULL ||		\
4784b17dab0SDag-Erling Smørgrav 			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
4794b17dab0SDag-Erling Smørgrav 			    (RB_RIGHT(tmp, field) == NULL ||		\
4804b17dab0SDag-Erling Smørgrav 			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
4814b17dab0SDag-Erling Smørgrav 				RB_COLOR(tmp, field) = RB_RED;		\
4824b17dab0SDag-Erling Smørgrav 				elm = parent;				\
4834b17dab0SDag-Erling Smørgrav 				parent = RB_PARENT(elm, field);		\
4844b17dab0SDag-Erling Smørgrav 			} else {					\
4854b17dab0SDag-Erling Smørgrav 				if (RB_LEFT(tmp, field) == NULL ||	\
4864b17dab0SDag-Erling Smørgrav 				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
4874b17dab0SDag-Erling Smørgrav 					struct type *oright;		\
4884b17dab0SDag-Erling Smørgrav 					if ((oright = RB_RIGHT(tmp, field)))\
4894b17dab0SDag-Erling Smørgrav 						RB_COLOR(oright, field) = RB_BLACK;\
4904b17dab0SDag-Erling Smørgrav 					RB_COLOR(tmp, field) = RB_RED;	\
4914b17dab0SDag-Erling Smørgrav 					RB_ROTATE_LEFT(head, tmp, oright, field);\
4924b17dab0SDag-Erling Smørgrav 					tmp = RB_LEFT(parent, field);	\
4934b17dab0SDag-Erling Smørgrav 				}					\
4944b17dab0SDag-Erling Smørgrav 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
4954b17dab0SDag-Erling Smørgrav 				RB_COLOR(parent, field) = RB_BLACK;	\
4964b17dab0SDag-Erling Smørgrav 				if (RB_LEFT(tmp, field))		\
4974b17dab0SDag-Erling Smørgrav 					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
4984b17dab0SDag-Erling Smørgrav 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
4994b17dab0SDag-Erling Smørgrav 				elm = RB_ROOT(head);			\
5004b17dab0SDag-Erling Smørgrav 				break;					\
5014b17dab0SDag-Erling Smørgrav 			}						\
5024b17dab0SDag-Erling Smørgrav 		}							\
5034b17dab0SDag-Erling Smørgrav 	}								\
5044b17dab0SDag-Erling Smørgrav 	if (elm)							\
5054b17dab0SDag-Erling Smørgrav 		RB_COLOR(elm, field) = RB_BLACK;			\
5064b17dab0SDag-Erling Smørgrav }									\
5074b17dab0SDag-Erling Smørgrav 									\
5084b17dab0SDag-Erling Smørgrav struct type *								\
5094b17dab0SDag-Erling Smørgrav name##_RB_REMOVE(struct name *head, struct type *elm)			\
5104b17dab0SDag-Erling Smørgrav {									\
5114b17dab0SDag-Erling Smørgrav 	struct type *child, *parent, *old = elm;			\
5124b17dab0SDag-Erling Smørgrav 	int color;							\
5134b17dab0SDag-Erling Smørgrav 	if (RB_LEFT(elm, field) == NULL)				\
5144b17dab0SDag-Erling Smørgrav 		child = RB_RIGHT(elm, field);				\
5154b17dab0SDag-Erling Smørgrav 	else if (RB_RIGHT(elm, field) == NULL)				\
5164b17dab0SDag-Erling Smørgrav 		child = RB_LEFT(elm, field);				\
5174b17dab0SDag-Erling Smørgrav 	else {								\
5184b17dab0SDag-Erling Smørgrav 		struct type *left;					\
5194b17dab0SDag-Erling Smørgrav 		elm = RB_RIGHT(elm, field);				\
5204b17dab0SDag-Erling Smørgrav 		while ((left = RB_LEFT(elm, field)))			\
5214b17dab0SDag-Erling Smørgrav 			elm = left;					\
5224b17dab0SDag-Erling Smørgrav 		child = RB_RIGHT(elm, field);				\
5234b17dab0SDag-Erling Smørgrav 		parent = RB_PARENT(elm, field);				\
5244b17dab0SDag-Erling Smørgrav 		color = RB_COLOR(elm, field);				\
5254b17dab0SDag-Erling Smørgrav 		if (child)						\
5264b17dab0SDag-Erling Smørgrav 			RB_PARENT(child, field) = parent;		\
5274b17dab0SDag-Erling Smørgrav 		if (parent) {						\
5284b17dab0SDag-Erling Smørgrav 			if (RB_LEFT(parent, field) == elm)		\
5294b17dab0SDag-Erling Smørgrav 				RB_LEFT(parent, field) = child;		\
5304b17dab0SDag-Erling Smørgrav 			else						\
5314b17dab0SDag-Erling Smørgrav 				RB_RIGHT(parent, field) = child;	\
5324b17dab0SDag-Erling Smørgrav 			RB_AUGMENT(parent);				\
5334b17dab0SDag-Erling Smørgrav 		} else							\
5344b17dab0SDag-Erling Smørgrav 			RB_ROOT(head) = child;				\
5354b17dab0SDag-Erling Smørgrav 		if (RB_PARENT(elm, field) == old)			\
5364b17dab0SDag-Erling Smørgrav 			parent = elm;					\
5374b17dab0SDag-Erling Smørgrav 		(elm)->field = (old)->field;				\
5384b17dab0SDag-Erling Smørgrav 		if (RB_PARENT(old, field)) {				\
5394b17dab0SDag-Erling Smørgrav 			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
5404b17dab0SDag-Erling Smørgrav 				RB_LEFT(RB_PARENT(old, field), field) = elm;\
5414b17dab0SDag-Erling Smørgrav 			else						\
5424b17dab0SDag-Erling Smørgrav 				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
5434b17dab0SDag-Erling Smørgrav 			RB_AUGMENT(RB_PARENT(old, field));		\
5444b17dab0SDag-Erling Smørgrav 		} else							\
5454b17dab0SDag-Erling Smørgrav 			RB_ROOT(head) = elm;				\
5464b17dab0SDag-Erling Smørgrav 		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
5474b17dab0SDag-Erling Smørgrav 		if (RB_RIGHT(old, field))				\
5484b17dab0SDag-Erling Smørgrav 			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
5494b17dab0SDag-Erling Smørgrav 		if (parent) {						\
5504b17dab0SDag-Erling Smørgrav 			left = parent;					\
5514b17dab0SDag-Erling Smørgrav 			do {						\
5524b17dab0SDag-Erling Smørgrav 				RB_AUGMENT(left);			\
5534b17dab0SDag-Erling Smørgrav 			} while ((left = RB_PARENT(left, field)));	\
5544b17dab0SDag-Erling Smørgrav 		}							\
5554b17dab0SDag-Erling Smørgrav 		goto color;						\
5564b17dab0SDag-Erling Smørgrav 	}								\
5574b17dab0SDag-Erling Smørgrav 	parent = RB_PARENT(elm, field);					\
5584b17dab0SDag-Erling Smørgrav 	color = RB_COLOR(elm, field);					\
5594b17dab0SDag-Erling Smørgrav 	if (child)							\
5604b17dab0SDag-Erling Smørgrav 		RB_PARENT(child, field) = parent;			\
5614b17dab0SDag-Erling Smørgrav 	if (parent) {							\
5624b17dab0SDag-Erling Smørgrav 		if (RB_LEFT(parent, field) == elm)			\
5634b17dab0SDag-Erling Smørgrav 			RB_LEFT(parent, field) = child;			\
5644b17dab0SDag-Erling Smørgrav 		else							\
5654b17dab0SDag-Erling Smørgrav 			RB_RIGHT(parent, field) = child;		\
5664b17dab0SDag-Erling Smørgrav 		RB_AUGMENT(parent);					\
5674b17dab0SDag-Erling Smørgrav 	} else								\
5684b17dab0SDag-Erling Smørgrav 		RB_ROOT(head) = child;					\
5694b17dab0SDag-Erling Smørgrav color:									\
5704b17dab0SDag-Erling Smørgrav 	if (color == RB_BLACK)						\
5714b17dab0SDag-Erling Smørgrav 		name##_RB_REMOVE_COLOR(head, parent, child);		\
5724b17dab0SDag-Erling Smørgrav 	return (old);							\
5734b17dab0SDag-Erling Smørgrav }									\
5744b17dab0SDag-Erling Smørgrav 									\
5754b17dab0SDag-Erling Smørgrav /* Inserts a node into the RB tree */					\
5764b17dab0SDag-Erling Smørgrav struct type *								\
5774b17dab0SDag-Erling Smørgrav name##_RB_INSERT(struct name *head, struct type *elm)			\
5784b17dab0SDag-Erling Smørgrav {									\
5794b17dab0SDag-Erling Smørgrav 	struct type *tmp;						\
5804b17dab0SDag-Erling Smørgrav 	struct type *parent = NULL;					\
5814b17dab0SDag-Erling Smørgrav 	int comp = 0;							\
5824b17dab0SDag-Erling Smørgrav 	tmp = RB_ROOT(head);						\
5834b17dab0SDag-Erling Smørgrav 	while (tmp) {							\
5844b17dab0SDag-Erling Smørgrav 		parent = tmp;						\
5854b17dab0SDag-Erling Smørgrav 		comp = (cmp)(elm, parent);				\
5864b17dab0SDag-Erling Smørgrav 		if (comp < 0)						\
5874b17dab0SDag-Erling Smørgrav 			tmp = RB_LEFT(tmp, field);			\
5884b17dab0SDag-Erling Smørgrav 		else if (comp > 0)					\
5894b17dab0SDag-Erling Smørgrav 			tmp = RB_RIGHT(tmp, field);			\
5904b17dab0SDag-Erling Smørgrav 		else							\
5914b17dab0SDag-Erling Smørgrav 			return (tmp);					\
5924b17dab0SDag-Erling Smørgrav 	}								\
5934b17dab0SDag-Erling Smørgrav 	RB_SET(elm, parent, field);					\
5944b17dab0SDag-Erling Smørgrav 	if (parent != NULL) {						\
5954b17dab0SDag-Erling Smørgrav 		if (comp < 0)						\
5964b17dab0SDag-Erling Smørgrav 			RB_LEFT(parent, field) = elm;			\
5974b17dab0SDag-Erling Smørgrav 		else							\
5984b17dab0SDag-Erling Smørgrav 			RB_RIGHT(parent, field) = elm;			\
5994b17dab0SDag-Erling Smørgrav 		RB_AUGMENT(parent);					\
6004b17dab0SDag-Erling Smørgrav 	} else								\
6014b17dab0SDag-Erling Smørgrav 		RB_ROOT(head) = elm;					\
6024b17dab0SDag-Erling Smørgrav 	name##_RB_INSERT_COLOR(head, elm);				\
6034b17dab0SDag-Erling Smørgrav 	return (NULL);							\
6044b17dab0SDag-Erling Smørgrav }									\
6054b17dab0SDag-Erling Smørgrav 									\
6064b17dab0SDag-Erling Smørgrav /* Finds the node with the same key as elm */				\
6074b17dab0SDag-Erling Smørgrav struct type *								\
6084b17dab0SDag-Erling Smørgrav name##_RB_FIND(struct name *head, struct type *elm)			\
6094b17dab0SDag-Erling Smørgrav {									\
6104b17dab0SDag-Erling Smørgrav 	struct type *tmp = RB_ROOT(head);				\
6114b17dab0SDag-Erling Smørgrav 	int comp;							\
6124b17dab0SDag-Erling Smørgrav 	while (tmp) {							\
6134b17dab0SDag-Erling Smørgrav 		comp = cmp(elm, tmp);					\
6144b17dab0SDag-Erling Smørgrav 		if (comp < 0)						\
6154b17dab0SDag-Erling Smørgrav 			tmp = RB_LEFT(tmp, field);			\
6164b17dab0SDag-Erling Smørgrav 		else if (comp > 0)					\
6174b17dab0SDag-Erling Smørgrav 			tmp = RB_RIGHT(tmp, field);			\
6184b17dab0SDag-Erling Smørgrav 		else							\
6194b17dab0SDag-Erling Smørgrav 			return (tmp);					\
6204b17dab0SDag-Erling Smørgrav 	}								\
6214b17dab0SDag-Erling Smørgrav 	return (NULL);							\
6224b17dab0SDag-Erling Smørgrav }									\
6234b17dab0SDag-Erling Smørgrav 									\
6244b17dab0SDag-Erling Smørgrav struct type *								\
6254b17dab0SDag-Erling Smørgrav name##_RB_NEXT(struct name *head, struct type *elm)			\
6264b17dab0SDag-Erling Smørgrav {									\
6274b17dab0SDag-Erling Smørgrav 	if (RB_RIGHT(elm, field)) {					\
6284b17dab0SDag-Erling Smørgrav 		elm = RB_RIGHT(elm, field);				\
6294b17dab0SDag-Erling Smørgrav 		while (RB_LEFT(elm, field))				\
6304b17dab0SDag-Erling Smørgrav 			elm = RB_LEFT(elm, field);			\
6314b17dab0SDag-Erling Smørgrav 	} else {							\
6324b17dab0SDag-Erling Smørgrav 		if (RB_PARENT(elm, field) &&				\
6334b17dab0SDag-Erling Smørgrav 		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\
6344b17dab0SDag-Erling Smørgrav 			elm = RB_PARENT(elm, field);			\
6354b17dab0SDag-Erling Smørgrav 		else {							\
6364b17dab0SDag-Erling Smørgrav 			while (RB_PARENT(elm, field) &&			\
6374b17dab0SDag-Erling Smørgrav 			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
6384b17dab0SDag-Erling Smørgrav 				elm = RB_PARENT(elm, field);		\
6394b17dab0SDag-Erling Smørgrav 			elm = RB_PARENT(elm, field);			\
6404b17dab0SDag-Erling Smørgrav 		}							\
6414b17dab0SDag-Erling Smørgrav 	}								\
6424b17dab0SDag-Erling Smørgrav 	return (elm);							\
6434b17dab0SDag-Erling Smørgrav }									\
6444b17dab0SDag-Erling Smørgrav 									\
6454b17dab0SDag-Erling Smørgrav struct type *								\
6464b17dab0SDag-Erling Smørgrav name##_RB_MINMAX(struct name *head, int val)				\
6474b17dab0SDag-Erling Smørgrav {									\
6484b17dab0SDag-Erling Smørgrav 	struct type *tmp = RB_ROOT(head);				\
6494b17dab0SDag-Erling Smørgrav 	struct type *parent = NULL;					\
6504b17dab0SDag-Erling Smørgrav 	while (tmp) {							\
6514b17dab0SDag-Erling Smørgrav 		parent = tmp;						\
6524b17dab0SDag-Erling Smørgrav 		if (val < 0)						\
6534b17dab0SDag-Erling Smørgrav 			tmp = RB_LEFT(tmp, field);			\
6544b17dab0SDag-Erling Smørgrav 		else							\
6554b17dab0SDag-Erling Smørgrav 			tmp = RB_RIGHT(tmp, field);			\
6564b17dab0SDag-Erling Smørgrav 	}								\
6574b17dab0SDag-Erling Smørgrav 	return (parent);						\
6584b17dab0SDag-Erling Smørgrav }
6594b17dab0SDag-Erling Smørgrav 
6604b17dab0SDag-Erling Smørgrav #define RB_NEGINF	-1
6614b17dab0SDag-Erling Smørgrav #define RB_INF	1
6624b17dab0SDag-Erling Smørgrav 
6634b17dab0SDag-Erling Smørgrav #define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
6644b17dab0SDag-Erling Smørgrav #define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
6654b17dab0SDag-Erling Smørgrav #define RB_FIND(name, x, y)	name##_RB_FIND(x, y)
6664b17dab0SDag-Erling Smørgrav #define RB_NEXT(name, x, y)	name##_RB_NEXT(x, y)
6674b17dab0SDag-Erling Smørgrav #define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)
6684b17dab0SDag-Erling Smørgrav #define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)
6694b17dab0SDag-Erling Smørgrav 
6704b17dab0SDag-Erling Smørgrav #define RB_FOREACH(x, name, head)					\
6714b17dab0SDag-Erling Smørgrav 	for ((x) = RB_MIN(name, head);					\
6724b17dab0SDag-Erling Smørgrav 	     (x) != NULL;						\
6734b17dab0SDag-Erling Smørgrav 	     (x) = name##_RB_NEXT(head, x))
6744b17dab0SDag-Erling Smørgrav 
6754b17dab0SDag-Erling Smørgrav #endif	/* _SYS_TREE_H_ */
676