Date: Sat, 24 Jan 2015 12:43:36 +0000 (UTC) From: Konstantin Belousov <kib@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r277642 - in head: share/man/man3 sys/sys Message-ID: <201501241243.t0OChaqf051241@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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.huber@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) \ { \
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201501241243.t0OChaqf051241>