57 #define SPLAY_HEAD(name, type)						\  argument
59 	struct type *sph_root; /* root of the tree */			\
69 #define SPLAY_ENTRY(type)						\  argument
71 	struct type *spe_left; /* left element */			\
72 	struct type *spe_right; /* right element */			\
114 #define SPLAY_PROTOTYPE(name, type, field, cmp)				\  argument
115 void name##_SPLAY(struct name *, struct type *);			\
117 struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
118 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
121 static __inline struct type *						\
122 name##_SPLAY_FIND(struct name *head, struct type *elm)			\
132 static __inline struct type *						\
133 name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
146 static __inline struct type *						\
156 #define SPLAY_GENERATE(name, type, field, cmp)				\  argument
157 struct type *								\
158 name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
181 struct type *								\
182 name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
184 	struct type *__tmp;						\
203 name##_SPLAY(struct name *head, struct type *elm)			\
205 	struct type __node, *__left, *__right, *__tmp;			\
242 	struct type __node, *__left, *__right, *__tmp;			\
291 #define RB_HEAD(name, type)						\  argument
293 	struct type *rbh_root; /* root of the tree */			\
305 #define RB_ENTRY(type)							\  argument
307 	struct type *rbe_left;		/* left element */		\
308 	struct type *rbe_right;		/* right element */		\
309 	struct type *rbe_parent;	/* parent element */		\
376 #define RB_PROTOTYPE(name, type, field, cmp)				\  argument
377 void name##_RB_INSERT_COLOR(struct name *, struct type *);	\
378 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
379 struct type *name##_RB_REMOVE(struct name *, struct type *);		\
380 struct type *name##_RB_INSERT(struct name *, struct type *);		\
381 struct type *name##_RB_FIND(struct name *, struct type *);		\
382 struct type *name##_RB_NEXT(struct type *);				\
383 struct type *name##_RB_MINMAX(struct name *, int);			\
389 #define RB_GENERATE(name, type, field, cmp)				\  argument
391 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
393 	struct type *parent, *gparent, *tmp;				\
435 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
437 	struct type *tmp;						\
457 					struct type *oleft;		\
489 					struct type *oright;		\
510 struct type *								\
511 name##_RB_REMOVE(struct name *head, struct type *elm)			\
513 	struct type *child, *parent, *old = elm;			\
520 		struct type *left;					\
578 struct type *								\
579 name##_RB_INSERT(struct name *head, struct type *elm)			\
581 	struct type *tmp;						\
582 	struct type *parent = NULL;					\
609 struct type *								\
610 name##_RB_FIND(struct name *head, struct type *elm)			\
612 	struct type *tmp = RB_ROOT(head);				\
626 struct type *								\
627 name##_RB_NEXT(struct type *elm)					\
647 struct type *								\
650 	struct type *tmp = RB_ROOT(head);				\
651 	struct type *parent = NULL;					\