Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 356 Lines • ▼ Show 20 Lines | #define RB_SET(elm, parent, field) do { \ | ||||
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_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)) | ||||
/* | /* | ||||
* Something to be invoked in a loop at the root of every modified subtree, | * Either RB_AUGMENT or RB_AUGMENT_CHECK is invoked in a loop at the root of | ||||
* from the bottom up to the root, to update augmented node data. | * every modified subtree, from the bottom up to the root, to update augmented | ||||
* node data. RB_AUGMENT_CHECK returns true only when the update changes the | |||||
* node data, so that updating can be stopped short of the root when it returns | |||||
* false. | |||||
*/ | */ | ||||
#ifndef RB_AUGMENT_CHECK | |||||
#ifndef RB_AUGMENT | #ifndef RB_AUGMENT | ||||
#define RB_AUGMENT(x) break | #define RB_AUGMENT_CHECK(x) false | ||||
#else | |||||
#define RB_AUGMENT_CHECK(x) (RB_AUGMENT(x), true) | |||||
#endif | #endif | ||||
#endif | |||||
#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 { \ | ||||
(tmp) = RB_RIGHT(elm, field); \ | |||||
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); \ | RB_AUGMENT_CHECK(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 { \ | ||||
(tmp) = RB_LEFT(elm, field); \ | |||||
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); \ | RB_AUGMENT_CHECK(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 48 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) | ||||
#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) \ | ||||
{ \ | { \ | ||||
struct type *child, *parent; \ | struct type *child, *parent; \ | ||||
while ((parent = RB_PARENT(elm, field)) != NULL) { \ | bool changed; \ | ||||
for (changed = true; \ | |||||
(parent = RB_PARENT(elm, field)) != NULL; \ | |||||
changed = changed && RB_AUGMENT_CHECK(elm), elm = parent) { \ | |||||
if (RB_LEFT(parent, field) == elm) { \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (RB_RED_LEFT(parent, field)) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
return; \ | break; \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (RB_RED_RIGHT(parent, field)) \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | |||||
if (!RB_RED_RIGHT(elm, field)) { \ | if (!RB_RED_RIGHT(elm, field)) { \ | ||||
RB_FLIP_LEFT(elm, field); \ | RB_FLIP_LEFT(elm, field); \ | ||||
child = RB_RIGHT(elm, field); \ | |||||
RB_ROTATE_LEFT(head, elm, child, field);\ | RB_ROTATE_LEFT(head, elm, child, field);\ | ||||
if (RB_RED_LEFT(child, field)) \ | if (RB_RED_LEFT(child, field)) \ | ||||
RB_FLIP_RIGHT(elm, field); \ | RB_FLIP_RIGHT(elm, field); \ | ||||
else if (RB_RED_RIGHT(child, field)) \ | else if (RB_RED_RIGHT(child, field)) \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
elm = child; \ | elm = child; \ | ||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, elm, field); \ | RB_ROTATE_RIGHT(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; \ | break; \ | ||||
} \ | } \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (RB_RED_LEFT(parent, field)) \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | |||||
if (!RB_RED_LEFT(elm, field)) { \ | if (!RB_RED_LEFT(elm, field)) { \ | ||||
RB_FLIP_RIGHT(elm, field); \ | RB_FLIP_RIGHT(elm, field); \ | ||||
child = RB_LEFT(elm, field); \ | |||||
RB_ROTATE_RIGHT(head, elm, child, field);\ | RB_ROTATE_RIGHT(head, elm, child, field);\ | ||||
if (RB_RED_RIGHT(child, field)) \ | if (RB_RED_RIGHT(child, field)) \ | ||||
RB_FLIP_LEFT(elm, field); \ | RB_FLIP_LEFT(elm, field); \ | ||||
else if (RB_RED_LEFT(child, field)) \ | else if (RB_RED_LEFT(child, field)) \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
elm = child; \ | elm = child; \ | ||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, parent, elm, field); \ | RB_ROTATE_LEFT(head, parent, elm, field); \ | ||||
} \ | } \ | ||||
RB_BITS(elm, field) &= ~RB_RED_MASK; \ | RB_BITS(elm, field) &= ~RB_RED_MASK; \ | ||||
RB_AUGMENT_CHECK(elm); \ | |||||
elm = RB_PARENT(elm, field); \ | |||||
break; \ | break; \ | ||||
} \ | } \ | ||||
if (changed) { \ | |||||
while (elm != NULL && RB_AUGMENT_CHECK(elm)) \ | |||||
elm = RB_PARENT(elm, field); \ | |||||
} \ | |||||
} | } | ||||
#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; \ | ||||
bool changed = true; \ | |||||
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; \ | RB_BITS(parent, field) &= ~RB_RED_MASK; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
parent = RB_PARENT(elm, field); \ | changed = changed && RB_AUGMENT_CHECK(elm); \ | ||||
if (parent == NULL) \ | if ((parent = RB_PARENT(elm, field)) == NULL) \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
do { \ | do { \ | ||||
if (RB_LEFT(parent, field) == elm) { \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (!RB_RED_LEFT(parent, field)) { \ | if (!RB_RED_LEFT(parent, field)) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
return; \ | break; \ | ||||
} \ | } \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
sib = RB_RIGHT(parent, field); \ | sib = RB_RIGHT(parent, field); \ | ||||
if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ | if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ | ||||
RB_BITS(sib, field) &= ~RB_RED_MASK; \ | RB_BITS(sib, field) &= ~RB_RED_MASK; \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(sib, field); \ | RB_FLIP_RIGHT(sib, field); \ | ||||
if (RB_RED_LEFT(sib, field)) \ | if (RB_RED_LEFT(sib, field)) \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
else if (!RB_RED_RIGHT(sib, field)) { \ | else if (!RB_RED_RIGHT(sib, field)) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
elm = RB_LEFT(sib, field); \ | |||||
RB_ROTATE_RIGHT(head, sib, elm, field); \ | RB_ROTATE_RIGHT(head, sib, elm, field); \ | ||||
if (RB_RED_RIGHT(elm, field)) \ | if (RB_RED_RIGHT(elm, field)) \ | ||||
RB_FLIP_LEFT(sib, field); \ | RB_FLIP_LEFT(sib, field); \ | ||||
if (RB_RED_LEFT(elm, field)) \ | if (RB_RED_LEFT(elm, field)) \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
RB_BITS(elm, field) |= RB_RED_MASK; \ | RB_BITS(elm, field) |= RB_RED_MASK; \ | ||||
sib = elm; \ | sib = elm; \ | ||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, parent, sib, field); \ | RB_ROTATE_LEFT(head, parent, sib, 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; \ | break; \ | ||||
} \ | } \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (RB_RED_LEFT(parent, field)) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
sib = RB_LEFT(parent, field); \ | sib = RB_LEFT(parent, field); \ | ||||
if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ | if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ | ||||
RB_BITS(sib, field) &= ~RB_RED_MASK; \ | RB_BITS(sib, field) &= ~RB_RED_MASK; \ | ||||
elm = parent; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
RB_FLIP_LEFT(sib, field); \ | RB_FLIP_LEFT(sib, field); \ | ||||
if (RB_RED_RIGHT(sib, field)) \ | if (RB_RED_RIGHT(sib, field)) \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
else if (!RB_RED_LEFT(sib, field)) { \ | else if (!RB_RED_LEFT(sib, field)) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
elm = RB_RIGHT(sib, field); \ | |||||
RB_ROTATE_LEFT(head, sib, elm, field); \ | RB_ROTATE_LEFT(head, sib, elm, field); \ | ||||
if (RB_RED_LEFT(elm, field)) \ | if (RB_RED_LEFT(elm, field)) \ | ||||
RB_FLIP_RIGHT(sib, field); \ | RB_FLIP_RIGHT(sib, field); \ | ||||
if (RB_RED_RIGHT(elm, field)) \ | if (RB_RED_RIGHT(elm, field)) \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
RB_BITS(elm, field) |= RB_RED_MASK; \ | RB_BITS(elm, field) |= RB_RED_MASK; \ | ||||
sib = elm; \ | sib = elm; \ | ||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, sib, field); \ | RB_ROTATE_RIGHT(head, parent, sib, field); \ | ||||
} \ | } \ | ||||
RB_AUGMENT_CHECK(sib); \ | |||||
parent = RB_PARENT(sib, field); \ | |||||
break; \ | break; \ | ||||
} while ((parent = RB_PARENT(elm, field)) != NULL); \ | } while (elm = parent, \ | ||||
changed = changed && RB_AUGMENT_CHECK(elm), \ | |||||
(parent = RB_PARENT(elm, field)) != NULL); \ | |||||
if (changed) { \ | |||||
while (parent != NULL && RB_AUGMENT_CHECK(parent)) \ | |||||
parent = RB_PARENT(parent, field); \ | |||||
} \ | |||||
} | } | ||||
#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) \ | ||||
{ \ | { \ | ||||
struct type *child, *old, *parent, *right; \ | struct type *child, *old, *parent, *right; \ | ||||
\ | \ | ||||
Show All 21 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); \ | ||||
while (parent != NULL) { \ | |||||
RB_AUGMENT(parent); \ | |||||
parent = RB_PARENT(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) \ | ||||
{ \ | { \ | ||||
Show All 14 Lines | name##_RB_INSERT(struct name *head, struct type *elm) \ | ||||
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, elm); \ | ||||
while (elm != NULL) { \ | |||||
RB_AUGMENT(elm); \ | |||||
elm = RB_PARENT(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 148 Lines • Show Last 20 Lines |