diff options
author | kib <kib@FreeBSD.org> | 2015-01-24 12:43:36 +0000 |
---|---|---|
committer | kib <kib@FreeBSD.org> | 2015-01-24 12:43:36 +0000 |
commit | f3fd716384efab41262353c6ad81586b9c202822 (patch) | |
tree | c11ef089d05a33f20a7afad29d8784e3b5f08d80 /sys/sys/tree.h | |
parent | 70c9059ac63a17a0170e0407668bfd907bedf638 (diff) | |
download | FreeBSD-src-f3fd716384efab41262353c6ad81586b9c202822.zip FreeBSD-src-f3fd716384efab41262353c6ad81586b9c202822.tar.gz |
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.huber@embedded-brains.de>
MFC after: 2 weeks
Diffstat (limited to 'sys/sys/tree.h')
-rw-r--r-- | sys/sys/tree.h | 86 |
1 files 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) \ { \ |