Date: Sat, 1 Oct 2022 17:54:03 GMT From: Doug Moore <dougm@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org Subject: git: 72c99edafa49 - stable/13 - rb_tree: reduce duplication in balancing code Message-ID: <202210011754.291Hs3f9072446@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=72c99edafa4998652e1347d9bcf4e0989d775313 commit 72c99edafa4998652e1347d9bcf4e0989d775313 Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-09-08 04:46:19 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-10-01 17:53:06 +0000 rb_tree: reduce duplication in balancing code Change RB_INSERT_COLOR and RB_REMOVE_COLOR so that the blocks of code that are identical except for left and right being exchanged are made only one block with a variable to indicate left- or right-handedness. Rename RB macros so that those not intended for external use begin with an underscore. Add comments to the balancing code so that another might understand it. Reviewed by: alc, kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D36393 (cherry picked from commit d0354fa7b6b1931afe1806bd0bfe3ba83e2aeb00) --- sys/compat/linuxkpi/common/include/linux/rbtree.h | 12 +- sys/kern/subr_stats.c | 4 +- sys/sys/tree.h | 437 +++++++++++----------- 3 files changed, 223 insertions(+), 230 deletions(-) diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h index 1db9b1d4fa21..1f337d59545c 100644 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -41,8 +41,8 @@ struct rb_node { RB_ENTRY(rb_node) __entry; }; -#define rb_left __entry.rbe_left -#define rb_right __entry.rbe_right +#define rb_left __entry.rbe_link[_RB_L] +#define rb_right __entry.rbe_link[_RB_R] /* * We provide a false structure that has the same bit pattern as tree.h @@ -134,10 +134,10 @@ rb_replace_node(struct rb_node *victim, struct rb_node *new, RB_SWAP_CHILD((struct linux_root *)root, rb_parent(victim), victim, new, __entry); - if (victim->rb_left) - RB_SET_PARENT(victim->rb_left, new, __entry); - if (victim->rb_right) - RB_SET_PARENT(victim->rb_right, new, __entry); + if (RB_LEFT(victim, __entry)) + RB_SET_PARENT(RB_LEFT(victim, __entry), new, __entry); + if (RB_RIGHT(victim, __entry)) + RB_SET_PARENT(RB_RIGHT(victim, __entry), new, __entry); *new = *victim; } diff --git a/sys/kern/subr_stats.c b/sys/kern/subr_stats.c index 0984d2a21014..ff8ddbac4d81 100644 --- a/sys/kern/subr_stats.c +++ b/sys/kern/subr_stats.c @@ -3411,8 +3411,8 @@ stats_v1_vsd_tdgst_add(enum vsd_dtype vs_dtype, struct voistatdata_tdgst *tdgst, int rb_color = parent == NULL ? 0 : RB_LEFT(parent, rblnk) == rbctd64 ? - (RB_BITS(parent, rblnk) & RB_RED_L) != 0 : - (RB_BITS(parent, rblnk) & RB_RED_R) != 0; + (_RB_BITSUP(parent, rblnk) & _RB_L) != 0 : + (_RB_BITSUP(parent, rblnk) & _RB_R) != 0; printf(" RB ctd=%3d p=%3d l=%3d r=%3d c=%2d " "mu=%s\n", (int)ARB_SELFIDX(ctd64tree, rbctd64), diff --git a/sys/sys/tree.h b/sys/sys/tree.h index face3386087f..6a64498f6deb 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -56,9 +56,11 @@ * the same, and defines the rank of that node. The rank of the null node * is -1. * - * Different additional conditions define different sorts of balanced - * trees, including "red-black" and "AVL" trees. The set of conditions - * applied here are the "weak-AVL" conditions of Haeupler, Sen and Tarjan: + * Different additional conditions define different sorts of balanced trees, + * including "red-black" and "AVL" trees. The set of conditions applied here + * are the "weak-AVL" conditions of Haeupler, Sen and Tarjan presented in in + * "Rank Balanced Trees", ACM Transactions on Algorithms Volume 11 Issue 4 June + * 2015 Article No.: 30pp 1–26 https://doi.org/10.1145/2689412 (the HST paper): * - every rank-difference is 1 or 2. * - the rank of any leaf is 1. * @@ -318,14 +320,9 @@ struct name { \ #define RB_ENTRY(type) \ struct { \ - struct type *rbe_left; /* left element */ \ - struct type *rbe_right; /* right element */ \ - struct type *rbe_parent; /* parent element */ \ + struct type *rbe_link[3]; \ } -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right - /* * With the expectation that any object of struct type has an * address that is a multiple of 4, and that therefore the @@ -333,27 +330,29 @@ struct { \ * 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_FLIP_ALL(elm, field) (RB_BITS(elm, field) ^= RB_RED_MASK) -#define _RB_PARENT_ONLY(elm) (__typeof(elm)) \ - ((__uintptr_t)elm & ~RB_RED_MASK) -#define RB_PARENT(elm, field) _RB_PARENT_ONLY(RB_UP(elm, field)) +#define _RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir] +#define _RB_UP(elm, field) _RB_LINK(elm, 0, field) +#define _RB_L ((__uintptr_t)1) +#define _RB_R ((__uintptr_t)2) +#define _RB_LR ((__uintptr_t)3) +#define _RB_BITS(elm) (*(__uintptr_t *)&elm) +#define _RB_BITSUP(elm, field) _RB_BITS(_RB_UP(elm, field)) +#define _RB_PTR(elm) (__typeof(elm)) \ + ((__uintptr_t)elm & ~_RB_LR) + +#define RB_PARENT(elm, field) _RB_PTR(_RB_UP(elm, field)) +#define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L, field) +#define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R, field) #define RB_ROOT(head) (head)->rbh_root #define RB_EMPTY(head) (RB_ROOT(head) == NULL) #define RB_SET_PARENT(dst, src, field) do { \ - RB_BITS(dst, field) = (__uintptr_t)src | \ - (RB_BITS(dst, field) & RB_RED_MASK); \ + _RB_BITSUP(dst, field) = (__uintptr_t)src | \ + (_RB_BITSUP(dst, field) & _RB_LR); \ } while (/*CONSTCOND*/ 0) #define RB_SET(elm, parent, field) do { \ - RB_UP(elm, field) = parent; \ + _RB_UP(elm, field) = parent; \ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ } while (/*CONSTCOND*/ 0) @@ -382,31 +381,20 @@ struct { \ } while (/*CONSTCOND*/ 0) /* - * RB_ROTATE macros partially restructure the tree to improve - * balance. The ROTATE_RIGHT case is just a reflection of the - * ROTATE_LEFT case. Initially, tmp is a right child of elm. After - * rotation, elm is a left child of tmp, and the subtree that - * represented the items between them, which formerly hung to the left - * of tmp now hangs to the right of elm. The parent-child - * relationship between elm and its former parent is not changed; - * where this macro once updated those fields, that is now left to the - * caller of RB_ROTATE to clean up, so that a pair of rotations does - * not twice update the same pair of pointer fields with distinct - * values. + * RB_ROTATE macro partially restructures the tree to improve balance. In the + * case when dir is _RB_L, tmp is a right child of elm. After rotation, elm + * is a left child of tmp, and the subtree that represented the items between + * them, which formerly hung to the left of tmp now hangs to the right of elm. + * The parent-child relationship between elm and its former parent is not + * changed; where this macro once updated those fields, that is now left to the + * caller of RB_ROTATE to clean up, so that a pair of rotations does not twice + * update the same pair of pointer fields with distinct values. */ -#define RB_ROTATE_LEFT(elm, tmp, field) do { \ - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ - RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ - } \ - RB_LEFT(tmp, field) = (elm); \ - RB_SET_PARENT(elm, tmp, field); \ -} while (/*CONSTCOND*/ 0) - -#define RB_ROTATE_RIGHT(elm, tmp, field) do { \ - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ - RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ - } \ - RB_RIGHT(tmp, field) = (elm); \ +#define RB_ROTATE(elm, tmp, dir, field) do { \ + if ((_RB_LINK(elm, dir ^ _RB_LR, field) = \ + _RB_LINK(tmp, dir, field)) != NULL) \ + RB_SET_PARENT(_RB_LINK(tmp, dir, field), elm, field); \ + _RB_LINK(tmp, dir, field) = (elm); \ RB_SET_PARENT(elm, tmp, field); \ } while (/*CONSTCOND*/ 0) @@ -480,17 +468,18 @@ struct { \ attr int \ name##_RB_RANK(struct type *elm) \ { \ - struct type *left, *right; \ + struct type *left, *right, *up; \ int left_rank, right_rank; \ - __uintptr_t bits; \ \ if (elm == NULL) \ return (0); \ - bits = RB_BITS(elm, field); \ + up = _RB_UP(elm, field); \ left = RB_LEFT(elm, field); \ - left_rank = ((bits & RB_RED_L) ? 2 : 1) + name##_RB_RANK(left); \ + left_rank = ((_RB_BITS(up) & _RB_L) ? 2 : 1) + \ + name##_RB_RANK(left); \ right = RB_RIGHT(elm, field); \ - right_rank = ((bits & RB_RED_R) ? 2 : 1) + name##_RB_RANK(right); \ + right_rank = ((_RB_BITS(up) & _RB_R) ? 2 : 1) + \ + name##_RB_RANK(right); \ if (left_rank != right_rank || \ (left_rank == 2 && left == NULL && right == NULL)) \ return (-1); \ @@ -514,72 +503,82 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ * uninitialized 'child', and a later iteration can only happen \ * when a value has been assigned to 'child' in the previous \ * one. \ - */ \ - struct type *child, *gpar = RB_UP(elm, field), *parent; \ - __uintptr_t red; \ + */ \ + struct type *child, *child_up, *gpar, *parent; \ + __uintptr_t elmdir, sibdir; \ \ + gpar = _RB_UP(elm, field); \ while ((parent = gpar) != NULL) { \ - red = RB_BITS(parent, field); \ - gpar = RB_UP(parent, field); \ - if (RB_LEFT(parent, field) == elm) { \ - if (red & RB_RED_L) { \ - RB_FLIP_LEFT(parent, field); \ - return; \ - } \ - RB_FLIP_RIGHT(parent, field); \ - if ((red & RB_RED_MASK) == 0) { \ - child = elm; \ - elm = parent; \ - continue; \ - } \ - red = RB_BITS(elm, field); \ - if (red & RB_RED_R) \ - child = elm; \ - else { \ - /* coverity[uninit_use] */ \ - RB_ROTATE_LEFT(elm, child, field); \ - red = RB_BITS(child, field); \ - if (red & RB_RED_R) \ - RB_FLIP_LEFT(parent, field); \ - if (red & RB_RED_L) \ - RB_FLIP_ALL(elm, field); \ - else \ - RB_FLIP_LEFT(elm, field); \ - if ((red & RB_RED_MASK) == 0) \ - elm = child; \ - } \ - RB_ROTATE_RIGHT(parent, child, field); \ - } else { \ - if (red & RB_RED_R) { \ - RB_FLIP_RIGHT(parent, field); \ - return; \ - } \ - RB_FLIP_LEFT(parent, field); \ - if ((red & RB_RED_MASK) == 0) { \ - child = elm; \ - elm = parent; \ - continue; \ - } \ - red = RB_BITS(elm, field); \ - if (red & RB_RED_L) \ - child = elm; \ - else { \ - /* coverity[uninit_use] */ \ - RB_ROTATE_RIGHT(elm, child, field); \ - red = RB_BITS(child, field); \ - if (red & RB_RED_L) \ - RB_FLIP_RIGHT(parent, field); \ - if (red & RB_RED_R) \ - RB_FLIP_ALL(elm, field); \ - else \ - RB_FLIP_RIGHT(elm, field); \ - if ((red & RB_RED_MASK) == 0) \ - elm = child; \ - } \ - RB_ROTATE_LEFT(parent, child, field); \ + /* the rank of the tree rooted at elm grew */ \ + gpar = _RB_UP(parent, field); \ + elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ + if (_RB_BITS(gpar) & elmdir) { \ + /* shorten the parent-elm edge to rebalance */ \ + _RB_BITSUP(parent, field) ^= elmdir; \ + return; \ + } \ + sibdir = elmdir ^ _RB_LR; \ + /* the other edge must change length */ \ + _RB_BITSUP(parent, field) ^= sibdir; \ + if ((_RB_BITS(gpar) & _RB_LR) == 0) { \ + /* both edges now short, retry from parent */ \ + child = elm; \ + elm = parent; \ + continue; \ } \ - gpar = _RB_PARENT_ONLY(gpar); \ - RB_UP(child, field) = gpar; \ + _RB_UP(parent, field) = gpar = _RB_PTR(gpar); \ + if (_RB_BITSUP(elm, field) & elmdir) { \ + /* \ + * Exactly one of the edges descending from elm \ + * is long. The long one is in the same \ + * direction as the edge from parent to elm, \ + * so change that by rotation. The edge from \ + * parent to z was shortened above. Shorten \ + * the long edge down from elm, and adjust \ + * other edge lengths based on the downward \ + * edges from 'child'. \ + * \ + * par par \ + * / \ / \ \ + * elm z / z \ + * / \ child \ + * / child / \ \ + * / / \ elm \ \ + * w / \ / \ y \ + * x y w \ \ + * x \ + */ \ + RB_ROTATE(elm, child, elmdir, field); \ + child_up = _RB_UP(child, field); \ + if (_RB_BITS(child_up) & sibdir) \ + _RB_BITSUP(parent, field) ^= elmdir; \ + if (_RB_BITS(child_up) & elmdir) \ + _RB_BITSUP(elm, field) ^= _RB_LR; \ + else \ + _RB_BITSUP(elm, field) ^= elmdir; \ + /* if child is a leaf, don't augment elm, \ + * since it is restored to be a leaf again. */ \ + if ((_RB_BITS(child_up) & _RB_LR) == 0) \ + elm = child; \ + } else \ + child = elm; \ + \ + /* \ + * The long edge descending from 'child' points back \ + * in the direction of 'parent'. Rotate to make \ + * 'parent' a child of 'child', then make both edges \ + * of 'child' short to rebalance. \ + * \ + * par child \ + * / \ / \ \ + * / z x par \ + * child / \ \ + * / \ / z \ + * x \ y \ + * y \ + */ \ + RB_ROTATE(parent, child, sibdir, field); \ + _RB_UP(child, field) = gpar; \ RB_SWAP_CHILD(head, gpar, parent, child, field); \ if (elm != child) \ RB_AUGMENT(elm); \ @@ -604,120 +603,112 @@ attr void \ name##_RB_REMOVE_COLOR(struct name *head, \ struct type *parent, struct type *elm) \ { \ - struct type *gpar, *sib; \ - __uintptr_t red; \ + struct type *gpar, *sib, *up; \ + __uintptr_t elmdir, sibdir; \ \ - if (RB_LEFT(parent, field) == elm && \ - RB_RIGHT(parent, field) == elm) { \ - RB_BITS(parent, field) &= ~RB_RED_MASK; \ + if (RB_RIGHT(parent, field) == elm && \ + RB_LEFT(parent, field) == elm) { \ + /* Deleting a leaf that is an only-child creates a \ + * rank-2 leaf. Demote that leaf. */ \ + _RB_UP(parent, field) = _RB_PTR(_RB_UP(parent, field)); \ elm = parent; \ - parent = RB_PARENT(elm, field); \ - if (parent == NULL) \ + if ((parent = _RB_UP(elm, field)) == NULL) \ return; \ } \ do { \ - red = RB_BITS(parent, field); \ - gpar = RB_UP(parent, field); \ - if (RB_LEFT(parent, field) == elm) { \ - if (~red & RB_RED_L) { \ - RB_FLIP_LEFT(parent, field); \ - return; \ - } \ - if ((~red & RB_RED_MASK) == 0) { \ - RB_FLIP_RIGHT(parent, field); \ - elm = parent; \ - continue; \ - } \ - sib = RB_RIGHT(parent, field); \ - red = RB_BITS(sib, field); \ - switch (red & RB_RED_MASK) { \ - case RB_RED_MASK: \ - RB_FLIP_ALL(sib, field); \ - elm = parent; \ - continue; \ - case RB_RED_R: \ - elm = RB_LEFT(sib, field); \ - RB_ROTATE_RIGHT(sib, elm, field); \ - red = RB_BITS(elm, field); \ - if (red & RB_RED_L) \ - RB_FLIP_ALL(parent, field); \ - else \ - RB_FLIP_LEFT(parent, field); \ - if (red & RB_RED_R) \ - RB_FLIP_ALL(sib, field); \ - else \ - RB_FLIP_RIGHT(sib, field); \ - RB_BITS(elm, field) |= RB_RED_MASK; \ - break; \ - case RB_RED_L: \ - if (RB_STRICT_HST && elm != NULL) { \ - RB_FLIP_RIGHT(parent, field); \ - RB_FLIP_ALL(sib, field); \ - elm = sib; \ - break; \ - } \ - RB_FLIP_LEFT(parent, field); \ - /* FALLTHROUGH */ \ - default: \ - RB_FLIP_RIGHT(sib, field); \ - elm = sib; \ - break; \ - } \ - RB_ROTATE_LEFT(parent, elm, field); \ + /* the rank of the tree rooted at elm shrank */ \ + gpar = _RB_UP(parent, field); \ + elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ + _RB_BITS(gpar) ^= elmdir; \ + if (_RB_BITS(gpar) & elmdir) { \ + /* lengthen the parent-elm edge to rebalance */ \ + _RB_UP(parent, field) = gpar; \ + return; \ + } \ + if (_RB_BITS(gpar) & _RB_LR) { \ + /* shorten other edge, retry from parent */ \ + _RB_BITS(gpar) ^= _RB_LR; \ + _RB_UP(parent, field) = gpar; \ + gpar = _RB_PTR(gpar); \ + continue; \ + } \ + sibdir = elmdir ^ _RB_LR; \ + sib = _RB_LINK(parent, sibdir, field); \ + up = _RB_UP(sib, field); \ + _RB_BITS(up) ^= _RB_LR; \ + if ((_RB_BITS(up) & _RB_LR) == 0) { \ + /* shorten edges descending from sib, retry */ \ + _RB_UP(sib, field) = up; \ + continue; \ + } \ + if ((_RB_BITS(up) & sibdir) == 0) { \ + /* \ + * The edge descending from 'sib' away from \ + * 'parent' is long. The short edge descending \ + * from 'sib' toward 'parent' points to 'elm*' \ + * Rotate to make 'sib' a child of 'elm*' \ + * then adjust the lengths of the edges \ + * descending from 'sib' and 'elm*'. \ + * \ + * par par \ + * / \ / \ \ + * / sib elm \ \ + * / / \ elm* \ + * elm elm* \ / \ \ + * / \ \ / \ \ + * / \ z / \ \ + * x y x sib \ + * / \ \ + * / z \ + * y \ + */ \ + elm = _RB_LINK(sib, elmdir, field); \ + /* elm is a 1-child. First rotate at elm. */ \ + RB_ROTATE(sib, elm, sibdir, field); \ + up = _RB_UP(elm, field); \ + _RB_BITSUP(parent, field) ^= \ + (_RB_BITS(up) & elmdir) ? _RB_LR : elmdir; \ + _RB_BITSUP(sib, field) ^= \ + (_RB_BITS(up) & sibdir) ? _RB_LR : sibdir; \ + _RB_BITSUP(elm, field) |= _RB_LR; \ } else { \ - if (~red & RB_RED_R) { \ - RB_FLIP_RIGHT(parent, field); \ - return; \ - } \ - if ((~red & RB_RED_MASK) == 0) { \ - RB_FLIP_LEFT(parent, field); \ - elm = parent; \ - continue; \ - } \ - sib = RB_LEFT(parent, field); \ - red = RB_BITS(sib, field); \ - switch (red & RB_RED_MASK) { \ - case RB_RED_MASK: \ - RB_FLIP_ALL(sib, field); \ - elm = parent; \ - continue; \ - case RB_RED_L: \ - elm = RB_RIGHT(sib, field); \ - RB_ROTATE_LEFT(sib, elm, field); \ - red = RB_BITS(elm, field); \ - if (red & RB_RED_R) \ - RB_FLIP_ALL(parent, field); \ - else \ - RB_FLIP_RIGHT(parent, field); \ - if (red & RB_RED_L) \ - RB_FLIP_ALL(sib, field); \ - else \ - RB_FLIP_LEFT(sib, field); \ - RB_BITS(elm, field) |= RB_RED_MASK; \ - break; \ - case RB_RED_R: \ - if (RB_STRICT_HST && elm != NULL) { \ - RB_FLIP_LEFT(parent, field); \ - RB_FLIP_ALL(sib, field); \ - elm = sib; \ - break; \ - } \ - RB_FLIP_RIGHT(parent, field); \ - /* FALLTHROUGH */ \ - default: \ - RB_FLIP_LEFT(sib, field); \ - elm = sib; \ - break; \ - } \ - RB_ROTATE_RIGHT(parent, elm, field); \ + if ((_RB_BITS(up) & elmdir) == 0 && \ + RB_STRICT_HST && elm != NULL) { \ + /* if parent does not become a leaf, \ + do not demote parent yet. */ \ + _RB_BITSUP(parent, field) ^= sibdir; \ + _RB_BITSUP(sib, field) ^= _RB_LR; \ + } else if ((_RB_BITS(up) & elmdir) == 0) { \ + /* demote parent. */ \ + _RB_BITSUP(parent, field) ^= elmdir; \ + _RB_BITSUP(sib, field) ^= sibdir; \ + } else \ + _RB_BITSUP(sib, field) ^= sibdir; \ + elm = sib; \ } \ - gpar = _RB_PARENT_ONLY(gpar); \ + \ + /* \ + * The edge descending from 'elm' away from 'parent' \ + * is short. Rotate to make 'parent' a child of 'elm', \ + * then lengthen the short edges descending from \ + * 'parent' and 'elm' to rebalance. \ + * \ + * par elm \ + * / \ / \ \ + * e \ / \ \ + * elm / \ \ + * / \ par s \ + * / \ / \ \ + * / \ e \ \ + * x s x \ + */ \ + RB_ROTATE(parent, elm, elmdir, field); \ RB_SET_PARENT(elm, gpar, field); \ RB_SWAP_CHILD(head, gpar, parent, elm, field); \ if (sib != elm) \ RB_AUGMENT(sib); \ break; \ - } while ((parent = _RB_PARENT_ONLY(gpar)) != NULL); \ + } while (elm = parent, (parent = gpar) != NULL); \ } #define RB_GENERATE_REMOVE(name, type, field, attr) \ @@ -728,10 +719,10 @@ name##_RB_REMOVE(struct name *head, struct type *out) \ \ child = RB_LEFT(out, field); \ in = RB_RIGHT(out, field); \ - opar = RB_UP(out, field); \ + opar = _RB_UP(out, field); \ if (in == NULL || child == NULL) { \ in = child = in == NULL ? child : in; \ - parent = opar = _RB_PARENT_ONLY(opar); \ + parent = opar = _RB_PTR(opar); \ } else { \ parent = in; \ while (RB_LEFT(in, field)) \ @@ -745,14 +736,16 @@ name##_RB_REMOVE(struct name *head, struct type *out) \ parent = RB_PARENT(in, field); \ RB_LEFT(parent, field) = child; \ } \ - RB_UP(in, field) = opar; \ - opar = _RB_PARENT_ONLY(opar); \ + _RB_UP(in, field) = opar; \ + opar = _RB_PTR(opar); \ } \ RB_SWAP_CHILD(head, opar, out, in, field); \ if (child != NULL) \ - RB_UP(child, field) = parent; \ + _RB_UP(child, field) = parent; \ if (parent != NULL) { \ name##_RB_REMOVE_COLOR(head, parent, child); \ + /* if rotation has made 'parent' the root of the same \ + * subtree as before, don't re-augment it. */ \ if (parent == in && RB_LEFT(parent, field) == NULL) \ parent = RB_PARENT(parent, field); \ RB_UPDATE_AUGMENT(parent, field); \
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202210011754.291Hs3f9072446>