summaryrefslogtreecommitdiffstats
path: root/libnetdata/avl
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2023-07-20 04:50:01 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2023-07-20 04:50:01 +0000
commitcd4377fab21e0f500bef7f06543fa848a039c1e0 (patch)
treeba00a55e430c052d6bed0b61c0f8bbe8ebedd313 /libnetdata/avl
parentReleasing debian version 1.40.1-1. (diff)
downloadnetdata-cd4377fab21e0f500bef7f06543fa848a039c1e0.tar.xz
netdata-cd4377fab21e0f500bef7f06543fa848a039c1e0.zip
Merging upstream version 1.41.0.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'libnetdata/avl')
-rw-r--r--libnetdata/avl/avl.c79
-rw-r--r--libnetdata/avl/avl.h32
2 files changed, 45 insertions, 66 deletions
diff --git a/libnetdata/avl/avl.c b/libnetdata/avl/avl.c
index 5a4c1a983..eef4c3116 100644
--- a/libnetdata/avl/avl.c
+++ b/libnetdata/avl/avl.c
@@ -316,34 +316,36 @@ int avl_traverse(avl_tree_type *tree, int (*callback)(void * /*entry*/, void * /
// ---------------------------
// locks
-void avl_read_lock(avl_tree_lock *t) {
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
- netdata_mutex_lock(&t->mutex);
-#else
+static inline void avl_read_lock(avl_tree_lock *t) {
+#if defined(AVL_LOCK_WITH_RWLOCK)
netdata_rwlock_rdlock(&t->rwlock);
+#else
+ rw_spinlock_read_lock(&t->rwlock);
#endif
-#endif /* AVL_WITHOUT_PTHREADS */
}
-void avl_write_lock(avl_tree_lock *t) {
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
- netdata_mutex_lock(&t->mutex);
-#else
+static inline void avl_write_lock(avl_tree_lock *t) {
+#if defined(AVL_LOCK_WITH_RWLOCK)
netdata_rwlock_wrlock(&t->rwlock);
+#else
+ rw_spinlock_write_lock(&t->rwlock);
#endif
-#endif /* AVL_WITHOUT_PTHREADS */
}
-void avl_unlock(avl_tree_lock *t) {
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
- netdata_mutex_unlock(&t->mutex);
+static inline void avl_read_unlock(avl_tree_lock *t) {
+#if defined(AVL_LOCK_WITH_RWLOCK)
+ netdata_rwlock_unlock(&t->rwlock);
#else
+ rw_spinlock_read_unlock(&t->rwlock);
+#endif
+}
+
+static inline void avl_write_unlock(avl_tree_lock *t) {
+#if defined(AVL_LOCK_WITH_RWLOCK)
netdata_rwlock_unlock(&t->rwlock);
+#else
+ rw_spinlock_write_unlock(&t->rwlock);
#endif
-#endif /* AVL_WITHOUT_PTHREADS */
}
// ---------------------------
@@ -352,63 +354,46 @@ void avl_unlock(avl_tree_lock *t) {
void avl_init_lock(avl_tree_lock *tree, int (*compar)(void * /*a*/, void * /*b*/)) {
avl_init(&tree->avl_tree, compar);
-#ifndef AVL_WITHOUT_PTHREADS
- int lock;
-
-#ifdef AVL_LOCK_WITH_MUTEX
- lock = netdata_mutex_init(&tree->mutex, NULL);
+#if defined(AVL_LOCK_WITH_RWLOCK)
+ if(netdata_rwlock_init(&tree->rwlock) != 0)
+ fatal("Failed to initialize AVL rwlock");
#else
- lock = netdata_rwlock_init(&tree->rwlock);
+ rw_spinlock_init(&tree->rwlock);
#endif
-
- if(lock != 0)
- fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
-
-#endif /* AVL_WITHOUT_PTHREADS */
}
-void avl_destroy_lock(avl_tree_lock *tree) {
-#ifndef AVL_WITHOUT_PTHREADS
- int lock;
-
-#ifdef AVL_LOCK_WITH_MUTEX
- lock = netdata_mutex_destroy(&tree->mutex);
-#else
- lock = netdata_rwlock_destroy(&tree->rwlock);
+void avl_destroy_lock(avl_tree_lock *tree __maybe_unused) {
+#if defined(AVL_LOCK_WITH_RWLOCK)
+ if(netdata_rwlock_destroy(&tree->rwlock) != 0)
+ fatal("Failed to destroy AVL rwlock");
#endif
-
- if(lock != 0)
- fatal("Failed to destroy AVL mutex/rwlock, error: %d", lock);
-
-#endif /* AVL_WITHOUT_PTHREADS */
}
avl_t *avl_search_lock(avl_tree_lock *tree, avl_t *item) {
avl_read_lock(tree);
avl_t *ret = avl_search(&tree->avl_tree, item);
- avl_unlock(tree);
+ avl_read_unlock(tree);
return ret;
}
avl_t * avl_remove_lock(avl_tree_lock *tree, avl_t *item) {
avl_write_lock(tree);
avl_t *ret = avl_remove(&tree->avl_tree, item);
- avl_unlock(tree);
+ avl_write_unlock(tree);
return ret;
}
avl_t *avl_insert_lock(avl_tree_lock *tree, avl_t *item) {
avl_write_lock(tree);
avl_t * ret = avl_insert(&tree->avl_tree, item);
- avl_unlock(tree);
+ avl_write_unlock(tree);
return ret;
}
int avl_traverse_lock(avl_tree_lock *tree, int (*callback)(void * /*entry*/, void * /*data*/), void *data) {
- int ret;
avl_read_lock(tree);
- ret = avl_traverse(&tree->avl_tree, callback, data);
- avl_unlock(tree);
+ int ret = avl_traverse(&tree->avl_tree, callback, data);
+ avl_read_unlock(tree);
return ret;
}
diff --git a/libnetdata/avl/avl.h b/libnetdata/avl/avl.h
index eba967fd0..595d6ec6c 100644
--- a/libnetdata/avl/avl.h
+++ b/libnetdata/avl/avl.h
@@ -10,20 +10,11 @@
#define AVL_MAX_HEIGHT 92
#endif
-#ifndef AVL_WITHOUT_PTHREADS
-#include <pthread.h>
-
-// #define AVL_LOCK_WITH_MUTEX 1
-
-#ifdef AVL_LOCK_WITH_MUTEX
-#define AVL_LOCK_INITIALIZER NETDATA_MUTEX_INITIALIZER
-#else /* AVL_LOCK_WITH_MUTEX */
+#if defined(AVL_LOCK_WITH_RWLOCK)
#define AVL_LOCK_INITIALIZER NETDATA_RWLOCK_INITIALIZER
-#endif /* AVL_LOCK_WITH_MUTEX */
-
-#else /* AVL_WITHOUT_PTHREADS */
-#define AVL_LOCK_INITIALIZER
-#endif /* AVL_WITHOUT_PTHREADS */
+#else
+#define AVL_LOCK_INITIALIZER NETDATA_RW_SPINLOCK_INITIALIZER
+#endif
/* Data structures */
@@ -33,6 +24,11 @@ typedef struct avl_element {
signed char avl_balance; /* Balance factor. */
} avl_t;
+typedef struct __attribute__((packed)) avl_element_packed {
+ struct avl_element *avl_link[2]; /* Subtrees. */
+ signed char avl_balance; /* Balance factor. */
+} avl_t_packed;
+
/* An AVL tree */
typedef struct avl_tree_type {
avl_t *root;
@@ -42,13 +38,11 @@ typedef struct avl_tree_type {
typedef struct avl_tree_lock {
avl_tree_type avl_tree;
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
- netdata_mutex_t mutex;
-#else /* AVL_LOCK_WITH_MUTEX */
+#if defined(AVL_LOCK_WITH_RWLOCK)
netdata_rwlock_t rwlock;
-#endif /* AVL_LOCK_WITH_MUTEX */
-#endif /* AVL_WITHOUT_PTHREADS */
+#else
+ RW_SPINLOCK rwlock;
+#endif
} avl_tree_lock;
/* Public methods */