From owner-freebsd-arch@FreeBSD.ORG Fri Jan 23 14:11:42 2015 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id C4FB214D for ; Fri, 23 Jan 2015 14:11:42 +0000 (UTC) Received: from mail-out.m-online.net (mail-out.m-online.net [212.18.0.9]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 6EE5CAFD for ; Fri, 23 Jan 2015 14:11:41 +0000 (UTC) Received: from frontend01.mail.m-online.net (unknown [192.168.8.182]) by mail-out.m-online.net (Postfix) with ESMTP id 3kTMpX4Bzlz3hj6s for ; Fri, 23 Jan 2015 15:11:31 +0100 (CET) Received: from mail.embedded-brains.de (host-82-135-62-35.customer.m-online.net [82.135.62.35]) by mail.mnet-online.de (Postfix) with ESMTP id 3kTMpW4bD8zvjN0 for ; Fri, 23 Jan 2015 15:11:31 +0100 (CET) Received: by mail.embedded-brains.de (Postfix, from userid 65534) id 34E85652CFF; Fri, 23 Jan 2015 15:11:31 +0100 (CET) X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on fidibusdmz X-Spam-Level: X-Spam-Status: No, score=-4.0 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00 autolearn=ham version=3.2.5 Received: from self.eb.z (unknown [192.168.100.11]) by mail.embedded-brains.de (Postfix) with ESMTP id 31B10652CFC; Fri, 23 Jan 2015 15:11:30 +0100 (CET) From: Sebastian Huber To: freebsd-arch@freebsd.org Subject: [PATCH v2] sys/tree.h: Add prototype and generate macros Date: Fri, 23 Jan 2015 15:11:28 +0100 Message-Id: <1422022288-17630-1-git-send-email-sebastian.huber@embedded-brains.de> X-Mailer: git-send-email 1.8.4.5 Cc: Sebastian Huber X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 23 Jan 2015 14:11:42 -0000 Provide individual prototype and generate macros for the red-black tree. This helps to reduce code size in statically linked applications. v2: Update man page. --- share/man/man3/tree.3 | 71 ++++++++++++++++++++++++++++++++++++++++++ sys/sys/tree.h | 86 ++++++++++++++++++++++++++++++++++++--------------- 2 files changed, 132 insertions(+), 25 deletions(-) diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 index 2e9c63c..0940a0c 100644 --- a/share/man/man3/tree.3 +++ b/share/man/man3/tree.3 @@ -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,29 @@ 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 +.Fa empty +for global functions or +.Fa static +for static functions. .Pp The function bodies are generated with the .Fn RB_GENERATE @@ -388,6 +447,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) \ { \ -- 1.8.4.5