62 #define SPLAY_HEAD(name, type)						\  argument
63 struct name {								\
119 #define SPLAY_PROTOTYPE(name, type, field, cmp)				\  argument
120 void name##_SPLAY(struct name *, struct type *);			\
121 void name##_SPLAY_MINMAX(struct name *, int);				\
122 struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
123 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
127 name##_SPLAY_FIND(struct name *head, struct type *elm)			\
131 	name##_SPLAY(head, elm);					\
138 name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
140 	name##_SPLAY(head, elm);					\
152 name##_SPLAY_MIN_MAX(struct name *head, int val)			\
154 	name##_SPLAY_MINMAX(head, val);					\
161 #define SPLAY_GENERATE(name, type, field, cmp)				\  argument
163 name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
169 	    name##_SPLAY(head, elm);					\
187 name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
192 	name##_SPLAY(head, elm);					\
199 			name##_SPLAY(head, elm);			\
208 name##_SPLAY(struct name *head, struct type *elm)			\
245 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
281 #define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)  argument
282 #define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)  argument
283 #define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)  argument
284 #define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)  argument
285 #define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\  argument
286 					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
287 #define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\  argument
288 					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
290 #define SPLAY_FOREACH(x, name, head)					\  argument
291 	for ((x) = SPLAY_MIN(name, head);				\
293 	     (x) = SPLAY_NEXT(name, head, x))
296 #define RB_HEAD(name, type)						\  argument
297 struct name {								\
381 #define	RB_PROTOTYPE(name, type, field, cmp)				\  argument
382 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
383 #define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\  argument
384 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
385 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\  argument
386 	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
387 	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
388 	RB_PROTOTYPE_INSERT(name, type, attr);				\
389 	RB_PROTOTYPE_REMOVE(name, type, attr);				\
390 	RB_PROTOTYPE_FIND(name, type, attr);				\
391 	RB_PROTOTYPE_NFIND(name, type, attr);				\
392 	RB_PROTOTYPE_NEXT(name, type, attr);				\
393 	RB_PROTOTYPE_PREV(name, type, attr);				\
394 	RB_PROTOTYPE_MINMAX(name, type, attr);
395 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\  argument
396 	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
397 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\  argument
398 	attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *)
399 #define RB_PROTOTYPE_REMOVE(name, type, attr)				\  argument
400 	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
401 #define RB_PROTOTYPE_INSERT(name, type, attr)				\  argument
402 	attr struct type *name##_RB_INSERT(struct name *, struct type *)
403 #define RB_PROTOTYPE_FIND(name, type, attr)				\  argument
404 	attr struct type *name##_RB_FIND(struct name *, struct type *)
405 #define RB_PROTOTYPE_NFIND(name, type, attr)				\  argument
406 	attr struct type *name##_RB_NFIND(struct name *, struct type *)
407 #define RB_PROTOTYPE_NEXT(name, type, attr)				\  argument
408 	attr struct type *name##_RB_NEXT(struct type *)
409 #define RB_PROTOTYPE_PREV(name, type, attr)				\  argument
410 	attr struct type *name##_RB_PREV(struct type *)
411 #define RB_PROTOTYPE_MINMAX(name, type, attr)				\  argument
412 	attr struct type *name##_RB_MINMAX(struct name *, int)
417 #define	RB_GENERATE(name, type, field, cmp)				\  argument
418 	RB_GENERATE_INTERNAL(name, type, field, cmp,)
419 #define	RB_GENERATE_STATIC(name, type, field, cmp)			\  argument
420 	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
421 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\  argument
422 	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
423 	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
424 	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
425 	RB_GENERATE_REMOVE(name, type, field, attr)			\
426 	RB_GENERATE_FIND(name, type, field, cmp, attr)			\
427 	RB_GENERATE_NFIND(name, type, field, cmp, attr)			\
428 	RB_GENERATE_NEXT(name, type, field, attr)			\
429 	RB_GENERATE_PREV(name, type, field, attr)			\
430 	RB_GENERATE_MINMAX(name, type, field, attr)
432 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\  argument
434 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
477 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\  argument
479 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
556 #define RB_GENERATE_REMOVE(name, type, field, attr)			\  argument
558 name##_RB_REMOVE(struct name *head, struct type *elm)			\
620 		name##_RB_REMOVE_COLOR(head, parent, child);		\
624 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\  argument
627 name##_RB_INSERT(struct name *head, struct type *elm)			\
652 	name##_RB_INSERT_COLOR(head, elm);				\
656 #define RB_GENERATE_FIND(name, type, field, cmp, attr)			\  argument
659 name##_RB_FIND(struct name *head, struct type *elm)			\
675 #define RB_GENERATE_NFIND(name, type, field, cmp, attr)			\  argument
678 name##_RB_NFIND(struct name *head, struct type *elm)			\
697 #define RB_GENERATE_NEXT(name, type, field, attr)			\  argument
700 name##_RB_NEXT(struct type *elm)					\
720 #define RB_GENERATE_PREV(name, type, field, attr)			\  argument
723 name##_RB_PREV(struct type *elm)					\
743 #define RB_GENERATE_MINMAX(name, type, field, attr)			\  argument
745 name##_RB_MINMAX(struct name *head, int val)				\
762 #define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)  argument
763 #define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)  argument
764 #define RB_FIND(name, x, y)	name##_RB_FIND(x, y)  argument
765 #define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)  argument
766 #define RB_NEXT(name, x, y)	name##_RB_NEXT(y)  argument
767 #define RB_PREV(name, x, y)	name##_RB_PREV(y)  argument
768 #define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)  argument
769 #define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)  argument
771 #define RB_FOREACH(x, name, head)					\  argument
772 	for ((x) = RB_MIN(name, head);					\
774 	     (x) = name##_RB_NEXT(x))
776 #define RB_FOREACH_FROM(x, name, y)					\  argument
778 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
781 #define RB_FOREACH_SAFE(x, name, head, y)				\  argument
782 	for ((x) = RB_MIN(name, head);					\
783 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
786 #define RB_FOREACH_REVERSE(x, name, head)				\  argument
787 	for ((x) = RB_MAX(name, head);					\
789 	     (x) = name##_RB_PREV(x))
791 #define RB_FOREACH_REVERSE_FROM(x, name, y)				\  argument
793 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
796 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\  argument
797 	for ((x) = RB_MAX(name, head);					\
798 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\