From owner-svn-src-head@freebsd.org Thu Jun 25 17:44:14 2020 Return-Path: Delivered-To: svn-src-head@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id CD636340887; Thu, 25 Jun 2020 17:44:14 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 49t6p64XKjz4MnX; Thu, 25 Jun 2020 17:44:14 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 7E40626D5E; Thu, 25 Jun 2020 17:44:14 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id 05PHiEZ6009740; Thu, 25 Jun 2020 17:44:14 GMT (envelope-from dougm@FreeBSD.org) Received: (from dougm@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id 05PHiEUu009739; Thu, 25 Jun 2020 17:44:14 GMT (envelope-from dougm@FreeBSD.org) Message-Id: <202006251744.05PHiEUu009739@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dougm set sender to dougm@FreeBSD.org using -f From: Doug Moore Date: Thu, 25 Jun 2020 17:44:14 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r362617 - head/sys/sys X-SVN-Group: head X-SVN-Commit-Author: dougm X-SVN-Commit-Paths: head/sys/sys X-SVN-Commit-Revision: 362617 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.33 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 25 Jun 2020 17:44:14 -0000 Author: dougm Date: Thu Jun 25 17:44:14 2020 New Revision: 362617 URL: https://svnweb.freebsd.org/changeset/base/362617 Log: Eliminate the color field from the RB element struct. Identify the color of a node (or, really, the color of the link from the parent to the node) by using one of the last two bits of the parent pointer in that parent node. Adjust rebalancing methods to account for where colors are stored, and the fact that null children have a color too. Adjust RB_PARENT and RB_SET_PARENT to account for this change. Reviewed by: markj Tested by: pho, hselasky Differential Revision: https://reviews.freebsd.org/D25418 Modified: head/sys/sys/tree.h Modified: head/sys/sys/tree.h ============================================================================== --- head/sys/sys/tree.h Thu Jun 25 17:04:22 2020 (r362616) +++ head/sys/sys/tree.h Thu Jun 25 17:44:14 2020 (r362617) @@ -307,38 +307,60 @@ struct name { \ (root)->rbh_root = NULL; \ } while (/*CONSTCOND*/ 0) -#define RB_BLACK 0 -#define RB_RED 1 #define RB_ENTRY(type) \ struct { \ struct type *rbe_left; /* left element */ \ struct type *rbe_right; /* right element */ \ struct type *rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ } #define RB_LEFT(elm, field) (elm)->field.rbe_left #define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ISRED(elm, field) ((elm) != NULL && RB_COLOR(elm, field) == RB_RED) + +/* + * With the expectation that any object of struct type has an + * address that is a multiple of 4, and that therefore the + * 2 least significant bits of a pointer to struct type are + * always zero, this implementation sets those bits to indicate + * that the left or right child of the tree node is "red". + */ +#define RB_UP(elm, field) (elm)->field.rbe_parent +#define RB_BITS(elm, field) *(__uintptr_t *)&RB_UP(elm, field) +#define RB_RED_L (__uintptr_t)1 +#define RB_RED_R (__uintptr_t)2 +#define RB_RED_MASK (__uintptr_t)3 +#define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) +#define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) +#define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) +#define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) +#define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ + (RB_BITS(elm, field) & ~RB_RED_MASK)) + +/* + * This header may appear in user code where 'bool' is not defined, + * so it defines its own boolean type to avoid breaking that code. + */ +#define RB_BOOL int +#define RB_TRUE 1 +#define RB_FALSE 0 + #define RB_ROOT(head) (head)->rbh_root #define RB_EMPTY(head) (RB_ROOT(head) == NULL) #define RB_SET_PARENT(dst, src, field) do { \ - RB_PARENT(dst, field) = src; \ + RB_BITS(dst, field) &= RB_RED_MASK; \ + RB_BITS(dst, field) |= (__uintptr_t)src; \ } while (/*CONSTCOND*/ 0) #define RB_SET(elm, parent, field) do { \ - RB_SET_PARENT(elm, parent, field); \ + RB_UP(elm, field) = parent; \ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ - RB_COLOR(elm, field) = RB_RED; \ } while (/*CONSTCOND*/ 0) -#define RB_SET_BLACKRED(black, red, field) do { \ - RB_COLOR(black, field) = RB_BLACK; \ - RB_COLOR(red, field) = RB_RED; \ -} while (/*CONSTCOND*/ 0) +#define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? RB_FALSE : \ + RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ + RB_RED_LEFT(RB_PARENT(elm, field), field) : \ + RB_RED_RIGHT(RB_PARENT(elm, field), field)) /* * Something to be invoked in a loop at the root of every modified subtree, @@ -442,106 +464,123 @@ struct { \ attr void \ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ { \ - struct type *parent, *gparent, *tmp; \ - while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (RB_ISRED(tmp, field)) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ + struct type *gparent, *parent; \ + while ((parent = RB_PARENT(elm, field)) != NULL) { \ + if (RB_LEFT(parent, field) == elm) \ + RB_FLIP_LEFT(parent, field); \ + else \ + RB_FLIP_RIGHT(parent, field); \ + if ((gparent = RB_PARENT(parent, field)) == NULL) \ + break; \ + if (RB_RED_LEFT(gparent, field) && \ + RB_RED_RIGHT(gparent, field)) { \ + RB_FLIP_LEFT(gparent, field); \ + RB_FLIP_RIGHT(gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (RB_RED_LEFT(gparent, field) && \ + parent == RB_LEFT(gparent, field)) { \ if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = parent; \ + RB_ROTATE_LEFT(head, parent, elm, field);\ + RB_FLIP_RIGHT(parent, field); \ + RB_FLIP_LEFT(elm, field); \ parent = elm; \ - elm = tmp; \ } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RB_LEFT(gparent, field); \ - if (RB_ISRED(tmp, field)) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ + RB_ROTATE_RIGHT(head, gparent, parent, field); \ + RB_FLIP_LEFT(gparent, field); \ + RB_FLIP_RIGHT(parent, field); \ + } else if (RB_RED_RIGHT(gparent, field) && \ + parent == RB_RIGHT(gparent, field)) { \ if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = parent; \ + RB_ROTATE_RIGHT(head, parent, elm, field);\ + RB_FLIP_LEFT(parent, field); \ + RB_FLIP_RIGHT(elm, field); \ parent = elm; \ - elm = tmp; \ } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_LEFT(head, gparent, tmp, field); \ + RB_ROTATE_LEFT(head, gparent, parent, field); \ + RB_FLIP_RIGHT(gparent, field); \ + RB_FLIP_LEFT(parent, field); \ } \ + break; \ } \ - 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) \ +name##_RB_REMOVE_COLOR(struct name *head, struct type *par) \ { \ - struct type *elm, *tmp; \ - elm = NULL; \ + struct type *gpr, *sib, *nec; \ + RB_BOOL left_elm, left_par, red_gpr; \ + left_par = (RB_LEFT(par, field) == NULL); \ do { \ - if (RB_LEFT(parent, field) == elm) { \ - tmp = RB_RIGHT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = RB_RIGHT(parent, field); \ + left_elm = left_par; \ + if (left_elm ? \ + !RB_RED_RIGHT(par, field) : \ + !RB_RED_LEFT(par, field)) { \ + gpr = RB_PARENT(par, field); \ + left_par = gpr != NULL && \ + RB_LEFT(gpr, field) == par; \ + red_gpr = gpr == NULL ? \ + RB_TRUE: RB_COLOR(par, field); \ + } \ + if (left_elm) { \ + if (RB_RED_RIGHT(par, field)) { \ + red_gpr = RB_TRUE; \ + RB_ROTATE_LEFT(head, par, gpr, field); \ + RB_FLIP_RIGHT(par, field); \ + RB_FLIP_LEFT(gpr, field); \ } \ - if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ - else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \ - struct type *oleft; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field); \ - RB_COLOR(oleft, field) = RB_BLACK; \ - tmp = oleft; \ + sib = RB_RIGHT(par, field); \ + if (RB_RED_RIGHT(sib, field)) { \ + if (RB_RED_LEFT(sib, field)) { \ + RB_FLIP_LEFT(sib, field); \ + RB_FLIP_RIGHT(par, field); \ + } \ + RB_FLIP_RIGHT(sib, field); \ + } else if (RB_RED_LEFT(sib, field)) { \ + RB_ROTATE_RIGHT(head, sib, nec, field); \ + RB_FLIP_LEFT(sib, field); \ + sib = nec; \ } else { \ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ + RB_FLIP_RIGHT(par, field); \ + par = gpr; \ continue; \ } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ - RB_COLOR(parent, field) = RB_BLACK; \ - RB_ROTATE_LEFT(head, parent, tmp, field); \ - elm = RB_ROOT(head); \ - break; \ + RB_ROTATE_LEFT(head, par, sib, field); \ + return; \ } else { \ - tmp = RB_LEFT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = RB_LEFT(parent, field); \ + if (RB_RED_LEFT(par, field)) { \ + red_gpr = RB_TRUE; \ + RB_ROTATE_RIGHT(head, par, gpr, field); \ + RB_FLIP_LEFT(par, field); \ + RB_FLIP_RIGHT(gpr, field); \ } \ - if (RB_ISRED(RB_LEFT(tmp, field), field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ - else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \ - struct type *oright; \ - RB_ROTATE_LEFT(head, tmp, oright, field); \ - RB_COLOR(oright, field) = RB_BLACK; \ - tmp = oright; \ - } else if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ + sib = RB_LEFT(par, field); \ + if (RB_RED_LEFT(sib, field)) { \ + if (RB_RED_RIGHT(sib, field)) { \ + RB_FLIP_RIGHT(sib, field); \ + RB_FLIP_LEFT(par, field); \ + } \ + RB_FLIP_LEFT(sib, field); \ + } else if (RB_RED_RIGHT(sib, field)) { \ + RB_ROTATE_LEFT(head, sib, nec, field); \ + RB_FLIP_RIGHT(sib, field); \ + sib = nec; \ + } else { \ + RB_FLIP_LEFT(par, field); \ + par = gpr; \ continue; \ } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ - RB_COLOR(parent, field) = RB_BLACK; \ - RB_ROTATE_RIGHT(head, parent, tmp, field); \ - elm = RB_ROOT(head); \ - break; \ + RB_ROTATE_RIGHT(head, par, sib, field); \ + return; \ } \ - } while (!RB_ISRED(elm, field) && parent != NULL); \ - RB_COLOR(elm, field) = RB_BLACK; \ + } while (!red_gpr); \ + if (gpr == NULL); \ + else if (left_par) \ + RB_FLIP_LEFT(gpr, field); \ + else \ + RB_FLIP_RIGHT(gpr, field); \ } #define RB_GENERATE_REMOVE(name, type, field, attr) \ @@ -549,12 +588,11 @@ attr struct type * \ name##_RB_REMOVE(struct name *head, struct type *elm) \ { \ struct type *child, *old, *parent, *right; \ - int color; \ + RB_BOOL red; \ \ old = elm; \ parent = RB_PARENT(elm, field); \ right = RB_RIGHT(elm, field); \ - color = RB_COLOR(elm, field); \ if (RB_LEFT(elm, field) == NULL) \ elm = child = right; \ else if (right == NULL) \ @@ -562,6 +600,9 @@ name##_RB_REMOVE(struct name *head, struct type *elm) else { \ if ((child = RB_LEFT(right, field)) == NULL) { \ child = RB_RIGHT(right, field); \ + red = RB_RED_RIGHT(old, field); \ + if (red) \ + RB_FLIP_RIGHT(old, field); \ RB_RIGHT(old, field) = child; \ parent = elm = right; \ } else { \ @@ -570,18 +611,27 @@ name##_RB_REMOVE(struct name *head, struct type *elm) while ((child = RB_LEFT(elm, field)) != NULL); \ child = RB_RIGHT(elm, field); \ parent = RB_PARENT(elm, field); \ + red = RB_RED_LEFT(parent, field); \ + if (red) \ + RB_FLIP_LEFT(parent, field); \ RB_LEFT(parent, field) = child; \ RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \ } \ RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ - color = RB_COLOR(elm, field); \ elm->field = old->field; \ } \ + if (elm == child) { \ + red = RB_COLOR(old, field); \ + if (!red); \ + else if (RB_LEFT(parent, field) == old) \ + RB_FLIP_LEFT(parent, field); \ + else \ + RB_FLIP_RIGHT(parent, field); \ + } \ RB_SWAP_CHILD(head, old, elm, field); \ - if (child != NULL) { \ + if (child != NULL) \ RB_SET_PARENT(child, parent, field); \ - RB_COLOR(child, field) = RB_BLACK; \ - } else if (color != RB_RED && parent != NULL) \ + else if (!red && parent != NULL) \ name##_RB_REMOVE_COLOR(head, parent); \ while (parent != NULL) { \ RB_AUGMENT(parent); \ @@ -610,13 +660,12 @@ name##_RB_INSERT(struct name *head, struct type *elm) return (tmp); \ } \ RB_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ - } else \ + if (parent == NULL) \ RB_ROOT(head) = elm; \ + else if (comp < 0) \ + RB_LEFT(parent, field) = elm; \ + else \ + RB_RIGHT(parent, field) = elm; \ name##_RB_INSERT_COLOR(head, elm); \ while (elm != NULL) { \ RB_AUGMENT(elm); \