-/*
- * 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
- *
- */
-#include <pthread.h>
#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
+#else /* AVL_LOCK_WITH_MUTEX */
+#define AVL_LOCK_INITIALIZER PTHREAD_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* 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);
- pthread_rwlock_t rwlock;
+ 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
+ pthread_mutex_t mutex;
+#else /* AVL_LOCK_WITH_MUTEX */
+ pthread_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 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(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.
+ * 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_remove(avl_tree* t, avl* a);
+avl *avl_remove_lock(avl_tree_lock *t, avl *a) WARNUNUSED;
+avl *avl_remove(avl_tree *t, avl *a) WARNUNUSED;
-/* Remove the root of the AVL tree t
- * Warning: dumps core if t is empty
+/* 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
*/
-int avl_removeroot(avl_tree* t);
+avl *avl_search_lock(avl_tree_lock *t, avl *a);
+avl *avl_search(avl_tree *t, avl *a);
-/* 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
+/* Initialize the avl_tree_lock
*/
-int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl* a), avl** ret);
+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));
-/* 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
- */
-int avl_search(avl_tree* t, avl* a, int (*iter)(avl* a), avl** ret);
-/* Initialize the avl_tree
- */
-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 */