[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: c0f47795c6a1a6a2f7a41b912430d56aab8da62a URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=c0f47795c6a1a6a2f7a41b912430d56aab8da62a Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 92306c89a3bdc2f7d8406bc9d3ef7cbbcbb7d5db URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=92306c89a3bdc2f7d8406bc9d3ef7cbbcbb7d5db Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 0714494b9c702133bb81d4fca18162f38eb153ef URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=0714494b9c702133bb81d4fca18162f38eb153ef Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 25b4dae360ce6e5cc285cb9edef1d0f3494ca122 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=25b4dae360ce6e5cc285cb9edef1d0f3494ca122 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 0ccaba80064e2d370a87c0ec95a95629055635a7 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=0ccaba80064e2d370a87c0ec95a95629055635a7 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 4a24e1cf778025e72262cb505c07c000dfafb8e9 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=4a24e1cf778025e72262cb505c07c000dfafb8e9 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 3cd883cb29b21a04cd1a94106a53bc9cbbbca127 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=3cd883cb29b21a04cd1a94106a53bc9cbbbca127 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 93259d96c1a7a87d8f361c519ef0375f288cb975 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=93259d96c1a7a87d8f361c519ef0375f288cb975 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 62be024e6600f6cec6382f32f8808509289059d9 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=62be024e6600f6cec6382f32f8808509289059d9 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: f0cca3e87a9f3c4503c42597d64fc9dac1d8985e URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=f0cca3e87a9f3c4503c42597d64fc9dac1d8985e Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 683c573477fedacbd97160e02508d70c83a3ce9b URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=683c573477fedacbd97160e02508d70c83a3ce9b Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 7e9ad1e620889bc6bbd63565206f9f31c9496713 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=7e9ad1e620889bc6bbd63565206f9f31c9496713 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: fe7c0f7fe424e98ec9f367765d43147964812ced URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=fe7c0f7fe424e98ec9f367765d43147964812ced Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: c524e68045d189a61762514d89c5e1680dbdc857 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=c524e68045d189a61762514d89c5e1680dbdc857 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 2d4ff23966c40cf24cb0ad671a38d3d4c47aeef7 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=2d4ff23966c40cf24cb0ad671a38d3d4c47aeef7 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 843ec77368dd4efaa5939f4f0f6aec0222f5b112 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=843ec77368dd4efaa5939f4f0f6aec0222f5b112 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 6f9a4cde8a8cfa7b5efbc7e29b7747d84e9e2f80 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=6f9a4cde8a8cfa7b5efbc7e29b7747d84e9e2f80 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: e570b31cdb914620c97cbea11368e8f0264de758 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=e570b31cdb914620c97cbea11368e8f0264de758 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: wip/dovetail Commit: 0e25606b1dd4c89d42ce5177023ceb2ab180c3f5 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=0e25606b1dd4c89d42ce5177023ceb2ab180c3f5 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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(st
[Xenomai-git] Philippe Gerum : boilerplate: add AVL library
Module: xenomai-3 Branch: next Commit: 0e25606b1dd4c89d42ce5177023ceb2ab180c3f5 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=0e25606b1dd4c89d42ce5177023ceb2ab180c3f5 Author: Philippe Gerum 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 000..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 + +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_UP0 +#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 (1thr &= ~(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