Module: xenomai-3
Branch: next
Commit: 6f9a4cde8a8cfa7b5efbc7e29b7747d84e9e2f80
URL:    
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=6f9a4cde8a8cfa7b5efbc7e29b7747d84e9e2f80

Author: Philippe Gerum <r...@xenomai.org>
Date:   Tue May 31 17:30:21 2016 +0200

boilerplate: add AVL library

---

 include/boilerplate/Makefile.am |    1 +
 include/boilerplate/avl.h       |  298 ++++++++++++++++++++++++++++++
 lib/boilerplate/Makefile.am     |    1 +
 lib/boilerplate/avl.c           |  380 +++++++++++++++++++++++++++++++++++++++
 4 files changed, 680 insertions(+)

diff --git a/include/boilerplate/Makefile.am b/include/boilerplate/Makefile.am
index 2d3ace8..c975509 100644
--- a/include/boilerplate/Makefile.am
+++ b/include/boilerplate/Makefile.am
@@ -3,6 +3,7 @@ includesubdir = $(includedir)/boilerplate
 includesub_HEADERS =   \
        ancillaries.h   \
        atomic.h        \
+       avl.h           \
        compiler.h      \
        debug.h         \
        hash.h          \
diff --git a/include/boilerplate/avl.h b/include/boilerplate/avl.h
new file mode 100644
index 0000000..1aa84bf
--- /dev/null
+++ b/include/boilerplate/avl.h
@@ -0,0 +1,298 @@
+/*
+ * Copyright (c) 2015 Gilles Chanteperdrix
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+#ifndef _BOILERPLATE_AVL_H
+#define _BOILERPLATE_AVL_H
+
+#include <stdlib.h>
+
+struct avlh {
+       unsigned int thr: 3;
+       int type: 2;
+       int balance :2;
+       unsigned int flags :25;         /* Application-specific */
+       struct avlh *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 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+       struct avlh anchor;
+       avl_search_t *search;
+       avlh_cmp_t *cmp;
+       struct avlh *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))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh *));
+
+int avl_insert(struct avl *avl, struct avlh *holder);
+
+int avl_prepend(struct avl *avl, struct avlh *holder);
+
+int avl_append(struct avl *avl, struct avlh *holder);
+
+struct avlh *avl_update(struct avl *avl, struct avlh *holder);
+
+struct avlh *avl_set(struct avl *avl, struct avlh *holder);
+
+int avl_delete(struct avl *avl, struct avlh *node);
+
+static inline struct avlh *avl_gettop(struct avl *const avl)
+{
+       struct avlh *const holder = avl_top(avl);
+
+       if (holder != avl_anchor(avl))
+               return holder;
+
+       return NULL;
+}
+
+static inline struct avlh *avl_gethead(struct avl *const avl)
+{
+       struct avlh *const holder = avl_head(avl);
+
+       if (holder != avl_anchor(avl))
+               return holder;
+
+       return NULL;
+}
+
+static inline struct avlh *avl_gettail(struct avl *const avl)
+{
+       struct avlh *const holder = avl_tail(avl);
+
+       if (holder != avl_anchor(avl))
+               return holder;
+
+       return NULL;
+}
+
+static inline unsigned avl_getcount(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)
+{
+       /* Assume dir == AVL_RIGHT in comments. */
+       struct avlh *child = avlh_link(holder, dir);
+
+       /* If the current node is not right threaded, then go down left, 
starting
+          from its right child. */
+       if (!avlh_thr_tst(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;
+
+       return child;
+}
+
+static inline struct avlh *avl_postorder(struct avl *const avl,
+                                        struct avlh *const holder, const int 
dir)
+{
+       /* Assume dir == AVL_RIGHT in comments. */
+       struct avlh *next = avlh_up(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))
+                       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;
+
+       return next;
+}
+
+static inline struct avlh *avl_preorder(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. */
+       next = holder;
+
+       while (avlh_thr_tst(next, dir)) {
+               next = avlh_link(next, dir);
+               if (next == avl_anchor(avl))
+                       goto ret_null;
+       }
+
+       return avlh_link(next, dir);
+ret_null:
+       return NULL;
+}
+
+/**
+ * Get next node in symmetrical a.k.a inorder ordering.
+ */
+static inline struct avlh *avl_next(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)
+{
+       return avl_inorder(avl, holder, AVL_LEFT);
+}
+
+static inline struct avlh *avl_postorder_next(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)
+{
+       return avl_postorder(avl, holder, AVL_LEFT);
+}
+
+static inline struct avlh *avl_preorder_next(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)
+{
+       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)
+{
+       struct avlh *holder;
+       int delta;
+
+       holder = avl_searchfn(avl)(avl, node, &delta);
+       if (!delta)
+               return holder;
+
+       return NULL;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+/**
+ * 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);                             \
+                                                                       \
+       if (holder != avl_anchor(avl)) {                                \
+               while ((delta = cmp(holder, node))) {                   \
+                       delta = delta < 0 ? -1 : 1;                     \
+                       if (avlh_thr_tst(holder,avl_sign2type(delta)))  \
+                               break;                                  \
+                       holder = avlh_link(holder, avl_sign2type(delta)); \
+               }                                                       \
+       }                                                               \
+       *pdelta = delta;                                                \
+       return holder;                                                  \
+}                                                                      \
+
+#endif /* !_BOILERPLATE_AVL_H */
diff --git a/lib/boilerplate/Makefile.am b/lib/boilerplate/Makefile.am
index 4176c6d..c9f8d41 100644
--- a/lib/boilerplate/Makefile.am
+++ b/lib/boilerplate/Makefile.am
@@ -5,6 +5,7 @@ libboilerplate_la_LIBADD = libversion.la libiniparser.la
 
 libboilerplate_la_SOURCES =    \
        ancillaries.c           \
+       avl.c                   \
        hash.c                  \
        obstack.c               \
        setup.c                 \
diff --git a/lib/boilerplate/avl.c b/lib/boilerplate/avl.c
new file mode 100644
index 0000000..4dcc177
--- /dev/null
+++ b/lib/boilerplate/avl.c
@@ -0,0 +1,380 @@
+/*
+ * Copyright (c) 2015 Gilles Chanteperdrix
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+#include <stdio.h>
+#include <errno.h>
+#include <string.h>
+#include <boilerplate/avl.h>
+
+/* Internal functions used for rebalancing (for insertion and deletion). */
+static inline struct avlh *avlh_rotate(struct avlh *const holder, const int 
dir)
+{
+       const int opp_dir = avl_opposite(dir);
+       struct avlh *const nexttop = avlh_link(holder, opp_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;
+               subtree->type = opp_dir;
+       } else
+               avlh_thr_set(holder, opp_dir);
+
+       avlh_link(nexttop, dir) = holder;
+       avlh_thr_clr(nexttop, dir);
+
+       avlh_up(nexttop) = avlh_up(holder);
+       nexttop->type = holder->type;
+       avlh_up(holder) = nexttop;
+       holder->type = dir;
+
+       avlh_parent_link(nexttop) = nexttop;
+
+       return nexttop;
+}
+
+static inline struct avlh *avlh_dbl_rotate(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);
+}
+
+static struct avlh *avlh_rebalance(struct avlh *holder, const int delta)
+{
+
+       int dir = avl_sign2type(delta);
+       struct avlh *const heavy_side = avlh_link(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->balance = 0;
+       } else {
+               /* 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));
+
+               /* recompute balances. */
+               holder->balance -= heavy_side->balance;
+               heavy_side->balance -= delta;
+
+               holder = heavy_side;
+       }
+       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)
+{
+       if (holder->balance == delta)
+               /* we need to rebalance the current subtree. */
+               return avlh_rebalance(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)
+{
+       struct avlh *const child = avlh_link(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;
+       }
+}
+
+static inline void avlh_replace(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_link_child(oldh, newh, AVL_LEFT);
+       avlh_link_child(oldh, newh, AVL_RIGHT);
+}
+
+/* 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. */
+
+       struct avlh *const new_node = avlh_up(node);
+       const int dir = node->type;
+
+       /* Suppress node. */
+       avlh_link(new_node, dir) = avlh_link(node, dir);
+       avlh_thr_set(new_node, dir);
+
+       if (node == avl_end(avl, dir))
+               avl_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. */
+
+       struct avlh *const new_node = avlh_link(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);
+
+       if (node == avl_end(avl, avl_opposite(dir)))
+               avl_end(avl, avl_opposite(dir)) = new_node;
+       /* new_node->balance 0, which is correct. */
+       return new_node;
+}
+
+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)
+{
+       avlh_link(child, side) = avlh_link(parent, side);
+       avlh_link(child, avl_opposite(side)) = parent;
+       avlh_up(child) = parent;
+       avlh_link(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);
+       ++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;
+
+       /* Do not touch these for first insertion. */
+       avlh_thr_clr(parent, side);
+       parent->balance += avl_type2sign(side);
+
+       while (parent->balance) {
+               const int delta = avl_type2sign(parent->type);
+               parent = avlh_up(parent);
+               if (parent == avl_anchor(avl))
+                       goto inc_height_and_ret; /* Get away from fast path */
+               parent = avlh_balance_add(parent, delta);
+       }
+
+       return;
+
+insert_first_and_ret:
+       avl_head(avl) = avl_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) {
+       case (AVL_THR_LEFT|AVL_THR_RIGHT): /* thr is 5 */
+               avl_delete_leaf(avl, node);
+               break;
+
+       case AVL_THR_LEFT: /* only AVL_LEFT bit is on, thr is 1. */
+               node = avl_delete_1child(avl, node, AVL_RIGHT);
+               break;
+
+       case AVL_THR_RIGHT: /* only AVL_RIGHT bit is on, thr is 4. */
+               node = avl_delete_1child(avl, node, AVL_LEFT);
+               break;
+
+       case 0:
+               return avl_delete_2children(avl, node);
+       }
+
+       /* node is the first node which needs to be rebalanced.
+          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);
+               if (node == avl_anchor(avl))
+                       goto dec_height_and_ret;
+               node = avlh_balance_add(node, delta);
+       }
+
+       return 0;
+
+delete_last_and_ret:
+       avl_top(avl) = avl_head(avl) = avl_tail(avl) = avl_anchor(avl);
+dec_height_and_ret:
+       --avl_height(avl);
+       return 0;
+}
+
+static int avl_delete_2children(struct avl *const avl, struct avlh *const node)
+{
+       const int dir = avl_sign2type(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);
+       new_node->balance = node->balance;
+       if (avl_end(avl, dir) == node)
+               avl_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;
+
+       if (parent == avl_anchor(avl) || avl_cmp(avl)(parent, holder) < 0) {
+               avl_insert_inner(avl, parent, holder, avl_type2sign(type));
+               return 0;
+       }
+
+       return -EINVAL;
+}
+
+int avl_insert(struct avl *const avl, struct avlh *const holder)
+{
+       int delta;
+       struct avlh *parent;
+
+       parent = avl_searchfn(avl)(avl, holder, &delta);
+       if (delta == 0)
+               return -EBUSY;
+
+       avl_insert_inner(avl, parent, holder, avl_sign2type(delta));
+       return 0;
+}
+
+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));
+               return 0;
+       }
+
+       return -EINVAL;
+}
+
+struct avlh *avl_update(struct avl *const avl, struct avlh *const holder)
+{
+       int delta;
+       struct avlh *const oldh = avl_searchfn(avl)(avl, holder, &delta);
+
+       if (!delta) {
+               avlh_replace(oldh, holder);
+               holder->balance = oldh->balance;
+               return oldh;
+       }
+
+       return NULL;
+}
+
+struct avlh *avl_set(struct avl *const avl, struct avlh *const holder)
+{
+       int delta;
+       struct avlh *const oldh = avl_searchfn(avl)(avl, holder, &delta);
+
+       if (delta) {
+               avl_insert_inner(avl, oldh, holder, avl_sign2type(delta));
+               return NULL;
+       }
+
+       avlh_replace(oldh, holder);
+       holder->balance = oldh->balance;
+       return oldh;
+}
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp)
+{
+       avlh_init(avl_anchor(avl)); /* Beware of the union; 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_head(avl) = avl_tail(avl) = avl_anchor(avl);
+}
+
+void avl_destroy(struct avl *avl)
+{
+       avl_init(avl, NULL, NULL);
+}
+
+void avl_clear(struct avl *const avl, void (*destruct)(struct avlh *))
+{
+       if (destruct) {
+               struct avlh *next, *holder = avl_gethead(avl);
+
+               while (holder) {
+                       next = avl_postorder_next(avl, holder);
+                       destruct(holder);
+                       holder = next;
+               }
+       }
+
+       avl_init(avl, avl_searchfn(avl), avl_cmp(avl));
+}


_______________________________________________
Xenomai-git mailing list
Xenomai-git@xenomai.org
https://xenomai.org/mailman/listinfo/xenomai-git

Reply via email to