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