diff options
Diffstat (limited to 'src/avl.h')
-rwxr-xr-x | src/avl.h | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/src/avl.h b/src/avl.h new file mode 100755 index 000000000..cbcc41211 --- /dev/null +++ b/src/avl.h @@ -0,0 +1,80 @@ +/* + * 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 + +#include <pthread.h> + +// #define AVL_LOCK_WITH_MUTEX 1 + +/* Data structures */ + +/* One element of the AVL tree */ +typedef struct avl { + struct avl* left; + struct avl* right; + signed char balance; +} avl; + +/* An AVL tree */ +typedef struct avl_tree { + avl* root; + int (*compar)(void* a, void* b); + +#ifdef AVL_LOCK_WITH_MUTEX + pthread_mutex_t mutex; +#else + pthread_rwlock_t rwlock; +#endif +} avl_tree; + +/* 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 + */ +int avl_insert(avl_tree* t, avl* a); + +/* 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(avl_tree* t, avl* a); + +/* Remove the root of the AVL tree t + * Warning: dumps core if t is empty + */ +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 + */ +int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret); + +/* 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*), avl** ret); + +/* Initialize the avl_tree + */ +void avl_init(avl_tree* t, int (*compar)(void* a, void* b)); + +#endif /* avl.h */ |