Page MenuHomeFreeBSD
Files F148344439

D53047.1786387422.diff
No OneTemporary
Actions

Size
6 KB
Referenced Files
None
Subscribers
None

D53047.1786387422.diff
View Options

Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -535,16 +535,25 @@
* with a black non-null child and a red null child. The \
* balance criterion "the rank of any leaf is 1" precludes the \
* possibility of two red null children for the initial parent. \
- * So the first loop iteration cannot lead to accessing an \
- * uninitialized 'child', and a later iteration can only happen \
- * when a value has been assigned to 'child' in the previous \
- * one. \
*/ \
struct type *child, *child_up, *gpar; \
__uintptr_t elmdir, sibdir; \
\
- do { \
- /* 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_MOD_XOR(_RB_UP(parent, field), elmdir); \
+ return (NULL); \
+ } \
+ do { \
+ /* the other edge must change length */ \
+ _RB_MOD_XOR(_RB_UP(parent, field), elmdir ^ _RB_LR); \
+ if (gpar == NULL) \
+ return (NULL); \
+ child = elm; \
+ elm = parent; \
+ parent = gpar; \
gpar = _RB_UP(parent, field); \
elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
if (_RB_BITS(gpar) & elmdir) { \
@@ -552,82 +561,70 @@
_RB_MOD_XOR(_RB_UP(parent, field), elmdir); \
return (NULL); \
} \
- sibdir = elmdir ^ _RB_LR; \
- /* the other edge must change length */ \
- _RB_MOD_XOR(_RB_UP(parent, field), sibdir); \
- if ((_RB_BITS(gpar) & _RB_LR) == 0) { \
- /* both edges now short, retry from parent */ \
- child = elm; \
- elm = parent; \
- continue; \
- } \
- _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_MOD_XOR(_RB_UP(parent, field), \
- elmdir); \
- if (_RB_BITS(child_up) & elmdir) \
- _RB_MOD_XOR(_RB_UP(elm, field), \
- _RB_LR); \
- else \
- _RB_MOD_XOR(_RB_UP(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; \
- \
+ } while ((_RB_BITS(gpar) & _RB_LR) == 0); \
+ sibdir = elmdir ^ _RB_LR; \
+ _RB_UP(parent, field) = gpar = _RB_PTR(gpar); \
+ if (_RB_BITSUP(elm, field) & elmdir) { \
/* \
- * 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. \
+ * 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 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); \
- /* \
- * Elements rotated down have new, smaller subtrees, \
- * so update augmentation for them. \
+ * par par \
+ * / \ / \ \
+ * elm z / z \
+ * / \ child \
+ * / child / \ \
+ * / / \ elm \ \
+ * w / \ / \ y \
+ * x y w \ \
+ * x \
*/ \
- if (elm != child) \
- (void)RB_AUGMENT_CHECK(elm); \
- (void)RB_AUGMENT_CHECK(parent); \
- return (child); \
- } while ((parent = gpar) != NULL); \
- return (NULL); \
+ RB_ROTATE(elm, child, elmdir, field); \
+ child_up = _RB_UP(child, field); \
+ if (_RB_BITS(child_up) & sibdir) \
+ _RB_MOD_XOR(_RB_UP(parent, field), elmdir); \
+ if (_RB_BITS(child_up) & elmdir) \
+ _RB_MOD_XOR(_RB_UP(elm, field), _RB_LR); \
+ else \
+ _RB_MOD_XOR(_RB_UP(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); \
+ /* \
+ * Elements rotated down have new, smaller subtrees, \
+ * so update augmentation for them. \
+ */ \
+ if (elm != child) \
+ (void)RB_AUGMENT_CHECK(elm); \
+ (void)RB_AUGMENT_CHECK(parent); \
+ return (child); \
}
#ifndef RB_STRICT_HST

File Metadata

Mime Type
text/plain
Expires
Mon, Aug 10, 6:43 PM (8 h, 45 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
29387376
Default Alt Text
D53047.1786387422.diff (6 KB)

Event Timeline