MFC r277642:

Provide individual prototype and generate macros for the red-black tree.

2 files changed, 131 insertions, 26 deletions

diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3
index e8ee4f7..5f35383 100644
--- a/share/man/man3/tree.3
+++ b/share/man/man3/tree.3
@@ -30,7 +30,7 @@
 .\"
 .\" $FreeBSD$
 .\"
-.Dd November 4, 2013
+.Dd January 24, 2015
 .Dt TREE 3
 .Os
 .Sh NAME
@@ -53,8 +53,26 @@
 .Nm SPLAY_REMOVE ,
 .Nm RB_PROTOTYPE ,
 .Nm RB_PROTOTYPE_STATIC ,
+.Nm RB_PROTOTYPE_INSERT ,
+.Nm RB_PROTOTYPE_INSERT_COLOR ,
+.Nm RB_PROTOTYPE_REMOVE ,
+.Nm RB_PROTOTYPE_REMOVE_COLOR ,
+.Nm RB_PROTOTYPE_FIND ,
+.Nm RB_PROTOTYPE_NFIND ,
+.Nm RB_PROTOTYPE_NEXT ,
+.Nm RB_PROTOTYPE_PREV ,
+.Nm RB_PROTOTYPE_MINMAX ,
 .Nm RB_GENERATE ,
 .Nm RB_GENERATE_STATIC ,
+.Nm RB_GENERATE_INSERT ,
+.Nm RB_GENERATE_INSERT_COLOR ,
+.Nm RB_GENERATE_REMOVE ,
+.Nm RB_GENERATE_REMOVE_COLOR ,
+.Nm RB_GENERATE_FIND ,
+.Nm RB_GENERATE_NFIND ,
+.Nm RB_GENERATE_NEXT ,
+.Nm RB_GENERATE_PREV ,
+.Nm RB_GENERATE_MINMAX ,
 .Nm RB_ENTRY ,
 .Nm RB_HEAD ,
 .Nm RB_INITIALIZER ,
@@ -109,8 +127,26 @@
 .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 .Fn RB_PROTOTYPE NAME TYPE FIELD CMP
 .Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
+.Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR
+.Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
+.Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR
+.Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
+.Fn RB_PROTOTYPE_FIND NAME TYPE ATTR
+.Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR
+.Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR
+.Fn RB_PROTOTYPE_PREV NAME TYPE ATTR
+.Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR
 .Fn RB_GENERATE NAME TYPE FIELD CMP
 .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
+.Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
+.Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
+.Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR
+.Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
+.Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
+.Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
+.Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR
+.Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR
+.Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR
 .Fn RB_ENTRY TYPE
 .Fn RB_HEAD HEADNAME TYPE
 .Fn RB_INITIALIZER "RB_HEAD *head"
@@ -373,6 +409,27 @@ The
 .Fa FIELD
 argument is the name of the element defined by
 .Fn RB_ENTRY .
+Individual prototypes can be declared with
+.Fn RB_PROTOTYPE_INSERT ,
+.Fn RB_PROTOTYPE_INSERT_COLOR ,
+.Fn RB_PROTOTYPE_REMOVE ,
+.Fn RB_PROTOTYPE_REMOVE_COLOR ,
+.Fn RB_PROTOTYPE_FIND ,
+.Fn RB_PROTOTYPE_NFIND ,
+.Fn RB_PROTOTYPE_NEXT ,
+.Fn RB_PROTOTYPE_PREV ,
+and
+.Fn RB_PROTOTYPE_MINMAX
+in case not all functions are required.  The individual prototype macros expect
+.Fa NAME ,
+.Fa TYPE ,
+and
+.Fa ATTR
+arguments.  The
+.Fa ATTR
+argument must be empty for global functions or
+.Fa static
+for static functions.
 .Pp
 The function bodies are generated with the
 .Fn RB_GENERATE
@@ -384,6 +441,18 @@ These macros take the same arguments as the
 and
 .Fn RB_PROTOTYPE_STATIC
 macros, but should be used only once.
