openbsd_wlan/sys/tree.h

79 #define SPLAY_ROOT(head)		(head)->sph_root
80 #define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)
83 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
84 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
85 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
86 	(head)->sph_root = tmp;						\
89 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
90 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
91 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
92 	(head)->sph_root = tmp;						\
95 #define SPLAY_LINKLEFT(head, tmp, field) do {				\
96 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
97 	tmp = (head)->sph_root;						\
98 	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
101 #define SPLAY_LINKRIGHT(head, tmp, field) do {				\
102 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
103 	tmp = (head)->sph_root;						\
104 	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
107 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
108 	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
109 	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
110 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
111 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
124 name##_SPLAY_FIND(struct name *head, struct type *elm)			\
126 	if (SPLAY_EMPTY(head))						\
128 	name##_SPLAY(head, elm);					\
129 	if ((cmp)(elm, (head)->sph_root) == 0)				\
130 		return (head->sph_root);				\
135 name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
137 	name##_SPLAY(head, elm);					\
149 name##_SPLAY_MIN_MAX(struct name *head, int val)			\
151 	name##_SPLAY_MINMAX(head, val);					\
152         return (SPLAY_ROOT(head));					\
160 name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
162     if (SPLAY_EMPTY(head)) {						\
166 	    name##_SPLAY(head, elm);					\
167 	    __comp = (cmp)(elm, (head)->sph_root);			\
169 		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
170 		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
171 		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
173 		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
174 		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
175 		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
177 		    return ((head)->sph_root);				\
179     (head)->sph_root = (elm);						\
184 name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
187 	if (SPLAY_EMPTY(head))						\
189 	name##_SPLAY(head, elm);					\
190 	if ((cmp)(elm, (head)->sph_root) == 0) {			\
191 		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
192 			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
194 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
195 			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
196 			name##_SPLAY(head, elm);			\
197 			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
205 name##_SPLAY(struct name *head, struct type *elm)			\
213 	while ((__comp = (cmp)(elm, (head)->sph_root))) {		\
215 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
219 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
220 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
223 			SPLAY_LINKLEFT(head, __right, field);		\
225 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
229 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
230 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
233 			SPLAY_LINKRIGHT(head, __left, field);		\
236 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
242 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
251 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
255 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
256 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
259 			SPLAY_LINKLEFT(head, __right, field);		\
261 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
265 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
266 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
269 			SPLAY_LINKRIGHT(head, __left, field);		\
272 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
287 #define SPLAY_FOREACH(x, name, head)					\
288 	for ((x) = SPLAY_MIN(name, head);				\
290 	     (x) = SPLAY_NEXT(name, head, x))
319 #define RB_ROOT(head)			(head)->rbh_root
320 #define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
337 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
349 		(head)->rbh_root = (tmp);				\
357 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
369 		(head)->rbh_root = (tmp);				\
403 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
418 				RB_ROTATE_LEFT(head, parent, tmp, field);\
424 			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
434 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
440 			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
443 	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
447 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
451 	    elm != RB_ROOT(head)) {					\
456 				RB_ROTATE_LEFT(head, parent, tmp, field);\
473 					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
480 				RB_ROTATE_LEFT(head, parent, tmp, field);\
481 				elm = RB_ROOT(head);			\
488 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
505 					RB_ROTATE_LEFT(head, tmp, oright, field);\
512 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
513 				elm = RB_ROOT(head);			\
523 name##_RB_REMOVE(struct name *head, struct type *elm)			\
548 			RB_ROOT(head) = child;				\
559 			RB_ROOT(head) = elm;				\
582 		RB_ROOT(head) = child;					\
585 		name##_RB_REMOVE_COLOR(head, parent, child);		\
591 name##_RB_INSERT(struct name *head, struct type *elm)			\
596 	tmp = RB_ROOT(head);						\
615 		RB_ROOT(head) = elm;					\
616 	name##_RB_INSERT_COLOR(head, elm);				\
622 name##_RB_FIND(struct name *head, struct type *elm)			\
624 	struct type *tmp = RB_ROOT(head);				\
640 name##_RB_NFIND(struct name *head, struct type *elm)			\
642 	struct type *tmp = RB_ROOT(head);				\
704 name##_RB_MINMAX(struct name *head, int val)				\
706 	struct type *tmp = RB_ROOT(head);				\
730 #define RB_FOREACH(x, name, head)					\
731 	for ((x) = RB_MIN(name, head);					\
735 #define RB_FOREACH_SAFE(x, name, head, y)				\
736 	for ((x) = RB_MIN(name, head);					\
740 #define RB_FOREACH_REVERSE(x, name, head)				\
741 	for ((x) = RB_MAX(name, head);					\
745 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\
746 	for ((x) = RB_MAX(name, head);					\
827 _name##_RBT_INIT(struct _name *head)					\
829 	_rb_init(&head->rbh_root);					\
833 _name##_RBT_INSERT(struct _name *head, struct _type *elm)		\
835 	return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm);	\
839 _name##_RBT_REMOVE(struct _name *head, struct _type *elm)		\
841 	return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm);	\
845 _name##_RBT_FIND(struct _name *head, const struct _type *key)		\
847 	return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key);	\
851 _name##_RBT_NFIND(struct _name *head, const struct _type *key)		\
853 	return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key);	\
857 _name##_RBT_ROOT(struct _name *head)					\
859 	return _rb_root(_name##_RBT_TYPE, &head->rbh_root);		\
863 _name##_RBT_EMPTY(struct _name *head)					\
865 	return _rb_empty(&head->rbh_root);				\
869 _name##_RBT_MIN(struct _name *head)					\
871 	return _rb_min(_name##_RBT_TYPE, &head->rbh_root);		\
875 _name##_RBT_MAX(struct _name *head)					\
877 	return _rb_max(_name##_RBT_TYPE, &head->rbh_root);		\