Module: xenomai-3
Branch: next
Commit: 3892e3e6fa10ad62024c956c83cca4beed8494be
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=3892e3e6fa10ad62024c956c83cca4beed8494be
Author: Gilles Chanteperdrix <gilles.chanteperd...@xenomai.org>
Date: Tue Jul 12 20:29:22 2016 +0200
boilerplate/avl: merge pshared support for AVL trees
Make the AVL tree usable in shared memory when AVL_SHARED is defined
at build time, switching to offset-based memory references.
Gilles published this code in July 2016 as part of his personal
toolkit for hobby projects aka 'libchutils'.
---
include/boilerplate/avl.h | 472 ++++++++++++++++++++++++++++--------------
lib/boilerplate/avl.c | 497 ++++++++++++++++++++++++++++++++++-----------
2 files changed, 697 insertions(+), 272 deletions(-)
diff --git a/include/boilerplate/avl.h b/include/boilerplate/avl.h
index 1aa84bf..34fb23a 100644
--- a/include/boilerplate/avl.h
+++ b/include/boilerplate/avl.h
@@ -23,276 +23,444 @@
#ifndef _BOILERPLATE_AVL_H
#define _BOILERPLATE_AVL_H
-#include <stdlib.h>
+#include <stddef.h>
+#include <stdio.h>
struct avlh {
- unsigned int thr: 3;
+#define AVLH_APP_BITS 28
+ unsigned int flags: AVLH_APP_BITS;
int type: 2;
- int balance :2;
- unsigned int flags :25; /* Application-specific */
- struct avlh *link[3];
+ int balance: 2;
+ union {
+ ptrdiff_t offset;
+ struct avlh *ptr;
+ } link[3];
};
-/* Using -1 and 1 for left and right is slightly faster than 0 and 1, using 0
- for "up" is just here for orthogonality... and avoid wasting 4 bytes or
- having to use a union in struct avlh. */
-#define AVL_LEFT -1
-#define AVL_UP 0
-#define AVL_RIGHT 1
-/* maps AVL_LEFT to AVL_RIGHT and reciprocally. */
-#define avl_opposite(type) (-(type))
-/* maps AVL_LEFT to -1 and AVL_RIGHT to 1. */
-#define avl_type2sign(type) (type)
-/* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */
-#define avl_type2index(type) ((type)+1)
-/* maps <0 to AVL_LEFT and >0 to AVL_RIGHT. */
-#define avl_sign2type(sign) (sign)
-
-#define AVL_THR_LEFT (1<<avl_type2index(AVL_LEFT))
-#define AVL_THR_RIGHT (1<<avl_type2index(AVL_RIGHT))
-
-#define avlh_thr_set(holder, side) ((holder)->thr |= 1 << avl_type2index(side))
-#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 <<
avl_type2index(side)))
-#define avlh_thr_tst(holder, side) ((holder)->thr & (1 <<
avl_type2index(side)))
-#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
-#define avlh_up(holder) avlh_link((holder), AVL_UP)
-#define avlh_left(holder) avlh_link((holder), AVL_LEFT)
-#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
-#define avlh_parent_link(holder) (avlh_link(avlh_up(holder), (holder)->type))
-
struct avl;
-typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int
*);
-
+/*
+ * Comparison function: should return -1 if left is less than right, 0
+ * if they are equal and 1 if left is greather than right. You can use
+ * the avl_sign function which will convert a difference to -1, 0,
+ * 1. Beware of overflow however. You can also use avl_cmp_sign()
+ * which should not have any such problems.
+ */
typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+typedef struct avlh *
+avl_search_t(const struct avl *, const struct avlh *, int *, int);
+
+typedef int avlh_prn_t(char *, size_t, const struct avlh *const);
+
struct avl {
struct avlh anchor;
avl_search_t *search;
avlh_cmp_t *cmp;
- struct avlh *end[3];
+ union {
+ ptrdiff_t offset;
+ struct avlh *ptr;
+ } end[3];
unsigned int count;
unsigned int height;
};
-#define avl_searchfn(avl) ((avl)->search)
-#define avl_cmp(avl) ((avl)->cmp)
-#define avl_count(avl) ((avl)->count)
-#define avl_height(avl) ((avl)->height)
-#define avl_anchor(avl) (&(avl)->anchor)
-#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
-#define avl_top(avl) (avlh_right(avl_anchor(avl)))
-#define avl_head(avl) (avl_end((avl), AVL_LEFT))
-#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+#define AVL_LEFT -1
+#define AVL_UP 0
+#define AVL_RIGHT 1
+/* maps AVL_LEFT to AVL_RIGHT and reciprocally. */
+#define avl_opposite(type) (-(type))
+/* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */
+#define avl_type2index(type) ((type)+1)
-#ifdef __cplusplus
-extern "C" {
-#endif
+#define AVL_THR_LEFT (1 << avl_type2index(AVL_LEFT))
+#define AVL_THR_RIGHT (1 << avl_type2index(AVL_RIGHT))
-void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+#define avlh_up(avl, holder) avlh_link((avl), (holder), AVL_UP)
+#define avlh_left(avl, holder) avlh_link((avl), (holder), AVL_LEFT)
+#define avlh_right(avl, holder) avlh_link((avl), (holder), AVL_RIGHT)
-void avl_destroy(struct avl *avl);
+#define avlh_thr_tst(avl, holder, side) (avlh_link(avl, holder, side) == NULL)
+#define avlh_child(avl, holder, side) (avlh_link((avl),(holder),(side)))
+#define avlh_has_child(avl, holder, side) (!avlh_thr_tst(avl, holder, side))
-void avl_clear(struct avl *avl, void (*destruct)(struct avlh *));
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl) ((avl)->cmp)
+#define avl_count(avl) ((avl)->count)
+#define avl_height(avl) ((avl)->height)
+#define avl_anchor(avl) (&(avl)->anchor)
+#define avl_top(avl) (avlh_right(avl, avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
-int avl_insert(struct avl *avl, struct avlh *holder);
+/*
+ * From "Bit twiddling hacks", returns v < 0 ? -1 : (v > 0 ? 1 : 0)
+ */
+#define avl_sign(v) \
+ ({ \
+ typeof(v) _v = (v); \
+ ((_v) > 0) - ((_v) < 0); \
+ })
-int avl_prepend(struct avl *avl, struct avlh *holder);
+/*
+ * Variation on the same theme.
+ */
+#define avl_cmp_sign(l, r) \
+ ({ \
+ typeof(l) _l = (l); \
+ typeof(r) _r = (r); \
+ (_l > _r) - (_l < _r); \
+ })
+
+#ifdef AVL_PSHARED
+
+static inline struct avlh *
+avlh_link(const struct avl *const avl,
+ const struct avlh *const holder, unsigned int dir)
+{
+ return (void *)avl + holder->link[avl_type2index(dir)].offset;
+}
-int avl_append(struct avl *avl, struct avlh *holder);
+static inline void
+avlh_set_link(struct avl *const avl, struct avlh *lhs, int dir, struct avlh
*rhs)
+{
+ lhs->link[avl_type2index(dir)].offset = (void *)rhs - (void *)avl;
+}
-struct avlh *avl_update(struct avl *avl, struct avlh *holder);
+static inline struct avlh *avl_end(const struct avl *const avl, int dir)
+{
+ return (void *)avl + avl->end[avl_type2index(dir)].offset;
+}
-struct avlh *avl_set(struct avl *avl, struct avlh *holder);
+static inline void
+avl_set_end(struct avl *const avl, int dir, struct avlh *holder)
+{
+ avl->end[avl_type2index(dir)].offset = (void *)holder - (void *)avl;
+}
-int avl_delete(struct avl *avl, struct avlh *node);
+#else /* !PSHARED */
-static inline struct avlh *avl_gettop(struct avl *const avl)
-{
- struct avlh *const holder = avl_top(avl);
+#define avlh_link(avl, holder, dir) ((holder)->link[avl_type2index(dir)].ptr)
- if (holder != avl_anchor(avl))
- return holder;
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)].ptr)
- return NULL;
+static inline void
+avlh_set_link(struct avl *const avl, struct avlh *lhs, int dir, struct avlh
*rhs)
+{
+ avlh_link(avl, lhs, dir) = rhs;
}
-static inline struct avlh *avl_gethead(struct avl *const avl)
+static inline void
+avl_set_end(struct avl *const avl, int dir, struct avlh *holder)
{
- struct avlh *const holder = avl_head(avl);
+ avl_end(avl, dir) = holder;
+}
- if (holder != avl_anchor(avl))
- return holder;
+#endif /* !PSHARED */
- return NULL;
+static inline struct avlh *
+__avl_search_inner(const struct avl *const avl, const struct avlh *n, int
*delta)
+{
+ return avl_searchfn(avl)(avl, n, delta, 0);
}
-static inline struct avlh *avl_gettail(struct avl *const avl)
+static inline struct avlh *avl_gettop(const struct avl *const avl)
{
- struct avlh *const holder = avl_tail(avl);
+ return avl_top(avl);
+}
- if (holder != avl_anchor(avl))
- return holder;
+static inline struct avlh *avl_gethead(const struct avl *const avl)
+{
+ return avl_head(avl);
+}
- return NULL;
+static inline struct avlh *avl_gettail(const struct avl *const avl)
+{
+ return avl_tail(avl);
}
-static inline unsigned avl_getcount(struct avl *const avl)
+static inline unsigned int avl_getcount(const struct avl *const avl)
{
return avl_count(avl);
}
-static inline struct avlh *avl_inorder(struct avl *const avl,
- struct avlh *const holder,
- const int dir)
+static inline struct avlh *
+avl_inorder(const struct avl *const avl,
+ struct avlh *holder,
+ const int dir)
{
/* Assume dir == AVL_RIGHT in comments. */
- struct avlh *child = avlh_link(holder, dir);
+ struct avlh *next;
- /* If the current node is not right threaded, then go down left,
starting
- from its right child. */
- if (!avlh_thr_tst(holder, dir)) {
+ /*
+ * If the current node is not right threaded, then go down left,
+ * starting from its right child.
+ */
+ if (avlh_has_child(avl, holder, dir)) {
const int opp_dir = avl_opposite(dir);
- while (!avlh_thr_tst(child, opp_dir))
- child = avlh_link(child, opp_dir);
- } else
- /* Else follow its right thread. */
- if (child != avl_anchor(avl))
- return child;
- else
- return NULL;
+ holder = avlh_link(avl, holder, dir);
+ while ((next = avlh_child(avl, holder, opp_dir)))
+ holder = next;
+ next = holder;
+ } else {
+ for(;;) {
+ next = avlh_up(avl, holder);
+ if (next == avl_anchor(avl))
+ return NULL;
+ if (holder->type != dir)
+ break;
+ holder = next;
+ }
+ }
- return child;
+ return next;
}
-static inline struct avlh *avl_postorder(struct avl *const avl,
- struct avlh *const holder, const int
dir)
+static inline struct avlh *
+avl_postorder(const struct avl *const avl,
+ struct avlh *const holder, const int dir)
{
/* Assume dir == AVL_RIGHT in comments. */
- struct avlh *next = avlh_up(holder);
+ struct avlh *next = avlh_up(avl, holder);
if (holder->type != dir)
- /* If the current node is not a right node, follow the nodes in
inorder
- until we find a right threaded node. */
- while (!avlh_thr_tst(next, dir))
+ /*
+ * If the current node is not a right node, follow the nodes in
+ * inorder until we find a right threaded node.
+ */
+ while (avlh_has_child(avl, next, dir))
next = avl_inorder(avl, next, dir);
else
- /* else the current node is a right node, its parent is the
next in
- postorder. */
- if (next != avl_anchor(avl))
- return next;
- else
- return NULL;
+ /*
+ * else the current node is a right node, its parent is the
+ * next in postorder.
+ */
+ if (next == avl_anchor(avl))
+ next = NULL;
return next;
}
-static inline struct avlh *avl_preorder(struct avl *const avl,
- struct avlh *holder, const int dir)
+static inline struct avlh *
+avl_preorder(const struct avl *const avl,
+ struct avlh *holder, const int dir)
{
+
struct avlh *next;
/* Assume dir == AVL_RIGHT in comments. */
- /* If the current node has a left child (hence is not left threaded),
then
- return it. */
- if (!avlh_thr_tst(holder, avl_opposite(dir)))
- return avlh_link(holder, avl_opposite(dir));
-
- /* Else follow the right threads until we find a node which is not right
- threaded (hence has a right child) and return its right child. */
+ /*
+ * If the current node has a left child (hence is not left threaded),
+ * then return it.
+ */
+
+ if (avlh_has_child(avl, holder, avl_opposite(dir)))
+ return avlh_link(avl, holder, avl_opposite(dir));
+
+ /*
+ * Else follow the right threads until we find a node which is not right
+ * threaded (hence has a right child) and return its right child.
+ */
next = holder;
- while (avlh_thr_tst(next, dir)) {
- next = avlh_link(next, dir);
- if (next == avl_anchor(avl))
- goto ret_null;
+ while (!avlh_has_child(avl, next, dir)) {
+ next = avl_inorder(avl, next, dir);
+ if (next == NULL)
+ return NULL;
}
- return avlh_link(next, dir);
-ret_null:
- return NULL;
+ return avlh_link(avl, next, dir);
}
-/**
- * Get next node in symmetrical a.k.a inorder ordering.
- */
-static inline struct avlh *avl_next(struct avl *const avl, struct avlh *const
holder)
+static inline struct avlh *
+avl_next(const struct avl *const avl, struct avlh *const holder)
{
return avl_inorder(avl, holder, AVL_RIGHT);
}
-/**
- * Get previous node in symmetrical a.k.a inorder ordering.
- */
-static inline struct avlh *avl_prev(struct avl *const avl, struct avlh *const
holder)
+static inline struct avlh *
+avl_prev(const struct avl *const avl, struct avlh *const holder)
{
return avl_inorder(avl, holder, AVL_LEFT);
}
-static inline struct avlh *avl_postorder_next(struct avl *const avl, struct
avlh *const holder)
+static inline struct avlh *
+avl_postorder_next(const struct avl *const avl, struct avlh *const holder)
{
return avl_postorder(avl, holder, AVL_RIGHT);
}
-static inline struct avlh *avl_postorder_prev(struct avl *const avl, struct
avlh *const holder)
+static inline struct avlh *
+avl_postorder_prev(const struct avl *const avl, struct avlh *const holder)
{
return avl_postorder(avl, holder, AVL_LEFT);
}
-static inline struct avlh *avl_preorder_next(struct avl *const avl, struct
avlh *const holder)
+static inline struct avlh *
+avl_preorder_next(const struct avl *const avl, struct avlh *const holder)
{
return avl_preorder(avl, holder, AVL_RIGHT);
}
-static inline struct avlh *avl_preorder_prev(struct avl *const avl, struct
avlh *const holder)
+static inline struct avlh *
+avl_preorder_prev(const struct avl *const avl, struct avlh *const holder)
{
return avl_preorder(avl, holder, AVL_LEFT);
}
static inline void avlh_init(struct avlh *const holder)
{
- *(unsigned long *)holder = 0UL; /* Please valgrind */
- holder->thr = AVL_THR_LEFT | AVL_THR_RIGHT;
holder->balance = 0;
holder->type = 0;
}
-static inline struct avlh *avl_search(struct avl *const avl, const struct avlh
*node)
+static inline struct avlh *
+avl_search(const struct avl *const avl, const struct avlh *node)
{
struct avlh *holder;
int delta;
- holder = avl_searchfn(avl)(avl, node, &delta);
+ holder = __avl_search_inner(avl, node, &delta);
if (!delta)
return holder;
return NULL;
}
-#ifdef __cplusplus
+static inline struct avlh *
+avl_search_nearest(const struct avl *const avl, const struct avlh *node, int
dir)
+{
+ struct avlh *holder;
+ int delta;
+
+ holder = __avl_search_inner(avl, node, &delta);
+ if (!holder || delta != dir)
+ return holder;
+
+ return avl_inorder(avl, holder, dir);
+}
+
+static inline struct avlh *
+avl_search_le(const struct avl *const avl, const struct avlh *node)
+{
+ return avl_search_nearest(avl, node, AVL_LEFT);
+}
+
+static inline struct avlh *
+avl_search_ge(const struct avl *const avl, const struct avlh *node)
+{
+ return avl_search_nearest(avl, node, AVL_RIGHT);
+}
+
+int avl_insert_front(struct avl *avl, struct avlh *holder);
+
+int avl_insert_back(struct avl *avl, struct avlh *holder);
+
+static inline struct avlh *
+avl_search_multi(const struct avl *const avl, const struct avlh *node, int dir)
+{
+ struct avlh *holder;
+ int delta;
+
+ holder = avl_searchfn(avl)(avl, node, &delta, dir);
+ if (!delta)
+ return holder;
+
+ if (!holder)
+ return NULL;
+
+ return avl_inorder(avl, holder, -dir);
}
-#endif
-/**
+static inline struct avlh *
+avl_search_first(const struct avl *const avl, const struct avlh *node)
+{
+ return avl_search_multi(avl, node, AVL_LEFT);
+}
+
+static inline struct avlh *
+avl_search_last(const struct avl *const avl, const struct avlh *node)
+{
+ return avl_search_multi(avl, node, AVL_RIGHT);
+}
+
+/*
* Search a node, return its parent if it could not be found.
*/
-#define DECLARE_AVL_SEARCH(avl_search_inner, cmp) \
-static struct avlh *avl_search_inner(const struct avl *const avl, \
- const struct avlh *const node, \
- int *const pdelta) \
-{ \
- int delta = avl_type2sign(AVL_RIGHT); \
- struct avlh *holder = avl_top(avl); \
+#define DECLARE_AVL_SEARCH(avl_search_inner, cmp) \
+ struct avlh *avl_search_inner(const struct avl *const avl, \
+ const struct avlh *const node, \
+ int *const pdelta, int dir) \
+ { \
+ int delta = AVL_RIGHT; \
+ struct avlh *holder = avl_top(avl), *next; \
\
- if (holder != avl_anchor(avl)) { \
- while ((delta = cmp(holder, node))) { \
- delta = delta < 0 ? -1 : 1; \
- if (avlh_thr_tst(holder,avl_sign2type(delta))) \
+ if (holder == NULL) \
+ goto done; \
+ \
+ for (;;) { \
+ delta = cmp(node, holder); \
+ /* \
+ * Handle duplicates keys here, according to \
+ * "dir", if dir is: \
+ * - AVL_LEFT, the leftmost node is returned, \
+ * - AVL_RIGHT, the rightmost node is returned, \
+ * - 0, the first match is returned. \
+ */ \
+ if (!(delta ?: dir)) \
+ break; \
+ next = avlh_child(avl, holder, delta ?: dir); \
+ if (next == NULL) \
break; \
- holder = avlh_link(holder, avl_sign2type(delta)); \
+ holder = next; \
} \
- } \
- *pdelta = delta; \
- return holder; \
-} \
+ \
+ done: \
+ *pdelta = delta; \
+ return holder; \
+ }
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+void avl_init(struct avl *const avl,
+ avl_search_t *searchfn, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *const avl);
+
+int avl_insert(struct avl *const avl, struct avlh *const holder);
+
+int avl_insert_front(struct avl *avl, struct avlh *holder);
+
+int avl_insert_back(struct avl *avl, struct avlh *holder);
+
+int avl_insert_at(struct avl *const avl,
+ struct avlh *parent, int dir, struct avlh *child);
+
+int avl_prepend(struct avl *const avl, struct avlh *const holder);
+
+int avl_append(struct avl *const avl, struct avlh *const holder);
+
+int avl_delete(struct avl *const avl, struct avlh *node);
+
+int avl_replace(struct avl *avl, struct avlh *oldh,
+ struct avlh *newh);
+
+struct avlh *avl_update(struct avl *const avl,
+ struct avlh *const holder);
+
+struct avlh *avl_set(struct avl *const avl,
+ struct avlh *const holder);
+
+void avl_clear(struct avl *const avl, void (*destruct)(struct avlh *));
+
+int avl_check(const struct avl *avl);
+
+void avl_dump(FILE *file, const struct avl *const avl,
+ avlh_prn_t *prn, unsigned int indent, unsigned int len);
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
#endif /* !_BOILERPLATE_AVL_H */
diff --git a/lib/boilerplate/avl.c b/lib/boilerplate/avl.c
index 4dcc177..7f4bb36 100644
--- a/lib/boilerplate/avl.c
+++ b/lib/boilerplate/avl.c
@@ -22,67 +22,123 @@
*/
#include <stdio.h>
#include <errno.h>
-#include <string.h>
+#include <memory.h>
#include <boilerplate/avl.h>
+static inline unsigned int avlh_thr(const struct avl *const avl, const struct
avlh *h)
+{
+ unsigned int result = 0;
+
+ if (avlh_link(avl, h, AVL_LEFT) == NULL)
+ result |= AVL_THR_LEFT;
+ if (avlh_link(avl, h, AVL_RIGHT) == NULL)
+ result |= AVL_THR_RIGHT;
+
+ return result;
+}
+
+static inline void
+avlh_set_parent_link(struct avl *const avl, struct avlh *lhs, struct avlh *rhs)
+{
+ avlh_set_link(avl, avlh_up(avl, lhs), lhs->type, rhs);
+}
+
+static inline void
+avlh_set_left(struct avl *const avl, struct avlh *lhs, struct avlh *rhs)
+{
+ avlh_set_link(avl, lhs, AVL_LEFT, rhs);
+}
+
+static inline void
+avlh_set_up(struct avl *const avl, struct avlh *lhs, struct avlh *rhs)
+{
+ avlh_set_link(avl, lhs, AVL_UP, rhs);
+}
+
+static inline void
+avlh_set_right(struct avl *const avl, struct avlh *lhs, struct avlh *rhs)
+{
+ avlh_set_link(avl, lhs, AVL_RIGHT, rhs);
+}
+
+static inline void avl_set_top(struct avl *const avl, struct avlh *holder)
+{
+ avlh_set_link(avl, avl_anchor(avl), AVL_RIGHT, holder);
+}
+
+static inline void avl_set_head(struct avl *const avl, struct avlh *holder)
+{
+ avl_set_end(avl, AVL_LEFT, holder);
+}
+
+static inline void avl_set_tail(struct avl *const avl, struct avlh *holder)
+{
+ avl_set_end(avl, AVL_RIGHT, holder);
+}
+
/* Internal functions used for rebalancing (for insertion and deletion). */
-static inline struct avlh *avlh_rotate(struct avlh *const holder, const int
dir)
+static inline struct avlh *
+avlh_rotate(struct avl *const avl, struct avlh *const holder, const int dir)
{
const int opp_dir = avl_opposite(dir);
- struct avlh *const nexttop = avlh_link(holder, opp_dir);
+ struct avlh *const nexttop = avlh_link(avl, holder, opp_dir);
+ struct avlh *const subtree = avlh_child(avl, nexttop, dir);
- if (!avlh_thr_tst(nexttop, dir)) {
- struct avlh *const subtree = avlh_link(nexttop, dir);
-
- avlh_link(holder, opp_dir) = subtree;
- avlh_thr_clr(holder, opp_dir);
- avlh_up(subtree) = holder;
+ if (subtree) {
+ avlh_set_link(avl, holder, opp_dir, subtree);
+ avlh_set_up(avl, subtree, holder);
subtree->type = opp_dir;
} else
- avlh_thr_set(holder, opp_dir);
-
- avlh_link(nexttop, dir) = holder;
- avlh_thr_clr(nexttop, dir);
+ avlh_set_link(avl, holder, opp_dir, NULL);
- avlh_up(nexttop) = avlh_up(holder);
+ avlh_set_link(avl, nexttop, dir, holder);
+ avlh_set_up(avl, nexttop, avlh_up(avl, holder));
nexttop->type = holder->type;
- avlh_up(holder) = nexttop;
+ avlh_set_up(avl, holder, nexttop);
holder->type = dir;
- avlh_parent_link(nexttop) = nexttop;
+ avlh_set_parent_link(avl, nexttop, nexttop);
return nexttop;
}
-static inline struct avlh *avlh_dbl_rotate(struct avlh *const holder, const
int dir)
+static inline struct avlh *
+avlh_dbl_rotate(struct avl *const avl, struct avlh *const holder, const int
dir)
{
const int opp = avl_opposite(dir);
- avlh_rotate(avlh_link(holder, opp), opp);
- return avlh_rotate(holder, dir);
+ avlh_rotate(avl, avlh_link(avl, holder, opp), opp);
+ return avlh_rotate(avl, holder, dir);
}
-static struct avlh *avlh_rebalance(struct avlh *holder, const int delta)
+static struct avlh *
+avlh_rebalance(struct avl *const avl, struct avlh *holder, const int delta)
{
- int dir = avl_sign2type(delta);
- struct avlh *const heavy_side = avlh_link(holder, dir);
+ int dir = delta;
+ struct avlh *const heavy_side = avlh_link(avl, holder, dir);
if (heavy_side->balance == -delta) {
/* heavy_side->balance == -delta, double rotation needed. */
- holder = avlh_dbl_rotate(holder, avl_opposite(dir));
-
- /* recompute balances, there are three nodes involved, two of
which
- balances become null.*/
- dir = holder->balance ? avl_sign2type(holder->balance) :
AVL_RIGHT;
- avlh_link(holder, dir)->balance = 0;
- avlh_link(holder, avl_opposite(dir))->balance =
-holder->balance;
+ holder = avlh_dbl_rotate(avl, holder, avl_opposite(dir));
+
+ /*
+ * recompute balances, there are three nodes involved, two of
+ * which balances become null.
+ */
+ dir = holder->balance ?: AVL_RIGHT;
+ avlh_link(avl, holder, dir)->balance = 0;
+ avlh_link(avl, holder, avl_opposite(dir))->balance
+ = -holder->balance;
holder->balance = 0;
} else {
- /* heavy_side->balance == delta or 0, simple rotation needed.
- the case 0 occurs only when deleting, never when inserting.
*/
+ /*
+ * heavy_side->balance == delta or 0, simple rotation needed.
+ * the case 0 occurs only when deleting, never when inserting.
+ */
+
/* heavy_side becomes the new root. */
- avlh_rotate(holder, avl_opposite(dir));
+ avlh_rotate(avl, holder, avl_opposite(dir));
/* recompute balances. */
holder->balance -= heavy_side->balance;
@@ -93,82 +149,107 @@ static struct avlh *avlh_rebalance(struct avlh *holder,
const int delta)
return holder;
}
-/* The avlh_rebalance functions was split in two parts to allow inlining in
- the simplest case. */
-static inline struct avlh *avlh_balance_add(struct avlh *const holder, const
int delta)
+/*
+ * The avlh_rebalance functions was split in two parts to allow inlining in
+ * the simplest case.
+ */
+static inline struct avlh *
+avlh_balance_add(struct avl *const avl, struct avlh *const holder, const int
delta)
{
if (holder->balance == delta)
/* we need to rebalance the current subtree. */
- return avlh_rebalance(holder, delta);
+ return avlh_rebalance(avl, holder, delta);
/* the current subtree does not need rebalancing */
holder->balance += delta;
return holder;
}
-static inline void avlh_link_child(struct avlh *const oldh,
- struct avlh *const newh, const int side)
+static inline void
+avlh_link_child(struct avl *const avl, struct avlh *const oldh,
+ struct avlh *const newh, const int side)
{
- struct avlh *const child = avlh_link(oldh, side);
+ struct avlh *const child = avlh_link(avl, oldh, side);
- avlh_link(newh, side) = child;
- if (!avlh_thr_tst(oldh, side)) {
- /* avl_inorder won't use its tree parameter, hence NULL is Ok.
*/
- struct avlh *const inorder_adj = avl_inorder(NULL, oldh, side);
- const int opp_side = avl_opposite(side);
- avlh_link(inorder_adj, opp_side) = newh;
- /* Do not change child before using avl_prev... */
- avlh_up(child) = newh;
- }
+ avlh_set_link(avl, newh, side, child);
+ if (avlh_has_child(avl, oldh, side))
+ avlh_set_up(avl, child, newh);
}
-static inline void avlh_replace(struct avlh *const oldh, struct avlh *const
newh)
+static inline void
+avlh_replace(struct avl *const avl, struct avlh *const oldh, struct avlh
*const newh)
{
- newh->thr = oldh->thr;
newh->type = oldh->type;
/* Do not update the balance, this has to be done by the caller. */
- avlh_up(newh) = avlh_up(oldh);
- avlh_parent_link(oldh) = newh;
+ avlh_set_up(avl, newh, avlh_up(avl, oldh));
+ avlh_set_parent_link(avl, oldh, newh);
- avlh_link_child(oldh, newh, AVL_LEFT);
- avlh_link_child(oldh, newh, AVL_RIGHT);
+ avlh_link_child(avl, oldh, newh, AVL_LEFT);
+ avlh_link_child(avl, oldh, newh, AVL_RIGHT);
+}
+
+/*
+ * Special case, when we know that replacing a node with another will not
change
+ * the avl, much faster than remove + add
+ */
+int avl_replace(struct avl *avl, struct avlh *oldh, struct avlh *newh)
+{
+ struct avlh *prev, *next;
+
+ prev = avl_prev(avl, oldh);
+ next = avl_next(avl, oldh);
+
+ if ((prev && avl_cmp(avl)(newh, prev) < 0)
+ || (next && avl_cmp(avl)(newh, next) > 0))
+ return -EINVAL;
+
+ avlh_replace(avl, oldh, newh);
+ if (oldh == avl_head(avl))
+ avl_set_head(avl, newh);
+ if (oldh == avl_tail(avl))
+ avl_set_tail(avl, newh);
+ newh->balance = oldh->balance;
+ return 0;
}
/* Deletion helpers. */
static void avl_delete_leaf(struct avl *const avl, struct avlh *const node)
{
- /* Node has no child at all. It disappears and its father becomes
- threaded on the side id was. */
+ /*
+ * Node has no child at all. It disappears and its father becomes
+ * threaded on the side id was.
+ */
- struct avlh *const new_node = avlh_up(node);
+ struct avlh *const new_node = avlh_up(avl, node);
const int dir = node->type;
/* Suppress node. */
- avlh_link(new_node, dir) = avlh_link(node, dir);
- avlh_thr_set(new_node, dir);
+ avlh_set_link(avl, new_node, dir, avlh_link(avl, node, dir));
if (node == avl_end(avl, dir))
- avl_end(avl, dir) = new_node;
+ avl_set_end(avl, dir, new_node);
}
static struct avlh *avl_delete_1child(struct avl *const avl,
struct avlh *const node, const int dir)
{
- /* Node is threaded on one side and has a child on the other
- side. In this case, node is replaced by its child. */
+ /*
+ * Node is threaded on one side and has a child on the other
+ * side. In this case, node is replaced by its child.
+ */
- struct avlh *const new_node = avlh_link(node, dir);
+ struct avlh *const new_node = avlh_link(avl, node, dir);
- /* Change links as if new_node was suppressed before calling
- avlh_replace. */
- avlh_link(node, dir) = avlh_link(new_node, dir);
- if (avlh_thr_tst(new_node, dir))
- avlh_thr_set(node, dir);
- avlh_replace(node, new_node);
+ /*
+ * Change links as if new_node was suppressed before calling
+ * avlh_replace.
+ */
+ avlh_set_link(avl, node, dir, avlh_link(avl, new_node, dir));
+ avlh_replace(avl, node, new_node);
if (node == avl_end(avl, avl_opposite(dir)))
- avl_end(avl, avl_opposite(dir)) = new_node;
+ avl_set_end(avl, avl_opposite(dir), new_node);
/* new_node->balance 0, which is correct. */
return new_node;
}
@@ -176,61 +257,60 @@ static struct avlh *avl_delete_1child(struct avl *const
avl,
static int avl_delete_2children(struct avl *const avl, struct avlh *const
node);
/* Insertion helpers. */
-static inline void avlh_attach(struct avlh *const parent,
- struct avlh *const child, const int side)
+static inline void
+avlh_attach(struct avl *const avl, struct avlh *const parent,
+ struct avlh *const child, const int side)
{
- avlh_link(child, side) = avlh_link(parent, side);
- avlh_link(child, avl_opposite(side)) = parent;
- avlh_up(child) = parent;
- avlh_link(parent, side) = child;
+ avlh_set_left(avl, child, NULL);
+ avlh_set_right(avl, child, NULL);
+ avlh_set_up(avl, child, parent);
+ avlh_set_link(avl, parent, side, child);
child->type = side;
}
-/**
+/*
* Insert a node, given its parent and the side where it should be inserted.
* Helper for all insertion functions.
*/
static inline void avl_insert_inner(struct avl *const avl, struct avlh *parent,
struct avlh *const node, const int side)
{
- avlh_attach(parent, node, side);
+ avlh_attach(avl, parent ?: avl_anchor(avl), node, side);
++avl_count(avl);
- if (parent == avl_anchor(avl)) {
- goto insert_first_and_ret; /* Get away from fast path */
- } else if (parent == avl_end(avl, side))
- avl_end(avl, side) = node;
+ if (parent == NULL)
+ goto insert_first_and_ret; /* Get away from fast path */
+
+ if (parent == avl_end(avl, side))
+ avl_set_end(avl, side, node);
- /* Do not touch these for first insertion. */
- avlh_thr_clr(parent, side);
- parent->balance += avl_type2sign(side);
+ parent->balance += side;
while (parent->balance) {
- const int delta = avl_type2sign(parent->type);
- parent = avlh_up(parent);
+ const int delta = parent->type;
+ parent = avlh_up(avl, parent);
if (parent == avl_anchor(avl))
goto inc_height_and_ret; /* Get away from fast path */
- parent = avlh_balance_add(parent, delta);
+ parent = avlh_balance_add(avl, parent, delta);
}
return;
insert_first_and_ret:
- avl_head(avl) = avl_tail(avl) = node;
+ avl_set_head(avl, node);
+ avl_set_tail(avl, node);
inc_height_and_ret:
++avl_height(avl);
- return;
}
/* External functions. */
-
int avl_delete(struct avl *const avl, struct avlh *node)
{
if (!--avl_count(avl)) {
goto delete_last_and_ret;
}
- switch(node->thr) {
+ switch(avlh_thr(avl, node)) {
case (AVL_THR_LEFT|AVL_THR_RIGHT): /* thr is 5 */
avl_delete_leaf(avl, node);
break;
@@ -251,17 +331,19 @@ int avl_delete(struct avl *const avl, struct avlh *node)
The tree is rebalanced, and contrarily to what happened for
insertion,
the rebalancing stops when a node which is NOT balanced is met. */
while (!node->balance) {
- const int delta = -avl_type2sign(node->type);
- node = avlh_up(node);
+ const int delta = -node->type;
+ node = avlh_up(avl, node);
if (node == avl_anchor(avl))
goto dec_height_and_ret;
- node = avlh_balance_add(node, delta);
+ node = avlh_balance_add(avl, node, delta);
}
return 0;
delete_last_and_ret:
- avl_top(avl) = avl_head(avl) = avl_tail(avl) = avl_anchor(avl);
+ avl_set_top(avl, NULL);
+ avl_set_head(avl, NULL);
+ avl_set_tail(avl, NULL);
dec_height_and_ret:
--avl_height(avl);
return 0;
@@ -269,40 +351,77 @@ dec_height_and_ret:
static int avl_delete_2children(struct avl *const avl, struct avlh *const node)
{
- const int dir = avl_sign2type(node->balance ? node->balance : 1);
+ const int dir = node->balance ? node->balance : 1;
struct avlh *const new_node = avl_inorder(avl, node, dir);
avl_delete(avl, new_node);
++avl_count(avl);
- avlh_replace(node, new_node);
+ avlh_replace(avl, node, new_node);
new_node->balance = node->balance;
if (avl_end(avl, dir) == node)
- avl_end(avl, dir) = new_node;
+ avl_set_end(avl, dir, new_node);
return 0;
}
int avl_prepend(struct avl *const avl, struct avlh *const holder)
{
struct avlh *const parent = avl_head(avl);
- int type = parent == avl_anchor(avl) ? AVL_RIGHT : AVL_LEFT;
+ int type = parent == NULL ? AVL_RIGHT : AVL_LEFT;
- if (parent == avl_anchor(avl) || avl_cmp(avl)(parent, holder) < 0) {
- avl_insert_inner(avl, parent, holder, avl_type2sign(type));
+ if (parent == NULL || avl_cmp(avl)(holder, parent) < 0) {
+ avl_insert_inner(avl, parent, holder, type);
return 0;
}
return -EINVAL;
}
+int avl_insert_at(struct avl *const avl,
+ struct avlh *parent, int dir, struct avlh *child)
+{
+ if (parent == NULL)
+ dir = AVL_RIGHT;
+ else {
+ if (!avlh_thr_tst(avl, parent, dir))
+ return -EINVAL;
+ }
+
+ avl_insert_inner(avl, parent, child, dir);
+ return 0;
+}
+
int avl_insert(struct avl *const avl, struct avlh *const holder)
{
int delta;
struct avlh *parent;
- parent = avl_searchfn(avl)(avl, holder, &delta);
+ parent = __avl_search_inner(avl, holder, &delta);
if (delta == 0)
return -EBUSY;
- avl_insert_inner(avl, parent, holder, avl_sign2type(delta));
+ avl_insert_inner(avl, parent, holder, delta);
+
+ return 0;
+}
+
+int avl_insert_front(struct avl *const avl, struct avlh *const holder)
+{
+ int delta;
+ struct avlh *parent;
+
+ parent = avl_searchfn(avl)(avl, holder, &delta, AVL_LEFT);
+
+ avl_insert_inner(avl, parent, holder, delta ?: AVL_LEFT);
+ return 0;
+}
+
+int avl_insert_back(struct avl *const avl, struct avlh *const holder)
+{
+ int delta;
+ struct avlh *parent;
+
+ parent = avl_searchfn(avl)(avl, holder, &delta, AVL_RIGHT);
+
+ avl_insert_inner(avl, parent, holder, delta ?: AVL_RIGHT);
return 0;
}
@@ -310,8 +429,8 @@ int avl_append(struct avl *const avl, struct avlh *const
holder)
{
struct avlh *const parent = avl_tail(avl);
- if (parent == avl_anchor(avl) || avl_cmp(avl)(parent, holder) > 0) {
- avl_insert_inner(avl, parent, holder, avl_type2sign(AVL_RIGHT));
+ if (parent == NULL || avl_cmp(avl)(holder, parent) > 0) {
+ avl_insert_inner(avl, parent, holder, AVL_RIGHT);
return 0;
}
@@ -321,11 +440,10 @@ int avl_append(struct avl *const avl, struct avlh *const
holder)
struct avlh *avl_update(struct avl *const avl, struct avlh *const holder)
{
int delta;
- struct avlh *const oldh = avl_searchfn(avl)(avl, holder, &delta);
+ struct avlh *const oldh = __avl_search_inner(avl, holder, &delta);
if (!delta) {
- avlh_replace(oldh, holder);
- holder->balance = oldh->balance;
+ avl_replace(avl, oldh, holder);
return oldh;
}
@@ -335,31 +453,31 @@ struct avlh *avl_update(struct avl *const avl, struct
avlh *const holder)
struct avlh *avl_set(struct avl *const avl, struct avlh *const holder)
{
int delta;
- struct avlh *const oldh = avl_searchfn(avl)(avl, holder, &delta);
+ struct avlh *const oldh = __avl_search_inner(avl, holder, &delta);
if (delta) {
- avl_insert_inner(avl, oldh, holder, avl_sign2type(delta));
+ avl_insert_inner(avl, oldh, holder, delta);
return NULL;
}
- avlh_replace(oldh, holder);
- holder->balance = oldh->balance;
+ avl_replace(avl, oldh, holder);
return oldh;
}
-void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp)
+void avl_init(struct avl *const avl, avl_search_t *searchfn, avlh_cmp_t *cmp)
{
- avlh_init(avl_anchor(avl)); /* Beware of the union; this must be first.
*/
+ avlh_init(avl_anchor(avl)); /* this must be first. */
avl_cmp(avl) = cmp;
avl_height(avl) = 0;
avl_count(avl) = 0;
- avl_searchfn(avl) = search;
- avlh_right(avl_anchor(avl)) = avl_anchor(avl);
+ avl_searchfn(avl) = searchfn;
+ avl_set_top(avl, NULL);
- avl_head(avl) = avl_tail(avl) = avl_anchor(avl);
+ avl_set_head(avl, NULL);
+ avl_set_tail(avl, NULL);
}
-void avl_destroy(struct avl *avl)
+void avl_destroy(struct avl *const avl)
{
avl_init(avl, NULL, NULL);
}
@@ -376,5 +494,144 @@ void avl_clear(struct avl *const avl, void
(*destruct)(struct avlh *))
}
}
- avl_init(avl, avl_searchfn(avl), avl_cmp(avl));
+ avl_init(avl, NULL, NULL);
+}
+
+static inline
+void avl_dumper_visit(FILE *file, const struct avl *const avl,
+ struct avlh *node,
+ avlh_prn_t *prn, const char *blank,
+ unsigned int blank_sz, char *buf,
+ unsigned int indent, unsigned int len)
+{
+ char bal;
+
+ if (avlh_has_child(avl, node, AVL_RIGHT)) {
+ if (blank_sz >= (unsigned int) (buf-blank)) {
+ snprintf(buf, len + 3, "%*s\n", (int)len + 1, "bug!");
+ fputs(buf - blank_sz, file);
+ } else
+ avl_dumper_visit(file, avl,
+ avlh_right(avl, node),
+ prn, blank,
+ blank_sz + indent, buf, indent, len);
+ }
+
+ switch(node->balance) {
+ case 0:
+ bal = '.';
+ break;
+ case -1:
+ bal = '-';
+ break;
+ case 1:
+ bal = '+';
+ break;
+ default:
+ bal = '?'; /* Bug. */
+ }
+
+ (*prn)(buf, len+1, node);
+ buf[len] = bal;
+ buf[len+1] = '\n';
+ buf[len+2] = '\0';
+
+ fputs(buf - blank_sz, file);
+
+ if (avlh_has_child(avl, node, AVL_LEFT)) {
+ if (blank_sz >= (unsigned int)(buf - blank)) {
+ snprintf(buf, len + 3, "%*s\n", (int)len + 1, "bug!");
+ fputs(buf-blank_sz, file);
+ } else
+ avl_dumper_visit(file, avl,
+ avlh_left(avl, node),
+ prn, blank,
+ blank_sz + indent, buf, indent, len);
+ }
+}
+
+void avl_dump(FILE *file, const struct avl *const avl,
+ avlh_prn_t *prn, unsigned int indent, unsigned int len)
+{
+
+ struct avlh *holder = avl_gettop(avl);
+
+ putc('\n', file);
+ if (!holder)
+ fputs("Empty.\n", file);
+ else {
+ size_t blank_sz = (avl_height(avl) - 1) * indent;
+ char buffer[blank_sz + len + 3];
+ /* 3 == balance char + sizeof("\n\0") */
+ memset(buffer, ' ', blank_sz);
+
+ avl_dumper_visit(file, avl, holder, prn, buffer, 0,
+ buffer + blank_sz, indent, len);
+ }
+ fflush(file);
+}
+
+static int avl_check_visit(const struct avl *avl,
+ struct avlh *node, unsigned int level)
+{
+ int err;
+
+ if (!avlh_has_child(avl, node, AVL_RIGHT))
+ goto check_balance;
+
+ if (level > avl_height(avl)) {
+ fprintf(stderr, "too much recursion\n");
+ return -EINVAL;
+ }
+
+ err = avl_check_visit(avl, avlh_right(avl, node), level + 1);
+ if (err < 0)
+ return err;
+
+check_balance:
+ switch(node->balance) {
+ case 0:
+ break;
+ case -1:
+ break;
+ case 1:
+ break;
+ default:
+ fprintf(stderr, "invalid balance\n");
+ return -EINVAL;
+ }
+
+ if (!avlh_has_child(avl, node, AVL_LEFT))
+ return 0;
+
+ err = avl_check_visit(avl, avlh_left(avl, node), level + 1);
+ if (err < 0)
+ return err;
+
+ return 0;
+}
+
+int avl_check(const struct avl *avl)
+{
+ struct avlh *holder = avl_gettop(avl), *last;
+ int err;
+
+ if (!holder)
+ return 0;
+
+ err = avl_check_visit(avl, holder, 0);
+ if (err < 0)
+ return err;
+
+ last = NULL;
+ for (holder = avl_gethead(avl); holder; holder = avl_next(avl, holder))
{
+ if (last != NULL)
+ if (avl_cmp(avl)(holder, last) < 0) {
+ fprintf(stderr, "disordered nodes\n");
+ return -EINVAL;
+ }
+ last = holder;
+ }
+
+ return 0;
}
_______________________________________________
Xenomai-git mailing list
Xenomai-git@xenomai.org
https://xenomai.org/mailman/listinfo/xenomai-git
