Author: kib
Date: Sat Jan 24 12:43:36 2015
New Revision: 277642
URL: https://svnweb.freebsd.org/changeset/base/277642
Log:
Provide individual prototype and generate macros for the red-black tree.
This helps to reduce code size in statically linked applications.
Submitted by: Sebastian Huber <sebastian.hu...@embedded-brains.de>
MFC after: 2 weeks
Modified:
head/share/man/man3/tree.3
head/sys/sys/tree.h
Modified: head/share/man/man3/tree.3
==============================================================================
--- head/share/man/man3/tree.3 Sat Jan 24 08:48:05 2015 (r277641)
+++ head/share/man/man3/tree.3 Sat Jan 24 12:43:36 2015 (r277642)
@@ -30,7 +30,7 @@
.\"
.\" $FreeBSD$
.\"
-.Dd November 10, 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 ,
@@ -111,8 +129,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"
@@ -377,6 +413,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
@@ -388,6 +445,18 @@ These macros take the same arguments as
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
Modified: head/sys/sys/tree.h
==============================================================================
--- head/sys/sys/tree.h Sat Jan 24 08:48:05 2015 (r277641)
+++ head/sys/sys/tree.h Sat Jan 24 12:43:36 2015 (r277642)
@@ -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(struc
#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
} \
} \
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
} \
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, stru
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
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, struc
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) \
{ \
_______________________________________________
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
