Changeset View
Changeset View
Standalone View
Standalone View
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_LF(elm, field) (elm)->field.rbe_left | #define RB_LEFT(elm, field) (elm)->field.rbe_left | ||||
#define RB_RT(elm, field) (elm)->field.rbe_right | #define RB_RIGHT(elm, field) (elm)->field.rbe_right | ||||
#define RB_FLIP(elm) (*(__uintptr_t *)&(elm) ^= 1) | |||||
#define RB_FLIP_LF(elm, field) RB_FLIP(RB_LF(elm, field)) | |||||
#define RB_FLIP_RT(elm, field) RB_FLIP(RB_RT(elm, field)) | |||||
#define RB_ISRED(elm) ((*(__uintptr_t *)&(elm) & 1) != 0) | |||||
#define RB_RED_LF(elm, field) RB_ISRED(RB_LF(elm, field)) | |||||
#define RB_RED_RT(elm, field) RB_ISRED(RB_RT(elm, field)) | |||||
#define RB_PTR(elm, field) ((__typeof(elm->field.rbe_parent)) \ | |||||
((__uintptr_t)(elm) & ~(__uintptr_t)1)) | |||||
#define RB_LEFT(elm, field) RB_PTR(RB_LF(elm, field), field) | |||||
#define RB_RIGHT(elm, field) RB_PTR(RB_RT(elm, field), field) | |||||
#define RB_PARENT(elm, field) (elm)->field.rbe_parent | #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) | |||||
#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_BOOL int | |||||
#define RB_TRUE 1 | |||||
#define RB_FALSE 0 | |||||
/* For debugging support */ | #define RB_SET(elm, parent, field) do { \ | ||||
#define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? RB_FALSE : \ | RB_PARENT(elm, field) = parent; \ | ||||
RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ | RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | ||||
RB_RED_LF(RB_PARENT(elm, field), field) : \ | RB_COLOR(elm, field) = RB_RED; \ | ||||
RB_RED_RT(RB_PARENT(elm, field), field)) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_SET_BLACKRED(black, red, field) do { \ | |||||
RB_COLOR(black, field) = RB_BLACK; \ | |||||
RB_COLOR(red, field) = RB_RED; \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
/* | /* | ||||
* 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 | ||||
/* | |||||
* Fix pointers to a parent, and from a parent, as part of rotation. | |||||
*/ | |||||
#define RB_ROTATE_PARENT(head, elm, tmp, field) do { \ | |||||
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) == NULL) \ | |||||
RB_ROOT(head) = (tmp); \ | |||||
else if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | |||||
RB_LF(RB_PARENT(elm, field), field) = (tmp); \ | |||||
else \ | |||||
RB_RT(RB_PARENT(elm, field), field) = (tmp); \ | |||||
RB_PARENT(elm, field) = (tmp); \ | |||||
} while (/*CONSTCOND*/ 0) | |||||
/* | |||||
* Rotation makes the descending node red, and the ascending | |||||
* node not-red. | |||||
*/ | |||||
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | ||||
(tmp) = RB_RIGHT(elm, field); \ | (tmp) = RB_RIGHT(elm, field); \ | ||||
if ((RB_RT(elm, field) = RB_LF(tmp, field)) != NULL) { \ | if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ | ||||
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ | RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ | ||||
} \ | } \ | ||||
RB_ROTATE_PARENT(head, elm, tmp, field); \ | if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ | ||||
RB_LF(tmp, field) = (elm); \ | if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | ||||
RB_FLIP_LF(tmp, field); \ | RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | ||||
else \ | |||||
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | |||||
} else \ | |||||
(head)->rbh_root = (tmp); \ | |||||
RB_LEFT(tmp, field) = (elm); \ | |||||
RB_PARENT(elm, field) = (tmp); \ | |||||
RB_AUGMENT(elm); \ | 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 { \ | ||||
(tmp) = RB_LEFT(elm, field); \ | (tmp) = RB_LEFT(elm, field); \ | ||||
if ((RB_LF(elm, field) = RB_RT(tmp, field)) != NULL) { \ | if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ | ||||
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ | RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ | ||||
} \ | } \ | ||||
RB_ROTATE_PARENT(head, elm, tmp, field); \ | if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ | ||||
RB_RT(tmp, field) = (elm); \ | if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | ||||
RB_FLIP_RT(tmp, field); \ | RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | ||||
else \ | |||||
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | |||||
} else \ | |||||
(head)->rbh_root = (tmp); \ | |||||
RB_RIGHT(tmp, field) = (elm); \ | |||||
RB_PARENT(elm, field) = (tmp); \ | |||||
RB_AUGMENT(elm); \ | 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) | ||||
▲ 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 *gparent, *parent; \ | struct type *parent, *gparent, *tmp; \ | ||||
while ((parent = RB_PARENT(elm, field)) != NULL) { \ | while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) { \ | ||||
if (RB_LEFT(parent, field) == elm) \ | gparent = RB_PARENT(parent, field); \ | ||||
RB_FLIP_LF(parent, field); \ | if (parent == RB_LEFT(gparent, field)) { \ | ||||
else \ | tmp = RB_RIGHT(gparent, field); \ | ||||
RB_FLIP_RT(parent, field); \ | if (RB_ISRED(tmp, field)) { \ | ||||
if ((gparent = RB_PARENT(parent, field)) == NULL) \ | RB_COLOR(tmp, field) = RB_BLACK; \ | ||||
break; \ | RB_SET_BLACKRED(parent, gparent, field);\ | ||||
if (RB_RED_LF(gparent, field) && \ | |||||
RB_RED_RT(gparent, field)) { \ | |||||
RB_FLIP_LF(gparent, field); \ | |||||
RB_FLIP_RT(gparent, field); \ | |||||
elm = gparent; \ | elm = gparent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (RB_RED_LF(gparent, field) && \ | |||||
parent == RB_LEFT(gparent, field)) { \ | |||||
if (RB_RIGHT(parent, field) == elm) { \ | if (RB_RIGHT(parent, field) == elm) { \ | ||||
RB_ROTATE_LEFT(head, parent, elm, field);\ | RB_ROTATE_LEFT(head, parent, tmp, field);\ | ||||
tmp = parent; \ | |||||
parent = elm; \ | parent = elm; \ | ||||
elm = tmp; \ | |||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, gparent, parent, field); \ | RB_SET_BLACKRED(parent, gparent, field); \ | ||||
} else if (RB_RED_RT(gparent, field) && \ | RB_ROTATE_RIGHT(head, gparent, tmp, field); \ | ||||
parent == RB_RIGHT(gparent, field)) { \ | } else { \ | ||||
tmp = RB_LEFT(gparent, field); \ | |||||
if (RB_ISRED(tmp, 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, elm, field);\ | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | ||||
tmp = parent; \ | |||||
parent = elm; \ | parent = elm; \ | ||||
elm = tmp; \ | |||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, gparent, parent, field); \ | RB_SET_BLACKRED(parent, gparent, field); \ | ||||
RB_ROTATE_LEFT(head, gparent, tmp, 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 *elm) \ | name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \ | ||||
{ \ | { \ | ||||
struct type *par, *sib, *tmp; \ | struct type *elm, *tmp; \ | ||||
RB_BOOL go_left, left_child, red_par; \ | elm = NULL; \ | ||||
left_child = (RB_LEFT(elm, field) == NULL); \ | |||||
do { \ | do { \ | ||||
go_left = left_child; \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (go_left ? \ | tmp = RB_RIGHT(parent, field); \ | ||||
!RB_RED_RT(elm, field) : \ | if (RB_COLOR(tmp, field) == RB_RED) { \ | ||||
!RB_RED_LF(elm, field)) { \ | RB_SET_BLACKRED(tmp, parent, field); \ | ||||
par = RB_PARENT(elm, field); \ | RB_ROTATE_LEFT(head, parent, tmp, field);\ | ||||
left_child = par != NULL && \ | tmp = RB_RIGHT(parent, field); \ | ||||
RB_LEFT(par, field) == elm; \ | |||||
red_par = left_child ? RB_RED_LF(par, field) : \ | |||||
par == NULL ? RB_TRUE : \ | |||||
RB_RED_RT(par, field); \ | |||||
} \ | } \ | ||||
if (go_left) { \ | if (RB_ISRED(RB_LEFT(tmp, field), field)) { \ | ||||
if (RB_RED_RT(elm, field)) { \ | struct type *oleft; \ | ||||
red_par = RB_TRUE; \ | oleft = RB_LEFT(tmp, field); \ | ||||
RB_ROTATE_LEFT(head, elm, par, field); \ | RB_COLOR(oleft, field) = RB_BLACK; \ | ||||
} \ | RB_COLOR(tmp, field) = RB_RED; \ | ||||
sib = RB_RIGHT(elm, field); \ | RB_ROTATE_RIGHT(head, tmp, oleft, field); \ | ||||
if (RB_RED_LF(sib, field)) { \ | tmp = RB_RIGHT(parent, field); \ | ||||
RB_ROTATE_RIGHT(head, sib, tmp, field); \ | } else if (!RB_ISRED(RB_RIGHT(tmp, field), field)) { \ | ||||
sib = tmp; \ | RB_COLOR(tmp, field) = RB_RED; \ | ||||
} else if (!RB_RED_RT(sib, field)) { \ | elm = parent; \ | ||||
RB_FLIP_RT(elm, field); \ | parent = RB_PARENT(elm, field); \ | ||||
elm = par; \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (RB_RED_RT(sib, field)) \ | if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ | ||||
RB_FLIP_RT(sib, field); \ | RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ | ||||
RB_ROTATE_LEFT(head, elm, sib, field); \ | RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ | ||||
RB_FLIP_LF(sib, field); \ | RB_COLOR(parent, field) = RB_BLACK; \ | ||||
RB_ROTATE_LEFT(head, parent, tmp, field); \ | |||||
elm = RB_ROOT(head); \ | |||||
break; \ | break; \ | ||||
} else { \ | } else { \ | ||||
if (RB_RED_LF(elm, field)) { \ | tmp = RB_LEFT(parent, field); \ | ||||
red_par = RB_TRUE; \ | if (RB_COLOR(tmp, field) == RB_RED) { \ | ||||
RB_ROTATE_RIGHT(head, elm, par, field); \ | RB_SET_BLACKRED(tmp, parent, field); \ | ||||
RB_ROTATE_RIGHT(head, parent, tmp, field);\ | |||||
tmp = RB_LEFT(parent, field); \ | |||||
} \ | } \ | ||||
sib = RB_LEFT(elm, field); \ | if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \ | ||||
if (RB_RED_RT(sib, field)) { \ | struct type *oright; \ | ||||
RB_ROTATE_LEFT(head, sib, tmp, field); \ | oright = RB_RIGHT(tmp, field); \ | ||||
sib = tmp; \ | RB_COLOR(oright, field) = RB_BLACK; \ | ||||
} else if (!RB_RED_LF(sib, field)) { \ | RB_COLOR(tmp, field) = RB_RED; \ | ||||
RB_FLIP_LF(elm, field); \ | RB_ROTATE_LEFT(head, tmp, oright, field); \ | ||||
elm = par; \ | tmp = RB_LEFT(parent, field); \ | ||||
} else if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \ | |||||
RB_COLOR(tmp, field) = RB_RED; \ | |||||
elm = parent; \ | |||||
parent = RB_PARENT(elm, field); \ | |||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (RB_RED_LF(sib, field)) \ | if (RB_ISRED(RB_LEFT(tmp, field), field)) \ | ||||
RB_FLIP_LF(sib, field); \ | RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ | ||||
RB_ROTATE_RIGHT(head, elm, sib, field); \ | RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ | ||||
RB_FLIP_RT(sib, field); \ | RB_COLOR(parent, field) = RB_BLACK; \ | ||||
RB_ROTATE_RIGHT(head, parent, tmp, field); \ | |||||
elm = RB_ROOT(head); \ | |||||
break; \ | break; \ | ||||
} \ | } \ | ||||
} while (!red_par); \ | } while (!RB_ISRED(elm, field) && parent != NULL); \ | ||||
if (par != NULL && red_par) { \ | RB_COLOR(elm, field) = RB_BLACK; \ | ||||
if (left_child) \ | |||||
RB_FLIP_LF(par, field); \ | |||||
else \ | |||||
RB_FLIP_RT(par, 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, *parent_old, *right; \ | struct type *child, *old, *parent, *parent_old, *right; \ | ||||
RB_BOOL old_red, red; \ | int color; \ | ||||
\ | \ | ||||
old = elm; \ | old = elm; \ | ||||
parent_old = parent = RB_PARENT(elm, field); \ | parent_old = 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_RT(old, field); \ | RB_RIGHT(old, field) = child; \ | ||||
RB_RT(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_LF(parent, field); \ | RB_LEFT(parent, field) = child; \ | ||||
RB_LF(parent, field) = child; \ | |||||
RB_PARENT(RB_RIGHT(old, field), field) = elm; \ | RB_PARENT(RB_RIGHT(old, field), field) = elm; \ | ||||
} \ | } \ | ||||
RB_PARENT(RB_LEFT(old, field), field) = elm; \ | RB_PARENT(RB_LEFT(old, field), field) = elm; \ | ||||
color = RB_COLOR(elm, field); \ | |||||
elm->field = old->field; \ | elm->field = old->field; \ | ||||
} \ | } \ | ||||
if (parent_old == NULL) { \ | if (parent_old == NULL) \ | ||||
RB_ROOT(head) = elm; \ | RB_ROOT(head) = elm; \ | ||||
old_red = RB_FALSE; \ | else if (RB_LEFT(parent_old, field) == old) \ | ||||
} else if (RB_LEFT(parent_old, field) == old) { \ | RB_LEFT(parent_old, field) = elm; \ | ||||
old_red = RB_RED_LF(parent_old, field); \ | else \ | ||||
RB_LF(parent_old, field) = elm; \ | RB_RIGHT(parent_old, field) = elm; \ | ||||
if (old_red && parent != parent_old) \ | if (child != NULL) { \ | ||||
RB_FLIP_LF(parent_old, field); \ | |||||
} else { \ | |||||
old_red = RB_RED_RT(parent_old, field); \ | |||||
RB_RT(parent_old, field) = elm; \ | |||||
if (old_red && parent != parent_old) \ | |||||
RB_FLIP_RT(parent_old, field); \ | |||||
} \ | |||||
if (child != NULL) \ | |||||
RB_PARENT(child, field) = parent; \ | RB_PARENT(child, field) = parent; \ | ||||
else if (parent != NULL && \ | RB_COLOR(child, field) = RB_BLACK; \ | ||||
(parent != parent_old ? !red : !old_red)) \ | } 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 11 Lines | while (tmp) { \ | ||||
comp = (cmp)(elm, parent); \ | comp = (cmp)(elm, parent); \ | ||||
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_PARENT(elm, field) = parent; \ | RB_SET(elm, parent, field); \ | ||||
RB_LF(elm, field) = RB_RT(elm, field) = NULL; \ | if (parent != NULL) { \ | ||||
if (parent == NULL) \ | if (comp < 0) \ | ||||
RB_ROOT(head) = elm; \ | RB_LEFT(parent, field) = elm; \ | ||||
else if (comp < 0) \ | |||||
RB_LF(parent, field) = elm; \ | |||||
else \ | else \ | ||||
RB_RT(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 |