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
20 // #define AVL_LOCK_WITH_MUTEX 1
24 /* One element of the AVL tree */
32 typedef struct avl_tree {
34 int (*compar)(void* a, void* b);
36 #ifdef AVL_LOCK_WITH_MUTEX
37 pthread_mutex_t mutex;
39 pthread_rwlock_t rwlock;
45 /* Insert element a into the AVL tree t
46 * returns 1 if the depth of the tree has grown
47 * Warning: do not insert elements already present
49 int avl_insert(avl_tree* t, avl* a);
51 /* Remove an element a from the AVL tree t
52 * returns -1 if the depth of the tree has shrunk
53 * Warning: if the element is not present in the tree,
54 * returns 0 as if it had been removed succesfully.
56 int avl_remove(avl_tree* t, avl* a);
58 /* Remove the root of the AVL tree t
59 * Warning: dumps core if t is empty
61 int avl_removeroot(avl_tree* t);
63 /* Iterate through elements in t from a range between a and b (inclusive)
64 * for each element calls iter(a) until it returns 0
65 * returns the last value returned by iterator or 0 if there were no calls
66 * Warning: a<=b must hold
68 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret);
70 /* Iterate through elements in t equal to a
71 * for each element calls iter(a) until it returns 0
72 * returns the last value returned by iterator or 0 if there were no calls
74 int avl_search(avl_tree* t, avl* a, int (*iter)(avl*), avl** ret);
76 /* Initialize the avl_tree
78 void avl_init(avl_tree* t, int (*compar)(void* a, void* b));