From owner-freebsd-arch@FreeBSD.ORG Thu Jan 22 08:28:15 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 0488E322 for ; Thu, 22 Jan 2015 08:28:15 +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 A0C03C75 for ; Thu, 22 Jan 2015 08:28:14 +0000 (UTC) Received: from frontend01.mail.m-online.net (unknown [192.168.8.182]) by mail-out.m-online.net (Postfix) with ESMTP id 3kSc5m4YCWz3hjKf for ; Thu, 22 Jan 2015 09:22:04 +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 3kSc5m36X8zvh2M for ; Thu, 22 Jan 2015 09:22:04 +0100 (CET) Received: by mail.embedded-brains.de (Postfix, from userid 65534) id 3BB55652CFD; Thu, 22 Jan 2015 09:22:03 +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 A8A0C65253A; Thu, 22 Jan 2015 09:22:01 +0100 (CET) From: Sebastian Huber To: freebsd-arch@freebsd.org Subject: [PATCH] sys/tree.h: Add prototype and generate macros Date: Thu, 22 Jan 2015 09:22:00 +0100 Message-Id: <1421914920-31394-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: Thu, 22 Jan 2015 08:28:15 -0000 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