summaryrefslogtreecommitdiffstats
path: root/libnetdata/avl/avl.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2018-11-07 12:22:44 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2018-11-07 12:22:44 +0000
commit1e6c93250172946eeb38e94a92a1fd12c9d3011e (patch)
tree8ca5e16dfc7ad6b3bf2738ca0a48408a950f8f7e /libnetdata/avl/avl.h
parentUpdate watch file (diff)
downloadnetdata-1e6c93250172946eeb38e94a92a1fd12c9d3011e.tar.xz
netdata-1e6c93250172946eeb38e94a92a1fd12c9d3011e.zip
Merging upstream version 1.11.0+dfsg.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'libnetdata/avl/avl.h')
-rw-r--r--libnetdata/avl/avl.h89
1 files changed, 89 insertions, 0 deletions
diff --git a/libnetdata/avl/avl.h b/libnetdata/avl/avl.h
new file mode 100644
index 000000000..070bb3d3d
--- /dev/null
+++ b/libnetdata/avl/avl.h
@@ -0,0 +1,89 @@
+// SPDX-License-Identifier: LGPL-3.0-or-later
+
+#ifndef _AVL_H
+#define _AVL_H 1
+
+#include "../libnetdata.h"
+
+/* Maximum AVL tree height. */
+#ifndef AVL_MAX_HEIGHT
+#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 */
+#define AVL_LOCK_INITIALIZER NETDATA_RWLOCK_INITIALIZER
+#endif /* AVL_LOCK_WITH_MUTEX */
+
+#else /* AVL_WITHOUT_PTHREADS */
+#define AVL_LOCK_INITIALIZER
+#endif /* AVL_WITHOUT_PTHREADS */
+
+/* Data structures */
+
+/* One element of the AVL tree */
+typedef struct avl {
+ struct avl *avl_link[2]; /* Subtrees. */
+ signed char avl_balance; /* Balance factor. */
+} avl;
+
+/* An AVL tree */
+typedef struct avl_tree {
+ avl *root;
+ int (*compar)(void *a, void *b);
+} avl_tree;
+
+typedef struct avl_tree_lock {
+ avl_tree avl_tree;
+
+#ifndef AVL_WITHOUT_PTHREADS
+#ifdef AVL_LOCK_WITH_MUTEX
+ netdata_mutex_t mutex;
+#else /* AVL_LOCK_WITH_MUTEX */
+ netdata_rwlock_t rwlock;
+#endif /* AVL_LOCK_WITH_MUTEX */
+#endif /* AVL_WITHOUT_PTHREADS */
+} avl_tree_lock;
+
+/* Public methods */
+
+/* Insert element a into the AVL tree t
+ * returns the added element a, or a pointer the
+ * element that is equal to a (as returned by t->compar())
+ * a is linked directly to the tree, so it has to
+ * be properly allocated by the caller.
+ */
+avl *avl_insert_lock(avl_tree_lock *tree, avl *item) NEVERNULL WARNUNUSED;
+avl *avl_insert(avl_tree *tree, avl *item) NEVERNULL WARNUNUSED;
+
+/* Remove an element a from the AVL tree t
+ * returns a pointer to the removed element
+ * or NULL if an element equal to a is not found
+ * (equal as returned by t->compar())
+ */
+avl *avl_remove_lock(avl_tree_lock *tree, avl *item) WARNUNUSED;
+avl *avl_remove(avl_tree *tree, avl *item) WARNUNUSED;
+
+/* Find the element into the tree that equal to a
+ * (equal as returned by t->compar())
+ * returns NULL is no element is equal to a
+ */
+avl *avl_search_lock(avl_tree_lock *tree, avl *item);
+avl *avl_search(avl_tree *tree, avl *item);
+
+/* Initialize the avl_tree_lock
+ */
+void avl_init_lock(avl_tree_lock *tree, int (*compar)(void *a, void *b));
+void avl_init(avl_tree *tree, int (*compar)(void *a, void *b));
+
+
+int avl_traverse_lock(avl_tree_lock *tree, int (*callback)(void *entry, void *data), void *data);
+int avl_traverse(avl_tree *tree, int (*callback)(void *entry, void *data), void *data);
+
+#endif /* avl.h */