X-Git-Url: https://arthur.barton.de/gitweb/?a=blobdiff_plain;f=src%2Favl.h;h=19648cd1db8ed1d719ee5e47390d8d54e2b4399f;hb=909e26f825bc1f6f907231761412c885331fec7e;hp=5397b196e81a9b34b7f980d40cbe2cdcad0af50f;hpb=ff91f2d1b765250ae2f345327e4a17b3e7b59f44;p=netdata.git

diff --git a/src/avl.h b/src/avl.h
index 5397b196..19648cd1 100644
--- a/src/avl.h
+++ b/src/avl.h
@@ -1,29 +1,21 @@
-/*
- * ANSI C Library for maintainance of AVL Balanced Trees
- *
- * ref.:
- *  G. M. Adelson-Velskij & E. M. Landis
- *  Doklady Akad. Nauk SSSR 146 (1962), 263-266
- *
- * see also:
- *  D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
- *
- * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
- * Released under GNU General Public License (GPL) version 2
- *
- */
+
 #ifndef _AVL_H
 #define _AVL_H 1
 
+/* 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 PTHREAD_MUTEX_INITIALIZER
+#define AVL_LOCK_INITIALIZER NETDATA_MUTEX_INITIALIZER
 #else /* AVL_LOCK_WITH_MUTEX */
-#define AVL_LOCK_INITIALIZER PTHREAD_RWLOCK_INITIALIZER
+#define AVL_LOCK_INITIALIZER NETDATA_RWLOCK_INITIALIZER
 #endif /* AVL_LOCK_WITH_MUTEX */
 
 #else /* AVL_WITHOUT_PTHREADS */
@@ -34,26 +26,24 @@
 
 /* One element of the AVL tree */
 typedef struct avl {
-	struct avl* left;
-	struct avl* right;
-	signed char balance;
+    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 *root;
+    int (*compar)(void *a, void *b);
 } avl_tree;
 
 typedef struct avl_tree_lock {
-	avl_tree avl_tree;
+    avl_tree avl_tree;
 
 #ifndef AVL_WITHOUT_PTHREADS
 #ifdef AVL_LOCK_WITH_MUTEX
-	pthread_mutex_t mutex;
+    netdata_mutex_t mutex;
 #else /* AVL_LOCK_WITH_MUTEX */
-	pthread_rwlock_t rwlock;
+    netdata_rwlock_t rwlock;
 #endif /* AVL_LOCK_WITH_MUTEX */
 #endif /* AVL_WITHOUT_PTHREADS */
 } avl_tree_lock;
@@ -61,37 +51,25 @@ typedef struct avl_tree_lock {
 /* Public methods */
 
 /* Insert element a into the AVL tree t
- * returns 1 if the depth of the tree has grown
- * Warning: do not insert elements already present
+ * 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.
  */
-int avl_insert_lock(avl_tree_lock *t, avl *a);
-int avl_insert(avl_tree *t, avl *a);
+avl *avl_insert_lock(avl_tree_lock *t, avl *a) NEVERNULL WARNUNUSED;
+avl *avl_insert(avl_tree *t, avl *a) NEVERNULL WARNUNUSED;
 
 /* Remove an element a from the AVL tree t
- * returns -1 if the depth of the tree has shrunk
- * Warning: if the element is not present in the tree,
- *          returns 0 as if it had been removed succesfully.
- */
-int avl_remove_lock(avl_tree_lock *t, avl *a);
-int avl_remove(avl_tree *t, avl *a);
-
-/* Remove the root of the AVL tree t
- * Warning: dumps core if t is empty
- */
-int avl_removeroot_lock(avl_tree_lock *t);
-int avl_removeroot(avl_tree *t);
-
-/* Iterate through elements in t from a range between a and b (inclusive)
- * for each element calls iter(a) until it returns 0
- * returns the last value returned by iterator or 0 if there were no calls
- * Warning: a<=b must hold
+ * returns a pointer to the removed element
+ * or NULL if an element equal to a is not found
+ * (equal as returned by t->compar())
  */
-int avl_range_lock(avl_tree_lock *t, avl *a, avl *b, int (*iter)(avl *), avl **ret);
-int avl_range(avl_tree *t, avl *a, avl *b, int (*iter)(avl *), avl **ret);
+avl *avl_remove_lock(avl_tree_lock *t, avl *a) WARNUNUSED;
+avl *avl_remove(avl_tree *t, avl *a) WARNUNUSED;
 
-/* Iterate through elements in t equal to a
- * for each element calls iter(a) until it returns 0
- * returns the last value returned by iterator or 0 if there were no calls
+/* 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 *t, avl *a);
 avl *avl_search(avl_tree *t, avl *a);
@@ -101,4 +79,8 @@ avl *avl_search(avl_tree *t, avl *a);
 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b));
 void avl_init(avl_tree *t, int (*compar)(void *a, void *b));
 
+
+int avl_traverse_lock(avl_tree_lock *t, int (*callback)(void *entry, void *data), void *data);
+int avl_traverse(avl_tree *t, int (*callback)(void *entry, void *data), void *data);
+
 #endif /* avl.h */