Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 641 Lines • ▼ Show 20 Lines | if (RB_LEFT(parent, field) == elm) { \ | ||||
RB_ROTATE_RIGHT(head, parent, sib, field); \ | RB_ROTATE_RIGHT(head, parent, sib, field); \ | ||||
} \ | } \ | ||||
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 *out) \ | ||||
{ \ | { \ | ||||
struct type *child, *old, *parent, *right; \ | struct type *child, *in, *left, *parent, *right; \ | ||||
\ | \ | ||||
old = elm; \ | left = RB_LEFT(out, field); \ | ||||
parent = RB_PARENT(elm, field); \ | right = RB_RIGHT(out, field); \ | ||||
right = RB_RIGHT(elm, field); \ | if (left == NULL || right == NULL) { \ | ||||
if (RB_LEFT(elm, field) == NULL) \ | child = in = (left == NULL) ? right : left; \ | ||||
elm = child = right; \ | parent = RB_PARENT(out, field); \ | ||||
else if (right == NULL) \ | |||||
elm = child = RB_LEFT(elm, field); \ | |||||
else { \ | |||||
if ((child = RB_LEFT(right, field)) == NULL) { \ | |||||
child = RB_RIGHT(right, field); \ | |||||
RB_RIGHT(old, field) = child; \ | |||||
parent = elm = right; \ | |||||
} else { \ | } else { \ | ||||
do \ | if ((in = RB_LEFT(right, field)) != NULL) { \ | ||||
elm = child; \ | parent = right; \ | ||||
while ((child = RB_LEFT(elm, field)) != NULL); \ | while (RB_LEFT(in, field) != NULL) { \ | ||||
child = RB_RIGHT(elm, field); \ | parent = in; \ | ||||
parent = RB_PARENT(elm, field); \ | in = RB_LEFT(parent, field); \ | ||||
} \ | |||||
child = RB_RIGHT(in, field); \ | |||||
RB_LEFT(parent, field) = child; \ | RB_LEFT(parent, field) = child; \ | ||||
RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\ | RB_SET_PARENT(left, in, field); \ | ||||
RB_SET_PARENT(right, in, field); \ | |||||
} else if ((in = RB_RIGHT(left, field)) != NULL) { \ | |||||
parent = left; \ | |||||
if (RB_RIGHT(in, field) != NULL) { \ | |||||
parent = in; \ | |||||
in = RB_RIGHT(parent, field); \ | |||||
child = NULL; \ | |||||
} else \ | |||||
child = RB_LEFT(in, field); \ | |||||
RB_RIGHT(parent, field) = child; \ | |||||
RB_SET_PARENT(left, in, field); \ | |||||
RB_SET_PARENT(right, in, field); \ | |||||
} else if ((child = RB_LEFT(left, field)) == NULL && \ | |||||
(child = RB_RIGHT(right, field)) != NULL) { \ | |||||
parent = in = right; \ | |||||
RB_RIGHT(out, field) = child; \ | |||||
RB_SET_PARENT(left, in, field); \ | |||||
} else { \ | |||||
parent = in = left; \ | |||||
RB_LEFT(out, field) = child; \ | |||||
RB_SET_PARENT(right, in, field); \ | |||||
} \ | } \ | ||||
RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ | in->field = out->field; \ | ||||
elm->field = old->field; \ | |||||
} \ | } \ | ||||
RB_SWAP_CHILD(head, old, elm, field); \ | RB_SWAP_CHILD(head, out, in, 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) { \ | while (parent != NULL) { \ | ||||
RB_AUGMENT(parent); \ | RB_AUGMENT(parent); \ | ||||
parent = RB_PARENT(parent, field); \ | parent = RB_PARENT(parent, field); \ | ||||
} \ | } \ | ||||
return (old); \ | return (out); \ | ||||
} | } | ||||
#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) \ | ||||
{ \ | { \ | ||||
struct type *tmp; \ | struct type *tmp; \ | ||||
▲ Show 20 Lines • Show All 181 Lines • Show Last 20 Lines |