Module: xenomai-3 Branch: wip/dovetail Commit: 0e25606b1dd4c89d42ce5177023ceb2ab180c3f5 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=0e25606b1dd4c89d42ce5177023ceb2ab180c3f5
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