im sending this diff out so marc.info backs it up for me.
avl trees are just binary search trees with a specific implementation
of insert and delete so the trees remain balanced. rb trees are the
same, so the diff factors the common functionality (which is
everything except insert and remove) into common binary search tree
code, and aliased the RBT and AVL functionality to that.
so the only interesting bit in this is the avl insert and delete code.
the implementation here has the avl nodes record their balance
rather than height (depth?), and performs the rotations when the
balance increases too much.
to use it, just pretend its RBT code but use AVL in all the names
instead.
Index: sys/tree.h
===================================================================
RCS file: /cvs/src/sys/sys/tree.h,v
retrieving revision 1.25
diff -u -p -d -r1.25 tree.h
--- sys/tree.h 26 Sep 2016 08:08:51 -0000 1.25
+++ sys/tree.h 31 Oct 2016 03:20:25 -0000
@@ -764,159 +764,167 @@ name##_RB_MINMAX(struct name *head, int
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
-struct rb_type {
+struct bst_type {
int (*t_compare)(const void *, const void *);
- void (*t_augment)(void *);
unsigned int t_offset; /* offset of rb_entry in type */
};
-struct rb_tree {
- struct rb_entry *rbt_root;
+struct bst_entry {
+ struct bst_entry *bst_parent;
+ struct bst_entry *bst_children[2];
+ unsigned int bst_data;
};
-struct rb_entry {
- struct rb_entry *rbt_parent;
- struct rb_entry *rbt_left;
- struct rb_entry *rbt_right;
- unsigned int rbt_color;
+struct bstree {
+ struct bst_entry *bst_root;
};
-#define RBT_HEAD(_name, _type) \
-struct _name { \
- struct rb_tree rbh_root; \
-}
-
-#define RBT_ENTRY(_type) struct rb_entry
-
-#ifdef _KERNEL
+#define BST_INITIALIZER() { NULL }
static inline void
-_rb_init(struct rb_tree *rbt)
+_bst_init(struct bstree *bst)
{
- rbt->rbt_root = NULL;
+ bst->bst_root = NULL;
}
static inline int
-_rb_empty(struct rb_tree *rbt)
+_bst_empty(struct bstree *bst)
{
- return (rbt->rbt_root == NULL);
+ return (bst->bst_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 *);
-void _rb_poison(const struct rb_type *, void *, unsigned long);
-int _rb_check(const struct rb_type *, void *, unsigned long);
+void *_bst_find(const struct bst_type *, struct bstree *, const void *);
+void *_bst_nfind(const struct bst_type *, struct bstree *, const void *);
+void *_bst_root(const struct bst_type *, struct bstree *);
+void *_bst_min(const struct bst_type *, struct bstree *);
+void *_bst_max(const struct bst_type *, struct bstree *);
+void *_bst_next(const struct bst_type *, void *);
+void *_bst_prev(const struct bst_type *, void *);
+void *_bst_left(const struct bst_type *, void *);
+void *_bst_right(const struct bst_type *, void *);
+void *_bst_parent(const struct bst_type *, void *);
+void _bst_poison(const struct bst_type *, void *, unsigned long);
+int _bst_check(const struct bst_type *, void *, unsigned long);
-#define RBT_INITIALIZER(_head) { { NULL } }
+/*
+ * red-black tree
+ */
+struct rbt_type {
+ void (*t_augment)(void *);
+ struct bst_type t_bst;
+};
+
+#define RBT_HEAD(_name, _type) \
+struct _name { \
+ struct bstree rb_tree; \
+}
+
+#define RBT_ENTRY(_type) struct bst_entry
+
+#define RBT_INITIALIZER(_head) { BST_INITIALIZER() }
+
+void *_rbt_insert(const struct rbt_type *, struct bstree *, void *);
+void *_rbt_remove(const struct rbt_type *, struct bstree *, void *);
#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \
-extern const struct rb_type *const _name##_RBT_TYPE; \
+extern const struct rbt_type _name##_RBT_TYPE; \
\
__unused static inline void \
_name##_RBT_INIT(struct _name *head) \
{ \
- _rb_init(&head->rbh_root); \
+ _bst_init(&head->rb_tree); \
} \
\
__unused static inline struct _type * \
_name##_RBT_INSERT(struct _name *head, struct _type *elm) \
{ \
- return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \
+ return _rbt_insert(&_name##_RBT_TYPE, &head->rb_tree, elm); \
} \
\
__unused static inline struct _type * \
_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \
{ \
- return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \
+ return _rbt_remove(&_name##_RBT_TYPE, &head->rb_tree, elm); \
} \
\
__unused static inline struct _type * \
_name##_RBT_FIND(struct _name *head, const struct _type *key) \
{ \
- return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \
+ return _bst_find(&_name##_RBT_TYPE.t_bst, \
+ &head->rb_tree, key); \
} \
\
__unused static inline struct _type * \
_name##_RBT_NFIND(struct _name *head, const struct _type *key) \
{ \
- return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \
+ return _bst_nfind(&_name##_RBT_TYPE.t_bst, \
+ &head->rb_tree, key); \
} \
\
__unused static inline struct _type * \
_name##_RBT_ROOT(struct _name *head) \
{ \
- return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \
+ return _bst_root(&_name##_RBT_TYPE.t_bst, &head->rb_tree); \
} \
\
__unused static inline int \
_name##_RBT_EMPTY(struct _name *head) \
{ \
- return _rb_empty(&head->rbh_root); \
+ return _bst_empty(&head->rb_tree); \
} \
\
__unused static inline struct _type * \
_name##_RBT_MIN(struct _name *head) \
{ \
- return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \
+ return _bst_min(&_name##_RBT_TYPE.t_bst, &head->rb_tree); \
} \
\
__unused static inline struct _type * \
_name##_RBT_MAX(struct _name *head) \
{ \
- return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \
+ return _bst_max(&_name##_RBT_TYPE.t_bst, &head->rb_tree); \
} \
\
__unused static inline struct _type * \
_name##_RBT_NEXT(struct _type *elm) \
{ \
- return _rb_next(_name##_RBT_TYPE, elm); \
+ return _bst_next(&_name##_RBT_TYPE.t_bst, elm); \
} \
\
__unused static inline struct _type * \
_name##_RBT_PREV(struct _type *elm) \
{ \
- return _rb_prev(_name##_RBT_TYPE, elm); \
+ return _bst_prev(&_name##_RBT_TYPE.t_bst, elm); \
} \
\
__unused static inline struct _type * \
_name##_RBT_LEFT(struct _type *elm) \
{ \
- return _rb_left(_name##_RBT_TYPE, elm); \
+ return _bst_left(&_name##_RBT_TYPE.t_bst, elm); \
} \
\
__unused static inline struct _type * \
_name##_RBT_RIGHT(struct _type *elm) \
{ \
- return _rb_right(_name##_RBT_TYPE, elm); \
+ return _bst_right(&_name##_RBT_TYPE.t_bst, elm); \
} \
\
__unused static inline struct _type * \
_name##_RBT_PARENT(struct _type *elm) \
{ \
- return _rb_parent(_name##_RBT_TYPE, elm); \
+ return _bst_parent(&_name##_RBT_TYPE.t_bst, elm); \
} \
\
__unused static inline void \
_name##_RBT_POISON(struct _type *elm, unsigned long poison) \
{ \
- return _rb_poison(_name##_RBT_TYPE, elm, poison); \
+ return _bst_poison(&_name##_RBT_TYPE.t_bst, elm, poison); \
} \
\
__unused static inline int \
_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \
{ \
- return _rb_check(_name##_RBT_TYPE, elm, poison); \
+ return _bst_check(&_name##_RBT_TYPE.t_bst, elm, poison); \
}
#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug)
\
@@ -926,12 +934,13 @@ _name##_RBT_COMPARE(const void *lptr, co
const struct _type *l = lptr, *r = rptr; \
return _cmp(l, r); \
} \
-static const struct rb_type _name##_RBT_INFO = { \
- _name##_RBT_COMPARE, \
+const struct rbt_type _name##_RBT_TYPE = { \
_aug, \
- offsetof(struct _type, _field), \
-}; \
-const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO
+ { \
+ _name##_RBT_COMPARE, \
+ offsetof(struct _type, _field), \
+ }, \
+}
#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \
static void \
@@ -982,6 +991,169 @@ RBT_GENERATE_INTERNAL(_name, _type, _fie
(_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \
(_e) = (_n))
-#endif /* _KERNEL */
+/*
+ * AVL tree
+ */
+
+#define AVL_HEAD(_name, _type) \
+struct _name { \
+ struct bstree avl_tree; \
+}
+
+#define AVL_ENTRY(_type) struct bst_entry
+
+#define AVL_INITIALIZER(_head) { BST_INITIALIZER() }
+
+void *_avl_insert(const struct bst_type *, struct bstree *, void *);
+void *_avl_remove(const struct bst_type *, struct bstree *, void *);
+
+#define AVL_PROTOTYPE(_name, _type, _field, _cmp) \
+extern const struct bst_type _name##_AVL_TYPE; \
+ \
+__unused static inline void \
+_name##_AVL_INIT(struct _name *head) \
+{ \
+ _bst_init(&head->avl_tree); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_INSERT(struct _name *head, struct _type *elm) \
+{ \
+ return _avl_insert(&_name##_AVL_TYPE, &head->avl_tree, elm); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_REMOVE(struct _name *head, struct _type *elm) \
+{ \
+ return _avl_remove(&_name##_AVL_TYPE, &head->avl_tree, elm); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_FIND(struct _name *head, const struct _type *key) \
+{ \
+ return _bst_find(&_name##_AVL_TYPE, &head->avl_tree, key); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_NFIND(struct _name *head, const struct _type *key) \
+{ \
+ return _bst_nfind(&_name##_AVL_TYPE, &head->avl_tree, key); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_ROOT(struct _name *head) \
+{ \
+ return _bst_root(&_name##_AVL_TYPE, &head->avl_tree); \
+} \
+ \
+__unused static inline int \
+_name##_AVL_EMPTY(struct _name *head) \
+{ \
+ return _bst_empty(&head->avl_tree); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_MIN(struct _name *head) \
+{ \
+ return _bst_min(&_name##_AVL_TYPE, &head->avl_tree); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_MAX(struct _name *head) \
+{ \
+ return _bst_max(&_name##_AVL_TYPE, &head->avl_tree); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_NEXT(struct _type *elm) \
+{ \
+ return _bst_next(&_name##_AVL_TYPE, elm); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_PREV(struct _type *elm) \
+{ \
+ return _bst_prev(&_name##_AVL_TYPE, elm); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_LEFT(struct _type *elm) \
+{ \
+ return _bst_left(&_name##_AVL_TYPE, elm); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_RIGHT(struct _type *elm) \
+{ \
+ return _bst_right(&_name##_AVL_TYPE, elm); \
+} \
+ \
+__unused static inline struct _type * \
+_name##_AVL_PARENT(struct _type *elm) \
+{ \
+ return _bst_parent(&_name##_AVL_TYPE, elm); \
+} \
+ \
+__unused static inline void \
+_name##_AVL_POISON(struct _type *elm, unsigned long poison) \
+{ \
+ return _bst_poison(&_name##_AVL_TYPE, elm, poison); \
+} \
+ \
+__unused static inline int \
+_name##_AVL_CHECK(struct _type *elm, unsigned long poison) \
+{ \
+ return _bst_check(&_name##_AVL_TYPE, elm, poison); \
+}
+
+#define AVL_GENERATE(_name, _type, _field, _cmp) \
+static int \
+_name##_AVL_COMPARE(const void *lptr, const void *rptr)
\
+{ \
+ const struct _type *l = lptr, *r = rptr; \
+ return _cmp(l, r); \
+} \
+const struct bst_type _name##_AVL_TYPE = { \
+ _name##_AVL_COMPARE, \
+ offsetof(struct _type, _field), \
+}
+
+#define AVL_INIT(_name, _head) _name##_AVL_INIT(_head)
+#define AVL_INSERT(_name, _head, _elm) _name##_AVL_INSERT(_head, _elm)
+#define AVL_REMOVE(_name, _head, _elm) _name##_AVL_REMOVE(_head, _elm)
+#define AVL_FIND(_name, _head, _key) _name##_AVL_FIND(_head, _key)
+#define AVL_NFIND(_name, _head, _key) _name##_AVL_NFIND(_head, _key)
+#define AVL_ROOT(_name, _head) _name##_AVL_ROOT(_head)
+#define AVL_EMPTY(_name, _head) _name##_AVL_EMPTY(_head)
+#define AVL_MIN(_name, _head) _name##_AVL_MIN(_head)
+#define AVL_MAX(_name, _head) _name##_AVL_MAX(_head)
+#define AVL_NEXT(_name, _elm) _name##_AVL_NEXT(_elm)
+#define AVL_PREV(_name, _elm) _name##_AVL_PREV(_elm)
+#define AVL_LEFT(_name, _elm) _name##_AVL_LEFT(_elm)
+#define AVL_RIGHT(_name, _elm) _name##_AVL_RIGHT(_elm)
+#define AVL_PARENT(_name, _elm) _name##_AVL_PARENT(_elm)
+#define AVL_POISON(_name, _elm, _p) _name##_AVL_POISON(_elm, _p)
+#define AVL_CHECK(_name, _elm, _p) _name##_AVL_CHECK(_elm, _p)
+
+#define AVL_FOREACH(_e, _name, _head) \
+ for ((_e) = AVL_MIN(_name, (_head)); \
+ (_e) != NULL; \
+ (_e) = AVL_NEXT(_name, (_e)))
+
+#define AVL_FOREACH_SAFE(_e, _name, _head, _n) \
+ for ((_e) = AVL_MIN(_name, (_head)); \
+ (_e) != NULL && ((_n) = AVL_NEXT(_name, (_e)), 1); \
+ (_e) = (_n))
+
+#define AVL_FOREACH_REVERSE(_e, _name, _head) \
+ for ((_e) = AVL_MAX(_name, (_head)); \
+ (_e) != NULL; \
+ (_e) = AVL_PREV(_name, (_e)))
+
+#define AVL_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \
+ for ((_e) = AVL_MAX(_name, (_head)); \
+ (_e) != NULL && ((_n) = AVL_PREV(_name, (_e)), 1); \
+ (_e) = (_n))
+
#endif /* _SYS_TREE_H_ */
Index: kern/subr_tree.c
===================================================================
RCS file: /cvs/src/sys/kern/subr_tree.c,v
retrieving revision 1.6
diff -u -p -d -r1.6 subr_tree.c
--- kern/subr_tree.c 20 Sep 2016 01:11:27 -0000 1.6
+++ kern/subr_tree.c 31 Oct 2016 03:20:25 -0000
@@ -44,63 +44,264 @@
#include <sys/param.h>
#include <sys/tree.h>
-static inline void *
-rb_n2e(const struct rb_type *t, void *node)
+static inline struct bst_entry *
+bst_n2e(const struct bst_type *t, void *node)
{
- caddr_t addr = (caddr_t)node;
+ unsigned long addr = (unsigned long)node;
- return ((void *)(addr + t->t_offset));
+ return ((struct bst_entry *)(addr + t->t_offset));
}
static inline void *
-rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
+bst_e2n(const struct bst_type *t, struct bst_entry *rbe)
{
- caddr_t addr = (caddr_t)rbe;
+ unsigned long addr = (unsigned long)rbe;
return ((void *)(addr - t->t_offset));
}
-#define RBE_LEFT(_rbe) (_rbe)->rbt_left
-#define RBE_RIGHT(_rbe) (_rbe)->rbt_right
-#define RBE_PARENT(_rbe) (_rbe)->rbt_parent
-#define RBE_COLOR(_rbe) (_rbe)->rbt_color
+#define BST_CHILD(_bse, _c) (_bse)->bst_children[(_c)]
+#define BST_LEFT(_bse) BST_CHILD((_bse), 0)
+#define BST_RIGHT(_bse) BST_CHILD((_bse), 1)
+#define BST_PARENT(_bse) (_bse)->bst_parent
+#define BST_DATA(_bse) (_bse)->bst_data
-#define RBH_ROOT(_rbt) (_rbt)->rbt_root
+#define BST_ROOT(_bst) (_bst)->bst_root
+
+/* Finds the node with the same key as elm */
+void *
+_bst_find(const struct bst_type *t, struct bstree *bst, const void *key)
+{
+ struct bst_entry *tmp = BST_ROOT(bst);
+ void *node;
+ int comp;
+
+ while (tmp != NULL) {
+ node = bst_e2n(t, tmp);
+ comp = (*t->t_compare)(key, node);
+ if (comp < 0)
+ tmp = BST_LEFT(tmp);
+ else if (comp > 0)
+ tmp = BST_RIGHT(tmp);
+ else
+ return (node);
+ }
+
+ return (NULL);
+}
+
+/* Finds the first node greater than or equal to the search key */
+void *
+_bst_nfind(const struct bst_type *t, struct bstree *bst, const void *key)
+{
+ struct bst_entry *tmp = BST_ROOT(bst);
+ void *node;
+ void *res = NULL;
+ int comp;
+
+ while (tmp != NULL) {
+ node = bst_e2n(t, tmp);
+ comp = (*t->t_compare)(key, node);
+ if (comp < 0) {
+ res = node;
+ tmp = BST_LEFT(tmp);
+ } else if (comp > 0)
+ tmp = BST_RIGHT(tmp);
+ else
+ return (node);
+ }
+
+ return (res);
+}
+
+void *
+_bst_next(const struct bst_type *t, void *elm)
+{
+ struct bst_entry *bste = bst_n2e(t, elm);
+
+ if (BST_RIGHT(bste) != NULL) {
+ bste = BST_RIGHT(bste);
+ while (BST_LEFT(bste) != NULL)
+ bste = BST_LEFT(bste);
+ } else {
+ if (BST_PARENT(bste) != NULL &&
+ (bste == BST_LEFT(BST_PARENT(bste))))
+ bste = BST_PARENT(bste);
+ else {
+ while (BST_PARENT(bste) != NULL &&
+ (bste == BST_RIGHT(BST_PARENT(bste))))
+ bste = BST_PARENT(bste);
+ bste = BST_PARENT(bste);
+ }
+ }
+
+ return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_prev(const struct bst_type *t, void *elm)
+{
+ struct bst_entry *bste = bst_n2e(t, elm);
+
+ if (BST_LEFT(bste) != NULL) {
+ bste = BST_LEFT(bste);
+ while (BST_RIGHT(bste) != NULL)
+ bste = BST_RIGHT(bste);
+ } else {
+ if (BST_PARENT(bste) != NULL &&
+ (bste == BST_RIGHT(BST_PARENT(bste))))
+ bste = BST_PARENT(bste);
+ else {
+ while (BST_PARENT(bste) != NULL &&
+ (bste == BST_LEFT(BST_PARENT(bste))))
+ bste = BST_PARENT(bste);
+ bste = BST_PARENT(bste);
+ }
+ }
+
+ return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_root(const struct bst_type *t, struct bstree *bst)
+{
+ struct bst_entry *bste = BST_ROOT(bst);
+
+ return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_min(const struct bst_type *t, struct bstree *bst)
+{
+ struct bst_entry *bste = BST_ROOT(bst);
+ struct bst_entry *parent = NULL;
+
+ while (bste != NULL) {
+ parent = bste;
+ bste = BST_LEFT(bste);
+ }
+
+ return (parent == NULL ? NULL : bst_e2n(t, parent));
+}
+
+void *
+_bst_max(const struct bst_type *t, struct bstree *bst)
+{
+ struct bst_entry *bste = BST_ROOT(bst);
+ struct bst_entry *parent = NULL;
+
+ while (bste != NULL) {
+ parent = bste;
+ bste = BST_RIGHT(bste);
+ }
+
+ return (parent == NULL ? NULL : bst_e2n(t, parent));
+}
+
+void *
+_bst_left(const struct bst_type *t, void *node)
+{
+ struct bst_entry *bste = bst_n2e(t, node);
+ bste = BST_LEFT(bste);
+ return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_right(const struct bst_type *t, void *node)
+{
+ struct bst_entry *bste = bst_n2e(t, node);
+ bste = BST_RIGHT(bste);
+ return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_parent(const struct bst_type *t, void *node)
+{
+ struct bst_entry *bste = bst_n2e(t, node);
+ bste = BST_PARENT(bste);
+ return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void
+_bst_poison(const struct bst_type *t, void *node, unsigned long poison)
+{
+ struct bst_entry *bste = bst_n2e(t, node);
+
+ BST_PARENT(bste) = BST_LEFT(bste) = BST_RIGHT(bste) =
+ (struct bst_entry *)poison;
+}
+
+int
+_bst_check(const struct bst_type *t, void *node, unsigned long poison)
+{
+ struct bst_entry *bste = bst_n2e(t, node);
+
+ return ((unsigned long)BST_PARENT(bste) == poison &&
+ (unsigned long)BST_LEFT(bste) == poison &&
+ (unsigned long)BST_RIGHT(bste) == poison);
+}
+
+/*
+ * Red-Black Trees
+ */
+
+static inline struct bst_entry *
+rbt_n2e(const struct rbt_type *t, void *node)
+{
+ return bst_n2e(&t->t_bst, node);
+}
+
+static inline void *
+rbt_e2n(const struct rbt_type *t, struct bst_entry *rbe)
+{
+ return bst_e2n(&t->t_bst, rbe);
+}
+
+#define RBE_BLACK 0
+#define RBE_RED 1
+
+#define RBE_CHILD(_rbe, _c) BST_CHILD((_rbe), (_c))
+#define RBE_LEFT(_rbe) BST_LEFT(_rbe)
+#define RBE_RIGHT(_rbe) BST_RIGHT(_rbe)
+#define RBE_PARENT(_rbe) BST_PARENT(_rbe)
+#define RBE_COLOR(_rbe) BST_DATA(_rbe)
+
+#define RBH_ROOT(_rbt) BST_ROOT(_rbt)
static inline void
-rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
+rbe_set(struct bst_entry *rbe, struct bst_entry *parent)
{
RBE_PARENT(rbe) = parent;
RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
- RBE_COLOR(rbe) = RB_RED;
+ RBE_COLOR(rbe) = RBE_RED;
}
static inline void
-rbe_set_blackred(struct rb_entry *black, struct rb_entry *red)
+rbe_set_blackred(struct bst_entry *black, struct bst_entry *red)
{
- RBE_COLOR(black) = RB_BLACK;
- RBE_COLOR(red) = RB_RED;
+ RBE_COLOR(black) = RBE_BLACK;
+ RBE_COLOR(red) = RBE_RED;
}
static inline void
-rbe_augment(const struct rb_type *t, struct rb_entry *rbe)
+rbe_augment(const struct rbt_type *t, struct bst_entry *rbe)
{
- (*t->t_augment)(rb_e2n(t, rbe));
+ (*t->t_augment)(rbt_e2n(t, rbe));
}
static inline void
-rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
+rbe_if_augment(const struct rbt_type *t, struct bst_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)
+rbe_rotate_left(const struct rbt_type *t, struct bstree *rbt,
+ struct bst_entry *rbe)
{
- struct rb_entry *parent;
- struct rb_entry *tmp;
+ struct bst_entry *parent;
+ struct bst_entry *tmp;
tmp = RBE_RIGHT(rbe);
RBE_RIGHT(rbe) = RBE_LEFT(tmp);
@@ -130,11 +331,11 @@ rbe_rotate_left(const struct rb_type *t,
}
static inline void
-rbe_rotate_right(const struct rb_type *t, struct rb_tree *rbt,
- struct rb_entry *rbe)
+rbe_rotate_right(const struct rbt_type *t, struct bstree *rbt,
+ struct bst_entry *rbe)
{
- struct rb_entry *parent;
- struct rb_entry *tmp;
+ struct bst_entry *parent;
+ struct bst_entry *tmp;
tmp = RBE_LEFT(rbe);
RBE_LEFT(rbe) = RBE_RIGHT(tmp);
@@ -164,19 +365,19 @@ rbe_rotate_right(const struct rb_type *t
}
static inline void
-rbe_insert_color(const struct rb_type *t, struct rb_tree *rbt,
- struct rb_entry *rbe)
+rbe_insert_color(const struct rbt_type *t, struct bstree *rbt,
+ struct bst_entry *rbe)
{
- struct rb_entry *parent, *gparent, *tmp;
+ struct bst_entry *parent, *gparent, *tmp;
while ((parent = RBE_PARENT(rbe)) != NULL &&
- RBE_COLOR(parent) == RB_RED) {
+ RBE_COLOR(parent) == RBE_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;
+ if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) {
+ RBE_COLOR(tmp) = RBE_BLACK;
rbe_set_blackred(parent, gparent);
rbe = gparent;
continue;
@@ -193,8 +394,8 @@ rbe_insert_color(const struct rb_type *t
rbe_rotate_right(t, rbt, gparent);
} else {
tmp = RBE_LEFT(gparent);
- if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
- RBE_COLOR(tmp) = RB_BLACK;
+ if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) {
+ RBE_COLOR(tmp) = RBE_BLACK;
rbe_set_blackred(parent, gparent);
rbe = gparent;
continue;
@@ -212,49 +413,49 @@ rbe_insert_color(const struct rb_type *t
}
}
- RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
+ RBE_COLOR(RBH_ROOT(rbt)) = RBE_BLACK;
}
static inline void
-rbe_remove_color(const struct rb_type *t, struct rb_tree *rbt,
- struct rb_entry *parent, struct rb_entry *rbe)
+rbe_remove_color(const struct rbt_type *t, struct bstree *rbt,
+ struct bst_entry *parent, struct bst_entry *rbe)
{
- struct rb_entry *tmp;
+ struct bst_entry *tmp;
- while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) &&
+ while ((rbe == NULL || RBE_COLOR(rbe) == RBE_BLACK) &&
rbe != RBH_ROOT(rbt)) {
if (RBE_LEFT(parent) == rbe) {
tmp = RBE_RIGHT(parent);
- if (RBE_COLOR(tmp) == RB_RED) {
+ if (RBE_COLOR(tmp) == RBE_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_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) &&
(RBE_RIGHT(tmp) == NULL ||
- RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
- RBE_COLOR(tmp) = RB_RED;
+ RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK)) {
+ RBE_COLOR(tmp) = RBE_RED;
rbe = parent;
parent = RBE_PARENT(rbe);
} else {
if (RBE_RIGHT(tmp) == NULL ||
- RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
- struct rb_entry *oleft;
+ RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK) {
+ struct bst_entry *oleft;
oleft = RBE_LEFT(tmp);
if (oleft != NULL)
- RBE_COLOR(oleft) = RB_BLACK;
+ RBE_COLOR(oleft) = RBE_BLACK;
- RBE_COLOR(tmp) = RB_RED;
+ RBE_COLOR(tmp) = RBE_RED;
rbe_rotate_right(t, rbt, tmp);
tmp = RBE_RIGHT(parent);
}
RBE_COLOR(tmp) = RBE_COLOR(parent);
- RBE_COLOR(parent) = RB_BLACK;
+ RBE_COLOR(parent) = RBE_BLACK;
if (RBE_RIGHT(tmp))
- RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
+ RBE_COLOR(RBE_RIGHT(tmp)) = RBE_BLACK;
rbe_rotate_left(t, rbt, parent);
rbe = RBH_ROOT(rbt);
@@ -262,37 +463,37 @@ rbe_remove_color(const struct rb_type *t
}
} else {
tmp = RBE_LEFT(parent);
- if (RBE_COLOR(tmp) == RB_RED) {
+ if (RBE_COLOR(tmp) == RBE_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_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) &&
(RBE_RIGHT(tmp) == NULL ||
- RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
- RBE_COLOR(tmp) = RB_RED;
+ RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK)) {
+ RBE_COLOR(tmp) = RBE_RED;
rbe = parent;
parent = RBE_PARENT(rbe);
} else {
if (RBE_LEFT(tmp) == NULL ||
- RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
- struct rb_entry *oright;
+ RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) {
+ struct bst_entry *oright;
oright = RBE_RIGHT(tmp);
if (oright != NULL)
- RBE_COLOR(oright) = RB_BLACK;
+ RBE_COLOR(oright) = RBE_BLACK;
- RBE_COLOR(tmp) = RB_RED;
+ RBE_COLOR(tmp) = RBE_RED;
rbe_rotate_left(t, rbt, tmp);
tmp = RBE_LEFT(parent);
}
RBE_COLOR(tmp) = RBE_COLOR(parent);
- RBE_COLOR(parent) = RB_BLACK;
+ RBE_COLOR(parent) = RBE_BLACK;
if (RBE_LEFT(tmp) != NULL)
- RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
+ RBE_COLOR(RBE_LEFT(tmp)) = RBE_BLACK;
rbe_rotate_right(t, rbt, parent);
rbe = RBH_ROOT(rbt);
@@ -302,13 +503,13 @@ rbe_remove_color(const struct rb_type *t
}
if (rbe != NULL)
- RBE_COLOR(rbe) = RB_BLACK;
+ RBE_COLOR(rbe) = RBE_BLACK;
}
-static inline struct rb_entry *
-rbe_remove(const struct rb_type *t, struct rb_tree *rbt, struct rb_entry *rbe)
+static inline struct bst_entry *
+rbe_remove(const struct rbt_type *t, struct bstree *rbt, struct bst_entry *rbe)
{
- struct rb_entry *child, *parent, *old = rbe;
+ struct bst_entry *child, *parent, *old = rbe;
unsigned int color;
if (RBE_LEFT(rbe) == NULL)
@@ -316,7 +517,7 @@ rbe_remove(const struct rb_type *t, stru
else if (RBE_RIGHT(rbe) == NULL)
child = RBE_LEFT(rbe);
else {
- struct rb_entry *tmp;
+ struct bst_entry *tmp;
rbe = RBE_RIGHT(rbe);
while ((tmp = RBE_LEFT(rbe)) != NULL)
@@ -381,29 +582,29 @@ rbe_remove(const struct rb_type *t, stru
} else
RBH_ROOT(rbt) = child;
color:
- if (color == RB_BLACK)
+ if (color == RBE_BLACK)
rbe_remove_color(t, rbt, parent, child);
return (old);
}
void *
-_rb_remove(const struct rb_type *t, struct rb_tree *rbt, void *elm)
+_rbt_remove(const struct rbt_type *t, struct bstree *rbt, void *elm)
{
- struct rb_entry *rbe = rb_n2e(t, elm);
- struct rb_entry *old;
+ struct bst_entry *rbe = rbt_n2e(t, elm);
+ struct bst_entry *old;
old = rbe_remove(t, rbt, rbe);
- return (old == NULL ? NULL : rb_e2n(t, old));
+ return (old == NULL ? NULL : rbt_e2n(t, old));
}
void *
-_rb_insert(const struct rb_type *t, struct rb_tree *rbt, void *elm)
+_rbt_insert(const struct rbt_type *t, struct bstree *rbt, void *elm)
{
- struct rb_entry *rbe = rb_n2e(t, elm);
- struct rb_entry *tmp;
- struct rb_entry *parent = NULL;
+ struct bst_entry *rbe = rbt_n2e(t, elm);
+ struct bst_entry *tmp;
+ struct bst_entry *parent = NULL;
void *node;
int comp = 0;
@@ -411,24 +612,19 @@ _rb_insert(const struct rb_type *t, stru
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
+ node = rbt_e2n(t, tmp);
+ comp = (*t->t_bst.t_compare)(elm, node);
+ if (comp == 0)
return (node);
+
+ comp = comp > 0;
+ tmp = RBE_CHILD(tmp, comp);
}
rbe_set(rbe, parent);
if (parent != NULL) {
- if (comp < 0)
- RBE_LEFT(parent) = rbe;
- else
- RBE_RIGHT(parent) = rbe;
-
+ RBE_CHILD(parent, comp) = rbe;
rbe_if_augment(t, parent);
} else
RBH_ROOT(rbt) = rbe;
@@ -438,175 +634,260 @@ _rb_insert(const struct rb_type *t, stru
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)
+/*
+ * AVL Trees
+ */
+
+#define avl_n2e(_t, _elm) bst_n2e((_t), (_elm))
+#define avl_e2n(_t, _avle) bst_e2n((_t), (_avle))
+
+#define AVLT_ROOT(_avlt) BST_ROOT(_avlt)
+
+#define AVLE_CHILD(_avle, _c) BST_CHILD((_avle), (_c))
+#define AVLE_LEFT(_avle) BST_LEFT(_avle)
+#define AVLE_RIGHT(_avle) BST_RIGHT(_avle)
+#define AVLE_PARENT(_avle) BST_PARENT(_avle)
+#define AVLE_BALANCE(_avle) BST_DATA(_avle)
+
+static const int avl_balances[2] = { -1, 1 };
+
+/*
+ * rotate "left"
+ *
+ * / /
+ * B D
+ * / \ / \
+ * A D ==> B E
+ * / \ / \
+ * C E A C
+ */
+
+static inline struct bst_entry *
+avl_rotate(struct bst_entry *avle, int d)
{
- struct rb_entry *tmp = RBH_ROOT(rbt);
- void *node;
- int comp;
+ struct bst_entry *child, *gchild;
- 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);
+ child = AVLE_CHILD(avle, !d);
+ gchild = AVLE_CHILD(child, d);
+
+ AVLE_CHILD(child, d) = avle;
+ AVLE_PARENT(avle) = child;
+
+ AVLE_CHILD(avle, !d) = gchild;
+ if (gchild != NULL)
+ AVLE_PARENT(gchild) = avle;
+
+ return (child);
+}
+
+static inline int
+avl_rebalance(struct bstree *avlt, struct bst_entry *parent,
+ struct bst_entry **avlep, int balance)
+{
+ struct bst_entry *avle = *avlep;
+ struct bst_entry *child;
+ int cbalance;
+ int diff;
+ int d;
+
+ d = balance > 0;
+ child = AVLE_CHILD(avle, d);
+
+ cbalance = AVLE_BALANCE(child);
+ if (avl_balances[!d] == cbalance) {
+ struct bst_entry *gchild;
+
+ gchild = AVLE_CHILD(child, !d);
+
+ cbalance = AVLE_BALANCE(gchild);
+ AVLE_BALANCE(avle) =
+ (cbalance == avl_balances[d]) ? avl_balances[!d] : 0;
+ AVLE_BALANCE(child) =
+ (cbalance == avl_balances[!d]) ? avl_balances[d] : 0;
+ AVLE_BALANCE(gchild) = 0;
+
+ child = avl_rotate(child, d);
+ AVLE_CHILD(avle, d) = child;
+ AVLE_PARENT(child) = avle;
+
+ diff = 1; /* tree is always shorter after double rotation */
+ } else {
+ cbalance += avl_balances[!d];
+
+ AVLE_BALANCE(child) = cbalance;
+ AVLE_BALANCE(avle) = -cbalance;
+
+ diff = (cbalance == 0) ? 1 : 0;
}
- return (NULL);
+ child = avl_rotate(avle, !d);
+ if (parent != NULL) {
+ d = AVLE_RIGHT(parent) == avle;
+ AVLE_CHILD(parent, d) = child;
+ } else
+ AVLT_ROOT(avlt) = child;
+ AVLE_PARENT(child) = parent;
+
+ *avlep = child;
+ return (diff);
}
-/* 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)
+_avl_insert(const struct bst_type *t, struct bstree *avlt, void *elm)
{
- struct rb_entry *tmp = RBH_ROOT(rbt);
+ struct bst_entry *avle = avl_n2e(t, elm);
+ struct bst_entry *tmp;
+ struct bst_entry *parent = NULL;
void *node;
- void *res = NULL;
- int comp;
+ int comp = 0;
+ tmp = AVLT_ROOT(avlt);
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
+ parent = tmp;
+
+ node = avl_e2n(t, tmp);
+ comp = (*t->t_compare)(elm, node);
+ if (comp == 0)
return (node);
- }
- return (res);
-}
+ comp = (comp > 0);
+ tmp = AVLE_CHILD(tmp, comp);
+ }
-void *
-_rb_next(const struct rb_type *t, void *elm)
-{
- struct rb_entry *rbe = rb_n2e(t, elm);
+ AVLE_PARENT(avle) = parent;
+ AVLE_LEFT(avle) = AVLE_RIGHT(avle) = NULL;
+ AVLE_BALANCE(avle) = 0;
- 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);
- }
+ if (parent == NULL) {
+ AVLT_ROOT(avlt) = avle;
+ return (NULL);
}
- return (rbe == NULL ? NULL : rb_e2n(t, rbe));
-}
+ AVLE_CHILD(parent, comp) = avle;
-void *
-_rb_prev(const struct rb_type *t, void *elm)
-{
- struct rb_entry *rbe = rb_n2e(t, elm);
+ for (;;) {
+ int obalance, nbalance;
- 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);
+ avle = parent;
+
+ obalance = AVLE_BALANCE(avle);
+ nbalance = obalance + avl_balances[comp];
+
+ /* the balance has gone from a lean to equality */
+ if (nbalance == 0) {
+ AVLE_BALANCE(avle) = 0;
+ break;
+ }
+
+ parent = AVLE_PARENT(avle);
+
+ /* an existing lean has increased, so rebalance */
+ if (obalance != 0) {
+ avl_rebalance(avlt, parent, &avle, nbalance);
+ break;
}
+
+ AVLE_BALANCE(avle) = nbalance;
+
+ if (parent == NULL)
+ break;
+
+ comp = AVLE_RIGHT(parent) == avle;
}
- return (rbe == NULL ? NULL : rb_e2n(t, rbe));
+ return (NULL);
}
+
void *
-_rb_root(const struct rb_type *t, struct rb_tree *rbt)
+_avl_remove(const struct bst_type *t, struct bstree *avlt, void *elm)
{
- struct rb_entry *rbe = RBH_ROOT(rbt);
+ struct bst_entry *avle = avl_n2e(t, elm);
+ struct bst_entry *parent;
+ struct bst_entry *next;
+ struct bst_entry sentinel;
+ int comp;
- return (rbe == NULL ? rbe : rb_e2n(t, rbe));
-}
+ parent = AVLE_PARENT(avle);
-void *
-_rb_min(const struct rb_type *t, struct rb_tree *rbt)
-{
- struct rb_entry *rbe = RBH_ROOT(rbt);
- struct rb_entry *parent = NULL;
+ if (AVLE_LEFT(avle) != NULL && AVLE_RIGHT(avle) != NULL) {
+ /* two children exist, so shuffle tree around */
+ struct bst_entry *nparent = parent;
- while (rbe != NULL) {
- parent = rbe;
- rbe = RBE_LEFT(rbe);
+ /* find the next (well, previous) ordered node */
+ next = AVLE_LEFT(avle);
+ if (AVLE_RIGHT(next) == NULL) {
+ /* avle is going to swap with its immediate child */
+
+ parent = next; /* so next will be the avle parent */
+ AVLE_PARENT(next) = parent;
+
+ AVLE_LEFT(avle) = &sentinel;
+ } else {
+ do {
+ parent = next;
+ next = AVLE_RIGHT(next);
+ } while (AVLE_RIGHT(next) != NULL);
+
+ AVLE_RIGHT(parent) = &sentinel;
+ }
+
+ /* swap the target entry with the next entry */
+ sentinel = *next;
+ *next = *avle;
+
+ /* patch the next node into the surrounding tree */
+ AVLE_PARENT(AVLE_LEFT(avle)) = next;
+ AVLE_PARENT(AVLE_RIGHT(avle)) = next;
+ if (nparent != NULL) {
+ comp = AVLE_RIGHT(nparent) == avle;
+ AVLE_CHILD(nparent, comp) = next;
+ } else
+ AVLT_ROOT(avlt) = next;
+
+ avle = &sentinel;
}
- return (parent == NULL ? NULL : rb_e2n(t, parent));
-}
+ next = AVLE_LEFT(avle);
+ if (next == NULL)
+ next = AVLE_RIGHT(avle);
-void *
-_rb_max(const struct rb_type *t, struct rb_tree *rbt)
-{
- struct rb_entry *rbe = RBH_ROOT(rbt);
- struct rb_entry *parent = NULL;
+ if (next != NULL)
+ AVLE_PARENT(next) = parent;
- while (rbe != NULL) {
- parent = rbe;
- rbe = RBE_RIGHT(rbe);
+ if (parent == NULL) {
+ AVLT_ROOT(avlt) = next;
+ return (elm);
}
- return (parent == NULL ? NULL : rb_e2n(t, parent));
-}
+ comp = AVLE_RIGHT(parent) == avle;
+ AVLE_CHILD(parent, comp) = next;
-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));
-}
+ for (;;) {
+ int obalance, nbalance;
-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));
-}
+ avle = parent;
-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));
-}
+ obalance = AVLE_BALANCE(avle);
+ nbalance = obalance - avl_balances[comp];
-void
-_rb_poison(const struct rb_type *t, void *node, unsigned long poison)
-{
- struct rb_entry *rbe = rb_n2e(t, node);
+ if (obalance == 0) {
+ AVLE_BALANCE(avle) = nbalance;
+ break;
+ }
- RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
- (struct rb_entry *)poison;
-}
+ parent = AVLE_PARENT(avle);
-int
-_rb_check(const struct rb_type *t, void *node, unsigned long poison)
-{
- struct rb_entry *rbe = rb_n2e(t, node);
+ if (nbalance == 0)
+ AVLE_BALANCE(avle) = 0;
+ else if (avl_rebalance(avlt, parent, &avle, nbalance) == 0)
+ break;
- return ((unsigned long)RBE_PARENT(rbe) == poison &&
- (unsigned long)RBE_LEFT(rbe) == poison &&
- (unsigned long)RBE_RIGHT(rbe) == poison);
+ if (parent == NULL)
+ break;
+
+ comp = AVLE_RIGHT(parent) == avle;
+ }
+
+ return (elm);
}
