2 * ANSI C Library for maintainance of AVL Balanced Trees
5 * G. M. Adelson-Velskij & E. M. Landis
6 * Doklady Akad. Nauk SSSR 146 (1962), 263-266
9 * D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
11 * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
12 * Released under GNU General Public License (GPL) version 2
18 #ifndef AVL_WITHOUT_PTHREADS
20 #endif /* AVL_WITHOUT_PTHREADS */
22 // #define AVL_LOCK_WITH_MUTEX 1
26 /* One element of the AVL tree */
34 typedef struct avl_tree {
36 int (*compar)(void* a, void* b);
38 #ifndef AVL_WITHOUT_PTHREADS
39 #ifdef AVL_LOCK_WITH_MUTEX
40 pthread_mutex_t mutex;
41 #else /* AVL_LOCK_WITH_MUTEX */
42 pthread_rwlock_t rwlock;
43 #endif /* AVL_LOCK_WITH_MUTEX */
44 #endif /* AVL_WITHOUT_PTHREADS */
49 /* Insert element a into the AVL tree t
50 * returns 1 if the depth of the tree has grown
51 * Warning: do not insert elements already present
53 int avl_insert(avl_tree* t, avl* a);
55 /* Remove an element a from the AVL tree t
56 * returns -1 if the depth of the tree has shrunk
57 * Warning: if the element is not present in the tree,
58 * returns 0 as if it had been removed succesfully.
60 int avl_remove(avl_tree* t, avl* a);
62 /* Remove the root of the AVL tree t
63 * Warning: dumps core if t is empty
65 int avl_removeroot(avl_tree* t);
67 /* Iterate through elements in t from a range between a and b (inclusive)
68 * for each element calls iter(a) until it returns 0
69 * returns the last value returned by iterator or 0 if there were no calls
70 * Warning: a<=b must hold
72 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret);
74 /* Iterate through elements in t equal to a
75 * for each element calls iter(a) until it returns 0
76 * returns the last value returned by iterator or 0 if there were no calls
78 int avl_search(avl_tree* t, avl* a, int (*iter)(avl*), avl** ret);
80 /* Initialize the avl_tree
82 void avl_init(avl_tree* t, int (*compar)(void* a, void* b));