openssh/openbsd-compat/sys-tree.h

84 #define SPLAY_ROOT(head)		(head)->sph_root
85 #define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)
88 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
89 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
90 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
91 	(head)->sph_root = tmp;						\
94 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
95 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
96 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
97 	(head)->sph_root = tmp;						\
100 #define SPLAY_LINKLEFT(head, tmp, field) do {				\
101 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
102 	tmp = (head)->sph_root;						\
103 	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
106 #define SPLAY_LINKRIGHT(head, tmp, field) do {				\
107 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
108 	tmp = (head)->sph_root;						\
109 	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
112 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
113 	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
114 	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
115 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
116 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
129 name##_SPLAY_FIND(struct name *head, struct type *elm)			\
131 	if (SPLAY_EMPTY(head))						\
133 	name##_SPLAY(head, elm);					\
134 	if ((cmp)(elm, (head)->sph_root) == 0)				\
135 		return (head->sph_root);				\
140 name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
142 	name##_SPLAY(head, elm);					\
154 name##_SPLAY_MIN_MAX(struct name *head, int val)			\
156 	name##_SPLAY_MINMAX(head, val);					\
157         return (SPLAY_ROOT(head));					\
165 name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
167     if (SPLAY_EMPTY(head)) {						\
171 	    name##_SPLAY(head, elm);					\
172 	    __comp = (cmp)(elm, (head)->sph_root);			\
174 		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
175 		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
176 		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
178 		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
179 		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
180 		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
182 		    return ((head)->sph_root);				\
184     (head)->sph_root = (elm);						\
189 name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
192 	if (SPLAY_EMPTY(head))						\
194 	name##_SPLAY(head, elm);					\
195 	if ((cmp)(elm, (head)->sph_root) == 0) {			\
196 		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
197 			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
199 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
200 			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
201 			name##_SPLAY(head, elm);			\
202 			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
210 name##_SPLAY(struct name *head, struct type *elm)			\
218 	while ((__comp = (cmp)(elm, (head)->sph_root))) {		\
220 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
224 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
225 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
228 			SPLAY_LINKLEFT(head, __right, field);		\
230 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
234 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
235 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
238 			SPLAY_LINKRIGHT(head, __left, field);		\
241 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
247 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
256 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
260 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
261 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
264 			SPLAY_LINKLEFT(head, __right, field);		\
266 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
270 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
271 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
274 			SPLAY_LINKRIGHT(head, __left, field);		\
277 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
292 #define SPLAY_FOREACH(x, name, head)					\
293 	for ((x) = SPLAY_MIN(name, head);				\
295 	     (x) = SPLAY_NEXT(name, head, x))
324 #define RB_ROOT(head)			(head)->rbh_root
325 #define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
342 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
354 		(head)->rbh_root = (tmp);				\
362 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
374 		(head)->rbh_root = (tmp);				\
408 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
423 				RB_ROTATE_LEFT(head, parent, tmp, field);\
429 			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
439 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
445 			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
448 	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
452 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
456 	    elm != RB_ROOT(head)) {					\
461 				RB_ROTATE_LEFT(head, parent, tmp, field);\
478 					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
485 				RB_ROTATE_LEFT(head, parent, tmp, field);\
486 				elm = RB_ROOT(head);			\
493 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
510 					RB_ROTATE_LEFT(head, tmp, oright, field);\
517 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
518 				elm = RB_ROOT(head);			\
528 name##_RB_REMOVE(struct name *head, struct type *elm)			\
553 			RB_ROOT(head) = child;				\
564 			RB_ROOT(head) = elm;				\
587 		RB_ROOT(head) = child;					\
590 		name##_RB_REMOVE_COLOR(head, parent, child);		\
596 name##_RB_INSERT(struct name *head, struct type *elm)			\
601 	tmp = RB_ROOT(head);						\
620 		RB_ROOT(head) = elm;					\
621 	name##_RB_INSERT_COLOR(head, elm);				\
627 name##_RB_FIND(struct name *head, struct type *elm)			\
629 	struct type *tmp = RB_ROOT(head);				\
645 name##_RB_NFIND(struct name *head, struct type *elm)			\
647 	struct type *tmp = RB_ROOT(head);				\
709 name##_RB_MINMAX(struct name *head, int val)				\
711 	struct type *tmp = RB_ROOT(head);				\
735 #define RB_FOREACH(x, name, head)					\
736 	for ((x) = RB_MIN(name, head);					\
740 #define RB_FOREACH_SAFE(x, name, head, y)				\
741 	for ((x) = RB_MIN(name, head);					\
745 #define RB_FOREACH_REVERSE(x, name, head)				\
746 	for ((x) = RB_MAX(name, head);					\
750 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\
751 	for ((x) = RB_MAX(name, head);					\