Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 350 Lines • ▼ Show 20 Lines | _RB_BITSUP(dst, field) = (__uintptr_t)src | \ | ||||
(_RB_BITSUP(dst, field) & _RB_LR); \ | (_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) | ||||
/* | /* | ||||
hselasky: Are you sure RB_RED_LEFT is expanded properly in RB_COLOR using different C-code pre-processors? | |||||
Done Inline ActionsI have solved the problem, if any, by rewriting code elsewhere. dougm: I have solved the problem, if any, by rewriting code elsewhere. | |||||
* 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 | ||||
#define RB_AUGMENT(x) break | #define RB_AUGMENT(x) break | ||||
#endif | #endif | ||||
#define RB_UPDATE_AUGMENT(elm, field) do { \ | #define RB_UPDATE_AUGMENT(elm, field) do { \ | ||||
▲ Show 20 Lines • Show All 53 Lines • ▼ Show 20 Lines | #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ | ||||
RB_PROTOTYPE_REINSERT(name, type, attr); | RB_PROTOTYPE_REINSERT(name, type, attr); | ||||
#ifdef _RB_DIAGNOSTIC | #ifdef _RB_DIAGNOSTIC | ||||
#define RB_PROTOTYPE_RANK(name, type, attr) \ | #define RB_PROTOTYPE_RANK(name, type, attr) \ | ||||
attr int name##_RB_RANK(struct type *); | attr int name##_RB_RANK(struct type *); | ||||
#else | #else | ||||
#define RB_PROTOTYPE_RANK(name, type, attr) | #define RB_PROTOTYPE_RANK(name, type, attr) | ||||
#endif | #endif | ||||
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ | #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ | ||||
attr void name##_RB_INSERT_COLOR(struct name *, struct type *) | attr void name##_RB_INSERT_COLOR(struct name *, \ | ||||
struct type *, struct type *) | |||||
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ | #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ | ||||
attr void name##_RB_REMOVE_COLOR(struct name *, \ | attr void name##_RB_REMOVE_COLOR(struct name *, \ | ||||
struct type *, struct type *) | struct type *, struct type *) | ||||
#define RB_PROTOTYPE_REMOVE(name, type, attr) \ | #define RB_PROTOTYPE_REMOVE(name, type, attr) \ | ||||
attr struct type *name##_RB_REMOVE(struct name *, struct type *) | attr struct type *name##_RB_REMOVE(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_INSERT(name, type, attr) \ | #define RB_PROTOTYPE_INSERT(name, type, attr) \ | ||||
attr struct type *name##_RB_INSERT(struct name *, struct type *) | attr struct type *name##_RB_INSERT(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_FIND(name, type, attr) \ | #define RB_PROTOTYPE_FIND(name, type, attr) \ | ||||
▲ Show 20 Lines • Show All 52 Lines • ▼ Show 20 Lines | name##_RB_RANK(struct type *elm) \ | ||||
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 *parent, 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, *child_up, *gpar, *parent; \ | struct type *child, *child_up, *gpar; \ | ||||
__uintptr_t elmdir, sibdir; \ | __uintptr_t elmdir, sibdir; \ | ||||
\ | \ | ||||
gpar = _RB_UP(elm, field); \ | do { \ | ||||
while ((parent = gpar) != NULL) { \ | |||||
/* the rank of the tree rooted at elm grew */ \ | /* the rank of the tree rooted at elm grew */ \ | ||||
gpar = _RB_UP(parent, field); \ | gpar = _RB_UP(parent, field); \ | ||||
elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ | elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ | ||||
if (_RB_BITS(gpar) & elmdir) { \ | if (_RB_BITS(gpar) & elmdir) { \ | ||||
/* shorten the parent-elm edge to rebalance */ \ | /* shorten the parent-elm edge to rebalance */ \ | ||||
_RB_BITSUP(parent, field) ^= elmdir; \ | _RB_BITSUP(parent, field) ^= elmdir; \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
▲ Show 20 Lines • Show All 59 Lines • ▼ Show 20 Lines | do { \ | ||||
*/ \ | */ \ | ||||
RB_ROTATE(parent, child, sibdir, field); \ | RB_ROTATE(parent, child, sibdir, field); \ | ||||
_RB_UP(child, field) = 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; \ | ||||
} \ | } while ((parent = gpar) != NULL); \ | ||||
} | } | ||||
#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 | ||||
▲ Show 20 Lines • Show All 173 Lines • ▼ Show 20 Lines | if (comp < 0) \ | ||||
tmpp = &RB_LEFT(parent, field); \ | tmpp = &RB_LEFT(parent, field); \ | ||||
else if (comp > 0) \ | else if (comp > 0) \ | ||||
tmpp = &RB_RIGHT(parent, field); \ | tmpp = &RB_RIGHT(parent, field); \ | ||||
else \ | else \ | ||||
return (parent); \ | return (parent); \ | ||||
} \ | } \ | ||||
RB_SET(elm, parent, field); \ | RB_SET(elm, parent, field); \ | ||||
*tmpp = elm; \ | *tmpp = elm; \ | ||||
name##_RB_INSERT_COLOR(head, elm); \ | if (parent != NULL) \ | ||||
name##_RB_INSERT_COLOR(head, parent, elm); \ | |||||
RB_UPDATE_AUGMENT(elm, field); \ | RB_UPDATE_AUGMENT(elm, field); \ | ||||
return (NULL); \ | return (NULL); \ | ||||
} | } | ||||
#define RB_GENERATE_FIND(name, type, field, cmp, attr) \ | #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ | ||||
/* Finds the node with the same key as elm */ \ | /* Finds the node with the same key as elm */ \ | ||||
attr struct type * \ | attr struct type * \ | ||||
name##_RB_FIND(struct name *head, struct type *elm) \ | name##_RB_FIND(struct name *head, struct type *elm) \ | ||||
▲ Show 20 Lines • Show All 149 Lines • Show Last 20 Lines |
Are you sure RB_RED_LEFT is expanded properly in RB_COLOR using different C-code pre-processors?