diff options
Diffstat (limited to 'lib/openbsd-tree.h')
| -rw-r--r-- | lib/openbsd-tree.h | 809 |
1 files changed, 397 insertions, 412 deletions
diff --git a/lib/openbsd-tree.h b/lib/openbsd-tree.h index 859f75167..22cb9252f 100644 --- a/lib/openbsd-tree.h +++ b/lib/openbsd-tree.h @@ -24,7 +24,7 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#ifndef _SYS_TREE_H_ +#ifndef _SYS_TREE_H_ #define _SYS_TREE_H_ /* @@ -54,26 +54,23 @@ * The maximum height of a red-black tree is 2lg (n+1). */ -#define SPLAY_HEAD(name, type) \ - struct name { \ - struct type *sph_root; /* root of the tree */ \ - } +#define SPLAY_HEAD(name, type) \ +struct name { \ + struct type *sph_root; /* root of the tree */ \ +} -#define SPLAY_INITIALIZER(root) \ - { \ - NULL \ - } +#define SPLAY_INITIALIZER(root) \ + { NULL } -#define SPLAY_INIT(root) \ - do { \ - (root)->sph_root = NULL; \ - } while (0) +#define SPLAY_INIT(root) do { \ + (root)->sph_root = NULL; \ +} while (0) -#define SPLAY_ENTRY(type) \ - struct { \ - struct type *spe_left; /* left element */ \ - struct type *spe_right; /* right element */ \ - } +#define SPLAY_ENTRY(type) \ +struct { \ + struct type *spe_left; /* left element */ \ + struct type *spe_right; /* right element */ \ +} #define SPLAY_LEFT(elm, field) (elm)->field.spe_left #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right @@ -81,220 +78,197 @@ #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ -#define SPLAY_ROTATE_RIGHT(head, tmp, field) \ - do { \ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ - } while (0) - -#define SPLAY_ROTATE_LEFT(head, tmp, field) \ - do { \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ - } while (0) - -#define SPLAY_LINKLEFT(head, tmp, field) \ - do { \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ - } while (0) - -#define SPLAY_LINKRIGHT(head, tmp, field) \ - do { \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ - } while (0) - -#define SPLAY_ASSEMBLE(head, node, left, right, field) \ - do { \ - SPLAY_RIGHT(left, field) = \ - SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_LEFT(right, field) = \ - SPLAY_RIGHT((head)->sph_root, field); \ - SPLAY_LEFT((head)->sph_root, field) = \ - SPLAY_RIGHT(node, field); \ - SPLAY_RIGHT((head)->sph_root, field) = \ - SPLAY_LEFT(node, field); \ - } while (0) +#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ +} while (0) + +#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ +} while (0) + +#define SPLAY_LINKLEFT(head, tmp, field) do { \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ +} while (0) + +#define SPLAY_LINKRIGHT(head, tmp, field) do { \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ +} while (0) + +#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ + SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ + SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ +} while (0) /* Generates prototypes and inline functions */ -#define SPLAY_PROTOTYPE(name, type, field, cmp) \ - void name##_SPLAY(struct name *, struct type *); \ - void name##_SPLAY_MINMAX(struct name *, int); \ - struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ - struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ - \ - /* Finds the node with the same key as elm */ \ - static __inline struct type *name##_SPLAY_FIND(struct name *head, \ - struct type *elm) \ - { \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) \ - return (head->sph_root); \ - return (NULL); \ - } \ - \ - static __inline struct type *name##_SPLAY_NEXT(struct name *head, \ - struct type *elm) \ - { \ - name##_SPLAY(head, elm); \ - if (SPLAY_RIGHT(elm, field) != NULL) { \ - elm = SPLAY_RIGHT(elm, field); \ - while (SPLAY_LEFT(elm, field) != NULL) { \ - elm = SPLAY_LEFT(elm, field); \ - } \ - } else \ - elm = NULL; \ - return (elm); \ - } \ - \ - static __inline struct type *name##_SPLAY_MIN_MAX(struct name *head, \ - int val) \ - { \ - name##_SPLAY_MINMAX(head, val); \ - return (SPLAY_ROOT(head)); \ - } +#define SPLAY_PROTOTYPE(name, type, field, cmp) \ +void name##_SPLAY(struct name *, struct type *); \ +void name##_SPLAY_MINMAX(struct name *, int); \ +struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ +struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ + \ +/* Finds the node with the same key as elm */ \ +static __inline struct type * \ +name##_SPLAY_FIND(struct name *head, struct type *elm) \ +{ \ + if (SPLAY_EMPTY(head)) \ + return(NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) \ + return (head->sph_root); \ + return (NULL); \ +} \ + \ +static __inline struct type * \ +name##_SPLAY_NEXT(struct name *head, struct type *elm) \ +{ \ + name##_SPLAY(head, elm); \ + if (SPLAY_RIGHT(elm, field) != NULL) { \ + elm = SPLAY_RIGHT(elm, field); \ + while (SPLAY_LEFT(elm, field) != NULL) { \ + elm = SPLAY_LEFT(elm, field); \ + } \ + } else \ + elm = NULL; \ + return (elm); \ +} \ + \ +static __inline struct type * \ +name##_SPLAY_MIN_MAX(struct name *head, int val) \ +{ \ + name##_SPLAY_MINMAX(head, val); \ + return (SPLAY_ROOT(head)); \ +} /* Main splay operation. * Moves node close to the key of elm to top */ -#define SPLAY_GENERATE(name, type, field, cmp) \ - struct type *name##_SPLAY_INSERT(struct name *head, struct type *elm) \ - { \ - if (SPLAY_EMPTY(head)) { \ - SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = \ - NULL; \ - } else { \ - int __comp; \ - name##_SPLAY(head, elm); \ - __comp = (cmp)(elm, (head)->sph_root); \ - if (__comp < 0) { \ - SPLAY_LEFT(elm, field) = \ - SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_RIGHT(elm, field) = (head)->sph_root; \ - SPLAY_LEFT((head)->sph_root, field) = NULL; \ - } else if (__comp > 0) { \ - SPLAY_RIGHT(elm, field) = \ - SPLAY_RIGHT((head)->sph_root, field); \ - SPLAY_LEFT(elm, field) = (head)->sph_root; \ - SPLAY_RIGHT((head)->sph_root, field) = NULL; \ - } else \ - return ((head)->sph_root); \ - } \ - (head)->sph_root = (elm); \ - return (NULL); \ - } \ - \ - struct type *name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ - { \ - struct type *__tmp; \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) { \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ - (head)->sph_root = \ - SPLAY_RIGHT((head)->sph_root, field); \ - } else { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - (head)->sph_root = \ - SPLAY_LEFT((head)->sph_root, field); \ - name##_SPLAY(head, elm); \ - SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ - } \ - return (elm); \ - } \ - return (NULL); \ - } \ - \ - void name##_SPLAY(struct name *head, struct type *elm) \ - { \ - struct type __node, *__left, *__right, *__tmp; \ - int __comp; \ - \ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \ - NULL; \ - __left = __right = &__node; \ - \ - while ((__comp = (cmp)(elm, (head)->sph_root))) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) < 0) { \ - SPLAY_ROTATE_RIGHT(head, __tmp, \ - field); \ - if (SPLAY_LEFT((head)->sph_root, \ - field) \ - == NULL) \ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, \ - field) \ - == NULL) \ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ - } \ - \ - /* Splay with either the minimum or the maximum element \ - * Used to find minimum or maximum element in tree. \ - */ \ - void name##_SPLAY_MINMAX(struct name *head, int __comp) \ - { \ - struct type __node, *__left, *__right, *__tmp; \ - \ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \ - NULL; \ - __left = __right = &__node; \ - \ - while (1) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp < 0) { \ - SPLAY_ROTATE_RIGHT(head, __tmp, \ - field); \ - if (SPLAY_LEFT((head)->sph_root, \ - field) \ - == NULL) \ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, \ - field) \ - == NULL) \ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ - } +#define SPLAY_GENERATE(name, type, field, cmp) \ +struct type * \ +name##_SPLAY_INSERT(struct name *head, struct type *elm) \ +{ \ + if (SPLAY_EMPTY(head)) { \ + SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ + } else { \ + int __comp; \ + name##_SPLAY(head, elm); \ + __comp = (cmp)(elm, (head)->sph_root); \ + if(__comp < 0) { \ + SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ + SPLAY_RIGHT(elm, field) = (head)->sph_root; \ + SPLAY_LEFT((head)->sph_root, field) = NULL; \ + } else if (__comp > 0) { \ + SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ + SPLAY_LEFT(elm, field) = (head)->sph_root; \ + SPLAY_RIGHT((head)->sph_root, field) = NULL; \ + } else \ + return ((head)->sph_root); \ + } \ + (head)->sph_root = (elm); \ + return (NULL); \ +} \ + \ +struct type * \ +name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ +{ \ + struct type *__tmp; \ + if (SPLAY_EMPTY(head)) \ + return (NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) { \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ + } else { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ + name##_SPLAY(head, elm); \ + SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ + } \ + return (elm); \ + } \ + return (NULL); \ +} \ + \ +void \ +name##_SPLAY(struct name *head, struct type *elm) \ +{ \ + struct type __node, *__left, *__right, *__tmp; \ + int __comp; \ +\ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ + __left = __right = &__node; \ +\ + while ((__comp = (cmp)(elm, (head)->sph_root))) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) < 0){ \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) > 0){ \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ +} \ + \ +/* Splay with either the minimum or the maximum element \ + * Used to find minimum or maximum element in tree. \ + */ \ +void name##_SPLAY_MINMAX(struct name *head, int __comp) \ +{ \ + struct type __node, *__left, *__right, *__tmp; \ +\ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ + __left = __right = &__node; \ +\ + while (1) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp < 0){ \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp > 0) { \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ +} #define SPLAY_NEGINF -1 #define SPLAY_INF 1 @@ -303,13 +277,14 @@ #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) -#define SPLAY_MIN(name, x) \ - (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) -#define SPLAY_MAX(name, x) \ - (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) - -#define SPLAY_FOREACH(x, name, head) \ - for ((x) = SPLAY_MIN(name, head); (x) != NULL; \ +#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ + : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) +#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ + : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) + +#define SPLAY_FOREACH(x, name, head) \ + for ((x) = SPLAY_MIN(name, head); \ + (x) != NULL; \ (x) = SPLAY_NEXT(name, head, x)) /* @@ -332,197 +307,203 @@ #define RB_RED 1 struct rb_type { - int (*t_compare)(const void *, const void *); - void (*t_augment)(void *); - unsigned int t_offset; /* offset of rb_entry in type */ + int (*t_compare)(const void *, const void *); + void (*t_augment)(void *); + unsigned int t_offset; /* offset of rb_entry in type */ }; struct rbt_tree { - struct rb_entry *rbt_root; + struct rb_entry *rbt_root; }; struct rb_entry { - struct rb_entry *rbt_parent; - struct rb_entry *rbt_left; - struct rb_entry *rbt_right; - unsigned int rbt_color; + struct rb_entry *rbt_parent; + struct rb_entry *rbt_left; + struct rb_entry *rbt_right; + unsigned int rbt_color; }; -#define RB_HEAD(_name, _type) \ - struct _name { \ - struct rbt_tree rbh_root; \ - } +#define RB_HEAD(_name, _type) \ +struct _name { \ + struct rbt_tree rbh_root; \ +} #define RB_ENTRY(_type) struct rb_entry -static inline void _rb_init(struct rbt_tree *rbt) +static inline void +_rb_init(struct rbt_tree *rbt) { rbt->rbt_root = NULL; } -static inline int _rb_empty(struct rbt_tree *rbt) +static inline int +_rb_empty(struct rbt_tree *rbt) { return (rbt->rbt_root == NULL); } -void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *); -void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *); -void *_rb_find(const struct rb_type *, struct rbt_tree *, const void *); -void *_rb_nfind(const struct rb_type *, struct rbt_tree *, const void *); -void *_rb_root(const struct rb_type *, struct rbt_tree *); -void *_rb_min(const struct rb_type *, struct rbt_tree *); -void *_rb_max(const struct rb_type *, struct rbt_tree *); -void *_rb_next(const struct rb_type *, void *); -void *_rb_prev(const struct rb_type *, void *); -void *_rb_left(const struct rb_type *, void *); -void *_rb_right(const struct rb_type *, void *); -void *_rb_parent(const struct rb_type *, void *); -void _rb_set_left(const struct rb_type *, void *, void *); -void _rb_set_right(const struct rb_type *, void *, void *); -void _rb_set_parent(const struct rb_type *, void *, void *); -void _rb_poison(const struct rb_type *, void *, unsigned long); -int _rb_check(const struct rb_type *, void *, unsigned long); +void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *); +void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *); +void *_rb_find(const struct rb_type *, struct rbt_tree *, const void *); +void *_rb_nfind(const struct rb_type *, struct rbt_tree *, const void *); +void *_rb_root(const struct rb_type *, struct rbt_tree *); +void *_rb_min(const struct rb_type *, struct rbt_tree *); +void *_rb_max(const struct rb_type *, struct rbt_tree *); +void *_rb_next(const struct rb_type *, void *); +void *_rb_prev(const struct rb_type *, void *); +void *_rb_left(const struct rb_type *, void *); +void *_rb_right(const struct rb_type *, void *); +void *_rb_parent(const struct rb_type *, void *); +void _rb_set_left(const struct rb_type *, void *, void *); +void _rb_set_right(const struct rb_type *, void *, void *); +void _rb_set_parent(const struct rb_type *, void *, void *); +void _rb_poison(const struct rb_type *, void *, unsigned long); +int _rb_check(const struct rb_type *, void *, unsigned long); #define RB_INITIALIZER(_head) { { NULL } } -#define RB_PROTOTYPE(_name, _type, _field, _cmp) \ - extern const struct rb_type *const _name##_RB_TYPE; \ - \ - __attribute__((__unused__)) static inline void _name##_RB_INIT( \ - struct _name *head) \ - { \ - _rb_init(&head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_INSERT(struct _name *head, struct _type *elm) \ - { \ - return _rb_insert(_name##_RB_TYPE, &head->rbh_root, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_REMOVE(struct _name *head, struct _type *elm) \ - { \ - return _rb_remove(_name##_RB_TYPE, &head->rbh_root, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_FIND(struct _name *head, const struct _type *key) \ - { \ - return _rb_find(_name##_RB_TYPE, &head->rbh_root, key); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_NFIND(struct _name *head, const struct _type *key) \ - { \ - return _rb_nfind(_name##_RB_TYPE, &head->rbh_root, key); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_ROOT(struct _name *head) \ - { \ - return _rb_root(_name##_RB_TYPE, &head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline int _name##_RB_EMPTY( \ - struct _name *head) \ - { \ - return _rb_empty(&head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_MIN(struct _name *head) \ - { \ - return _rb_min(_name##_RB_TYPE, &head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_MAX(struct _name *head) \ - { \ - return _rb_max(_name##_RB_TYPE, &head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_NEXT(struct _type *elm) \ - { \ - return _rb_next(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_PREV(struct _type *elm) \ - { \ - return _rb_prev(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_LEFT(struct _type *elm) \ - { \ - return _rb_left(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_RIGHT(struct _type *elm) \ - { \ - return _rb_right(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_PARENT(struct _type *elm) \ - { \ - return _rb_parent(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline void _name##_RB_SET_LEFT( \ - struct _type *elm, struct _type *left) \ - { \ - return _rb_set_left(_name##_RB_TYPE, elm, left); \ - } \ - \ - __attribute__((__unused__)) static inline void _name##_RB_SET_RIGHT( \ - struct _type *elm, struct _type *right) \ - { \ - return _rb_set_right(_name##_RB_TYPE, elm, right); \ - } \ - \ - __attribute__((__unused__)) static inline void _name##_RB_SET_PARENT( \ - struct _type *elm, struct _type *parent) \ - { \ - return _rb_set_parent(_name##_RB_TYPE, elm, parent); \ - } \ - \ - __attribute__((__unused__)) static inline void _name##_RB_POISON( \ - struct _type *elm, unsigned long poison) \ - { \ - return _rb_poison(_name##_RB_TYPE, elm, poison); \ - } \ - \ - __attribute__((__unused__)) static inline int _name##_RB_CHECK( \ - struct _type *elm, unsigned long poison) \ - { \ - return _rb_check(_name##_RB_TYPE, elm, poison); \ - } - -#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ - static int _name##_RB_COMPARE(const void *lptr, const void *rptr) \ - { \ - const struct _type *l = lptr, *r = rptr; \ - return _cmp(l, r); \ - } \ - static const struct rb_type _name##_RB_INFO = { \ - _name##_RB_COMPARE, _aug, offsetof(struct _type, _field), \ - }; \ - const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO; - -#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ - static void _name##_RB_AUGMENT(void *ptr) \ - { \ - struct _type *p = ptr; \ - return _aug(p); \ - } \ - RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT) - -#define RB_GENERATE(_name, _type, _field, _cmp) \ - RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) +#define RB_PROTOTYPE(_name, _type, _field, _cmp) \ +extern const struct rb_type *const _name##_RB_TYPE; \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_INIT(struct _name *head) \ +{ \ + _rb_init(&head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_INSERT(struct _name *head, struct _type *elm) \ +{ \ + return _rb_insert(_name##_RB_TYPE, &head->rbh_root, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_REMOVE(struct _name *head, struct _type *elm) \ +{ \ + return _rb_remove(_name##_RB_TYPE, &head->rbh_root, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_FIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_find(_name##_RB_TYPE, &head->rbh_root, key); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_NFIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_nfind(_name##_RB_TYPE, &head->rbh_root, key); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_ROOT(struct _name *head) \ +{ \ + return _rb_root(_name##_RB_TYPE, &head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline int \ +_name##_RB_EMPTY(struct _name *head) \ +{ \ + return _rb_empty(&head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_MIN(struct _name *head) \ +{ \ + return _rb_min(_name##_RB_TYPE, &head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_MAX(struct _name *head) \ +{ \ + return _rb_max(_name##_RB_TYPE, &head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_NEXT(struct _type *elm) \ +{ \ + return _rb_next(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_PREV(struct _type *elm) \ +{ \ + return _rb_prev(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_LEFT(struct _type *elm) \ +{ \ + return _rb_left(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_RIGHT(struct _type *elm) \ +{ \ + return _rb_right(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_PARENT(struct _type *elm) \ +{ \ + return _rb_parent(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_LEFT(struct _type *elm, struct _type *left) \ +{ \ + return _rb_set_left(_name##_RB_TYPE, elm, left); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_RIGHT(struct _type *elm, struct _type *right) \ +{ \ + return _rb_set_right(_name##_RB_TYPE, elm, right); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_PARENT(struct _type *elm, struct _type *parent) \ +{ \ + return _rb_set_parent(_name##_RB_TYPE, elm, parent); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_POISON(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_poison(_name##_RB_TYPE, elm, poison); \ +} \ + \ +__attribute__((__unused__)) static inline int \ +_name##_RB_CHECK(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_check(_name##_RB_TYPE, elm, poison); \ +} + +#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ +static int \ +_name##_RB_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct rb_type _name##_RB_INFO = { \ + _name##_RB_COMPARE, \ + _aug, \ + offsetof(struct _type, _field), \ +}; \ +const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO; + +#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ +static void \ +_name##_RB_AUGMENT(void *ptr) \ +{ \ + struct _type *p = ptr; \ + return _aug(p); \ +} \ +RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT) + +#define RB_GENERATE(_name, _type, _field, _cmp) \ + RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) #define RB_INIT(_name, _head) _name##_RB_INIT(_head) #define RB_INSERT(_name, _head, _elm) _name##_RB_INSERT(_head, _elm) @@ -544,20 +525,24 @@ int _rb_check(const struct rb_type *, void *, unsigned long); #define RB_POISON(_name, _elm, _p) _name##_RB_POISON(_elm, _p) #define RB_CHECK(_name, _elm, _p) _name##_RB_CHECK(_elm, _p) -#define RB_FOREACH(_e, _name, _head) \ - for ((_e) = RB_MIN(_name, (_head)); (_e) != NULL; \ +#define RB_FOREACH(_e, _name, _head) \ + for ((_e) = RB_MIN(_name, (_head)); \ + (_e) != NULL; \ (_e) = RB_NEXT(_name, (_e))) -#define RB_FOREACH_SAFE(_e, _name, _head, _n) \ - for ((_e) = RB_MIN(_name, (_head)); \ - (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); (_e) = (_n)) +#define RB_FOREACH_SAFE(_e, _name, _head, _n) \ + for ((_e) = RB_MIN(_name, (_head)); \ + (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); \ + (_e) = (_n)) -#define RB_FOREACH_REVERSE(_e, _name, _head) \ - for ((_e) = RB_MAX(_name, (_head)); (_e) != NULL; \ +#define RB_FOREACH_REVERSE(_e, _name, _head) \ + for ((_e) = RB_MAX(_name, (_head)); \ + (_e) != NULL; \ (_e) = RB_PREV(_name, (_e))) -#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ - for ((_e) = RB_MAX(_name, (_head)); \ - (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); (_e) = (_n)) +#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ + for ((_e) = RB_MAX(_name, (_head)); \ + (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); \ + (_e) = (_n)) -#endif /* _SYS_TREE_H_ */ +#endif /* _SYS_TREE_H_ */ |