From patchwork Sat Jun 17 09:32:40 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9794017 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 05B796038E for ; Sat, 17 Jun 2017 09:36:03 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id EB9812856A for ; Sat, 17 Jun 2017 09:36:02 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id E06E128562; Sat, 17 Jun 2017 09:36:02 +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=-4.1 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_MED, 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 62BE3284B3 for ; Sat, 17 Jun 2017 09:36:02 +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 1dMA6y-0002Cm-CV; Sat, 17 Jun 2017 09:33:44 +0000 Received: from mail6.bemta6.messagelabs.com ([193.109.254.103]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dMA6w-0002Bm-U4 for xen-devel@lists.xen.org; Sat, 17 Jun 2017 09:33:43 +0000 Received: from [193.109.254.147] by server-8.bemta-6.messagelabs.com id 35/68-03696-677F4495; Sat, 17 Jun 2017 09:33:42 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFprHIsWRWlGSWpSXmKPExsXiVRvsolv63SX S4N16eYslHxezODB6HN39mymAMYo1My8pvyKBNeNQ+122gsMqFWf69jA2MF6X62Lk4hASmMgo cX3ZZUYQh0XgJYtEw9+9YI6EQD+rxItnm5i6GDmBnDiJBSd3QdmVErsutTOC2EICahJb5p1ih hj1m1Hi16pr7F2MHBxsAroS7bcKQGpEBKQlrn2G2MAs8J1RYs37KawgCWGBGIlP1z+BDWIRUJ XYOeUfWJxXwFri1qSDzBDL5CUWbZrBAjKTU8BGomeRJ4gpBFRyYg77BEaBBYwMqxjVi1OLylK LdE31kooy0zNKchMzc3QNDcz0clOLixPTU3MSk4r1kvNzNzECw4oBCHYwTr/sf4hRkoNJSZQ3 J9wlUogvKT+lMiOxOCO+qDQntfgQowwHh5IE75OvQDnBotT01Iq0zBxggMOkJTh4lER4zz8GS vMWFyTmFmemQ6ROMepyTDqw/QuTEEtefl6qlDjvKpAZAiBFGaV5cCNg0XaJUVZKmJcR6Cghno LUotzMElT5V4ziHIxKwrweIFN4MvNK4Da9AjqCCegI5jNgR5QkIqSkGhh7NvGJnLwao/Kvv0H p0DLfnD3Br30PPnj9OkWrU6QslCd/86SkIz+2a0wOMmNYIuDkX+W/XfZ54UTG5TEP7rVHx31t tCq4sTvjiBtrn19eEO+nNJ9OoS83Yt+ntG5askjD/GKK3qlpPZdWvt1h0O+6wEdl4R3uZjaBa e5zFiyplrhkXCehl6TEUpyRaKjFXFScCACx+RsjsQIAAA== X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-11.tower-27.messagelabs.com!1497692020!77576229!1 X-Originating-IP: [74.125.83.68] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 9.4.19; banners=-,-,- X-VirusChecked: Checked Received: (qmail 54303 invoked from network); 17 Jun 2017 09:33:41 -0000 Received: from mail-pg0-f68.google.com (HELO mail-pg0-f68.google.com) (74.125.83.68) by server-11.tower-27.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 17 Jun 2017 09:33:41 -0000 Received: by mail-pg0-f68.google.com with SMTP id f127so9498085pgc.2 for ; Sat, 17 Jun 2017 02:33:41 -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=u3Dr4MrFuhsk/oIch2/FDpF5soiCQAWitZHzJ7G2Rsc=; b=qL1cIrvm+8SCA25hPnFk6UqDe249zCDDZh/gcgXykxPn8yDiE/rXa3hBj9AzJA1N6N MTP8gYC76NI3JxeQj9cGJWEDw601pXEy1RpdA9vTZGU9f+S19GwlR7bgKFs+QN8danUE V1nO/CvolSCE4J7wI/aS1pQvMYGkRcm/6NSmG+QE6iLFfG9JxoeSAJyzVuI+Q1pMc5vm 7UyvhAylAjk6K1ZYm7BldWy7aH2npFeOmGLNuQf1M4xgv/DIeTAbh/LROOrWQSD+pGD7 QC7KsE84lAJe3lFwniBw1TeTcPcWyaG7KsAdmoG9Lckd5pfkxiOLBbevFK/bHghAPvcc 5Wdw== 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=u3Dr4MrFuhsk/oIch2/FDpF5soiCQAWitZHzJ7G2Rsc=; b=mhRcDJEDJgxBXDXTEd89v8Mc9rH6nHnVAVWDMcFA/eICt4bfOR1v9mtJ6meY/fxp2t tCOYoOSBXi8qIERm9Gj9Xnw6AlWR5oK0Bqf9pPotX/mA7WI0Av5SShac2NY0+qXu3cQY YDi7Gq5UfY41ibtsVyLQp4uqvBPHjunhTOcrfvPsSTujM0yKC8Udze0Dv357A4NBbFu4 1UROjZz4kften3E2HgBj22o6xG3FlB74SX3vFVsPEJqzRb4NZ/o68XbU1aNjd8OcfQnK EVxRBdRHE0CpoMmqZkuw2I0vPXHFzw7mH6sn38XgRmQHYR+bkI0Qq7xwmXkm3NbMpLu7 KGnQ== X-Gm-Message-State: AKS2vOwgsJtxwrMP6EYSLWkBUn4dVjBx7gPL81SjJbCSscKww3dJkQy2 TBbeiYc8rPOUBzjQ X-Received: by 10.84.231.194 with SMTP id g2mr17937829pln.34.1497692019660; Sat, 17 Jun 2017 02:33:39 -0700 (PDT) Received: from kpraveen.labs.blr.name ([103.227.99.177]) by smtp.gmail.com with ESMTPSA id k129sm9653921pfc.87.2017.06.17.02.33.36 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 17 Jun 2017 02:33:39 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Sat, 17 Jun 2017 15:02:40 +0530 Message-Id: <20170617093253.3990-8-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170617093253.3990-1-kpraveen.lkml@gmail.com> References: <20170617093253.3990-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 v2 07/20] 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 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 | 29 +++++++---------------------- 2 files changed, 26 insertions(+), 23 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 2561dbc7d9..49f73e2461 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; @@ -255,7 +273,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 f74b68ce62..89df40afd0 100644 --- a/xen/include/xen/rbtree.h +++ b/xen/include/xen/rbtree.h @@ -21,9 +21,7 @@ struct rb_node { - unsigned long rb_parent_color; -#define RB_RED 0 -#define RB_BLACK 1 + unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; }; @@ -33,21 +31,7 @@ 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) @@ -55,9 +39,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 +60,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;