Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 50 Lines • ▼ Show 20 Lines | |||||
* amortized cost for a sequence of m accesses to a splay tree is O(lg n); | * amortized cost for a sequence of m accesses to a splay tree is O(lg n); | ||||
* | * | ||||
* A rank-balanced tree is a binary search tree with an integer | * A rank-balanced tree is a binary search tree with an integer | ||||
* rank-difference as an attribute of each pointer from parent to child. | * rank-difference as an attribute of each pointer from parent to child. | ||||
* The sum of the rank-differences on any path from a node down to null is | * The sum of the rank-differences on any path from a node down to null is | ||||
* the same, and defines the rank of that node. The rank of the null node | * the same, and defines the rank of that node. The rank of the null node | ||||
* is -1. | * is -1. | ||||
* | * | ||||
* Different additional conditions define different sorts of balanced | * Different additional conditions define different sorts of balanced trees, | ||||
* trees, including "red-black" and "AVL" trees. The set of conditions | * including "red-black" and "AVL" trees. The set of conditions applied here | ||||
* applied here are the "weak-AVL" conditions of Haeupler, Sen and Tarjan: | * 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. | * - every rank-difference is 1 or 2. | ||||
* - the rank of any leaf is 1. | * - the rank of any leaf is 1. | ||||
* | * | ||||
* For historical reasons, rank differences that are even are associated | * For historical reasons, rank differences that are even are associated | ||||
* with the color red (Rank-Even-Difference), and the child that a red edge | * with the color red (Rank-Even-Difference), and the child that a red edge | ||||
* points to is called a red child. | * points to is called a red child. | ||||
* | * | ||||
* Every operation on a rank-balanced tree is bounded as O(lg n). | * Every operation on a rank-balanced tree is bounded as O(lg n). | ||||
▲ Show 20 Lines • Show All 243 Lines • ▼ Show 20 Lines | #define RB_INITIALIZER(root) \ | ||||
{ NULL } | { NULL } | ||||
#define RB_INIT(root) do { \ | #define RB_INIT(root) do { \ | ||||
(root)->rbh_root = NULL; \ | (root)->rbh_root = NULL; \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_ENTRY(type) \ | #define RB_ENTRY(type) \ | ||||
struct { \ | struct { \ | ||||
struct type *rbe_left; /* left element */ \ | struct type *rbe_link[3]; \ | ||||
struct type *rbe_right; /* right element */ \ | |||||
struct type *rbe_parent; /* parent element */ \ | |||||
} | } | ||||
#define RB_LEFT(elm, field) (elm)->field.rbe_left | |||||
#define RB_RIGHT(elm, field) (elm)->field.rbe_right | |||||
/* | /* | ||||
hselasky: Maybe this piece of repeated code should have its own macro for readability:
```
#define… | |||||
* With the expectation that any object of struct type has an | * With the expectation that any object of struct type has an | ||||
* address that is a multiple of 4, and that therefore the | * address that is a multiple of 4, and that therefore the | ||||
* 2 least significant bits of a pointer to struct type are | * 2 least significant bits of a pointer to struct type are | ||||
* always zero, this implementation sets those bits to indicate | * always zero, this implementation sets those bits to indicate | ||||
* that the left or right child of the tree node is "red". | * that the left or right child of the tree node is "red". | ||||
*/ | */ | ||||
#define RB_UP(elm, field) (elm)->field.rbe_parent | #define _RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir] | ||||
#define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field)) | #define _RB_UP(elm, field) _RB_LINK(elm, 0, field) | ||||
#define RB_RED_L ((__uintptr_t)1) | #define _RB_L ((__uintptr_t)1) | ||||
#define RB_RED_R ((__uintptr_t)2) | #define _RB_R ((__uintptr_t)2) | ||||
#define RB_RED_MASK ((__uintptr_t)3) | #define _RB_LR ((__uintptr_t)3) | ||||
#define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) | #define _RB_BITS(elm) (*(__uintptr_t *)&elm) | ||||
#define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) | #define _RB_BITSUP(elm, field) _RB_BITS(_RB_UP(elm, field)) | ||||
#define RB_FLIP_ALL(elm, field) (RB_BITS(elm, field) ^= RB_RED_MASK) | #define _RB_PTR(elm) (__typeof(elm)) \ | ||||
#define _RB_PARENT_ONLY(elm) (__typeof(elm)) \ | ((__uintptr_t)elm & ~_RB_LR) | ||||
((__uintptr_t)elm & ~RB_RED_MASK) | |||||
#define RB_PARENT(elm, field) _RB_PARENT_ONLY(RB_UP(elm, field)) | #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_ROOT(head) (head)->rbh_root | ||||
#define RB_EMPTY(head) (RB_ROOT(head) == NULL) | #define RB_EMPTY(head) (RB_ROOT(head) == NULL) | ||||
#define RB_SET_PARENT(dst, src, field) do { \ | #define RB_SET_PARENT(dst, src, field) do { \ | ||||
RB_BITS(dst, field) = (__uintptr_t)src | \ | _RB_BITSUP(dst, field) = (__uintptr_t)src | \ | ||||
(RB_BITS(dst, field) & RB_RED_MASK); \ | (_RB_BITSUP(dst, field) & _RB_LR); \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_SET(elm, parent, field) do { \ | #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; \ | RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
/* | /* | ||||
* Something to be invoked in a loop at the root of every modified subtree, | * 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. | * from the bottom up to the root, to update augmented node data. | ||||
*/ | */ | ||||
#ifndef RB_AUGMENT | #ifndef RB_AUGMENT | ||||
Show All 12 Lines | if (par == NULL) \ | ||||
RB_ROOT(head) = (in); \ | RB_ROOT(head) = (in); \ | ||||
else if ((out) == RB_LEFT(par, field)) \ | else if ((out) == RB_LEFT(par, field)) \ | ||||
RB_LEFT(par, field) = (in); \ | RB_LEFT(par, field) = (in); \ | ||||
else \ | else \ | ||||
RB_RIGHT(par, field) = (in); \ | RB_RIGHT(par, field) = (in); \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
/* | /* | ||||
* RB_ROTATE macros partially restructure the tree to improve | * RB_ROTATE macro partially restructures the tree to improve balance. In the | ||||
* balance. The ROTATE_RIGHT case is just a reflection of the | * case when dir is _RB_L, tmp is a right child of elm. After rotation, elm | ||||
* ROTATE_LEFT case. Initially, tmp is a right child of elm. After | * is a left child of tmp, and the subtree that represented the items between | ||||
* rotation, elm is a left child of tmp, and the subtree that | * them, which formerly hung to the left of tmp now hangs to the right of elm. | ||||
* represented the items between them, which formerly hung to the left | * The parent-child relationship between elm and its former parent is not | ||||
* of tmp now hangs to the right of elm. The parent-child | * changed; where this macro once updated those fields, that is now left to the | ||||
* relationship between elm and its former parent is not changed; | * caller of RB_ROTATE to clean up, so that a pair of rotations does not twice | ||||
* where this macro once updated those fields, that is now left to the | * update the same pair of pointer fields with distinct values. | ||||
* 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 { \ | #define RB_ROTATE(elm, tmp, dir, field) do { \ | ||||
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ | if ((_RB_LINK(elm, dir ^ _RB_LR, field) = \ | ||||
RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ | _RB_LINK(tmp, dir, field)) != NULL) \ | ||||
} \ | RB_SET_PARENT(_RB_LINK(tmp, dir, field), elm, field); \ | ||||
RB_LEFT(tmp, field) = (elm); \ | _RB_LINK(tmp, dir, field) = (elm); \ | ||||
RB_SET_PARENT(elm, tmp, field); \ | RB_SET_PARENT(elm, tmp, field); \ | ||||
} while (/*CONSTCOND*/ 0) | } 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); \ | |||||
RB_SET_PARENT(elm, tmp, field); \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
#if defined(_KERNEL) && defined(DIAGNOSTIC) && !defined(_RB_DIAGNOSTIC) | #if defined(_KERNEL) && defined(DIAGNOSTIC) && !defined(_RB_DIAGNOSTIC) | ||||
#define _RB_DIAGNOSTIC 1 | #define _RB_DIAGNOSTIC 1 | ||||
#endif | #endif | ||||
/* Generates prototypes and inline functions */ | /* Generates prototypes and inline functions */ | ||||
#define RB_PROTOTYPE(name, type, field, cmp) \ | #define RB_PROTOTYPE(name, type, field, cmp) \ | ||||
RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) | RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) | ||||
#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ | #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ | ||||
▲ Show 20 Lines • Show All 58 Lines • ▼ Show 20 Lines | #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ | ||||
RB_GENERATE_MINMAX(name, type, field, attr) \ | RB_GENERATE_MINMAX(name, type, field, attr) \ | ||||
RB_GENERATE_REINSERT(name, type, field, cmp, attr) | RB_GENERATE_REINSERT(name, type, field, cmp, attr) | ||||
#ifdef _RB_DIAGNOSTIC | #ifdef _RB_DIAGNOSTIC | ||||
#define RB_GENERATE_RANK(name, type, field, attr) \ | #define RB_GENERATE_RANK(name, type, field, attr) \ | ||||
attr int \ | attr int \ | ||||
name##_RB_RANK(struct type *elm) \ | name##_RB_RANK(struct type *elm) \ | ||||
{ \ | { \ | ||||
struct type *left, *right; \ | struct type *left, *right, *up; \ | ||||
int left_rank, right_rank; \ | int left_rank, right_rank; \ | ||||
__uintptr_t bits; \ | |||||
\ | \ | ||||
if (elm == NULL) \ | if (elm == NULL) \ | ||||
return (0); \ | return (0); \ | ||||
bits = RB_BITS(elm, field); \ | up = _RB_UP(elm, field); \ | ||||
left = RB_LEFT(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 = 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 || \ | if (left_rank != right_rank || \ | ||||
(left_rank == 2 && left == NULL && right == NULL)) \ | (left_rank == 2 && left == NULL && right == NULL)) \ | ||||
return (-1); \ | return (-1); \ | ||||
return (left_rank); \ | return (left_rank); \ | ||||
} | } | ||||
#else | #else | ||||
#define RB_GENERATE_RANK(name, type, field, attr) | #define RB_GENERATE_RANK(name, type, field, attr) | ||||
#endif | #endif | ||||
#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ | #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ | ||||
attr void \ | attr void \ | ||||
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | ||||
{ \ | { \ | ||||
/* \ | /* \ | ||||
* Initially, elm is a leaf. Either its parent was previously \ | * Initially, elm is a leaf. Either its parent was previously \ | ||||
* a leaf, with two black null children, or an interior node \ | * a leaf, with two black null children, or an interior node \ | ||||
* with a black non-null child and a red null child. The \ | * with a black non-null child and a red null child. The \ | ||||
* balance criterion "the rank of any leaf is 1" precludes the \ | * balance criterion "the rank of any leaf is 1" precludes the \ | ||||
* possibility of two red null children for the initial parent. \ | * possibility of two red null children for the initial parent. \ | ||||
* So the first loop iteration cannot lead to accessing an \ | * So the first loop iteration cannot lead to accessing an \ | ||||
* uninitialized 'child', and a later iteration can only happen \ | * uninitialized 'child', and a later iteration can only happen \ | ||||
* when a value has been assigned to 'child' in the previous \ | * when a value has been assigned to 'child' in the previous \ | ||||
* one. \ | * one. \ | ||||
*/ \ | */ \ | ||||
struct type *child, *gpar = RB_UP(elm, field), *parent; \ | struct type *child, *child_up, *gpar, *parent; \ | ||||
__uintptr_t red; \ | __uintptr_t elmdir, sibdir; \ | ||||
\ | \ | ||||
gpar = _RB_UP(elm, field); \ | |||||
while ((parent = gpar) != NULL) { \ | while ((parent = gpar) != NULL) { \ | ||||
red = RB_BITS(parent, field); \ | /* the rank of the tree rooted at elm grew */ \ | ||||
gpar = RB_UP(parent, field); \ | gpar = _RB_UP(parent, field); \ | ||||
if (RB_LEFT(parent, field) == elm) { \ | elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ | ||||
if (red & RB_RED_L) { \ | if (_RB_BITS(gpar) & elmdir) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | /* shorten the parent-elm edge to rebalance */ \ | ||||
_RB_BITSUP(parent, field) ^= elmdir; \ | |||||
return; \ | return; \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(parent, field); \ | sibdir = elmdir ^ _RB_LR; \ | ||||
if ((red & RB_RED_MASK) == 0) { \ | /* 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; \ | child = elm; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
red = RB_BITS(elm, field); \ | _RB_UP(parent, field) = gpar = _RB_PTR(gpar); \ | ||||
if (red & RB_RED_R) \ | if (_RB_BITSUP(elm, field) & elmdir) { \ | ||||
child = elm; \ | /* \ | ||||
else { \ | * Exactly one of the edges descending from elm \ | ||||
/* coverity[uninit_use] */ \ | * is long. The long one is in the same \ | ||||
RB_ROTATE_LEFT(elm, child, field); \ | * direction as the edge from parent to elm, \ | ||||
red = RB_BITS(child, field); \ | * so change that by rotation. The edge from \ | ||||
if (red & RB_RED_R) \ | * parent to z was shortened above. Shorten \ | ||||
RB_FLIP_LEFT(parent, field); \ | * the long edge down from elm, and adjust \ | ||||
if (red & RB_RED_L) \ | * other edge lengths based on the downward \ | ||||
Not Done Inline ActionsSince this has proven to be useless, as in it doesn't quiet Coverity, I would argue for deleting it. The above block comment addresses this issue in great detail. alc: Since this has proven to be useless, as in it doesn't quiet Coverity, I would argue for… | |||||
RB_FLIP_ALL(elm, field); \ | * 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 \ | else \ | ||||
RB_FLIP_LEFT(elm, field); \ | _RB_BITSUP(elm, field) ^= elmdir; \ | ||||
if ((red & RB_RED_MASK) == 0) \ | /* 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; \ | elm = child; \ | ||||
} \ | } else \ | ||||
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; \ | child = elm; \ | ||||
elm = parent; \ | \ | ||||
continue; \ | /* \ | ||||
} \ | * The long edge descending from 'child' points back \ | ||||
red = RB_BITS(elm, field); \ | * in the direction of 'parent'. Rotate to make \ | ||||
if (red & RB_RED_L) \ | * 'parent' a child of 'child', then make both edges \ | ||||
child = elm; \ | * of 'child' short to rebalance. \ | ||||
else { \ | * \ | ||||
/* coverity[uninit_use] */ \ | * par child \ | ||||
RB_ROTATE_RIGHT(elm, child, field); \ | * / \ / \ \ | ||||
red = RB_BITS(child, field); \ | * / z x par \ | ||||
if (red & RB_RED_L) \ | * child / \ \ | ||||
RB_FLIP_RIGHT(parent, field); \ | * / \ / z \ | ||||
if (red & RB_RED_R) \ | * x \ y \ | ||||
RB_FLIP_ALL(elm, field); \ | * y \ | ||||
else \ | */ \ | ||||
RB_FLIP_RIGHT(elm, field); \ | RB_ROTATE(parent, child, sibdir, field); \ | ||||
if ((red & RB_RED_MASK) == 0) \ | _RB_UP(child, field) = gpar; \ | ||||
elm = child; \ | |||||
} \ | |||||
RB_ROTATE_LEFT(parent, child, field); \ | |||||
} \ | |||||
gpar = _RB_PARENT_ONLY(gpar); \ | |||||
RB_UP(child, field) = gpar; \ | |||||
RB_SWAP_CHILD(head, gpar, parent, child, field); \ | RB_SWAP_CHILD(head, gpar, parent, child, field); \ | ||||
if (elm != child) \ | if (elm != child) \ | ||||
RB_AUGMENT(elm); \ | RB_AUGMENT(elm); \ | ||||
RB_AUGMENT(parent); \ | RB_AUGMENT(parent); \ | ||||
break; \ | break; \ | ||||
} \ | } \ | ||||
} | } | ||||
#ifndef RB_STRICT_HST | #ifndef RB_STRICT_HST | ||||
/* | /* | ||||
* In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has | * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has | ||||
* 'parent' with one higher rank, and then reduces its rank if 'parent' has | * 'parent' with one higher rank, and then reduces its rank if 'parent' has | ||||
* become a leaf. This implementation always has the parent in its new position | * become a leaf. This implementation always has the parent in its new position | ||||
* with lower rank, to avoid the leaf check. Define RB_STRICT_HST to 1 to get | * with lower rank, to avoid the leaf check. Define RB_STRICT_HST to 1 to get | ||||
* the behavior that HST describes. | * the behavior that HST describes. | ||||
*/ | */ | ||||
#define RB_STRICT_HST 0 | #define RB_STRICT_HST 0 | ||||
#endif | #endif | ||||
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ | #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ | ||||
attr void \ | attr void \ | ||||
name##_RB_REMOVE_COLOR(struct name *head, \ | name##_RB_REMOVE_COLOR(struct name *head, \ | ||||
struct type *parent, struct type *elm) \ | struct type *parent, struct type *elm) \ | ||||
{ \ | { \ | ||||
struct type *gpar, *sib; \ | struct type *gpar, *sib, *up; \ | ||||
__uintptr_t red; \ | __uintptr_t elmdir, sibdir; \ | ||||
\ | \ | ||||
if (RB_LEFT(parent, field) == elm && \ | if (RB_RIGHT(parent, field) == elm && \ | ||||
RB_RIGHT(parent, field) == elm) { \ | RB_LEFT(parent, field) == elm) { \ | ||||
RB_BITS(parent, field) &= ~RB_RED_MASK; \ | /* 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; \ | elm = parent; \ | ||||
parent = RB_PARENT(elm, field); \ | if ((parent = _RB_UP(elm, field)) == NULL) \ | ||||
if (parent == NULL) \ | |||||
return; \ | return; \ | ||||
} \ | } \ | ||||
do { \ | do { \ | ||||
red = RB_BITS(parent, field); \ | /* the rank of the tree rooted at elm shrank */ \ | ||||
gpar = RB_UP(parent, field); \ | gpar = _RB_UP(parent, field); \ | ||||
if (RB_LEFT(parent, field) == elm) { \ | elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ | ||||
if (~red & RB_RED_L) { \ | _RB_BITS(gpar) ^= elmdir; \ | ||||
RB_FLIP_LEFT(parent, field); \ | if (_RB_BITS(gpar) & elmdir) { \ | ||||
/* lengthen the parent-elm edge to rebalance */ \ | |||||
_RB_UP(parent, field) = gpar; \ | |||||
return; \ | return; \ | ||||
} \ | } \ | ||||
if ((~red & RB_RED_MASK) == 0) { \ | if (_RB_BITS(gpar) & _RB_LR) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | /* shorten other edge, retry from parent */ \ | ||||
elm = parent; \ | _RB_BITS(gpar) ^= _RB_LR; \ | ||||
_RB_UP(parent, field) = gpar; \ | |||||
gpar = _RB_PTR(gpar); \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
sib = RB_RIGHT(parent, field); \ | sibdir = elmdir ^ _RB_LR; \ | ||||
red = RB_BITS(sib, field); \ | sib = _RB_LINK(parent, sibdir, field); \ | ||||
switch (red & RB_RED_MASK) { \ | up = _RB_UP(sib, field); \ | ||||
case RB_RED_MASK: \ | _RB_BITS(up) ^= _RB_LR; \ | ||||
RB_FLIP_ALL(sib, field); \ | if ((_RB_BITS(up) & _RB_LR) == 0) { \ | ||||
elm = parent; \ | /* shorten edges descending from sib, retry */ \ | ||||
_RB_UP(sib, field) = up; \ | |||||
continue; \ | 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); \ | if ((_RB_BITS(up) & sibdir) == 0) { \ | ||||
/* FALLTHROUGH */ \ | /* \ | ||||
default: \ | * The edge descending from 'sib' away from \ | ||||
RB_FLIP_RIGHT(sib, field); \ | * 'parent' is long. The short edge descending \ | ||||
elm = sib; \ | * from 'sib' toward 'parent' points to 'elm*' \ | ||||
break; \ | * Rotate to make 'sib' a child of 'elm*' \ | ||||
} \ | * then adjust the lengths of the edges \ | ||||
RB_ROTATE_LEFT(parent, elm, field); \ | * 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 { \ | } else { \ | ||||
if (~red & RB_RED_R) { \ | if ((_RB_BITS(up) & elmdir) == 0 && \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_STRICT_HST && elm != NULL) { \ | ||||
return; \ | /* if parent does not become a leaf, \ | ||||
} \ | do not demote parent yet. */ \ | ||||
if ((~red & RB_RED_MASK) == 0) { \ | _RB_BITSUP(parent, field) ^= sibdir; \ | ||||
RB_FLIP_LEFT(parent, field); \ | _RB_BITSUP(sib, field) ^= _RB_LR; \ | ||||
elm = parent; \ | } else if ((_RB_BITS(up) & elmdir) == 0) { \ | ||||
continue; \ | /* demote parent. */ \ | ||||
} \ | _RB_BITSUP(parent, field) ^= elmdir; \ | ||||
sib = RB_LEFT(parent, field); \ | _RB_BITSUP(sib, field) ^= sibdir; \ | ||||
red = RB_BITS(sib, field); \ | } else \ | ||||
switch (red & RB_RED_MASK) { \ | _RB_BITSUP(sib, field) ^= sibdir; \ | ||||
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; \ | elm = sib; \ | ||||
break; \ | |||||
} \ | } \ | ||||
RB_FLIP_RIGHT(parent, field); \ | \ | ||||
/* FALLTHROUGH */ \ | /* \ | ||||
default: \ | * The edge descending from 'elm' away from 'parent' \ | ||||
RB_FLIP_LEFT(sib, field); \ | * is short. Rotate to make 'parent' a child of 'elm', \ | ||||
elm = sib; \ | * then lengthen the short edges descending from \ | ||||
break; \ | * 'parent' and 'elm' to rebalance. \ | ||||
} \ | * \ | ||||
RB_ROTATE_RIGHT(parent, elm, field); \ | * par elm \ | ||||
} \ | * / \ / \ \ | ||||
gpar = _RB_PARENT_ONLY(gpar); \ | * e \ / \ \ | ||||
* elm / \ \ | |||||
* / \ par s \ | |||||
* / \ / \ \ | |||||
* / \ e \ \ | |||||
* x s x \ | |||||
*/ \ | |||||
RB_ROTATE(parent, elm, elmdir, field); \ | |||||
RB_SET_PARENT(elm, gpar, field); \ | RB_SET_PARENT(elm, gpar, field); \ | ||||
RB_SWAP_CHILD(head, gpar, parent, elm, field); \ | RB_SWAP_CHILD(head, gpar, parent, elm, field); \ | ||||
if (sib != elm) \ | if (sib != elm) \ | ||||
RB_AUGMENT(sib); \ | RB_AUGMENT(sib); \ | ||||
break; \ | break; \ | ||||
} while ((parent = _RB_PARENT_ONLY(gpar)) != NULL); \ | } while (elm = parent, (parent = gpar) != NULL); \ | ||||
} | } | ||||
#define RB_GENERATE_REMOVE(name, type, field, attr) \ | #define RB_GENERATE_REMOVE(name, type, field, attr) \ | ||||
attr struct type * \ | attr struct type * \ | ||||
name##_RB_REMOVE(struct name *head, struct type *out) \ | name##_RB_REMOVE(struct name *head, struct type *out) \ | ||||
{ \ | { \ | ||||
struct type *child, *in, *opar, *parent; \ | struct type *child, *in, *opar, *parent; \ | ||||
\ | \ | ||||
child = RB_LEFT(out, field); \ | child = RB_LEFT(out, field); \ | ||||
in = RB_RIGHT(out, field); \ | in = RB_RIGHT(out, field); \ | ||||
opar = RB_UP(out, field); \ | opar = _RB_UP(out, field); \ | ||||
if (in == NULL || child == NULL) { \ | if (in == NULL || child == NULL) { \ | ||||
in = child = in == NULL ? child : in; \ | in = child = in == NULL ? child : in; \ | ||||
parent = opar = _RB_PARENT_ONLY(opar); \ | parent = opar = _RB_PTR(opar); \ | ||||
} else { \ | } else { \ | ||||
parent = in; \ | parent = in; \ | ||||
while (RB_LEFT(in, field)) \ | while (RB_LEFT(in, field)) \ | ||||
in = RB_LEFT(in, field); \ | in = RB_LEFT(in, field); \ | ||||
RB_SET_PARENT(child, in, field); \ | RB_SET_PARENT(child, in, field); \ | ||||
RB_LEFT(in, field) = child; \ | RB_LEFT(in, field) = child; \ | ||||
child = RB_RIGHT(in, field); \ | child = RB_RIGHT(in, field); \ | ||||
if (parent != in) { \ | if (parent != in) { \ | ||||
RB_SET_PARENT(parent, in, field); \ | RB_SET_PARENT(parent, in, field); \ | ||||
RB_RIGHT(in, field) = parent; \ | RB_RIGHT(in, field) = parent; \ | ||||
parent = RB_PARENT(in, field); \ | parent = RB_PARENT(in, field); \ | ||||
RB_LEFT(parent, field) = child; \ | RB_LEFT(parent, field) = child; \ | ||||
} \ | } \ | ||||
RB_UP(in, field) = opar; \ | _RB_UP(in, field) = opar; \ | ||||
opar = _RB_PARENT_ONLY(opar); \ | opar = _RB_PTR(opar); \ | ||||
} \ | } \ | ||||
RB_SWAP_CHILD(head, opar, out, in, field); \ | RB_SWAP_CHILD(head, opar, out, in, field); \ | ||||
if (child != NULL) \ | if (child != NULL) \ | ||||
RB_UP(child, field) = parent; \ | _RB_UP(child, field) = parent; \ | ||||
if (parent != NULL) { \ | if (parent != NULL) { \ | ||||
name##_RB_REMOVE_COLOR(head, parent, child); \ | 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) \ | if (parent == in && RB_LEFT(parent, field) == NULL) \ | ||||
parent = RB_PARENT(parent, field); \ | parent = RB_PARENT(parent, field); \ | ||||
RB_UPDATE_AUGMENT(parent, field); \ | RB_UPDATE_AUGMENT(parent, field); \ | ||||
} \ | } \ | ||||
return (out); \ | return (out); \ | ||||
} | } | ||||
#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ | #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ | ||||
▲ Show 20 Lines • Show All 178 Lines • Show Last 20 Lines |
Maybe this piece of repeated code should have its own macro for readability: