subject:"\[Xenomai\-git\] Philippe Gerum \: boilerplate\: add AVL library"

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2017-07-27 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2017-06-03 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2017-05-15 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2017-03-13 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2017-03-05 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2017-02-15 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2017-01-26 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2016-12-09 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2016-11-28 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2016-11-21 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2016-11-15 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2016-10-17 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2016-09-22 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2016-06-28 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

2016-06-08 Thread git repository hosting

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  (1<thr |= 1 << avl_type2index(side))
+#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1 << 
avl_type2index(side)))
+#define avlh_thr_tst(holder, side) ((holder)->thr & (1 << 
avl_type2index(side)))
+#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)])
+#define avlh_up(holder)avlh_link((holder), AVL_UP)
+#define avlh_left(holder)  avlh_link((holder), AVL_LEFT)
+#define avlh_right(holder) avlh_link((holder), AVL_RIGHT)
+#define avlh_parent_link(holder)   (avlh_link(avlh_up(holder), (holder)->type))
+
+struct avl;
+
+typedef struct avlh *avl_search_t(const struct avl *, const struct avlh *, int 
*);
+
+typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+
+struct avl {
+   struct avlh anchor;
+   avl_search_t *search;
+   avlh_cmp_t *cmp;
+   struct avlh *end[3];
+   unsigned int count;
+   unsigned int height;
+};
+
+#define avl_searchfn(avl) ((avl)->search)
+#define avl_cmp(avl)  ((avl)->cmp)
+#define avl_count(avl)((avl)->count)
+#define avl_height(avl)   ((avl)->height)
+#define avl_anchor(avl)   (&(avl)->anchor)
+#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
+#define avl_top(avl)  (avlh_right(avl_anchor(avl)))
+#define avl_head(avl) (avl_end((avl), AVL_LEFT))
+#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+
+void avl_destroy(struct avl *avl);
+
+void avl_clear(struct avl *avl, void (*destruct)(struct avlh

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

[Xenomai-git] Philippe Gerum : boilerplate: add AVL library

15 matches

Site Navigation

Mail list logo

Footer information