[Xenomai-git] Gilles Chanteperdrix : boilerplate/avl: merge pshared support for AVL trees
Module: xenomai-3
Branch: wip/heapmem
Commit: 748488c18143c680696714428dda8e05a9bd31c0
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=748488c18143c680696714428dda8e05a9bd31c0
Author: Gilles Chanteperdrix
Date: Tue Jul 12 20:29:22 2016 +0200
boilerplate/avl: merge pshared support for AVL trees
Make the AVL tree usable in shared memory when AVL_SHARED is defined
at build time, switching to offset-based memory references.
Gilles published this code in July 2016 as part of his personal
toolkit for hobby projects aka 'libchutils'.
---
include/boilerplate/avl.h | 472 --
lib/boilerplate/avl.c | 497 ++---
2 files changed, 697 insertions(+), 272 deletions(-)
diff --git a/include/boilerplate/avl.h b/include/boilerplate/avl.h
index 1aa84bf..34fb23a 100644
--- a/include/boilerplate/avl.h
+++ b/include/boilerplate/avl.h
@@ -23,276 +23,444 @@
#ifndef _BOILERPLATE_AVL_H
#define _BOILERPLATE_AVL_H
-#include
+#include
+#include
struct avlh {
- unsigned int thr: 3;
+#define AVLH_APP_BITS 28
+ unsigned int flags: AVLH_APP_BITS;
int type: 2;
- int balance :2;
- unsigned int flags :25; /* Application-specific */
- struct avlh *link[3];
+ int balance: 2;
+ union {
+ ptrdiff_t offset;
+ struct avlh *ptr;
+ } link[3];
};
-/* Using -1 and 1 for left and right is slightly faster than 0 and 1, using 0
- for "up" is just here for orthogonality... and avoid wasting 4 bytes or
- having to use a union in struct avlh. */
-#define AVL_LEFT -1
-#define AVL_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
*);
-
+/*
+ * Comparison function: should return -1 if left is less than right, 0
+ * if they are equal and 1 if left is greather than right. You can use
+ * the avl_sign function which will convert a difference to -1, 0,
+ * 1. Beware of overflow however. You can also use avl_cmp_sign()
+ * which should not have any such problems.
+ */
typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+typedef struct avlh *
+avl_search_t(const struct avl *, const struct avlh *, int *, int);
+
+typedef int avlh_prn_t(char *, size_t, const struct avlh *const);
+
struct avl {
struct avlh anchor;
avl_search_t *search;
avlh_cmp_t *cmp;
- struct avlh *end[3];
+ union {
+ ptrdiff_t offset;
+ struct avlh *ptr;
+ } end[3];
unsigned int count;
unsigned int height;
};
-#define avl_searchfn(avl) ((avl)->search)
-#define avl_cmp(avl) ((avl)->cmp)
-#define avl_count(avl)((avl)->count)
-#define avl_height(avl) ((avl)->height)
-#define avl_anchor(avl) (&(avl)->anchor)
-#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
-#define avl_top(avl) (avlh_right(avl_anchor(avl)))
-#define avl_head(avl) (avl_end((avl), AVL_LEFT))
-#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+#define AVL_LEFT-1
+#define AVL_UP 0
+#define AVL_RIGHT1
+/* maps AVL_LEFT to AVL_RIGHT and reciprocally. */
+#define avl_opposite(type) (-(type))
+/* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */
+#define avl_type2index(type) ((type)+1)
-#ifdef __cplusplus
-extern "C" {
-#endif
+#define AVL_THR_LEFT (1 << avl_type2index(AVL_LEFT))
+#define AVL_THR_RIGHT (1 << avl_type2index(AVL_RIGHT))
-void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+#define avlh_up(avl, holder) avlh_link((avl), (holder), AVL_UP)
+#define avlh_left(avl, holder) avlh_link((avl), (holder), AVL_LEFT)
+#define avlh_right(avl, holder)avlh_link((avl), (holder), AVL_RIGHT)
-void avl_destroy(struct avl *avl);
+#define avlh_thr_tst(avl, holder, side) (avlh_link(avl, holder, side) == NULL)
+#define avlh_child(avl, holder, side) (av
[Xenomai-git] Gilles Chanteperdrix : boilerplate/avl: merge pshared support for AVL trees
Module: xenomai-3
Branch: wip/heapmem
Commit: 8ae78f22f49024090218d55487db85e842a9f877
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=8ae78f22f49024090218d55487db85e842a9f877
Author: Gilles Chanteperdrix
Date: Tue Jul 12 20:29:22 2016 +0200
boilerplate/avl: merge pshared support for AVL trees
Make the AVL tree usable in shared memory when AVL_SHARED is defined
at build time, switching to offset-based memory references.
Gilles published this code in July 2016 as part of his personal
toolkit for hobby projects aka 'libchutils'.
---
include/boilerplate/avl.h | 472 --
lib/boilerplate/avl.c | 497 ++---
2 files changed, 697 insertions(+), 272 deletions(-)
diff --git a/include/boilerplate/avl.h b/include/boilerplate/avl.h
index 1aa84bf..34fb23a 100644
--- a/include/boilerplate/avl.h
+++ b/include/boilerplate/avl.h
@@ -23,276 +23,444 @@
#ifndef _BOILERPLATE_AVL_H
#define _BOILERPLATE_AVL_H
-#include
+#include
+#include
struct avlh {
- unsigned int thr: 3;
+#define AVLH_APP_BITS 28
+ unsigned int flags: AVLH_APP_BITS;
int type: 2;
- int balance :2;
- unsigned int flags :25; /* Application-specific */
- struct avlh *link[3];
+ int balance: 2;
+ union {
+ ptrdiff_t offset;
+ struct avlh *ptr;
+ } link[3];
};
-/* Using -1 and 1 for left and right is slightly faster than 0 and 1, using 0
- for "up" is just here for orthogonality... and avoid wasting 4 bytes or
- having to use a union in struct avlh. */
-#define AVL_LEFT -1
-#define AVL_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
*);
-
+/*
+ * Comparison function: should return -1 if left is less than right, 0
+ * if they are equal and 1 if left is greather than right. You can use
+ * the avl_sign function which will convert a difference to -1, 0,
+ * 1. Beware of overflow however. You can also use avl_cmp_sign()
+ * which should not have any such problems.
+ */
typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+typedef struct avlh *
+avl_search_t(const struct avl *, const struct avlh *, int *, int);
+
+typedef int avlh_prn_t(char *, size_t, const struct avlh *const);
+
struct avl {
struct avlh anchor;
avl_search_t *search;
avlh_cmp_t *cmp;
- struct avlh *end[3];
+ union {
+ ptrdiff_t offset;
+ struct avlh *ptr;
+ } end[3];
unsigned int count;
unsigned int height;
};
-#define avl_searchfn(avl) ((avl)->search)
-#define avl_cmp(avl) ((avl)->cmp)
-#define avl_count(avl)((avl)->count)
-#define avl_height(avl) ((avl)->height)
-#define avl_anchor(avl) (&(avl)->anchor)
-#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
-#define avl_top(avl) (avlh_right(avl_anchor(avl)))
-#define avl_head(avl) (avl_end((avl), AVL_LEFT))
-#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+#define AVL_LEFT-1
+#define AVL_UP 0
+#define AVL_RIGHT1
+/* maps AVL_LEFT to AVL_RIGHT and reciprocally. */
+#define avl_opposite(type) (-(type))
+/* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */
+#define avl_type2index(type) ((type)+1)
-#ifdef __cplusplus
-extern "C" {
-#endif
+#define AVL_THR_LEFT (1 << avl_type2index(AVL_LEFT))
+#define AVL_THR_RIGHT (1 << avl_type2index(AVL_RIGHT))
-void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+#define avlh_up(avl, holder) avlh_link((avl), (holder), AVL_UP)
+#define avlh_left(avl, holder) avlh_link((avl), (holder), AVL_LEFT)
+#define avlh_right(avl, holder)avlh_link((avl), (holder), AVL_RIGHT)
-void avl_destroy(struct avl *avl);
+#define avlh_thr_tst(avl, holder, side) (avlh_link(avl, holder, side) == NULL)
+#define avlh_child(avl, holder, side) (av
[Xenomai-git] Gilles Chanteperdrix : boilerplate/avl: merge pshared support for AVL trees
Module: xenomai-3
Branch: next
Commit: 3892e3e6fa10ad62024c956c83cca4beed8494be
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=3892e3e6fa10ad62024c956c83cca4beed8494be
Author: Gilles Chanteperdrix
Date: Tue Jul 12 20:29:22 2016 +0200
boilerplate/avl: merge pshared support for AVL trees
Make the AVL tree usable in shared memory when AVL_SHARED is defined
at build time, switching to offset-based memory references.
Gilles published this code in July 2016 as part of his personal
toolkit for hobby projects aka 'libchutils'.
---
include/boilerplate/avl.h | 472 --
lib/boilerplate/avl.c | 497 ++---
2 files changed, 697 insertions(+), 272 deletions(-)
diff --git a/include/boilerplate/avl.h b/include/boilerplate/avl.h
index 1aa84bf..34fb23a 100644
--- a/include/boilerplate/avl.h
+++ b/include/boilerplate/avl.h
@@ -23,276 +23,444 @@
#ifndef _BOILERPLATE_AVL_H
#define _BOILERPLATE_AVL_H
-#include
+#include
+#include
struct avlh {
- unsigned int thr: 3;
+#define AVLH_APP_BITS 28
+ unsigned int flags: AVLH_APP_BITS;
int type: 2;
- int balance :2;
- unsigned int flags :25; /* Application-specific */
- struct avlh *link[3];
+ int balance: 2;
+ union {
+ ptrdiff_t offset;
+ struct avlh *ptr;
+ } link[3];
};
-/* Using -1 and 1 for left and right is slightly faster than 0 and 1, using 0
- for "up" is just here for orthogonality... and avoid wasting 4 bytes or
- having to use a union in struct avlh. */
-#define AVL_LEFT -1
-#define AVL_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
*);
-
+/*
+ * Comparison function: should return -1 if left is less than right, 0
+ * if they are equal and 1 if left is greather than right. You can use
+ * the avl_sign function which will convert a difference to -1, 0,
+ * 1. Beware of overflow however. You can also use avl_cmp_sign()
+ * which should not have any such problems.
+ */
typedef int avlh_cmp_t(const struct avlh *const, const struct avlh *const);
+typedef struct avlh *
+avl_search_t(const struct avl *, const struct avlh *, int *, int);
+
+typedef int avlh_prn_t(char *, size_t, const struct avlh *const);
+
struct avl {
struct avlh anchor;
avl_search_t *search;
avlh_cmp_t *cmp;
- struct avlh *end[3];
+ union {
+ ptrdiff_t offset;
+ struct avlh *ptr;
+ } end[3];
unsigned int count;
unsigned int height;
};
-#define avl_searchfn(avl) ((avl)->search)
-#define avl_cmp(avl) ((avl)->cmp)
-#define avl_count(avl)((avl)->count)
-#define avl_height(avl) ((avl)->height)
-#define avl_anchor(avl) (&(avl)->anchor)
-#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)])
-#define avl_top(avl) (avlh_right(avl_anchor(avl)))
-#define avl_head(avl) (avl_end((avl), AVL_LEFT))
-#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
+#define AVL_LEFT-1
+#define AVL_UP 0
+#define AVL_RIGHT1
+/* maps AVL_LEFT to AVL_RIGHT and reciprocally. */
+#define avl_opposite(type) (-(type))
+/* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */
+#define avl_type2index(type) ((type)+1)
-#ifdef __cplusplus
-extern "C" {
-#endif
+#define AVL_THR_LEFT (1 << avl_type2index(AVL_LEFT))
+#define AVL_THR_RIGHT (1 << avl_type2index(AVL_RIGHT))
-void avl_init(struct avl *avl, avl_search_t *search, avlh_cmp_t *cmp);
+#define avlh_up(avl, holder) avlh_link((avl), (holder), AVL_UP)
+#define avlh_left(avl, holder) avlh_link((avl), (holder), AVL_LEFT)
+#define avlh_right(avl, holder)avlh_link((avl), (holder), AVL_RIGHT)
-void avl_destroy(struct avl *avl);
+#define avlh_thr_tst(avl, holder, side) (avlh_link(avl, holder, side) == NULL)
+#define avlh_child(avl, holder, side) (avlh_link
