Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 382 Lines • ▼ Show 20 Lines | |||||
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | ||||
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); \ | |||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ | #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ | ||||
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); \ | |||||
} 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 74 Lines • ▼ Show 20 Lines | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
child = elm; \ | child = elm; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (!RB_RED_RIGHT(elm, field)) { \ | if (!RB_RED_RIGHT(elm, field)) { \ | ||||
/* coverity[uninit_use] */ \ | /* coverity[uninit_use] */ \ | ||||
RB_ROTATE_LEFT(head, elm, child, field);\ | RB_ROTATE_LEFT(head, elm, child, field);\ | ||||
if (RB_RED_RIGHT(child, field)) \ | switch (RB_BITS(child, field) & \ | ||||
RB_RED_MASK) { \ | |||||
case RB_RED_R: \ | |||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(child, field)) \ | |||||
RB_FLIP_ALL(elm, field); \ | |||||
else \ | |||||
RB_FLIP_LEFT(elm, field); \ | RB_FLIP_LEFT(elm, field); \ | ||||
RB_AUGMENT(elm); \ | |||||
break; \ | |||||
default: \ | |||||
RB_FLIP_LEFT(elm, field); \ | |||||
break; \ | |||||
case RB_RED_L: \ | |||||
RB_FLIP_ALL(elm, field); \ | |||||
RB_AUGMENT(elm); \ | |||||
break; \ | |||||
} \ | |||||
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; \ | return; \ | ||||
} \ | } \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (RB_RED_LEFT(parent, field)) { \ | ||||
child = elm; \ | child = elm; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (!RB_RED_LEFT(elm, field)) { \ | if (!RB_RED_LEFT(elm, field)) { \ | ||||
/* coverity[uninit_use] */ \ | /* coverity[uninit_use] */ \ | ||||
RB_ROTATE_RIGHT(head, elm, child, field);\ | RB_ROTATE_RIGHT(head, elm, child, field);\ | ||||
if (RB_RED_LEFT(child, field)) \ | switch (RB_BITS(child, field) & \ | ||||
RB_RED_MASK) { \ | |||||
case RB_RED_L: \ | |||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(child, field)) \ | |||||
RB_FLIP_ALL(elm, field); \ | |||||
else \ | |||||
RB_FLIP_RIGHT(elm, field); \ | RB_FLIP_RIGHT(elm, field); \ | ||||
RB_AUGMENT(elm); \ | |||||
break; \ | |||||
default: \ | |||||
RB_FLIP_RIGHT(elm, field); \ | |||||
break; \ | |||||
case RB_RED_R: \ | |||||
RB_FLIP_ALL(elm, field); \ | |||||
RB_AUGMENT(elm); \ | |||||
break; \ | |||||
} \ | |||||
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(parent); \ | |||||
break; \ | break; \ | ||||
} \ | } \ | ||||
} | } | ||||
#ifndef RB_STRICT_HST | #ifndef RB_STRICT_HST | ||||
/* | /* | ||||
* In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has | * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has | ||||
* 'parent' with one higher rank, and then reduces its rank if 'parent' has | * 'parent' with one higher rank, and then reduces its rank if 'parent' has | ||||
Show All 31 Lines | if (RB_LEFT(parent, field) == elm) { \ | ||||
} \ | } \ | ||||
sib = RB_RIGHT(parent, field); \ | sib = RB_RIGHT(parent, field); \ | ||||
switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | ||||
case RB_RED_MASK: \ | case RB_RED_MASK: \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
case RB_RED_R: \ | case RB_RED_R: \ | ||||
elm = RB_LEFT(sib, field); \ | elm = sib; \ | ||||
RB_ROTATE_RIGHT(head, sib, elm, field); \ | sib = RB_LEFT(elm, field); \ | ||||
if (RB_RED_LEFT(elm, field)) \ | RB_ROTATE_RIGHT(head, elm, sib, field); \ | ||||
if (RB_RED_LEFT(sib, field)) \ | |||||
RB_FLIP_ALL(parent, field); \ | RB_FLIP_ALL(parent, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_RIGHT(elm, field)) \ | if (RB_RED_RIGHT(sib, field)) \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(elm, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_RIGHT(sib, field); \ | RB_FLIP_RIGHT(elm, field); \ | ||||
RB_BITS(elm, field) |= RB_RED_MASK; \ | RB_BITS(sib, field) |= RB_RED_MASK; \ | ||||
sib = elm; \ | RB_AUGMENT(elm); \ | ||||
break; \ | break; \ | ||||
case RB_RED_L: \ | case RB_RED_L: \ | ||||
if (RB_STRICT_HST && elm != NULL) { \ | if (RB_STRICT_HST && elm != NULL) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
break; \ | break; \ | ||||
} \ | } \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
Show All 15 Lines | if (RB_LEFT(parent, field) == elm) { \ | ||||
} \ | } \ | ||||
sib = RB_LEFT(parent, field); \ | sib = RB_LEFT(parent, field); \ | ||||
switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | ||||
case RB_RED_MASK: \ | case RB_RED_MASK: \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
case RB_RED_L: \ | case RB_RED_L: \ | ||||
elm = RB_RIGHT(sib, field); \ | elm = sib; \ | ||||
RB_ROTATE_LEFT(head, sib, elm, field); \ | sib = RB_RIGHT(elm, field); \ | ||||
if (RB_RED_RIGHT(elm, field)) \ | RB_ROTATE_LEFT(head, elm, sib, field); \ | ||||
if (RB_RED_RIGHT(sib, field)) \ | |||||
RB_FLIP_ALL(parent, field); \ | RB_FLIP_ALL(parent, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_LEFT(elm, field)) \ | if (RB_RED_LEFT(sib, field)) \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(elm, field); \ | ||||
else \ | else \ | ||||
RB_FLIP_LEFT(sib, field); \ | RB_FLIP_LEFT(elm, field); \ | ||||
RB_BITS(elm, field) |= RB_RED_MASK; \ | RB_BITS(sib, field) |= RB_RED_MASK; \ | ||||
sib = elm; \ | RB_AUGMENT(elm); \ | ||||
break; \ | break; \ | ||||
case RB_RED_R: \ | case RB_RED_R: \ | ||||
if (RB_STRICT_HST && elm != NULL) { \ | if (RB_STRICT_HST && elm != NULL) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
RB_FLIP_ALL(sib, field); \ | RB_FLIP_ALL(sib, field); \ | ||||
break; \ | break; \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
Show All 36 Lines | if ((child = RB_LEFT(right, field)) == NULL) { \ | ||||
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); \ | ||||
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) { \ | if (parent == elm && RB_LEFT(parent, field) == NULL) \ | ||||
RB_AUGMENT(parent); \ | |||||
parent = RB_PARENT(parent, field); \ | parent = RB_PARENT(parent, field); \ | ||||
do \ | |||||
RB_AUGMENT(parent); \ | |||||
while ((parent = RB_PARENT(parent, field)) != NULL); \ | |||||
} \ | } \ | ||||
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 15 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) { \ | do \ | ||||
RB_AUGMENT(elm); \ | RB_AUGMENT(elm); \ | ||||
elm = RB_PARENT(elm, field); \ | while ((elm = RB_PARENT(elm, field)) != NULL); \ | ||||
} \ | |||||
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 |