Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 335 Lines • ▼ Show 20 Lines | |||||
#define RB_UP(elm, field) (elm)->field.rbe_parent | #define RB_UP(elm, field) (elm)->field.rbe_parent | ||||
#define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field)) | #define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field)) | ||||
#define RB_RED_L ((__uintptr_t)1) | #define RB_RED_L ((__uintptr_t)1) | ||||
#define RB_RED_R ((__uintptr_t)2) | #define RB_RED_R ((__uintptr_t)2) | ||||
#define RB_RED_MASK ((__uintptr_t)3) | #define RB_RED_MASK ((__uintptr_t)3) | ||||
#define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) | #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_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_FLIP_ALL(elm, field) (RB_BITS(elm, field) ^= RB_RED_MASK) | ||||
#define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) | |||||
#define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) | |||||
#define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ | #define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ | ||||
(RB_BITS(elm, field) & ~RB_RED_MASK)) | (RB_BITS(elm, field) & ~RB_RED_MASK)) | ||||
#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_BITS(dst, field) = (__uintptr_t)src | \ | ||||
(RB_BITS(dst, field) & RB_RED_MASK); \ | (RB_BITS(dst, field) & RB_RED_MASK); \ | ||||
} 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) | ||||
#define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) | |||||
#define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) | |||||
#define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? 0 : \ | #define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? 0 : \ | ||||
RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ | RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ | ||||
RB_RED_LEFT(RB_PARENT(elm, field), field) : \ | RB_RED_LEFT(RB_PARENT(elm, field), field) : \ | ||||
RB_RED_RIGHT(RB_PARENT(elm, field), field)) | RB_RED_RIGHT(RB_PARENT(elm, field), field)) | ||||
#undef RB_RED_LEFT | |||||
hselasky: Are you sure RB_RED_LEFT is expanded properly in RB_COLOR using different C-code pre-processors? | |||||
dougmAuthorUnsubmitted 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. | |||||
#undef RB_RED_RIGHT | |||||
/* | /* | ||||
* 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 { \ | ||||
__typeof(elm) rb_update_tmp = (elm); \ | __typeof(elm) rb_update_tmp = (elm); \ | ||||
do { \ | do { \ | ||||
RB_AUGMENT(rb_update_tmp); \ | RB_AUGMENT(rb_update_tmp); \ | ||||
} while ((rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL); \ | } while ((rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL); \ | ||||
} while (0) | } while (0) | ||||
#define RB_SWAP_CHILD(head, out, in, field) do { \ | #define RB_SWAP_CHILD(head, parent, out, in, field) do { \ | ||||
if (RB_PARENT(out, field) == NULL) \ | if ((parent) == NULL) \ | ||||
RB_ROOT(head) = (in); \ | RB_ROOT(head) = (in); \ | ||||
else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ | else if ((out) == RB_LEFT(parent, field)) \ | ||||
RB_LEFT(RB_PARENT(out, field), field) = (in); \ | RB_LEFT(parent, field) = (in); \ | ||||
else \ | else \ | ||||
RB_RIGHT(RB_PARENT(out, field), field) = (in); \ | RB_RIGHT(parent, field) = (in); \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | #define RB_ROTATE_LEFT(elm, tmp, field) do { \ | ||||
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ | if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ | ||||
RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ | RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ | ||||
} \ | } \ | ||||
RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ | |||||
RB_SWAP_CHILD(head, elm, tmp, field); \ | |||||
RB_LEFT(tmp, field) = (elm); \ | RB_LEFT(tmp, field) = (elm); \ | ||||
RB_SET_PARENT(elm, tmp, field); \ | RB_SET_PARENT(elm, tmp, field); \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ | #define RB_ROTATE_RIGHT(elm, tmp, field) do { \ | ||||
if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ | if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ | ||||
RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ | RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ | ||||
} \ | } \ | ||||
RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ | |||||
RB_SWAP_CHILD(head, elm, tmp, field); \ | |||||
RB_RIGHT(tmp, field) = (elm); \ | RB_RIGHT(tmp, field) = (elm); \ | ||||
RB_SET_PARENT(elm, tmp, field); \ | RB_SET_PARENT(elm, tmp, field); \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
/* 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) \ | ||||
RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) | RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) | ||||
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ | #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ | ||||
RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ | RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ | ||||
RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ | RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ | ||||
RB_PROTOTYPE_INSERT(name, type, attr); \ | RB_PROTOTYPE_INSERT(name, type, attr); \ | ||||
RB_PROTOTYPE_REMOVE(name, type, attr); \ | RB_PROTOTYPE_REMOVE(name, type, attr); \ | ||||
RB_PROTOTYPE_FIND(name, type, attr); \ | RB_PROTOTYPE_FIND(name, type, attr); \ | ||||
RB_PROTOTYPE_NFIND(name, type, attr); \ | RB_PROTOTYPE_NFIND(name, type, attr); \ | ||||
RB_PROTOTYPE_NEXT(name, type, attr); \ | RB_PROTOTYPE_NEXT(name, type, attr); \ | ||||
RB_PROTOTYPE_PREV(name, type, attr); \ | RB_PROTOTYPE_PREV(name, type, attr); \ | ||||
RB_PROTOTYPE_MINMAX(name, type, attr); \ | RB_PROTOTYPE_MINMAX(name, type, attr); \ | ||||
RB_PROTOTYPE_REINSERT(name, type, attr); | RB_PROTOTYPE_REINSERT(name, type, attr); | ||||
#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 All 25 Lines | #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ | ||||
RB_GENERATE_NFIND(name, type, field, cmp, attr) \ | RB_GENERATE_NFIND(name, type, field, cmp, attr) \ | ||||
RB_GENERATE_NEXT(name, type, field, attr) \ | RB_GENERATE_NEXT(name, type, field, attr) \ | ||||
RB_GENERATE_PREV(name, type, field, attr) \ | RB_GENERATE_PREV(name, type, field, 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) | ||||
#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, *parent; \ | struct type *child; \ | ||||
while ((parent = RB_PARENT(elm, field)) != NULL) { \ | __uintptr_t gp_bits; \ | ||||
do { \ | |||||
gp_bits = RB_BITS(parent, field); \ | |||||
if (RB_LEFT(parent, field) == elm) { \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (gp_bits & RB_RED_L) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (!(gp_bits & RB_RED_MASK)) \ | ||||
child = elm; \ | |||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | if (RB_BITS(elm, field) & RB_RED_R) \ | ||||
if (RB_RED_RIGHT(elm, field)) \ | |||||
child = elm; \ | child = elm; \ | ||||
else { \ | else { \ | ||||
/* coverity[uninit_use] */ \ | /* coverity[uninit_use] */ \ | ||||
RB_ROTATE_LEFT(head, elm, child, field);\ | RB_ROTATE_LEFT(elm, child, field); \ | ||||
if (RB_RED_RIGHT(child, field)) \ | __uintptr_t red = RB_BITS(child, field); \ | ||||
if (red & RB_RED_R) \ | |||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(child, field)) \ | if (red & RB_RED_L) \ | ||||
RB_FLIP_ALL(elm, field); \ | RB_FLIP_ALL(elm, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_LEFT(elm, field); \ | RB_FLIP_LEFT(elm, field); \ | ||||
if ((RB_BITS(child, field) & \ | if (!(red & RB_RED_MASK)) \ | ||||
RB_RED_MASK) == 0) \ | |||||
elm = child; \ | elm = child; \ | ||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, child, field); \ | RB_ROTATE_RIGHT(parent, child, field); \ | ||||
} else { \ | } else { \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (gp_bits & RB_RED_R) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (!(gp_bits & RB_RED_MASK)) \ | ||||
child = elm; \ | |||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | if (RB_BITS(elm, field) & RB_RED_L) \ | ||||
if (RB_RED_LEFT(elm, field)) \ | |||||
child = elm; \ | child = elm; \ | ||||
else { \ | else { \ | ||||
/* coverity[uninit_use] */ \ | /* coverity[uninit_use] */ \ | ||||
RB_ROTATE_RIGHT(head, elm, child, field);\ | RB_ROTATE_RIGHT(elm, child, field); \ | ||||
if (RB_RED_LEFT(child, field)) \ | __uintptr_t red = RB_BITS(child, field); \ | ||||
if (red & RB_RED_L) \ | |||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(child, field)) \ | if (red & RB_RED_R) \ | ||||
RB_FLIP_ALL(elm, field); \ | RB_FLIP_ALL(elm, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_RIGHT(elm, field); \ | RB_FLIP_RIGHT(elm, field); \ | ||||
if ((RB_BITS(child, field) & \ | if (!(red & RB_RED_MASK)) \ | ||||
RB_RED_MASK) == 0) \ | |||||
elm = child; \ | elm = child; \ | ||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, parent, child, field); \ | RB_ROTATE_LEFT(parent, child, field); \ | ||||
} \ | } \ | ||||
RB_BITS(child, field) &= ~RB_RED_MASK; \ | gp_bits &= ~RB_RED_MASK; \ | ||||
RB_UP(child, field) = (struct type *)gp_bits; \ | |||||
RB_SWAP_CHILD(head, (struct type *)gp_bits, \ | |||||
parent, child, field); \ | |||||
if (elm != child) \ | if (elm != child) \ | ||||
RB_AUGMENT(elm); \ | RB_AUGMENT(elm); \ | ||||
RB_AUGMENT(parent); \ | RB_AUGMENT(parent); \ | ||||
break; \ | break; \ | ||||
} \ | } while (child = elm, elm = parent, \ | ||||
(parent = (struct type *)gp_bits) != 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 | ||||
* 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 *sib; \ | struct type *sib; \ | ||||
__uintptr_t gp_bits; \ | |||||
if (RB_LEFT(parent, field) == elm && \ | if (RB_LEFT(parent, field) == elm && \ | ||||
RB_RIGHT(parent, field) == elm) { \ | RB_RIGHT(parent, field) == elm) { \ | ||||
RB_BITS(parent, field) &= ~RB_RED_MASK; \ | |||||
elm = parent; \ | elm = parent; \ | ||||
parent = RB_PARENT(elm, field); \ | RB_BITS(elm, field) &= ~RB_RED_MASK; \ | ||||
if (parent == NULL) \ | if ((parent = RB_UP(elm, field)) == NULL) \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
do { \ | do { \ | ||||
gp_bits = RB_BITS(parent, field); \ | |||||
if (RB_LEFT(parent, field) == elm) { \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (!RB_RED_LEFT(parent, field)) { \ | if (!(gp_bits & RB_RED_L)) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (gp_bits & RB_RED_R) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
sib = RB_RIGHT(parent, field); \ | sib = RB_RIGHT(parent, field); \ | ||||
switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | ||||
case RB_RED_MASK: \ | case RB_RED_MASK: \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
case RB_RED_R: \ | case RB_RED_R: \ | ||||
elm = RB_LEFT(sib, field); \ | elm = RB_LEFT(sib, field); \ | ||||
RB_ROTATE_RIGHT(head, sib, elm, field); \ | RB_ROTATE_RIGHT(sib, elm, field); \ | ||||
if (RB_RED_LEFT(elm, field)) \ | __uintptr_t red = RB_BITS(elm, field); \ | ||||
if (red & RB_RED_L) \ | |||||
RB_FLIP_ALL(parent, field); \ | RB_FLIP_ALL(parent, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_RIGHT(elm, field)) \ | if (red & RB_RED_R) \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_RIGHT(sib, field); \ | RB_FLIP_RIGHT(sib, field); \ | ||||
RB_BITS(elm, field) |= RB_RED_MASK; \ | RB_BITS(elm, field) |= RB_RED_MASK; \ | ||||
break; \ | break; \ | ||||
case RB_RED_L: \ | case RB_RED_L: \ | ||||
if (RB_STRICT_HST && elm != NULL) { \ | if (RB_STRICT_HST && elm != NULL) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
elm = sib; \ | elm = sib; \ | ||||
break; \ | break; \ | ||||
} \ | } \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
/* FALLTHROUGH */ \ | /* FALLTHROUGH */ \ | ||||
default: \ | default: \ | ||||
RB_FLIP_RIGHT(sib, field); \ | RB_FLIP_RIGHT(sib, field); \ | ||||
elm = sib; \ | elm = sib; \ | ||||
break; \ | break; \ | ||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, parent, elm, field); \ | RB_ROTATE_LEFT(parent, elm, field); \ | ||||
} else { \ | } else { \ | ||||
if (!RB_RED_RIGHT(parent, field)) { \ | if (!(gp_bits & RB_RED_R)) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (gp_bits & RB_RED_L) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
sib = RB_LEFT(parent, field); \ | sib = RB_LEFT(parent, field); \ | ||||
switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | ||||
case RB_RED_MASK: \ | case RB_RED_MASK: \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
case RB_RED_L: \ | case RB_RED_L: \ | ||||
elm = RB_RIGHT(sib, field); \ | elm = RB_RIGHT(sib, field); \ | ||||
RB_ROTATE_LEFT(head, sib, elm, field); \ | RB_ROTATE_LEFT(sib, elm, field); \ | ||||
if (RB_RED_RIGHT(elm, field)) \ | __uintptr_t red = RB_BITS(elm, field); \ | ||||
if (red & RB_RED_R) \ | |||||
RB_FLIP_ALL(parent, field); \ | RB_FLIP_ALL(parent, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_LEFT(elm, field)) \ | if (red & RB_RED_L) \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_LEFT(sib, field); \ | RB_FLIP_LEFT(sib, field); \ | ||||
RB_BITS(elm, field) |= RB_RED_MASK; \ | RB_BITS(elm, field) |= RB_RED_MASK; \ | ||||
break; \ | break; \ | ||||
case RB_RED_R: \ | case RB_RED_R: \ | ||||
if (RB_STRICT_HST && elm != NULL) { \ | if (RB_STRICT_HST && elm != NULL) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
elm = sib; \ | elm = sib; \ | ||||
break; \ | break; \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
/* FALLTHROUGH */ \ | /* FALLTHROUGH */ \ | ||||
default: \ | default: \ | ||||
RB_FLIP_LEFT(sib, field); \ | RB_FLIP_LEFT(sib, field); \ | ||||
elm = sib; \ | elm = sib; \ | ||||
break; \ | break; \ | ||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, elm, field); \ | RB_ROTATE_RIGHT(parent, elm, field); \ | ||||
} \ | } \ | ||||
gp_bits &= ~RB_RED_MASK; \ | |||||
RB_SET_PARENT(elm, (struct type *)gp_bits, field); \ | |||||
RB_SWAP_CHILD(head, (struct type *)gp_bits, \ | |||||
parent, elm, field); \ | |||||
if (sib != elm) \ | if (sib != elm) \ | ||||
RB_AUGMENT(sib); \ | RB_AUGMENT(sib); \ | ||||
break; \ | break; \ | ||||
} while ((parent = RB_PARENT(elm, field)) != NULL); \ | } while (gp_bits &= ~RB_RED_MASK, elm = parent, \ | ||||
(parent = (struct type *)gp_bits) != 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 *elm) \ | name##_RB_REMOVE(struct name *head, struct type *old) \ | ||||
{ \ | { \ | ||||
struct type *child, *old, *parent, *right; \ | struct type *child, *elm, *old_parent, *old_up, *parent; \ | ||||
\ | \ | ||||
old = elm; \ | old_up = RB_UP(old, field); \ | ||||
parent = RB_PARENT(elm, field); \ | old_parent = RB_PARENT(old, field); \ | ||||
right = RB_RIGHT(elm, field); \ | elm = RB_RIGHT(old, field); \ | ||||
if (RB_LEFT(elm, field) == NULL) \ | child = RB_LEFT(old, field); \ | ||||
elm = child = right; \ | if (elm == NULL || child == NULL) { \ | ||||
else if (right == NULL) \ | if (elm == NULL) \ | ||||
elm = child = RB_LEFT(elm, field); \ | |||||
else { \ | |||||
if ((child = RB_LEFT(right, field)) == NULL) { \ | |||||
child = RB_RIGHT(right, field); \ | |||||
RB_RIGHT(old, field) = child; \ | |||||
parent = elm = right; \ | |||||
} else { \ | |||||
do \ | |||||
elm = child; \ | elm = child; \ | ||||
while ((child = RB_LEFT(elm, field)) != NULL); \ | child = elm; \ | ||||
parent = old_parent; \ | |||||
} else { \ | |||||
parent = elm; \ | |||||
while (RB_LEFT(elm, field) != NULL) \ | |||||
elm = RB_LEFT(elm, field); \ | |||||
RB_SET_PARENT(child, elm, field); \ | |||||
RB_LEFT(elm, field) = child; \ | |||||
child = RB_RIGHT(elm, field); \ | child = RB_RIGHT(elm, field); \ | ||||
if (parent != elm) { \ | |||||
RB_SET_PARENT(parent, elm, field); \ | |||||
RB_RIGHT(elm, field) = parent; \ | |||||
parent = RB_PARENT(elm, field); \ | parent = RB_PARENT(elm, field); \ | ||||
RB_LEFT(parent, field) = child; \ | RB_LEFT(parent, field) = child; \ | ||||
RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\ | |||||
} \ | } \ | ||||
RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ | RB_UP(elm, field) = old_up; \ | ||||
elm->field = old->field; \ | |||||
} \ | } \ | ||||
RB_SWAP_CHILD(head, old, elm, field); \ | RB_SWAP_CHILD(head, old_parent, old, elm, field); \ | ||||
if (child != NULL) \ | if (child != NULL) \ | ||||
RB_SET_PARENT(child, parent, field); \ | 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 (parent == elm && RB_LEFT(parent, field) == NULL) \ | if (parent == elm && 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 (old); \ | return (old); \ | ||||
} | } | ||||
#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ | #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ | ||||
/* Inserts a node into the RB tree */ \ | /* Inserts a node into the RB tree */ \ | ||||
attr struct type * \ | attr struct type * \ | ||||
name##_RB_INSERT(struct name *head, struct type *elm) \ | name##_RB_INSERT(struct name *head, struct type *elm) \ | ||||
{ \ | { \ | ||||
struct type *tmp; \ | struct type *tmp; \ | ||||
struct type *parent = NULL; \ | struct type *parent = NULL; \ | ||||
__typeof(cmp(NULL, NULL)) comp = 0; \ | __typeof(cmp(NULL, NULL)) comp = 0; \ | ||||
tmp = RB_ROOT(head); \ | tmp = RB_ROOT(head); \ | ||||
while (tmp) { \ | while (tmp) { \ | ||||
parent = tmp; \ | parent = tmp; \ | ||||
comp = (cmp)(elm, parent); \ | comp = (cmp)(elm, parent); \ | ||||
if (comp < 0) \ | if (comp < 0) \ | ||||
tmp = RB_LEFT(tmp, field); \ | tmp = RB_LEFT(parent, field); \ | ||||
else if (comp > 0) \ | else if (comp > 0) \ | ||||
tmp = RB_RIGHT(tmp, field); \ | tmp = RB_RIGHT(parent, field); \ | ||||
else \ | else \ | ||||
return (tmp); \ | return (parent); \ | ||||
} \ | } \ | ||||
RB_SET(elm, parent, field); \ | RB_SET(elm, parent, field); \ | ||||
if (parent == NULL) \ | if (parent == NULL) \ | ||||
RB_ROOT(head) = elm; \ | RB_ROOT(head) = elm; \ | ||||
else if (comp < 0) \ | else { \ | ||||
if (comp < 0) \ | |||||
RB_LEFT(parent, field) = elm; \ | RB_LEFT(parent, field) = elm; \ | ||||
else \ | else \ | ||||
RB_RIGHT(parent, field) = elm; \ | RB_RIGHT(parent, field) = elm; \ | ||||
name##_RB_INSERT_COLOR(head, elm); \ | 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?