Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 366 Lines • ▼ Show 20 Lines | |||||
* 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, out, in, field) do { \ | ||||
if (RB_PARENT(out, field) == NULL) \ | if (RB_PARENT(out, field) == NULL) \ | ||||
RB_ROOT(head) = (in); \ | RB_ROOT(head) = (in); \ | ||||
else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ | else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ | ||||
RB_LEFT(RB_PARENT(out, field), field) = (in); \ | RB_LEFT(RB_PARENT(out, field), field) = (in); \ | ||||
else \ | else \ | ||||
RB_RIGHT(RB_PARENT(out, field), field) = (in); \ | RB_RIGHT(RB_PARENT(out, field), field) = (in); \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | #define RB_ROTATE_LEFT(head, 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_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ | ||||
RB_SWAP_CHILD(head, elm, tmp, 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); \ | ||||
RB_AUGMENT(elm); \ | |||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ | #define RB_ROTATE_RIGHT(head, 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_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ | ||||
RB_SWAP_CHILD(head, elm, tmp, 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); \ | ||||
RB_AUGMENT(elm); \ | |||||
} 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) \ | ||||
▲ Show 20 Lines • Show All 71 Lines • ▼ Show 20 Lines | if (RB_LEFT(parent, field) == elm) { \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
child = elm; \ | child = elm; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (!RB_RED_RIGHT(elm, field)) { \ | if (RB_RED_RIGHT(elm, field)) \ | ||||
child = elm; \ | |||||
else { \ | |||||
/* coverity[uninit_use] */ \ | /* coverity[uninit_use] */ \ | ||||
RB_ROTATE_LEFT(head, elm, child, field);\ | RB_ROTATE_LEFT(head, elm, child, field);\ | ||||
if (RB_RED_RIGHT(child, field)) \ | if (RB_RED_RIGHT(child, field)) \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(child, field)) \ | if (RB_RED_LEFT(child, field)) \ | ||||
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) & \ | |||||
RB_RED_MASK) == 0) \ | |||||
elm = child; \ | elm = child; \ | ||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, elm, field); \ | RB_ROTATE_RIGHT(head, parent, child, field); \ | ||||
} else { \ | } else { \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
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 (RB_RED_LEFT(parent, field)) { \ | ||||
child = elm; \ | child = elm; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (!RB_RED_LEFT(elm, field)) { \ | if (RB_RED_LEFT(elm, field)) \ | ||||
child = elm; \ | |||||
else { \ | |||||
/* coverity[uninit_use] */ \ | /* coverity[uninit_use] */ \ | ||||
RB_ROTATE_RIGHT(head, elm, child, field);\ | RB_ROTATE_RIGHT(head, elm, child, field);\ | ||||
if (RB_RED_LEFT(child, field)) \ | if (RB_RED_LEFT(child, field)) \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(child, field)) \ | if (RB_RED_RIGHT(child, field)) \ | ||||
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) & \ | |||||
RB_RED_MASK) == 0) \ | |||||
elm = child; \ | elm = child; \ | ||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, parent, elm, field); \ | RB_ROTATE_LEFT(head, parent, child, field); \ | ||||
} \ | } \ | ||||
RB_BITS(elm, field) &= ~RB_RED_MASK; \ | RB_BITS(child, field) &= ~RB_RED_MASK; \ | ||||
if (elm != child) \ | |||||
RB_AUGMENT(elm); \ | |||||
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 | ||||
▲ Show 20 Lines • Show All 42 Lines • ▼ Show 20 Lines | if (RB_LEFT(parent, field) == elm) { \ | ||||
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 (RB_RED_RIGHT(elm, field)) \ | ||||
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; \ | ||||
sib = elm; \ | |||||
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; \ | |||||
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; \ | |||||
break; \ | break; \ | ||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, parent, sib, field); \ | RB_ROTATE_LEFT(head, parent, elm, field); \ | ||||
} else { \ | } else { \ | ||||
if (!RB_RED_RIGHT(parent, field)) { \ | if (!RB_RED_RIGHT(parent, field)) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (RB_RED_LEFT(parent, field)) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
elm = parent; \ | elm = parent; \ | ||||
Show All 12 Lines | if (RB_LEFT(parent, field) == elm) { \ | ||||
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 (RB_RED_LEFT(elm, field)) \ | ||||
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; \ | ||||
sib = elm; \ | |||||
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; \ | |||||
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; \ | |||||
break; \ | break; \ | ||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, sib, field); \ | RB_ROTATE_RIGHT(head, parent, elm, field); \ | ||||
} \ | } \ | ||||
if (sib != elm) \ | |||||
RB_AUGMENT(sib); \ | |||||
break; \ | break; \ | ||||
} while ((parent = RB_PARENT(elm, field)) != NULL); \ | } while ((parent = RB_PARENT(elm, field)) != 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 *elm) \ | ||||
{ \ | { \ | ||||
Show All 23 Lines | else { \ | ||||
RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ | RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ | ||||
elm->field = old->field; \ | elm->field = old->field; \ | ||||
} \ | } \ | ||||
RB_SWAP_CHILD(head, old, elm, field); \ | RB_SWAP_CHILD(head, old, elm, field); \ | ||||
if (child != NULL) \ | if (child != NULL) \ | ||||
RB_SET_PARENT(child, parent, field); \ | RB_SET_PARENT(child, parent, field); \ | ||||
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) \ | |||||
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 * \ | ||||
▲ Show 20 Lines • Show All 181 Lines • Show Last 20 Lines |