73 #define SPLAY_HEAD(name, type)						\  argument
74 struct name {								\
130 #define SPLAY_PROTOTYPE(name, type, field, cmp)				\  argument
131 void name##_SPLAY(struct name *, struct type *);			\
132 void name##_SPLAY_MINMAX(struct name *, int);				\
133 struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
134 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
138 name##_SPLAY_FIND(struct name *head, struct type *elm)			\
142 	name##_SPLAY(head, elm);					\
149 name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
151 	name##_SPLAY(head, elm);					\
163 name##_SPLAY_MIN_MAX(struct name *head, int val)			\
165 	name##_SPLAY_MINMAX(head, val);					\
172 #define SPLAY_GENERATE(name, type, field, cmp)				\  argument
174 name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
180 	    name##_SPLAY(head, elm);					\
198 name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
203 	name##_SPLAY(head, elm);					\
210 			name##_SPLAY(head, elm);			\
219 name##_SPLAY(struct name *head, struct type *elm)			\
256 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
292 #define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)  argument
293 #define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)  argument
294 #define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)  argument
295 #define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)  argument
296 #define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\  argument
297 					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
298 #define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\  argument
299 					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
301 #define SPLAY_FOREACH(x, name, head)					\  argument
302 	for ((x) = SPLAY_MIN(name, head);				\
304 	     (x) = SPLAY_NEXT(name, head, x))
307 #define RB_HEAD(name, type)						\  argument
308 struct name {								\
407 #define	RB_PROTOTYPE(name, type, field, cmp)				\  argument
408 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
409 #define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\  argument
410 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
411 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\  argument
412 	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
413 	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
414 	RB_PROTOTYPE_INSERT(name, type, attr);				\
415 	RB_PROTOTYPE_REMOVE(name, type, attr);				\
416 	RB_PROTOTYPE_FIND(name, type, attr);				\
417 	RB_PROTOTYPE_NFIND(name, type, attr);				\
418 	RB_PROTOTYPE_NEXT(name, type, attr);				\
419 	RB_PROTOTYPE_PREV(name, type, attr);				\
420 	RB_PROTOTYPE_MINMAX(name, type, attr);				\
421 	RB_PROTOTYPE_REINSERT(name, type, attr);
422 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\  argument
423 	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
424 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\  argument
425 	attr void name##_RB_REMOVE_COLOR(struct name *,			\
427 #define RB_PROTOTYPE_REMOVE(name, type, attr)				\  argument
428 	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
429 #define RB_PROTOTYPE_INSERT(name, type, attr)				\  argument
430 	attr struct type *name##_RB_INSERT(struct name *, struct type *)
431 #define RB_PROTOTYPE_FIND(name, type, attr)				\  argument
432 	attr struct type *name##_RB_FIND(struct name *, struct type *)
433 #define RB_PROTOTYPE_NFIND(name, type, attr)				\  argument
434 	attr struct type *name##_RB_NFIND(struct name *, struct type *)
435 #define RB_PROTOTYPE_NEXT(name, type, attr)				\  argument
436 	attr struct type *name##_RB_NEXT(struct type *)
437 #define RB_PROTOTYPE_PREV(name, type, attr)				\  argument
438 	attr struct type *name##_RB_PREV(struct type *)
439 #define RB_PROTOTYPE_MINMAX(name, type, attr)				\  argument
440 	attr struct type *name##_RB_MINMAX(struct name *, int)
441 #define RB_PROTOTYPE_REINSERT(name, type, attr)			\  argument
442 	attr struct type *name##_RB_REINSERT(struct name *, struct type *)
447 #define	RB_GENERATE(name, type, field, cmp)				\  argument
448 	RB_GENERATE_INTERNAL(name, type, field, cmp,)
449 #define	RB_GENERATE_STATIC(name, type, field, cmp)			\  argument
450 	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
451 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\  argument
452 	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
453 	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
454 	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
455 	RB_GENERATE_REMOVE(name, type, field, attr)			\
456 	RB_GENERATE_FIND(name, type, field, cmp, attr)			\
457 	RB_GENERATE_NFIND(name, type, field, cmp, attr)			\
458 	RB_GENERATE_NEXT(name, type, field, attr)			\
459 	RB_GENERATE_PREV(name, type, field, attr)			\
460 	RB_GENERATE_MINMAX(name, type, field, attr)			\
461 	RB_GENERATE_REINSERT(name, type, field, cmp, attr)
463 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\  argument
465 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
515 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\  argument
517 name##_RB_REMOVE_COLOR(struct name *head,				\
595 #define RB_GENERATE_REMOVE(name, type, field, attr)			\  argument
597 name##_RB_REMOVE(struct name *head, struct type *elm)			\
629 		name##_RB_REMOVE_COLOR(head, parent, child);		\
637 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\  argument
640 name##_RB_INSERT(struct name *head, struct type *elm)			\
663 	name##_RB_INSERT_COLOR(head, elm);				\
671 #define RB_GENERATE_FIND(name, type, field, cmp, attr)			\  argument
674 name##_RB_FIND(struct name *head, struct type *elm)			\
690 #define RB_GENERATE_NFIND(name, type, field, cmp, attr)			\  argument
693 name##_RB_NFIND(struct name *head, struct type *elm)			\
712 #define RB_GENERATE_NEXT(name, type, field, attr)			\  argument
715 name##_RB_NEXT(struct type *elm)					\
735 #define RB_GENERATE_PREV(name, type, field, attr)			\  argument
738 name##_RB_PREV(struct type *elm)					\
758 #define RB_GENERATE_MINMAX(name, type, field, attr)			\  argument
760 name##_RB_MINMAX(struct name *head, int val)				\
774 #define	RB_GENERATE_REINSERT(name, type, field, cmp, attr)		\  argument
776 name##_RB_REINSERT(struct name *head, struct type *elm)			\
779 	if (((cmpelm = RB_PREV(name, head, elm)) != NULL &&		\
781 	    ((cmpelm = RB_NEXT(name, head, elm)) != NULL &&		\
784 		RB_REMOVE(name, head, elm);				\
785 		return (RB_INSERT(name, head, elm));			\
793 #define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)  argument
794 #define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)  argument
795 #define RB_FIND(name, x, y)	name##_RB_FIND(x, y)  argument
796 #define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)  argument
797 #define RB_NEXT(name, x, y)	name##_RB_NEXT(y)  argument
798 #define RB_PREV(name, x, y)	name##_RB_PREV(y)  argument
799 #define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)  argument
800 #define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)  argument
801 #define RB_REINSERT(name, x, y)	name##_RB_REINSERT(x, y)  argument
803 #define RB_FOREACH(x, name, head)					\  argument
804 	for ((x) = RB_MIN(name, head);					\
806 	     (x) = name##_RB_NEXT(x))
808 #define RB_FOREACH_FROM(x, name, y)					\  argument
810 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
813 #define RB_FOREACH_SAFE(x, name, head, y)				\  argument
814 	for ((x) = RB_MIN(name, head);					\
815 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
818 #define RB_FOREACH_REVERSE(x, name, head)				\  argument
819 	for ((x) = RB_MAX(name, head);					\
821 	     (x) = name##_RB_PREV(x))
823 #define RB_FOREACH_REVERSE_FROM(x, name, y)				\  argument
825 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
828 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\  argument
829 	for ((x) = RB_MAX(name, head);					\
830 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\