68 #define SPLAY_HEAD(name, type)						\  argument
69 struct name {								\
125 #define SPLAY_PROTOTYPE(name, type, field, cmp)				\  argument
126 void name##_SPLAY(struct name *, struct type *);			\
127 void name##_SPLAY_MINMAX(struct name *, int);				\
128 struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
129 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
133 name##_SPLAY_FIND(struct name *head, struct type *elm)			\
137 	name##_SPLAY(head, elm);					\
144 name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
146 	name##_SPLAY(head, elm);					\
158 name##_SPLAY_MIN_MAX(struct name *head, int val)			\
160 	name##_SPLAY_MINMAX(head, val);					\
167 #define SPLAY_GENERATE(name, type, field, cmp)				\  argument
169 name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
175 	    name##_SPLAY(head, elm);					\
193 name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
198 	name##_SPLAY(head, elm);					\
205 			name##_SPLAY(head, elm);			\
214 name##_SPLAY(struct name *head, struct type *elm)			\
251 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
287 #define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)  argument
288 #define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)  argument
289 #define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)  argument
290 #define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)  argument
291 #define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\  argument
292 					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
293 #define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\  argument
294 					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
296 #define SPLAY_FOREACH(x, name, head)					\  argument
297 	for ((x) = SPLAY_MIN(name, head);				\
299 	     (x) = SPLAY_NEXT(name, head, x))
302 #define RB_HEAD(name, type)						\  argument
303 struct name {								\
459 #define	RB_PROTOTYPE(name, type, field, cmp)				\  argument
460 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
461 #define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\  argument
462 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
463 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\  argument
464 	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
465 	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
466 	RB_PROTOTYPE_INSERT(name, type, attr);				\
467 	RB_PROTOTYPE_REMOVE(name, type, attr);				\
468 	RB_PROTOTYPE_FIND(name, type, attr);				\
469 	RB_PROTOTYPE_NFIND(name, type, attr);				\
470 	RB_PROTOTYPE_NEXT(name, type, attr);				\
471 	RB_PROTOTYPE_PREV(name, type, attr);				\
472 	RB_PROTOTYPE_MINMAX(name, type, attr);				\
473 	RB_PROTOTYPE_REINSERT(name, type, attr);
474 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\  argument
475 	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
476 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\  argument
477 	attr void name##_RB_REMOVE_COLOR(struct name *, struct type *)
478 #define RB_PROTOTYPE_REMOVE(name, type, attr)				\  argument
479 	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
480 #define RB_PROTOTYPE_INSERT(name, type, attr)				\  argument
481 	attr struct type *name##_RB_INSERT(struct name *, struct type *)
482 #define RB_PROTOTYPE_FIND(name, type, attr)				\  argument
483 	attr struct type *name##_RB_FIND(struct name *, struct type *)
484 #define RB_PROTOTYPE_NFIND(name, type, attr)				\  argument
485 	attr struct type *name##_RB_NFIND(struct name *, struct type *)
486 #define RB_PROTOTYPE_NEXT(name, type, attr)				\  argument
487 	attr struct type *name##_RB_NEXT(struct type *)
488 #define RB_PROTOTYPE_PREV(name, type, attr)				\  argument
489 	attr struct type *name##_RB_PREV(struct type *)
490 #define RB_PROTOTYPE_MINMAX(name, type, attr)				\  argument
491 	attr struct type *name##_RB_MINMAX(struct name *, int)
492 #define RB_PROTOTYPE_REINSERT(name, type, attr)			\  argument
493 	attr struct type *name##_RB_REINSERT(struct name *, struct type *)
498 #define	RB_GENERATE(name, type, field, cmp)				\  argument
499 	RB_GENERATE_INTERNAL(name, type, field, cmp,)
500 #define	RB_GENERATE_STATIC(name, type, field, cmp)			\  argument
501 	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
502 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\  argument
503 	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
504 	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
505 	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
506 	RB_GENERATE_REMOVE(name, type, field, attr)			\
507 	RB_GENERATE_FIND(name, type, field, cmp, attr)			\
508 	RB_GENERATE_NFIND(name, type, field, cmp, attr)			\
509 	RB_GENERATE_NEXT(name, type, field, attr)			\
510 	RB_GENERATE_PREV(name, type, field, attr)			\
511 	RB_GENERATE_MINMAX(name, type, field, attr)			\
512 	RB_GENERATE_REINSERT(name, type, field, cmp, attr)
515 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\  argument
517 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
561 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\  argument
563 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent)		\
625 #define RB_GENERATE_REMOVE(name, type, field, attr)			\  argument
627 name##_RB_REMOVE(struct name *head, struct type *elm)			\
663 		name##_RB_REMOVE_COLOR(head, parent);			\
671 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\  argument
674 name##_RB_INSERT(struct name *head, struct type *elm)			\
698 	name##_RB_INSERT_COLOR(head, elm);				\
706 #define RB_GENERATE_FIND(name, type, field, cmp, attr)			\  argument
709 name##_RB_FIND(struct name *head, struct type *elm)			\
725 #define RB_GENERATE_NFIND(name, type, field, cmp, attr)			\  argument
728 name##_RB_NFIND(struct name *head, struct type *elm)			\
747 #define RB_GENERATE_NEXT(name, type, field, attr)			\  argument
750 name##_RB_NEXT(struct type *elm)					\
770 #define RB_GENERATE_PREV(name, type, field, attr)			\  argument
773 name##_RB_PREV(struct type *elm)					\
793 #define RB_GENERATE_MINMAX(name, type, field, attr)			\  argument
795 name##_RB_MINMAX(struct name *head, int val)				\
809 #define	RB_GENERATE_REINSERT(name, type, field, cmp, attr)		\  argument
811 name##_RB_REINSERT(struct name *head, struct type *elm)			\
814 	if (((cmpelm = RB_PREV(name, head, elm)) != NULL &&		\
816 	    ((cmpelm = RB_NEXT(name, head, elm)) != NULL &&		\
819 		RB_REMOVE(name, head, elm);				\
820 		return (RB_INSERT(name, head, elm));			\
828 #define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)  argument
829 #define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)  argument
830 #define RB_FIND(name, x, y)	name##_RB_FIND(x, y)  argument
831 #define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)  argument
832 #define RB_NEXT(name, x, y)	name##_RB_NEXT(y)  argument
833 #define RB_PREV(name, x, y)	name##_RB_PREV(y)  argument
834 #define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)  argument
835 #define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)  argument
836 #define RB_REINSERT(name, x, y)	name##_RB_REINSERT(x, y)  argument
838 #define RB_FOREACH(x, name, head)					\  argument
839 	for ((x) = RB_MIN(name, head);					\
841 	     (x) = name##_RB_NEXT(x))
843 #define RB_FOREACH_FROM(x, name, y)					\  argument
845 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
848 #define RB_FOREACH_SAFE(x, name, head, y)				\  argument
849 	for ((x) = RB_MIN(name, head);					\
850 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
853 #define RB_FOREACH_REVERSE(x, name, head)				\  argument
854 	for ((x) = RB_MAX(name, head);					\
856 	     (x) = name##_RB_PREV(x))
858 #define RB_FOREACH_REVERSE_FROM(x, name, y)				\  argument
860 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
863 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\  argument
864 	for ((x) = RB_MAX(name, head);					\
865 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\