From patchwork Mon Jul 3 19:58:08 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9823905 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 2B4BC60353 for ; Mon, 3 Jul 2017 20:01:20 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1CF9127F3E for ; Mon, 3 Jul 2017 20:01:20 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 1108827FB7; Mon, 3 Jul 2017 20:01:20 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-3.6 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_MED, RCVD_IN_SORBS_SPAM, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 6C0B027F3E for ; Mon, 3 Jul 2017 20:01:19 +0000 (UTC) Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dS7Uo-0000nx-KB; Mon, 03 Jul 2017 19:58:58 +0000 Received: from mail6.bemta6.messagelabs.com ([193.109.254.103]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dS7Un-0000nZ-GG for xen-devel@lists.xen.org; Mon, 03 Jul 2017 19:58:57 +0000 Received: from [193.109.254.147] by server-2.bemta-6.messagelabs.com id D7/C6-03032-002AA595; Mon, 03 Jul 2017 19:58:56 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrGIsWRWlGSWpSXmKPExsXiVRvkqPt/YVS kwfP/VhZLPi5mcWD0OLr7N1MAYxRrZl5SfkUCa0Zbz0eWglWqFV92T2RtYJyv0MXIxSEkMJFR 4syB7YwgDovASxaJB/vPsYM4EgL9rBJHz3YDORxATpzEwlfuXYycQGaZxKW2SSwgtpCAmsSWe aeYISb9Z5S4+mcmK0g9m4CuRPutApAaEQFpiWufL4MtYBb4ziix5v0UVpCEsECMREfTarBBLA KqEtM7joHZvAI2Es8+bGeFWCYvsWjTDLA4p4CtxMwHM5ggFttI/LzSzziBUWABI8MqRo3i1KK y1CJdI0u9pKLM9IyS3MTMHF1DAzO93NTi4sT01JzEpGK95PzcTYzA0GIAgh2MBxYFHmKU5GBS EuV1vRkZKcSXlJ9SmZFYnBFfVJqTWnyIUYaDQ0mClxUYqkKCRanpqRVpmTnAIIdJS3DwKInwT m4ESvMWFyTmFmemQ6ROMRpzTDqw/QsTx6sJ/78xCbHk5eelSonzaoFMEgApzSjNgxsEi75LjL JSwryMQKcJ8RSkFuVmlqDKv2IU52BUEuatXwA0hSczrwRu3yugU5iATmnoiQA5pSQRISXVwLj /fsXiR4emVmhPXT0nZGXIWzF9IeVPnTFzclYsNvS76sj+4J/KtTdbWY9fkvL4U2JpECz1UlZ6 VtK+jDM+TkwrTs1TkovceFHOrX3PjYfz8y5UFRfsDzj+7GOY3ne7ycnP3qUf5ppqu591lcAM6 edcrVfD97I8fDmTS3P2etEfHY+ZW5OlOEOVWIozEg21mIuKEwEBYaLWuQIAAA== X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-5.tower-27.messagelabs.com!1499111935!99901139!1 X-Originating-IP: [74.125.82.65] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 9.4.25; banners=-,-,- X-VirusChecked: Checked Received: (qmail 28005 invoked from network); 3 Jul 2017 19:58:55 -0000 Received: from mail-wm0-f65.google.com (HELO mail-wm0-f65.google.com) (74.125.82.65) by server-5.tower-27.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 3 Jul 2017 19:58:55 -0000 Received: by mail-wm0-f65.google.com with SMTP id j85so22410899wmj.0 for ; Mon, 03 Jul 2017 12:58:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=WEOwhYJkcMCshQMmcTlBpo5fi2eoCsbwTNy5CxMDqVY=; b=MvEEG9T5NUB2GSJOE7b0XVMh6+cN5XhMK9JdVf292bDkxElSQKDLpe7GgdsfTHdNSo YUDlXHDn2XKXvn48M+/NYGeMsxRRfdcO97Of7LrciYrnYNJnbOQZ3enp3bV/DdOOi/Oe GQnaOxHsFJjTk5fj1rOCdXHYB42R49+Kft1ju/L3mscChMEQ1tTPQ9bhpr/Wz1Ab8gn8 0quONGAzDyQCrnBo/wW2hfyYNJDBo3zAd9RvZ2029lwT2E6zHrg3sxwVFwE79Gslhvo6 lmwIG1ijxFL7GqWUWQvMnWaRWSWLi8A8MoX20ztH3ChqbJmGVV3LcsBxC3TTpC9M5+Yi P6Ow== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=WEOwhYJkcMCshQMmcTlBpo5fi2eoCsbwTNy5CxMDqVY=; b=OHNvxq/cErOTgveCs0dY8OFSbhEKTcpTYzyYJrveBQkjCJB1/+1WuL7q5h+1FF9mxI ck6R3UAD9pNKBMmmMVk/XMrSYzSQ+FM9sMLQ+hdncooA7EfB+xJvJ/bY2zbvuM3dRSYT 8jUVJsqxyJF5FaFjhtLiOmNSsuMVs0jJ6eV+4fSb5c6p3I+/cq1IdtvBBj2j5Fy0sm8o xD/c1fhLvZQoEz8g7yeGoPfvjYUwaO6W1pme6hI0Y6jxA12eJpQkyvzflXSrBjMxvwP+ 76jUqrVjrKn+y96YXhruzhQQgcTJ78457TglJMw9OJdroJXHB2cuLjpJO7TQssag0g+6 bvXw== X-Gm-Message-State: AIVw11380cuV6vV26GhLmwROz1ejHuV4x9+imHEGfVUYq9r5EDGYmPlA vIt2HmNZ72I9VyUy X-Received: by 10.28.21.80 with SMTP id 77mr5080154wmv.79.1499111935366; Mon, 03 Jul 2017 12:58:55 -0700 (PDT) Received: from kpraveen.labs.blr.novell.com ([106.51.128.11]) by smtp.gmail.com with ESMTPSA id 21sm25658979wmo.16.2017.07.03.12.58.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 03 Jul 2017 12:58:54 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Tue, 4 Jul 2017 01:28:08 +0530 Message-Id: <20170703195821.29845-5-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170703195821.29845-1-kpraveen.lkml@gmail.com> References: <20170703195821.29845-1-kpraveen.lkml@gmail.com> Cc: sstabellini@kernel.org, wei.liu2@citrix.com, George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, kpraveen.lkml@gmail.com, jbeulich@suse.com Subject: [Xen-devel] [PATCH v4 04/17] rbtree: move some implementation details from rbtree.h to rbtree.c X-BeenThere: xen-devel@lists.xen.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: xen-devel-bounces@lists.xen.org Sender: "Xen-devel" X-Virus-Scanned: ClamAV using ClamSMTP From: Michel Lespinasse rbtree users must use the documented APIs to manipulate the tree structure. Low-level helpers to manipulate node colors and parenthood are not part of that API, so move them to lib/rbtree.c Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds [Linux commit bf7ad8eeab995710c766df49c9c69a8592ca0216] Ported to Xen. Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 20 +++++++++++++++++++- xen/include/xen/rbtree.h | 34 +++++++++------------------------- 2 files changed, 28 insertions(+), 26 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index e2a665118b..1ed5943c5a 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -22,6 +22,24 @@ #include #include +#define RB_RED 0 +#define RB_BLACK 1 + +#define rb_color(r) ((r)->__rb_parent_color & 1) +#define rb_is_red(r) (!rb_color(r)) +#define rb_is_black(r) rb_color(r) +#define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0) +#define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; +} +static inline void rb_set_color(struct rb_node *rb, int color) +{ + rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; +} + static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) { struct rb_node *right = node->rb_right; @@ -254,7 +272,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) rb_set_parent(old->rb_right, node); } - node->rb_parent_color = old->rb_parent_color; + node->__rb_parent_color = old->__rb_parent_color; node->rb_left = old->rb_left; rb_set_parent(old->rb_left, node); diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h index 4249752dcb..c3af3db5d0 100644 --- a/xen/include/xen/rbtree.h +++ b/xen/include/xen/rbtree.h @@ -19,36 +19,18 @@ #ifndef __RBTREE_H__ #define __RBTREE_H__ -struct rb_node -{ - unsigned long rb_parent_color; -#define RB_RED 0 -#define RB_BLACK 1 +struct rb_node { + unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); /* The alignment might seem pointless, but allegedly CRIS needs it */ -struct rb_root -{ +struct rb_root { struct rb_node *rb_node; }; -#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) -#define rb_color(r) ((r)->rb_parent_color & 1) -#define rb_is_red(r) (!rb_color(r)) -#define rb_is_black(r) rb_color(r) -#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) -#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) - -static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) -{ - rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; -} -static inline void rb_set_color(struct rb_node *rb, int color) -{ - rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; -} +#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) #define RB_ROOT (struct rb_root) { NULL, } #define rb_entry(ptr, type, member) container_of(ptr, type, member) @@ -56,8 +38,10 @@ static inline void rb_set_color(struct rb_node *rb, int color) #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) /* 'empty' nodes are nodes that are known not to be inserted in an rbree */ -#define RB_EMPTY_NODE(node) ((node)->rb_parent_color == (unsigned long)(node)) -#define RB_CLEAR_NODE(node) ((node)->rb_parent_color = (unsigned long)(node)) +#define RB_EMPTY_NODE(node) \ + ((node)->__rb_parent_color == (unsigned long)(node)) +#define RB_CLEAR_NODE(node) \ + ((node)->__rb_parent_color = (unsigned long)(node)) extern void rb_insert_color(struct rb_node *, struct rb_root *); extern void rb_erase(struct rb_node *, struct rb_root *); @@ -75,7 +59,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link) { - node->rb_parent_color = (unsigned long )parent; + node->__rb_parent_color = (unsigned long )parent; node->rb_left = node->rb_right = NULL; *rb_link = node;