Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Context not available. | |||||
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 { \ | ||||
Context not available. | |||||
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 { \ | ||||
Context not available. | |||||
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 */ | ||||
Context not available. | |||||
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); \ | ||||
RB_ROTATE_LEFT(head, elm, child, field);\ | RB_ROTATE_LEFT(head, elm, child, field);\ | ||||
Context not available. | |||||
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; \ | |||||
} \ | } \ | ||||
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); \ | ||||
RB_ROTATE_RIGHT(head, elm, child, field);\ | RB_ROTATE_RIGHT(head, elm, child, field);\ | ||||
Context not available. | |||||
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; \ | |||||
} \ | } \ | ||||
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) \ | ||||
Context not available. | |||||
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 = 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); \ | ||||
Context not available. | |||||
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; \ | |||||
} \ | } \ | ||||
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; \ | 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); \ | ||||
Context not available. | |||||
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; \ | |||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, sib, field); \ | RB_ROTATE_RIGHT(head, parent, elm, field); \ | ||||
} \ | } \ | ||||
RB_AUGMENT_CHECK(elm); \ | |||||
parent = RB_PARENT(elm, 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) \ | ||||
Context not available. | |||||
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); \ | ||||
} | } | ||||
Context not available. | |||||
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); \ | ||||
} | } | ||||
Context not available. |