diff options
| -rw-r--r-- | sys/kern/subr_tree.c | 594 | ||||
| -rw-r--r-- | sys/sys/tree.h | 224 |
2 files changed, 817 insertions, 1 deletions
diff --git a/sys/kern/subr_tree.c b/sys/kern/subr_tree.c new file mode 100644 index 00000000000..4c2ba48a14d --- /dev/null +++ b/sys/kern/subr_tree.c @@ -0,0 +1,594 @@ +/* $OpenBSD */ + +/* + * Copyright 2002 Niels Provos <provos@citi.umich.edu> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <sys/param.h> +#include <sys/tree.h> + +static inline void * +rb_n2e(const struct rb_type *t, void *node) +{ + caddr_t addr = (caddr_t)node; + + return ((void *)(addr + t->t_offset)); +} + +static inline void * +rb_e2n(const struct rb_type *t, struct rb_entry *rbe) +{ + caddr_t addr = (caddr_t)rbe; + + return ((void *)(addr - t->t_offset)); +} + +#define RBE_LEFT(_rbe) (_rbe)->rbe_left +#define RBE_RIGHT(_rbe) (_rbe)->rbe_right +#define RBE_PARENT(_rbe) (_rbe)->rbe_parent +#define RBE_COLOR(_rbe) (_rbe)->rbe_color + +#define RBH_ROOT(_rbt) (_rbt)->rbt_root + +static inline void +rbe_set(struct rb_entry *rbe, struct rb_entry *parent) +{ + RBE_PARENT(rbe) = parent; + RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL; + RBE_COLOR(rbe) = RB_RED; +} + +static inline void +rbe_set_blackred(struct rb_entry *black, struct rb_entry *red) +{ + RBE_COLOR(black) = RB_BLACK; + RBE_COLOR(red) = RB_RED; +} + +static inline void +rbe_augment(const struct rb_type *t, struct rb_entry *rbe) +{ + (*t->t_augment)(rb_e2n(t, rbe)); +} + +static inline void +rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe) +{ + if (t->t_augment != NULL) + rbe_augment(t, rbe); +} + +static inline void +rbe_rotate_left(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_RIGHT(rbe); + RBE_RIGHT(rbe) = RBE_LEFT(tmp); + if (RBE_RIGHT(rbe) != NULL) + RBE_PARENT(RBE_LEFT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBH_ROOT(rbt) = tmp; + + RBE_LEFT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; + + if (t->t_augment != NULL) { + rbe_augment(t, rbe); + rbe_augment(t, tmp); + parent = RBE_PARENT(tmp); + if (parent != NULL) + rbe_augment(t, parent); + } +} + +static inline void +rbe_rotate_right(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_LEFT(rbe); + RBE_LEFT(rbe) = RBE_RIGHT(tmp); + if (RBE_LEFT(rbe) != NULL) + RBE_PARENT(RBE_RIGHT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBH_ROOT(rbt) = tmp; + + RBE_RIGHT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; + + if (t->t_augment != NULL) { + rbe_augment(t, rbe); + rbe_augment(t, tmp); + parent = RBE_PARENT(tmp); + if (parent != NULL) + rbe_augment(t, parent); + } +} + +static inline void +rbe_insert_color(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent, *gparent, *tmp; + + while ((parent = RBE_PARENT(rbe)) != NULL && + RBE_COLOR(parent) == RB_RED) { + gparent = RBE_PARENT(parent); + + if (parent == RBE_LEFT(gparent)) { + tmp = RBE_RIGHT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { + RBE_COLOR(tmp) = RB_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_RIGHT(parent) == rbe) { + rbe_rotate_left(t, rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_right(t, rbt, gparent); + } else { + tmp = RBE_LEFT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { + RBE_COLOR(tmp) = RB_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_LEFT(parent) == rbe) { + rbe_rotate_right(t, rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_left(t, rbt, gparent); + } + } + + RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK; +} + +static inline void +rbe_remove_color(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *parent, struct rb_entry *rbe) +{ + struct rb_entry *tmp; + + while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) && + rbe != RBH_ROOT(rbt)) { + if (RBE_LEFT(parent) == rbe) { + tmp = RBE_RIGHT(parent); + if (RBE_COLOR(tmp) == RB_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_left(t, rbt, parent); + tmp = RBE_RIGHT(parent); + } + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + RBE_COLOR(tmp) = RB_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) { + struct rb_entry *oleft; + + oleft = RBE_LEFT(tmp); + if (oleft != NULL) + RBE_COLOR(oleft) = RB_BLACK; + + RBE_COLOR(tmp) = RB_RED; + rbe_rotate_right(t, rbt, tmp); + tmp = RBE_RIGHT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RB_BLACK; + if (RBE_RIGHT(tmp)) + RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK; + + rbe_rotate_left(t, rbt, parent); + rbe = RBH_ROOT(rbt); + break; + } + } else { + tmp = RBE_LEFT(parent); + if (RBE_COLOR(tmp) == RB_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_right(t, rbt, parent); + tmp = RBE_LEFT(parent); + } + + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + RBE_COLOR(tmp) = RB_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) { + struct rb_entry *oright; + + oright = RBE_RIGHT(tmp); + if (oright != NULL) + RBE_COLOR(oright) = RB_BLACK; + + RBE_COLOR(tmp) = RB_RED; + rbe_rotate_left(t, rbt, tmp); + tmp = RBE_LEFT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RB_BLACK; + if (RBE_LEFT(tmp) != NULL) + RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK; + + rbe_rotate_right(t, rbt, parent); + rbe = RBH_ROOT(rbt); + break; + } + } + } + + if (rbe != NULL) + RBE_COLOR(rbe) = RB_BLACK; +} + +static inline struct rb_entry * +rbe_remove(const struct rb_type *t, struct rb_tree *rbt, struct rb_entry *rbe) +{ + struct rb_entry *child, *parent, *old = rbe; + unsigned int color; + + if (RBE_LEFT(rbe) == NULL) + child = RBE_RIGHT(rbe); + else if (RBE_RIGHT(rbe) == NULL) + child = RBE_LEFT(rbe); + else { + struct rb_entry *tmp; + + rbe = RBE_RIGHT(rbe); + while ((tmp = RBE_LEFT(rbe)) != NULL) + rbe = tmp; + + child = RBE_RIGHT(rbe); + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = child; + if (RBE_PARENT(rbe) == old) + parent = rbe; + *rbe = *old; + + tmp = RBE_PARENT(old); + if (tmp != NULL) { + if (RBE_LEFT(tmp) == old) + RBE_LEFT(tmp) = rbe; + else + RBE_RIGHT(tmp) = rbe; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = rbe; + + RBE_PARENT(RBE_LEFT(old)) = rbe; + if (RBE_RIGHT(old)) + RBE_PARENT(RBE_RIGHT(old)) = rbe; + + if (t->t_augment != NULL && parent != NULL) { + tmp = parent; + do { + rbe_augment(t, tmp); + tmp = RBE_PARENT(tmp); + } while (tmp != NULL); + } + + goto color; + } + + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = child; +color: + if (color == RB_BLACK) + rbe_remove_color(t, rbt, parent, child); + + return (old); +} + +void * +_rb_remove(const struct rb_type *t, struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + struct rb_entry *old; + + old = rbe_remove(t, rbt, rbe); + + return (old == NULL ? NULL : rb_e2n(t, old)); +} + +void * +_rb_insert(const struct rb_type *t, struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + struct rb_entry *tmp; + struct rb_entry *parent = NULL; + void *node; + int comp = 0; + + tmp = RBH_ROOT(rbt); + while (tmp != NULL) { + parent = tmp; + + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(elm, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + rbe_set(rbe, parent); + + if (parent != NULL) { + if (comp < 0) + RBE_LEFT(parent) = rbe; + else + RBE_RIGHT(parent) = rbe; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = rbe; + + rbe_insert_color(t, rbt, rbe); + + return (NULL); +} + +/* Finds the node with the same key as elm */ +void * +_rb_find(const struct rb_type *t, struct rb_tree *rbt, const void *key) +{ + struct rb_entry *tmp = RBH_ROOT(rbt); + void *node; + int comp; + + while (tmp != NULL) { + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(key, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (NULL); +} + +/* Finds the first node greater than or equal to the search key */ \ +void * +_rb_nfind(const struct rb_type *t, struct rb_tree *rbt, const void *key) +{ + struct rb_entry *tmp = RBH_ROOT(rbt); + void *node; + void *res = NULL; + int comp; + + while (tmp != NULL) { + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(key, node); + if (comp < 0) { + res = node; + tmp = RBE_LEFT(tmp); + } else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (res); +} + +void * +_rb_next(const struct rb_type *t, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + + if (RBE_RIGHT(rbe) != NULL) { + rbe = RBE_RIGHT(rbe); + while (RBE_LEFT(rbe) != NULL) + rbe = RBE_LEFT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_prev(const struct rb_type *t, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + + if (RBE_LEFT(rbe)) { + rbe = RBE_LEFT(rbe); + while (RBE_RIGHT(rbe)) + rbe = RBE_RIGHT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_root(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + + return (rbe == NULL ? rbe : rb_e2n(t, rbe)); +} + +void * +_rb_min(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_LEFT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(t, parent)); +} + +void * +_rb_max(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_RIGHT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(t, parent)); +} + +void * +_rb_left(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_LEFT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_right(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_RIGHT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_parent(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_PARENT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + diff --git a/sys/sys/tree.h b/sys/sys/tree.h index e6502b1e744..6872f4e5fa3 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -1,4 +1,4 @@ -/* $OpenBSD: tree.h,v 1.14 2015/05/25 03:07:49 deraadt Exp $ */ +/* $OpenBSD: tree.h,v 1.15 2016/09/02 11:17:14 dlg Exp $ */ /* * Copyright 2002 Niels Provos <provos@citi.umich.edu> * All rights reserved. @@ -745,4 +745,226 @@ name##_RB_MINMAX(struct name *head, int val) \ ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ (x) = (y)) +#if 0 && defined(_KERNEL) + +/* + * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <sys/param.h> /* for NULL */ + +struct rb_type { + int (*t_compare)(const void *, const void *); + void (*t_augment)(void *); + size_t t_offset; /* offset of rb_entry in type */ +}; + +struct rb_entry { + struct rb_entry *rbe_parent; + struct rb_entry *rbe_left; + struct rb_entry *rbe_right; + unsigned int rbe_color; +}; + +struct rb_tree { + struct rb_entry *rbt_root; +}; + +static inline void +_rb_init(struct rb_tree *rbt) +{ + rbt->rbt_root = NULL; +} + +static inline int +_rb_empty(struct rb_tree *rbt) +{ + return (rbt->rbt_root == NULL); +} + +void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); +void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); +void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); +void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); +void *_rb_root(const struct rb_type *, struct rb_tree *); +void *_rb_min(const struct rb_type *, struct rb_tree *); +void *_rb_max(const struct rb_type *, struct rb_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_color(const struct rb_type *, void *); + +#define RBT_HEAD(_name, _type) \ +struct _name { \ + struct rb_tree rbh_root; \ +} + +#define RBT_INITIALIZER(_head) { { NULL } } + +#define RBT_ENTRY(_type) struct rb_entry + +#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ +extern const struct rb_type *const _name##_RBT_TYPE; \ + \ +static inline void \ +_name##_RBT_INIT(struct _name *head) \ +{ \ + _rb_init(&head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ +{ \ + return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ +{ \ + return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_FIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_ROOT(struct _name *head) \ +{ \ + return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline int \ +_name##_RBT_EMPTY(struct _name *head) \ +{ \ + return _rb_empty(&head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_MIN(struct _name *head) \ +{ \ + return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_MAX(struct _name *head) \ +{ \ + return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_NEXT(struct _type *elm) \ +{ \ + return _rb_next(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_PREV(struct _type *elm) \ +{ \ + return _rb_prev(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_LEFT(struct _type *elm) \ +{ \ + return _rb_left(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_RIGHT(struct _type *elm) \ +{ \ + return _rb_right(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_PARENT(struct _type *elm) \ +{ \ + return _rb_parent(_name##_RBT_TYPE, elm); \ +} + +#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ +static int \ +_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct rb_type _name##_RBT_INFO = { \ + _name##_RBT_COMPARE, \ + _aug, \ + offsetof(struct _type, _field), \ +}; \ +const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO + +#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ +static void \ +_name##_RBT_AUGMENT(void *ptr) \ +{ \ + struct _type *p = ptr; \ + return _aug(p); \ +} \ +RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) + +#define RBT_GENERATE(_name, _type, _field, _cmp) \ + RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) + +#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) +#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) +#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) +#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) +#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) +#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) +#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) +#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) +#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) +#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) +#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) +#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) +#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) +#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) + +#define RBT_FOREACH(_e, _name, _head) \ + for ((_e) = RBT_MIN(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RBT_NEXT(_name, (_e))) + +#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ + for ((_e) = RBT_MIN(_name, (_head)); \ + (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ + (_e) = (_n)) + +#define RBT_FOREACH_REVERSE(_e, _name, _head) \ + for ((_e) = RBT_MAX(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RBT_PREV(_name, (_e))) + +#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ + for ((_e) = RBT_MAX(_name, (_head)); \ + (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ + (_e) = (_n)) + +#endif /* _KERNEL */ + #endif /* _SYS_TREE_H_ */ |