Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 721 Lines • ▼ Show 20 Lines | name##_RB_REMOVE(struct name *head, struct type *elm) \ | ||||
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) \ | ||||
{ \ | { \ | ||||
struct type *tmp; \ | struct type **tmp = &RB_ROOT(head); \ | ||||
struct type *parent = NULL; \ | struct type *parent = NULL; \ | ||||
__typeof(cmp(NULL, NULL)) comp = 0; \ | __typeof(cmp(NULL, NULL)) comp; \ | ||||
alc: This variable is now unnecessary. | |||||
tmp = RB_ROOT(head); \ | while (*tmp) { \ | ||||
alcUnsubmitted Done Inline ActionsI would try two variables: the original tmp and a new tmpp. The point being not to rely on the compiler not reloading *tmp below. alc: I would try two variables: the original tmp and a new tmpp. The point being not to rely on the… | |||||
dougmAuthorUnsubmitted Done Inline ActionsI'm happy to do that, to work around some stupid compiler someday, though it does not affect the results produced by the compiler I'm using now. dougm: I'm happy to do that, to work around some stupid compiler someday, though it does not affect… | |||||
while (tmp) { \ | parent = *tmp; \ | ||||
parent = tmp; \ | |||||
comp = (cmp)(elm, parent); \ | comp = (cmp)(elm, parent); \ | ||||
if (comp < 0) \ | if (comp < 0) \ | ||||
tmp = RB_LEFT(tmp, field); \ | tmp = &RB_LEFT(parent, field); \ | ||||
else if (comp > 0) \ | else if (comp > 0) \ | ||||
tmp = RB_RIGHT(tmp, field); \ | tmp = &RB_RIGHT(parent, field); \ | ||||
else \ | else \ | ||||
return (tmp); \ | return (parent); \ | ||||
} \ | } \ | ||||
RB_SET(elm, parent, field); \ | RB_SET(elm, parent, field); \ | ||||
if (parent == NULL) \ | *tmp = elm; \ | ||||
RB_ROOT(head) = elm; \ | |||||
else if (comp < 0) \ | |||||
RB_LEFT(parent, field) = elm; \ | |||||
else \ | |||||
RB_RIGHT(parent, field) = elm; \ | |||||
name##_RB_INSERT_COLOR(head, elm); \ | name##_RB_INSERT_COLOR(head, elm); \ | ||||
RB_UPDATE_AUGMENT(elm, field); \ | RB_UPDATE_AUGMENT(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 * \ | ||||
▲ Show 20 Lines • Show All 150 Lines • Show Last 20 Lines |
This variable is now unnecessary.