+As an alternative individual function bodies are generated with the
+.Fn RB_GENERATE_INSERT ,
+.Fn RB_GENERATE_INSERT_COLOR ,
+.Fn RB_GENERATE_REMOVE ,
+.Fn RB_GENERATE_REMOVE_COLOR ,
+.Fn RB_GENERATE_FIND ,
+.Fn RB_GENERATE_NFIND ,
+.Fn RB_GENERATE_NEXT ,
+.Fn RB_GENERATE_PREV ,
+and
+.Fn RB_GENERATE_MINMAX
+macros.
 .Pp
 Finally,
 the
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index 1cce727..c9df686 100644
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -383,16 +383,33 @@ struct {								\
 #define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
-attr void name##_RB_INSERT_COLOR(struct name *, struct type *);		\
-attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
-attr struct type *name##_RB_REMOVE(struct name *, struct type *);	\
-attr struct type *name##_RB_INSERT(struct name *, struct type *);	\
-attr struct type *name##_RB_FIND(struct name *, struct type *);		\
-attr struct type *name##_RB_NFIND(struct name *, struct type *);	\
-attr struct type *name##_RB_NEXT(struct type *);			\
-attr struct type *name##_RB_PREV(struct type *);			\
-attr struct type *name##_RB_MINMAX(struct name *, int);			\
-									\
+	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
+	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
+	RB_PROTOTYPE_INSERT(name, type, attr);				\
+	RB_PROTOTYPE_REMOVE(name, type, attr);				\
+	RB_PROTOTYPE_FIND(name, type, attr);				\
+	RB_PROTOTYPE_NFIND(name, type, attr);				\
+	RB_PROTOTYPE_NEXT(name, type, attr);				\
+	RB_PROTOTYPE_PREV(name, type, attr);				\
+	RB_PROTOTYPE_MINMAX(name, type, attr);
+#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\
+	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
+#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\
+	attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *)
+#define RB_PROTOTYPE_REMOVE(name, type, attr)				\
+	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
+#define RB_PROTOTYPE_INSERT(name, type, attr)				\
+	attr struct type *name##_RB_INSERT(struct name *, struct type *)
+#define RB_PROTOTYPE_FIND(name, type, attr)				\
+	attr struct type *name##_RB_FIND(struct name *, struct type *)
+#define RB_PROTOTYPE_NFIND(name, type, attr)				\
+	attr struct type *name##_RB_NFIND(struct name *, struct type *)
+#define RB_PROTOTYPE_NEXT(name, type, attr)				\
+	attr struct type *name##_RB_NEXT(struct type *)
+#define RB_PROTOTYPE_PREV(name, type, attr)				\
+	attr struct type *name##_RB_PREV(struct type *)
+#define RB_PROTOTYPE_MINMAX(name, type, attr)				\
+	attr struct type *name##_RB_MINMAX(struct name *, int)
 
 /* Main rb operation.
  * Moves node close to the key of elm to top
@@ -402,6 +419,17 @@ attr struct type *name##_RB_MINMAX(struct name *, int);			\
 #define	RB_GENERATE_STATIC(name, type, field, cmp)			\
 	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
+	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
+	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
+	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
+	RB_GENERATE_REMOVE(name, type, field, attr)			\
+	RB_GENERATE_FIND(name, type, field, cmp, attr)			\
+	RB_GENERATE_NFIND(name, type, field, cmp, attr)			\
+	RB_GENERATE_NEXT(name, type, field, attr)			\
+	RB_GENERATE_PREV(name, type, field, attr)			\
+	RB_GENERATE_MINMAX(name, type, field, attr)
+
+#define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
 attr void								\
 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
 {									\
@@ -444,8 +472,9 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
 		}							\
 	}								\
 	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
-}									\
-									\
+}
+
+#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
 attr void								\
 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
 {									\
@@ -522,8 +551,9 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm)
 	}								\
 	if (elm)							\
 		RB_COLOR(elm, field) = RB_BLACK;			\
-}									\
-									\
+}
+
+#define RB_GENERATE_REMOVE(name, type, field, attr)			\
 attr struct type *							\
 name##_RB_REMOVE(struct name *head, struct type *elm)			\
 {									\
@@ -590,7 +620,8 @@ color:									\
 		name##_RB_REMOVE_COLOR(head, parent, child);		\
 	return (old);							\
 }									\
-									\
+
+#define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
 /* Inserts a node into the RB tree */					\
 attr struct type *							\
 name##_RB_INSERT(struct name *head, struct type *elm)			\
@@ -620,8 +651,9 @@ name##_RB_INSERT(struct name *head, struct type *elm)			\
 		RB_ROOT(head) = elm;					\
 	name##_RB_INSERT_COLOR(head, elm);				\
 	return (NULL);							\
-}									\
-									\
+}
+
+#define RB_GENERATE_FIND(name, type, field, cmp, attr)			\
 /* Finds the node with the same key as elm */				\
 attr struct type *							\
 name##_RB_FIND(struct name *head, struct type *elm)			\
@@ -638,8 +670,9 @@ name##_RB_FIND(struct name *head, struct type *elm)			\
 			return (tmp);					\
 	}								\
 	return (NULL);							\
-}									\
-									\
+}
+
+#define RB_GENERATE_NFIND(name, type, field, cmp, attr)			\
 /* Finds the first node greater than or equal to the search key */	\
 attr struct type *							\
 name##_RB_NFIND(struct name *head, struct type *elm)			\
@@ -659,8 +692,9 @@ name##_RB_NFIND(struct name *head, struct type *elm)			\
 			return (tmp);					\
 	}								\
 	return (res);							\
-}									\
-									\
+}
+
+#define RB_GENERATE_NEXT(name, type, field, attr)			\
 /* ARGSUSED */								\
 attr struct type *							\
 name##_RB_NEXT(struct type *elm)					\
@@ -681,8 +715,9 @@ name##_RB_NEXT(struct type *elm)					\
 		}							\
 	}								\
 	return (elm);							\
-}									\
-									\
+}
+
+#define RB_GENERATE_PREV(name, type, field, attr)			\
 /* ARGSUSED */								\
 attr struct type *							\
 name##_RB_PREV(struct type *elm)					\
@@ -703,8 +738,9 @@ name##_RB_PREV(struct type *elm)					\
 		}							\
 	}								\
 	return (elm);							\
-}									\
-									\
+}
+
+#define RB_GENERATE_MINMAX(name, type, field, attr)			\
 attr struct type *							\
 name##_RB_MINMAX(struct name *head, int val)				\
 {									\