From owner-svn-src-all@freebsd.org Tue Jun 9 22:55:19 2020 Return-Path: Delivered-To: svn-src-all@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 0D62233FAF6; Tue, 9 Jun 2020 22:55:19 +0000 (UTC) (envelope-from mjguzik@gmail.com) Received: from mail-wm1-x344.google.com (mail-wm1-x344.google.com [IPv6:2a00:1450:4864:20::344]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1O1" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 49hQSQ5HTcz3grw; Tue, 9 Jun 2020 22:55:18 +0000 (UTC) (envelope-from mjguzik@gmail.com) Received: by mail-wm1-x344.google.com with SMTP id y20so105662wmi.2; Tue, 09 Jun 2020 15:55:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=cOjT879WTizIscWWu/SjMAVd02cbXn8keo3wnncJZXc=; b=hhuzOX+HKAIXkGzytXyGUsY+yhVt8rkvNkFPhSCQONit680zZy/4gfXKLVcpiPUGG5 2Nwnpep33eFqJ/wtw2p5bnD6xPvkDlns5hkVe9VRQtaYgmqkPlT87/mg/Akd1t678Ut1 26EkdGqdBoExuDN3cJsRIQCeWgbpYx7xjSfwNy84Mc3RAxPk+Ags3xKbbp9exYQ9tT24 oxYo8Rs///Q2hItEnt6gXG3GBPWIlH9riR3V1on8ho7o6qdKTihfLVSkDCXAieOeQEFv mKndzAL7Ky1muvkDMxVhyvzATE/XeENFfhRgbyofGUXbFVY7EMq4tMtBNAcGp0Lido1T pU6w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=cOjT879WTizIscWWu/SjMAVd02cbXn8keo3wnncJZXc=; b=ssNcYGudeSQoYICZ9SAZv/SJ5TxdtMPLy3g32EnGM+4ZTauJowx/PZiVIXUrB6LEsP 9KviZvPJmitzJy3p/+Ty54YOHZvZfbqjVH6QrLbIuYrpHHuGZczx5MKObcpAZ8a1WJKT sSH2un5S1hbp3BVnuKityOSlRWkelauIvudvrr1W43xG3GkqSYRgqIpz9ZvDZRX9FiXf wpO6Un3TfCMBgggCfgTTdkSWbiHBCNVkIxtQ3WB4xG1CW4Py3cd7e2VRnOxXJ9PK4i3l XsBSv0bYSCUyeCdBLXl+compv4YTy2aYr60a6kPlj2RahErQfV0TKoTrXLS7RsbzSQvb WcaQ== X-Gm-Message-State: AOAM530N7n/USGcfeXX+tN1xmTDzf/ZaXUp9d7c8DGWkfZMgXqfA9Tcn M2njBFhVNxGEuIGD++m81u+DvdGOd/50rzuSdyiKGsvB X-Google-Smtp-Source: ABdhPJyNymUkkKgJxq/ZvPYUWvU7k/RdQmO8YNTaFWjMf3EZzsBTdREoj6cDgx9yW4FZW+GFAtByx6tcY8PzWclZvqU= X-Received: by 2002:a1c:7f87:: with SMTP id a129mr310005wmd.10.1591743315532; Tue, 09 Jun 2020 15:55:15 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:adf:fd8f:0:0:0:0:0 with HTTP; Tue, 9 Jun 2020 15:55:14 -0700 (PDT) In-Reply-To: <202006092019.059KJCLG039099@repo.freebsd.org> References: <202006092019.059KJCLG039099@repo.freebsd.org> From: Mateusz Guzik Date: Wed, 10 Jun 2020 00:55:14 +0200 Message-ID: Subject: Re: svn commit: r361984 - in head/sys: compat/linuxkpi/common/include/linux sys To: Doug Moore Cc: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Content-Type: text/plain; charset="UTF-8" X-Rspamd-Queue-Id: 49hQSQ5HTcz3grw X-Spamd-Bar: ---- Authentication-Results: mx1.freebsd.org; none X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:15169, ipnet:2a00:1450::/32, country:US] X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.33 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 09 Jun 2020 22:55:19 -0000 This broke lint kernels as they define DIAGNOSTIC and fail in kern/subr_stat.c: /usr/src/sys/kern/subr_stats.c:3384:9: error: implicit declaration of function 'RB_COLOR' is invalid in C99 [-Werror,-Wimplicit-function-declaration] RB_COLOR(rbctd64, rblnk), ^ /usr/src/sys/kern/subr_stats.c:3384:27: error: use of undeclared identifier 'rblnk' RB_COLOR(rbctd64, rblnk), On 6/9/20, Doug Moore wrote: > Author: dougm > Date: Tue Jun 9 20:19:11 2020 > New Revision: 361984 > URL: https://svnweb.freebsd.org/changeset/base/361984 > > Log: > To reduce the size of an rb_node, drop the color field. Set the least > significant bit in the pointer to the node from its parent to indicate > that the node is red. Have the tree rotation macros leave the > old-parent/new-child node red and the new-parent/old-child node black. > > This change makes RB_LEFT and RB_RIGHT no longer assignable, and > RB_COLOR no longer defined. Any code that modifies the tree or > examines a node color would have to be modified after this change. > > Reviewed by: markj > Tested by: pho > Differential Revision: https://reviews.freebsd.org/D25105 > > Modified: > head/sys/compat/linuxkpi/common/include/linux/rbtree.h > head/sys/sys/tree.h > > Modified: head/sys/compat/linuxkpi/common/include/linux/rbtree.h > ============================================================================== > --- head/sys/compat/linuxkpi/common/include/linux/rbtree.h Tue Jun 9 > 19:16:49 2020 (r361983) > +++ head/sys/compat/linuxkpi/common/include/linux/rbtree.h Tue Jun 9 > 20:19:11 2020 (r361984) > @@ -57,11 +57,7 @@ RB_HEAD(linux_root, rb_node); > RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp); > > #define rb_parent(r) RB_PARENT(r, __entry) > -#define rb_color(r) RB_COLOR(r, __entry) > -#define rb_is_red(r) (rb_color(r) == RB_RED) > -#define rb_is_black(r) (rb_color(r) == RB_BLACK) > #define rb_set_parent(r, p) rb_parent((r)) = (p) > -#define rb_set_color(r, c) rb_color((r)) = (c) > #define rb_entry(ptr, type, member) container_of(ptr, type, member) > > #define RB_EMPTY_ROOT(root) RB_EMPTY((struct linux_root *)root) > @@ -82,7 +78,6 @@ rb_link_node(struct rb_node *node, struct rb_node *par > struct rb_node **rb_link) > { > rb_set_parent(node, parent); > - rb_set_color(node, RB_RED); > node->__entry.rbe_left = node->__entry.rbe_right = NULL; > *rb_link = node; > } > > Modified: head/sys/sys/tree.h > ============================================================================== > --- head/sys/sys/tree.h Tue Jun 9 19:16:49 2020 (r361983) > +++ head/sys/sys/tree.h Tue Jun 9 20:19:11 2020 (r361984) > @@ -307,35 +307,32 @@ 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_LF(elm, field) (elm)->field.rbe_left > +#define RB_RT(elm, field) (elm)->field.rbe_right > +#define RB_FLIP(elm) (*(__uintptr_t *)&(elm) ^= 1) > +#define RB_FLIP_LF(elm, field) RB_FLIP(RB_LF(elm, field)) > +#define RB_FLIP_RT(elm, field) RB_FLIP(RB_RT(elm, field)) > +#define RB_ISRED(elm) ((*(__uintptr_t *)&(elm) & 1) != 0) > +#define RB_RED_LF(elm, field) RB_ISRED(RB_LF(elm, field)) > +#define RB_RED_RT(elm, field) RB_ISRED(RB_RT(elm, field)) > +#define RB_PTR(elm, field) ((__typeof(elm->field.rbe_parent)) \ > + ((__uintptr_t)(elm) & ~(__uintptr_t)1)) > +#define RB_LEFT(elm, field) RB_PTR(RB_LF(elm, field), field) > +#define RB_RIGHT(elm, field) RB_PTR(RB_RT(elm, field), field) > #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) > #define RB_ROOT(head) (head)->rbh_root > #define RB_EMPTY(head) (RB_ROOT(head) == NULL) > +#define RB_BOOL int > +#define RB_TRUE 1 > +#define RB_FALSE 0 > > -#define RB_SET(elm, parent, field) do { \ > - RB_PARENT(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) > - > /* > * Something to be invoked in a loop at the root of every modified > subtree, > * from the bottom up to the root, to update augmented node data. > @@ -344,37 +341,42 @@ struct { \ > #define RB_AUGMENT(x) break > #endif > > +/* > + * Fix pointers to a parent, and from a parent, as part of rotation. > + */ > +#define RB_ROTATE_PARENT(head, elm, tmp, field) do { \ > + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) == NULL) \ > + RB_ROOT(head) = (tmp); \ > + else if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ > + RB_LF(RB_PARENT(elm, field), field) = (tmp); \ > + else \ > + RB_RT(RB_PARENT(elm, field), field) = (tmp); \ > + RB_PARENT(elm, field) = (tmp); \ > +} while (/*CONSTCOND*/ 0) > + > +/* > + * Rotation makes the descending node red, and the ascending > + * node not-red. > + */ > #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ > (tmp) = RB_RIGHT(elm, field); \ > - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ > + if ((RB_RT(elm, field) = RB_LF(tmp, field)) != NULL) { \ > RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ > } \ > - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ > - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ > - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ > - else \ > - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ > - } else \ > - (head)->rbh_root = (tmp); \ > - RB_LEFT(tmp, field) = (elm); \ > - RB_PARENT(elm, field) = (tmp); \ > + RB_ROTATE_PARENT(head, elm, tmp, field); \ > + RB_LF(tmp, field) = (elm); \ > + RB_FLIP_LF(tmp, field); \ > RB_AUGMENT(elm); \ > } while (/*CONSTCOND*/ 0) > > #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ > (tmp) = RB_LEFT(elm, field); \ > - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ > + if ((RB_LF(elm, field) = RB_RT(tmp, field)) != NULL) { \ > RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ > } \ > - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ > - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ > - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ > - else \ > - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ > - } else \ > - (head)->rbh_root = (tmp); \ > - RB_RIGHT(tmp, field) = (elm); \ > - RB_PARENT(elm, field) = (tmp); \ > + RB_ROTATE_PARENT(head, elm, tmp, field); \ > + RB_RT(tmp, field) = (elm); \ > + RB_FLIP_RT(tmp, field); \ > RB_AUGMENT(elm); \ > } while (/*CONSTCOND*/ 0) > > @@ -439,110 +441,105 @@ 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_LF(parent, field); \ > + else \ > + RB_FLIP_RT(parent, field); \ > + if ((gparent = RB_PARENT(parent, field)) == NULL) \ > + break; \ > + if (RB_RED_LF(gparent, field) && \ > + RB_RED_RT(gparent, field)) { \ > + RB_FLIP_LF(gparent, field); \ > + RB_FLIP_RT(gparent, field); \ > + elm = gparent; \ > + continue; \ > + } \ > + if (RB_RED_LF(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);\ > 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); \ > + } else if (RB_RED_RT(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);\ > parent = elm; \ > - elm = tmp; \ > } \ > - RB_SET_BLACKRED(parent, gparent, field); \ > - RB_ROTATE_LEFT(head, gparent, tmp, field); \ > + RB_ROTATE_LEFT(head, gparent, 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 *elm) \ > { \ > - struct type *elm, *tmp; \ > - elm = NULL; \ > + struct type *par, *sib, *tmp; \ > + RB_BOOL go_left, left_child, red_par; \ > + left_child = (RB_LEFT(elm, 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); \ > + go_left = left_child; \ > + if (go_left ? \ > + !RB_RED_RT(elm, field) : \ > + !RB_RED_LF(elm, field)) { \ > + par = RB_PARENT(elm, field); \ > + left_child = par != NULL && \ > + RB_LEFT(par, field) == elm; \ > + red_par = left_child ? RB_RED_LF(par, field) : \ > + par == NULL ? RB_TRUE : \ > + RB_RED_RT(par, field); \ > + } \ > + if (go_left) { \ > + if (RB_RED_RT(elm, field)) { \ > + red_par = RB_TRUE; \ > + RB_ROTATE_LEFT(head, elm, par, field); \ > } \ > - if (RB_ISRED(RB_LEFT(tmp, field), field)) { \ > - struct type *oleft; \ > - oleft = RB_LEFT(tmp, field); \ > - RB_COLOR(oleft, field) = RB_BLACK; \ > - RB_COLOR(tmp, field) = RB_RED; \ > - RB_ROTATE_RIGHT(head, tmp, oleft, field); \ > - tmp = RB_RIGHT(parent, field); \ > - } else if (!RB_ISRED(RB_RIGHT(tmp, field), field)) { \ > - RB_COLOR(tmp, field) = RB_RED; \ > - elm = parent; \ > - parent = RB_PARENT(elm, field); \ > + sib = RB_RIGHT(elm, field); \ > + if (RB_RED_LF(sib, field)) { \ > + RB_ROTATE_RIGHT(head, sib, tmp, field); \ > + sib = tmp; \ > + } else if (!RB_RED_RT(sib, field)) { \ > + RB_FLIP_RT(elm, field); \ > + elm = par; \ > continue; \ > } \ > - if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ > - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ > - 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); \ > + if (RB_RED_RT(sib, field)) \ > + RB_FLIP_RT(sib, field); \ > + RB_ROTATE_LEFT(head, elm, sib, field); \ > + RB_FLIP_LF(sib, field); \ > break; \ > } 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_LF(elm, field)) { \ > + red_par = RB_TRUE; \ > + RB_ROTATE_RIGHT(head, elm, par, field); \ > } \ > - if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \ > - struct type *oright; \ > - oright = RB_RIGHT(tmp, field); \ > - RB_COLOR(oright, field) = RB_BLACK; \ > - RB_COLOR(tmp, field) = RB_RED; \ > - RB_ROTATE_LEFT(head, tmp, oright, field); \ > - tmp = RB_LEFT(parent, field); \ > - } 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(elm, field); \ > + if (RB_RED_RT(sib, field)) { \ > + RB_ROTATE_LEFT(head, sib, tmp, field); \ > + sib = tmp; \ > + } else if (!RB_RED_LF(sib, field)) { \ > + RB_FLIP_LF(elm, field); \ > + elm = par; \ > continue; \ > } \ > - if (RB_ISRED(RB_LEFT(tmp, field), field)) \ > - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ > - 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); \ > + if (RB_RED_LF(sib, field)) \ > + RB_FLIP_LF(sib, field); \ > + RB_ROTATE_RIGHT(head, elm, sib, field); \ > + RB_FLIP_RT(sib, field); \ > break; \ > } \ > - } while (!RB_ISRED(elm, field) && parent != NULL); \ > - RB_COLOR(elm, field) = RB_BLACK; \ > + } while (!red_par); \ > + if (par != NULL && red_par) { \ > + if (left_child) \ > + RB_FLIP_LF(par, field); \ > + else \ > + RB_FLIP_RT(par, field); \ > + } \ > } > > #define RB_GENERATE_REMOVE(name, type, field, attr) \ > @@ -550,12 +547,11 @@ attr struct type * \ > name##_RB_REMOVE(struct name *head, struct type *elm) \ > { \ > struct type *child, *old, *parent, *parent_old, *right; \ > - int color; \ > + RB_BOOL old_red, red; \ > \ > old = elm; \ > parent_old = 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) \ > @@ -563,7 +559,8 @@ name##_RB_REMOVE(struct name *head, struct type *elm) > else { \ > if ((child = RB_LEFT(right, field)) == NULL) { \ > child = RB_RIGHT(right, field); \ > - RB_RIGHT(old, field) = child; \ > + red = RB_RED_RT(old, field); \ > + RB_RT(old, field) = child; \ > parent = elm = right; \ > } else { \ > do \ > @@ -571,23 +568,31 @@ 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); \ > - RB_LEFT(parent, field) = child; \ > + red = RB_RED_LF(parent, field); \ > + RB_LF(parent, field) = child; \ > RB_PARENT(RB_RIGHT(old, field), field) = elm; \ > } \ > RB_PARENT(RB_LEFT(old, field), field) = elm; \ > - color = RB_COLOR(elm, field); \ > elm->field = old->field; \ > } \ > - if (parent_old == NULL) \ > + if (parent_old == NULL) { \ > RB_ROOT(head) = elm; \ > - else if (RB_LEFT(parent_old, field) == old) \ > - RB_LEFT(parent_old, field) = elm; \ > - else \ > - RB_RIGHT(parent_old, field) = elm; \ > - if (child != NULL) { \ > + old_red = RB_FALSE; \ > + } else if (RB_LEFT(parent_old, field) == old) { \ > + old_red = RB_RED_LF(parent_old, field); \ > + RB_LF(parent_old, field) = elm; \ > + if (old_red && parent != parent_old) \ > + RB_FLIP_LF(parent_old, field); \ > + } else { \ > + old_red = RB_RED_RT(parent_old, field); \ > + RB_RT(parent_old, field) = elm; \ > + if (old_red && parent != parent_old) \ > + RB_FLIP_RT(parent_old, field); \ > + } \ > + if (child != NULL) \ > RB_PARENT(child, field) = parent; \ > - RB_COLOR(child, field) = RB_BLACK; \ > - } else if (color != RB_RED && parent != NULL) \ > + else if (parent != NULL && \ > + (parent != parent_old ? !red : !old_red)) \ > name##_RB_REMOVE_COLOR(head, parent); \ > while (parent != NULL) { \ > RB_AUGMENT(parent); \ > @@ -615,14 +620,14 @@ name##_RB_INSERT(struct name *head, struct type > *elm) > else \ > 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 \ > + RB_PARENT(elm, field) = parent; \ > + RB_LF(elm, field) = RB_RT(elm, field) = NULL; \ > + if (parent == NULL) \ > RB_ROOT(head) = elm; \ > + else if (comp < 0) \ > + RB_LF(parent, field) = elm; \ > + else \ > + RB_RT(parent, field) = elm; \ > name##_RB_INSERT_COLOR(head, elm); \ > while (elm != NULL) { \ > RB_AUGMENT(elm); \ > -- Mateusz Guzik