Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 365 Lines • ▼ Show 20 Lines | |||||
/* | /* | ||||
* 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 | ||||
#define RB_UPDATE_AUGMENT(elm, field) do { \ | |||||
__typeof(elm) tmp = (elm); \ | |||||
kib: I suspect this line has inconsistent indentation | |||||
do { \ | |||||
RB_AUGMENT(tmp); \ | |||||
} while ((tmp = RB_PARENT(tmp, field)) != NULL); \ | |||||
Done Inline ActionsDon't we need the block ({}) around RB_AUGMENT() there, for macro expansion safety? kib: Don't we need the block (`{}`) around RB_AUGMENT() there, for macro expansion safety? | |||||
\ | |||||
} while (0) | |||||
Done Inline ActionsI believe CONSTCOND was the annotation for lint, which we removed quite long time ago. I do not see a need to insert it into the new code. kib: I believe CONSTCOND was the annotation for lint, which we removed quite long time ago. I do… | |||||
#define RB_SWAP_CHILD(head, out, in, field) do { \ | #define RB_SWAP_CHILD(head, out, in, field) do { \ | ||||
if (RB_PARENT(out, field) == NULL) \ | if (RB_PARENT(out, field) == NULL) \ | ||||
RB_ROOT(head) = (in); \ | RB_ROOT(head) = (in); \ | ||||
else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ | else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ | ||||
RB_LEFT(RB_PARENT(out, field), field) = (in); \ | RB_LEFT(RB_PARENT(out, field), field) = (in); \ | ||||
else \ | else \ | ||||
RB_RIGHT(RB_PARENT(out, field), field) = (in); \ | RB_RIGHT(RB_PARENT(out, field), field) = (in); \ | ||||
} while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
▲ Show 20 Lines • Show All 291 Lines • ▼ Show 20 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) { \ | RB_UPDATE_AUGMENT(parent, field); \ | ||||
RB_AUGMENT(parent); \ | |||||
parent = RB_PARENT(parent, field); \ | |||||
} \ | } \ | ||||
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) { \ | RB_UPDATE_AUGMENT(elm, field); \ | ||||
RB_AUGMENT(elm); \ | |||||
elm = RB_PARENT(elm, field); \ | |||||
} \ | |||||
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 |
I suspect this line has inconsistent indentation