Changeset View
Changeset View
Standalone View
Standalone View
head/sys/sys/tree.h
Show First 20 Lines • Show All 301 Lines • ▼ Show 20 Lines | |||||
#define RB_INITIALIZER(root) \ | #define RB_INITIALIZER(root) \ | ||||
{ NULL } | { NULL } | ||||
#define RB_INIT(root) do { \ | #define RB_INIT(root) do { \ | ||||
(root)->rbh_root = NULL; \ | (root)->rbh_root = NULL; \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_BLACK 0 | |||||
#define RB_RED 1 | |||||
#define RB_ENTRY(type) \ | #define RB_ENTRY(type) \ | ||||
struct { \ | struct { \ | ||||
struct type *rbe_left; /* left element */ \ | struct type *rbe_left; /* left element */ \ | ||||
struct type *rbe_right; /* right element */ \ | struct type *rbe_right; /* right element */ \ | ||||
struct type *rbe_parent; /* parent element */ \ | struct type *rbe_parent; /* parent element */ \ | ||||
int rbe_color; /* node color */ \ | |||||
} | } | ||||
#define RB_LEFT(elm, field) (elm)->field.rbe_left | #define RB_LEFT(elm, field) (elm)->field.rbe_left | ||||
#define RB_RIGHT(elm, field) (elm)->field.rbe_right | #define RB_RIGHT(elm, field) (elm)->field.rbe_right | ||||
#define RB_PARENT(elm, field) (elm)->field.rbe_parent | |||||
#define RB_COLOR(elm, field) (elm)->field.rbe_color | /* | ||||
#define RB_ISRED(elm, field) ((elm) != NULL && RB_COLOR(elm, field) == RB_RED) | * With the expectation that any object of struct type has an | ||||
* address that is a multiple of 4, and that therefore the | |||||
* 2 least significant bits of a pointer to struct type are | |||||
* always zero, this implementation sets those bits to indicate | |||||
* that the left or right child of the tree node is "red". | |||||
*/ | |||||
#define RB_UP(elm, field) (elm)->field.rbe_parent | |||||
#define RB_BITS(elm, field) *(__uintptr_t *)&RB_UP(elm, field) | |||||
#define RB_RED_L (__uintptr_t)1 | |||||
#define RB_RED_R (__uintptr_t)2 | |||||
#define RB_RED_MASK (__uintptr_t)3 | |||||
#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_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))) \ | |||||
(RB_BITS(elm, field) & ~RB_RED_MASK)) | |||||
/* | |||||
* This header may appear in user code where 'bool' is not defined, | |||||
* so it defines its own boolean type to avoid breaking that code. | |||||
*/ | |||||
#define RB_BOOL int | |||||
#define RB_TRUE 1 | |||||
#define RB_FALSE 0 | |||||
#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_PARENT(dst, field) = src; \ | RB_BITS(dst, field) &= RB_RED_MASK; \ | ||||
RB_BITS(dst, field) |= (__uintptr_t)src; \ | |||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_SET(elm, parent, field) do { \ | #define RB_SET(elm, parent, field) do { \ | ||||
RB_SET_PARENT(elm, parent, field); \ | RB_UP(elm, field) = parent; \ | ||||
RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | ||||
RB_COLOR(elm, field) = RB_RED; \ | |||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_SET_BLACKRED(black, red, field) do { \ | #define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? RB_FALSE : \ | ||||
RB_COLOR(black, field) = RB_BLACK; \ | RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ | ||||
RB_COLOR(red, field) = RB_RED; \ | RB_RED_LEFT(RB_PARENT(elm, field), field) : \ | ||||
} while (/*CONSTCOND*/ 0) | RB_RED_RIGHT(RB_PARENT(elm, field), field)) | ||||
/* | /* | ||||
* 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 | ||||
▲ Show 20 Lines • Show All 87 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 *parent, *gparent, *tmp; \ | struct type *gparent, *parent; \ | ||||
while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) { \ | while ((parent = RB_PARENT(elm, field)) != NULL) { \ | ||||
gparent = RB_PARENT(parent, field); \ | if (RB_LEFT(parent, field) == elm) \ | ||||
if (parent == RB_LEFT(gparent, field)) { \ | RB_FLIP_LEFT(parent, field); \ | ||||
tmp = RB_RIGHT(gparent, field); \ | else \ | ||||
if (RB_ISRED(tmp, field)) { \ | RB_FLIP_RIGHT(parent, field); \ | ||||
RB_COLOR(tmp, field) = RB_BLACK; \ | if ((gparent = RB_PARENT(parent, field)) == NULL) \ | ||||
RB_SET_BLACKRED(parent, gparent, field);\ | break; \ | ||||
if (RB_RED_LEFT(gparent, field) && \ | |||||
RB_RED_RIGHT(gparent, field)) { \ | |||||
RB_FLIP_LEFT(gparent, field); \ | |||||
RB_FLIP_RIGHT(gparent, field); \ | |||||
elm = gparent; \ | elm = gparent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (RB_RED_LEFT(gparent, field) && \ | |||||
parent == RB_LEFT(gparent, field)) { \ | |||||
if (RB_RIGHT(parent, field) == elm) { \ | if (RB_RIGHT(parent, field) == elm) { \ | ||||
RB_ROTATE_LEFT(head, parent, tmp, field);\ | RB_ROTATE_LEFT(head, parent, elm, field);\ | ||||
tmp = parent; \ | RB_FLIP_RIGHT(parent, field); \ | ||||
RB_FLIP_LEFT(elm, field); \ | |||||
parent = elm; \ | parent = elm; \ | ||||
elm = tmp; \ | |||||
} \ | } \ | ||||
RB_SET_BLACKRED(parent, gparent, field); \ | RB_ROTATE_RIGHT(head, gparent, parent, field); \ | ||||
RB_ROTATE_RIGHT(head, gparent, tmp, field); \ | RB_FLIP_LEFT(gparent, field); \ | ||||
} else { \ | RB_FLIP_RIGHT(parent, field); \ | ||||
tmp = RB_LEFT(gparent, field); \ | } else if (RB_RED_RIGHT(gparent, field) && \ | ||||
if (RB_ISRED(tmp, field)) { \ | parent == RB_RIGHT(gparent, field)) { \ | ||||
RB_COLOR(tmp, field) = RB_BLACK; \ | |||||
RB_SET_BLACKRED(parent, gparent, field);\ | |||||
elm = gparent; \ | |||||
continue; \ | |||||
} \ | |||||
if (RB_LEFT(parent, field) == elm) { \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
RB_ROTATE_RIGHT(head, parent, tmp, field);\ | RB_ROTATE_RIGHT(head, parent, elm, field);\ | ||||
tmp = parent; \ | RB_FLIP_LEFT(parent, field); \ | ||||
RB_FLIP_RIGHT(elm, field); \ | |||||
parent = elm; \ | parent = elm; \ | ||||
elm = tmp; \ | |||||
} \ | } \ | ||||
RB_SET_BLACKRED(parent, gparent, field); \ | RB_ROTATE_LEFT(head, gparent, parent, field); \ | ||||
RB_ROTATE_LEFT(head, gparent, tmp, field); \ | RB_FLIP_RIGHT(gparent, field); \ | ||||
RB_FLIP_LEFT(parent, field); \ | |||||
} \ | } \ | ||||
break; \ | |||||
} \ | } \ | ||||
RB_COLOR(head->rbh_root, field) = RB_BLACK; \ | |||||
} | } | ||||
#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, struct type *parent) \ | name##_RB_REMOVE_COLOR(struct name *head, struct type *par) \ | ||||
{ \ | { \ | ||||
struct type *elm, *tmp; \ | struct type *gpr, *sib, *nec; \ | ||||
elm = NULL; \ | RB_BOOL left_elm, left_par, red_gpr; \ | ||||
left_par = (RB_LEFT(par, field) == NULL); \ | |||||
do { \ | do { \ | ||||
if (RB_LEFT(parent, field) == elm) { \ | left_elm = left_par; \ | ||||
tmp = RB_RIGHT(parent, field); \ | if (left_elm ? \ | ||||
if (RB_COLOR(tmp, field) == RB_RED) { \ | !RB_RED_RIGHT(par, field) : \ | ||||
RB_SET_BLACKRED(tmp, parent, field); \ | !RB_RED_LEFT(par, field)) { \ | ||||
RB_ROTATE_LEFT(head, parent, tmp, field);\ | gpr = RB_PARENT(par, field); \ | ||||
tmp = RB_RIGHT(parent, field); \ | left_par = gpr != NULL && \ | ||||
RB_LEFT(gpr, field) == par; \ | |||||
red_gpr = gpr == NULL ? \ | |||||
RB_TRUE: RB_COLOR(par, field); \ | |||||
} \ | } \ | ||||
if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ | if (left_elm) { \ | ||||
RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ | if (RB_RED_RIGHT(par, field)) { \ | ||||
else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \ | red_gpr = RB_TRUE; \ | ||||
struct type *oleft; \ | RB_ROTATE_LEFT(head, par, gpr, field); \ | ||||
RB_ROTATE_RIGHT(head, tmp, oleft, field); \ | RB_FLIP_RIGHT(par, field); \ | ||||
RB_COLOR(oleft, field) = RB_BLACK; \ | RB_FLIP_LEFT(gpr, field); \ | ||||
tmp = oleft; \ | } \ | ||||
sib = RB_RIGHT(par, field); \ | |||||
if (RB_RED_RIGHT(sib, field)) { \ | |||||
if (RB_RED_LEFT(sib, field)) { \ | |||||
RB_FLIP_LEFT(sib, field); \ | |||||
RB_FLIP_RIGHT(par, field); \ | |||||
} \ | |||||
RB_FLIP_RIGHT(sib, field); \ | |||||
} else if (RB_RED_LEFT(sib, field)) { \ | |||||
RB_ROTATE_RIGHT(head, sib, nec, field); \ | |||||
RB_FLIP_LEFT(sib, field); \ | |||||
sib = nec; \ | |||||
} else { \ | } else { \ | ||||
RB_COLOR(tmp, field) = RB_RED; \ | RB_FLIP_RIGHT(par, field); \ | ||||
elm = parent; \ | par = gpr; \ | ||||
parent = RB_PARENT(elm, field); \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ | RB_ROTATE_LEFT(head, par, sib, field); \ | ||||
RB_COLOR(parent, field) = RB_BLACK; \ | return; \ | ||||
RB_ROTATE_LEFT(head, parent, tmp, field); \ | |||||
elm = RB_ROOT(head); \ | |||||
break; \ | |||||
} else { \ | } else { \ | ||||
tmp = RB_LEFT(parent, field); \ | if (RB_RED_LEFT(par, field)) { \ | ||||
if (RB_COLOR(tmp, field) == RB_RED) { \ | red_gpr = RB_TRUE; \ | ||||
RB_SET_BLACKRED(tmp, parent, field); \ | RB_ROTATE_RIGHT(head, par, gpr, field); \ | ||||
RB_ROTATE_RIGHT(head, parent, tmp, field);\ | RB_FLIP_LEFT(par, field); \ | ||||
tmp = RB_LEFT(parent, field); \ | RB_FLIP_RIGHT(gpr, field); \ | ||||
} \ | } \ | ||||
if (RB_ISRED(RB_LEFT(tmp, field), field)) \ | sib = RB_LEFT(par, field); \ | ||||
RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ | if (RB_RED_LEFT(sib, field)) { \ | ||||
else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \ | if (RB_RED_RIGHT(sib, field)) { \ | ||||
struct type *oright; \ | RB_FLIP_RIGHT(sib, field); \ | ||||
RB_ROTATE_LEFT(head, tmp, oright, field); \ | RB_FLIP_LEFT(par, field); \ | ||||
RB_COLOR(oright, field) = RB_BLACK; \ | } \ | ||||
tmp = oright; \ | RB_FLIP_LEFT(sib, field); \ | ||||
} else if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \ | } else if (RB_RED_RIGHT(sib, field)) { \ | ||||
RB_COLOR(tmp, field) = RB_RED; \ | RB_ROTATE_LEFT(head, sib, nec, field); \ | ||||
elm = parent; \ | RB_FLIP_RIGHT(sib, field); \ | ||||
parent = RB_PARENT(elm, field); \ | sib = nec; \ | ||||
} else { \ | |||||
RB_FLIP_LEFT(par, field); \ | |||||
par = gpr; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ | RB_ROTATE_RIGHT(head, par, sib, field); \ | ||||
RB_COLOR(parent, field) = RB_BLACK; \ | return; \ | ||||
RB_ROTATE_RIGHT(head, parent, tmp, field); \ | |||||
elm = RB_ROOT(head); \ | |||||
break; \ | |||||
} \ | } \ | ||||
} while (!RB_ISRED(elm, field) && parent != NULL); \ | } while (!red_gpr); \ | ||||
RB_COLOR(elm, field) = RB_BLACK; \ | if (gpr == NULL); \ | ||||
else if (left_par) \ | |||||
RB_FLIP_LEFT(gpr, field); \ | |||||
else \ | |||||
RB_FLIP_RIGHT(gpr, 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; \ | ||||
int color; \ | RB_BOOL red; \ | ||||
\ | \ | ||||
old = elm; \ | old = elm; \ | ||||
parent = RB_PARENT(elm, field); \ | parent = RB_PARENT(elm, field); \ | ||||
right = RB_RIGHT(elm, field); \ | right = RB_RIGHT(elm, field); \ | ||||
color = RB_COLOR(elm, field); \ | |||||
if (RB_LEFT(elm, field) == NULL) \ | if (RB_LEFT(elm, field) == NULL) \ | ||||
elm = child = right; \ | elm = child = right; \ | ||||
else if (right == NULL) \ | else if (right == NULL) \ | ||||
elm = child = RB_LEFT(elm, field); \ | elm = child = RB_LEFT(elm, field); \ | ||||
else { \ | else { \ | ||||
if ((child = RB_LEFT(right, field)) == NULL) { \ | if ((child = RB_LEFT(right, field)) == NULL) { \ | ||||
child = RB_RIGHT(right, field); \ | child = RB_RIGHT(right, field); \ | ||||
red = RB_RED_RIGHT(old, field); \ | |||||
if (red) \ | |||||
RB_FLIP_RIGHT(old, field); \ | |||||
RB_RIGHT(old, field) = child; \ | RB_RIGHT(old, field) = child; \ | ||||
parent = elm = right; \ | parent = elm = right; \ | ||||
} else { \ | } else { \ | ||||
do \ | do \ | ||||
elm = child; \ | elm = child; \ | ||||
while ((child = RB_LEFT(elm, field)) != NULL); \ | while ((child = RB_LEFT(elm, field)) != NULL); \ | ||||
child = RB_RIGHT(elm, field); \ | child = RB_RIGHT(elm, field); \ | ||||
parent = RB_PARENT(elm, field); \ | parent = RB_PARENT(elm, field); \ | ||||
red = RB_RED_LEFT(parent, field); \ | |||||
if (red) \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
RB_LEFT(parent, field) = child; \ | RB_LEFT(parent, field) = child; \ | ||||
RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \ | RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \ | ||||
} \ | } \ | ||||
RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ | RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ | ||||
color = RB_COLOR(elm, field); \ | |||||
elm->field = old->field; \ | elm->field = old->field; \ | ||||
} \ | } \ | ||||
if (elm == child) { \ | |||||
red = RB_COLOR(old, field); \ | |||||
if (!red); \ | |||||
else if (RB_LEFT(parent, field) == old) \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
else \ | |||||
RB_FLIP_RIGHT(parent, 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); \ | ||||
RB_COLOR(child, field) = RB_BLACK; \ | else if (!red && parent != NULL) \ | ||||
} else if (color != RB_RED && parent != NULL) \ | |||||
name##_RB_REMOVE_COLOR(head, parent); \ | name##_RB_REMOVE_COLOR(head, parent); \ | ||||
while (parent != NULL) { \ | while (parent != NULL) { \ | ||||
RB_AUGMENT(parent); \ | RB_AUGMENT(parent); \ | ||||
parent = RB_PARENT(parent, field); \ | parent = RB_PARENT(parent, field); \ | ||||
} \ | } \ | ||||
return (old); \ | return (old); \ | ||||
} | } | ||||
Show All 12 Lines | while (tmp) { \ | ||||
if (comp < 0) \ | if (comp < 0) \ | ||||
tmp = RB_LEFT(tmp, field); \ | tmp = RB_LEFT(tmp, field); \ | ||||
else if (comp > 0) \ | else if (comp > 0) \ | ||||
tmp = RB_RIGHT(tmp, field); \ | tmp = RB_RIGHT(tmp, field); \ | ||||
else \ | else \ | ||||
return (tmp); \ | return (tmp); \ | ||||
} \ | } \ | ||||
RB_SET(elm, parent, field); \ | RB_SET(elm, parent, field); \ | ||||
if (parent != NULL) { \ | if (parent == NULL) \ | ||||
if (comp < 0) \ | RB_ROOT(head) = elm; \ | ||||
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; \ | ||||
} else \ | |||||
RB_ROOT(head) = elm; \ | |||||
name##_RB_INSERT_COLOR(head, elm); \ | name##_RB_INSERT_COLOR(head, elm); \ | ||||
while (elm != NULL) { \ | while (elm != NULL) { \ | ||||
RB_AUGMENT(elm); \ | RB_AUGMENT(elm); \ | ||||
elm = RB_PARENT(elm, field); \ | elm = RB_PARENT(elm, field); \ | ||||
} \ | } \ | ||||
return (NULL); \ | return (NULL); \ | ||||
} | } | ||||
▲ Show 20 Lines • Show All 163 Lines • Show Last 20 Lines |