Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 408 Lines • ▼ Show 20 Lines | |||||
#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) \ | ||||
RB_PROTOTYPE_RANK(name, type, attr) \ | RB_PROTOTYPE_RANK(name, type, attr) \ | ||||
RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ | RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ | ||||
RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ | RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ | ||||
RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \ | |||||
RB_PROTOTYPE_INSERT(name, type, attr); \ | RB_PROTOTYPE_INSERT(name, type, attr); \ | ||||
RB_PROTOTYPE_REMOVE(name, type, attr); \ | RB_PROTOTYPE_REMOVE(name, type, attr); \ | ||||
RB_PROTOTYPE_FIND(name, type, attr); \ | RB_PROTOTYPE_FIND(name, type, attr); \ | ||||
RB_PROTOTYPE_NFIND(name, type, attr); \ | RB_PROTOTYPE_NFIND(name, type, attr); \ | ||||
RB_PROTOTYPE_NEXT(name, type, attr); \ | RB_PROTOTYPE_NEXT(name, type, attr); \ | ||||
RB_PROTOTYPE_INSERT_NEXT(name, type, attr); \ | |||||
RB_PROTOTYPE_PREV(name, type, attr); \ | RB_PROTOTYPE_PREV(name, type, attr); \ | ||||
RB_PROTOTYPE_INSERT_PREV(name, type, attr); \ | |||||
RB_PROTOTYPE_MINMAX(name, type, attr); \ | RB_PROTOTYPE_MINMAX(name, type, attr); \ | ||||
RB_PROTOTYPE_REINSERT(name, type, attr); | RB_PROTOTYPE_REINSERT(name, type, attr); | ||||
#ifdef _RB_DIAGNOSTIC | #ifdef _RB_DIAGNOSTIC | ||||
#define RB_PROTOTYPE_RANK(name, type, attr) \ | #define RB_PROTOTYPE_RANK(name, type, attr) \ | ||||
attr int name##_RB_RANK(struct type *); | attr int name##_RB_RANK(struct type *); | ||||
#else | #else | ||||
#define RB_PROTOTYPE_RANK(name, type, attr) | #define RB_PROTOTYPE_RANK(name, type, attr) | ||||
#endif | #endif | ||||
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ | #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ | ||||
attr struct type *name##_RB_INSERT_COLOR(struct name *, \ | attr struct type *name##_RB_INSERT_COLOR(struct name *, \ | ||||
struct type *, struct type *) | struct type *, struct type *) | ||||
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ | #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ | ||||
attr struct type *name##_RB_REMOVE_COLOR(struct name *, \ | attr struct type *name##_RB_REMOVE_COLOR(struct name *, \ | ||||
struct type *, struct type *) | struct type *, struct type *) | ||||
#define RB_PROTOTYPE_REMOVE(name, type, attr) \ | #define RB_PROTOTYPE_REMOVE(name, type, attr) \ | ||||
attr struct type *name##_RB_REMOVE(struct name *, struct type *) | attr struct type *name##_RB_REMOVE(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_INSERT_FINISH(name, type, attr) \ | |||||
attr struct type *name##_RB_INSERT_FINISH(struct name *, \ | |||||
struct type *, struct type **, struct type *) | |||||
#define RB_PROTOTYPE_INSERT(name, type, attr) \ | #define RB_PROTOTYPE_INSERT(name, type, attr) \ | ||||
attr struct type *name##_RB_INSERT(struct name *, struct type *) | attr struct type *name##_RB_INSERT(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_FIND(name, type, attr) \ | #define RB_PROTOTYPE_FIND(name, type, attr) \ | ||||
attr struct type *name##_RB_FIND(struct name *, struct type *) | attr struct type *name##_RB_FIND(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_NFIND(name, type, attr) \ | #define RB_PROTOTYPE_NFIND(name, type, attr) \ | ||||
attr struct type *name##_RB_NFIND(struct name *, struct type *) | attr struct type *name##_RB_NFIND(struct name *, struct type *) | ||||
#define RB_PROTOTYPE_NEXT(name, type, attr) \ | #define RB_PROTOTYPE_NEXT(name, type, attr) \ | ||||
attr struct type *name##_RB_NEXT(struct type *) | attr struct type *name##_RB_NEXT(struct type *) | ||||
#define RB_PROTOTYPE_INSERT_NEXT(name, type, attr) \ | |||||
attr struct type *name##_RB_INSERT_NEXT(struct name *, \ | |||||
struct type *, struct type *) | |||||
#define RB_PROTOTYPE_PREV(name, type, attr) \ | #define RB_PROTOTYPE_PREV(name, type, attr) \ | ||||
attr struct type *name##_RB_PREV(struct type *) | attr struct type *name##_RB_PREV(struct type *) | ||||
#define RB_PROTOTYPE_INSERT_PREV(name, type, attr) \ | |||||
attr struct type *name##_RB_INSERT_PREV(struct name *, \ | |||||
struct type *, struct type *) | |||||
#define RB_PROTOTYPE_MINMAX(name, type, attr) \ | #define RB_PROTOTYPE_MINMAX(name, type, attr) \ | ||||
attr struct type *name##_RB_MINMAX(struct name *, int) | attr struct type *name##_RB_MINMAX(struct name *, int) | ||||
#define RB_PROTOTYPE_REINSERT(name, type, attr) \ | #define RB_PROTOTYPE_REINSERT(name, type, attr) \ | ||||
attr struct type *name##_RB_REINSERT(struct name *, struct type *) | attr struct type *name##_RB_REINSERT(struct name *, struct type *) | ||||
/* Main rb operation. | /* Main rb operation. | ||||
* Moves node close to the key of elm to top | * Moves node close to the key of elm to top | ||||
*/ | */ | ||||
#define RB_GENERATE(name, type, field, cmp) \ | #define RB_GENERATE(name, type, field, cmp) \ | ||||
RB_GENERATE_INTERNAL(name, type, field, cmp,) | RB_GENERATE_INTERNAL(name, type, field, cmp,) | ||||
#define RB_GENERATE_STATIC(name, type, field, cmp) \ | #define RB_GENERATE_STATIC(name, type, field, cmp) \ | ||||
RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) | RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) | ||||
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ | #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ | ||||
RB_GENERATE_RANK(name, type, field, attr) \ | RB_GENERATE_RANK(name, type, field, attr) \ | ||||
RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ | RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ | ||||
RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ | RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ | ||||
RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ | |||||
RB_GENERATE_INSERT(name, type, field, cmp, attr) \ | RB_GENERATE_INSERT(name, type, field, cmp, attr) \ | ||||
RB_GENERATE_REMOVE(name, type, field, attr) \ | RB_GENERATE_REMOVE(name, type, field, attr) \ | ||||
RB_GENERATE_FIND(name, type, field, cmp, attr) \ | RB_GENERATE_FIND(name, type, field, cmp, attr) \ | ||||
RB_GENERATE_NFIND(name, type, field, cmp, attr) \ | RB_GENERATE_NFIND(name, type, field, cmp, attr) \ | ||||
RB_GENERATE_NEXT(name, type, field, attr) \ | RB_GENERATE_NEXT(name, type, field, attr) \ | ||||
RB_GENERATE_INSERT_NEXT(name, type, field, attr) \ | |||||
RB_GENERATE_PREV(name, type, field, attr) \ | RB_GENERATE_PREV(name, type, field, attr) \ | ||||
RB_GENERATE_INSERT_PREV(name, type, field, 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) | ||||
#ifdef _RB_DIAGNOSTIC | #ifdef _RB_DIAGNOSTIC | ||||
#ifndef RB_AUGMENT | #ifndef RB_AUGMENT | ||||
#define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x) | #define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x) | ||||
#else | #else | ||||
#define _RB_AUGMENT_VERIFY(x) 0 | #define _RB_AUGMENT_VERIFY(x) 0 | ||||
▲ Show 20 Lines • Show All 302 Lines • ▼ Show 20 Lines | if (parent != NULL) { \ | ||||
if (opar != NULL) { \ | if (opar != NULL) { \ | ||||
RB_AUGMENT_CHECK(opar); \ | RB_AUGMENT_CHECK(opar); \ | ||||
RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \ | RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \ | ||||
} \ | } \ | ||||
} \ | } \ | ||||
return (out); \ | return (out); \ | ||||
} | } | ||||
#define RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ | |||||
/* Inserts a node into the RB tree */ \ | |||||
attr struct type * \ | |||||
name##_RB_INSERT_FINISH(struct name *head, struct type *parent, \ | |||||
struct type **pptr, struct type *elm) \ | |||||
{ \ | |||||
struct type *tmp = NULL; \ | |||||
\ | |||||
RB_SET(elm, parent, field); \ | |||||
*pptr = elm; \ | |||||
if (parent != NULL) \ | |||||
tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ | |||||
_RB_AUGMENT_WALK(elm, tmp, field); \ | |||||
if (tmp != NULL) \ | |||||
RB_AUGMENT_CHECK(tmp); \ | |||||
return (NULL); \ | |||||
} | |||||
#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; \ | ||||
struct type **tmpp = &RB_ROOT(head); \ | struct type **tmpp = &RB_ROOT(head); \ | ||||
struct type *parent = NULL; \ | struct type *parent = NULL; \ | ||||
\ | \ | ||||
while ((tmp = *tmpp) != NULL) { \ | while ((tmp = *tmpp) != NULL) { \ | ||||
parent = tmp; \ | parent = tmp; \ | ||||
__typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \ | __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \ | ||||
if (comp < 0) \ | if (comp < 0) \ | ||||
tmpp = &RB_LEFT(parent, field); \ | tmpp = &RB_LEFT(parent, field); \ | ||||
else if (comp > 0) \ | else if (comp > 0) \ | ||||
tmpp = &RB_RIGHT(parent, field); \ | tmpp = &RB_RIGHT(parent, field); \ | ||||
else \ | else \ | ||||
return (parent); \ | return (parent); \ | ||||
} \ | } \ | ||||
RB_SET(elm, parent, field); \ | return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \ | ||||
*tmpp = elm; \ | |||||
if (parent != NULL) \ | |||||
tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ | |||||
_RB_AUGMENT_WALK(elm, tmp, field); \ | |||||
if (tmp != NULL) \ | |||||
RB_AUGMENT_CHECK(tmp); \ | |||||
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) \ | ||||
{ \ | { \ | ||||
struct type *tmp = RB_ROOT(head); \ | struct type *tmp = RB_ROOT(head); \ | ||||
▲ Show 20 Lines • Show All 45 Lines • ▼ Show 20 Lines | if (RB_RIGHT(elm, field)) { \ | ||||
while (RB_PARENT(elm, field) && \ | while (RB_PARENT(elm, field) && \ | ||||
(elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ | (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ | ||||
elm = RB_PARENT(elm, field); \ | elm = RB_PARENT(elm, field); \ | ||||
elm = RB_PARENT(elm, field); \ | elm = RB_PARENT(elm, field); \ | ||||
} \ | } \ | ||||
return (elm); \ | return (elm); \ | ||||
} | } | ||||
#define RB_GENERATE_INSERT_NEXT(name, type, field, attr) \ | |||||
/* Inserts a node into the next position in the RB tree */ \ | |||||
attr struct type * \ | |||||
name##_RB_INSERT_NEXT(struct name *head, \ | |||||
struct type *elm, struct type *next) \ | |||||
{ \ | |||||
struct type *tmp; \ | |||||
struct type **tmpp = &RB_RIGHT(elm, field); \ | |||||
\ | |||||
while ((tmp = *tmpp) != NULL) { \ | |||||
elm = tmp; \ | |||||
tmpp = &RB_LEFT(elm, field); \ | |||||
} \ | |||||
return (name##_RB_INSERT_FINISH(head, elm, tmpp, next)); \ | |||||
} | |||||
#define RB_GENERATE_PREV(name, type, field, attr) \ | #define RB_GENERATE_PREV(name, type, field, attr) \ | ||||
/* ARGSUSED */ \ | /* ARGSUSED */ \ | ||||
attr struct type * \ | attr struct type * \ | ||||
name##_RB_PREV(struct type *elm) \ | name##_RB_PREV(struct type *elm) \ | ||||
{ \ | { \ | ||||
if (RB_LEFT(elm, field)) { \ | if (RB_LEFT(elm, field)) { \ | ||||
elm = RB_LEFT(elm, field); \ | elm = RB_LEFT(elm, field); \ | ||||
while (RB_RIGHT(elm, field)) \ | while (RB_RIGHT(elm, field)) \ | ||||
elm = RB_RIGHT(elm, field); \ | elm = RB_RIGHT(elm, field); \ | ||||
} else { \ | } else { \ | ||||
while (RB_PARENT(elm, field) && \ | while (RB_PARENT(elm, field) && \ | ||||
(elm == RB_LEFT(RB_PARENT(elm, field), field))) \ | (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ | ||||
elm = RB_PARENT(elm, field); \ | elm = RB_PARENT(elm, field); \ | ||||
elm = RB_PARENT(elm, field); \ | elm = RB_PARENT(elm, field); \ | ||||
} \ | } \ | ||||
return (elm); \ | return (elm); \ | ||||
} | } | ||||
#define RB_GENERATE_INSERT_PREV(name, type, field, attr) \ | |||||
/* Inserts a node into the prev position in the RB tree */ \ | |||||
attr struct type * \ | |||||
name##_RB_INSERT_PREV(struct name *head, \ | |||||
struct type *elm, struct type *prev) \ | |||||
{ \ | |||||
struct type *tmp; \ | |||||
struct type **tmpp = &RB_LEFT(elm, field); \ | |||||
\ | |||||
while ((tmp = *tmpp) != NULL) { \ | |||||
elm = tmp; \ | |||||
tmpp = &RB_RIGHT(elm, field); \ | |||||
} \ | |||||
return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev)); \ | |||||
} | |||||
#define RB_GENERATE_MINMAX(name, type, field, attr) \ | #define RB_GENERATE_MINMAX(name, type, field, attr) \ | ||||
attr struct type * \ | attr struct type * \ | ||||
name##_RB_MINMAX(struct name *head, int val) \ | name##_RB_MINMAX(struct name *head, int val) \ | ||||
{ \ | { \ | ||||
struct type *tmp = RB_ROOT(head); \ | struct type *tmp = RB_ROOT(head); \ | ||||
struct type *parent = NULL; \ | struct type *parent = NULL; \ | ||||
while (tmp) { \ | while (tmp) { \ | ||||
parent = tmp; \ | parent = tmp; \ | ||||
Show All 20 Lines | name##_RB_REINSERT(struct name *head, struct type *elm) \ | ||||
} \ | } \ | ||||
return (NULL); \ | return (NULL); \ | ||||
} \ | } \ | ||||
#define RB_NEGINF -1 | #define RB_NEGINF -1 | ||||
#define RB_INF 1 | #define RB_INF 1 | ||||
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) | #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) | ||||
#define RB_INSERT_NEXT(name, x, y, z) name##_RB_INSERT_NEXT(x, y, z) | |||||
#define RB_INSERT_PREV(name, x, y, z) name##_RB_INSERT_PREV(x, y, z) | |||||
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) | #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) | ||||
#define RB_FIND(name, x, y) name##_RB_FIND(x, y) | #define RB_FIND(name, x, y) name##_RB_FIND(x, y) | ||||
#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) | #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) | ||||
#define RB_NEXT(name, x, y) name##_RB_NEXT(y) | #define RB_NEXT(name, x, y) name##_RB_NEXT(y) | ||||
#define RB_PREV(name, x, y) name##_RB_PREV(y) | #define RB_PREV(name, x, y) name##_RB_PREV(y) | ||||
#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) | #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) | ||||
#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) | #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) | ||||
#define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) | #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) | ||||
Show All 32 Lines |