Date: Thu, 22 Jan 2015 09:22:00 +0100 From: Sebastian Huber <sebastian.huber@embedded-brains.de> To: freebsd-arch@freebsd.org Cc: Sebastian Huber <sebastian.huber@embedded-brains.de> Subject: [PATCH] sys/tree.h: Add prototype and generate macros Message-ID: <1421914920-31394-1-git-send-email-sebastian.huber@embedded-brains.de>
next in thread | raw e-mail | index | archive | help
Provide individual prototype and generate macros for the red-black tree.
This helps to reduce code size in statically linked applications.
---
sys/sys/tree.h | 86 +++++++++++++++++++++++++++++++++++++++++-----------------
1 file changed, 61 insertions(+), 25 deletions(-)
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) \
{ \
--
1.8.4.5
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?1421914920-31394-1-git-send-email-sebastian.huber>