diff options
Diffstat (limited to '')
| -rw-r--r-- | src/avl.h | 80 |
1 files changed, 31 insertions, 49 deletions
@@ -1,20 +1,12 @@ -/* - * 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> @@ -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; + pthread_mutex_t mutex; #else /* AVL_LOCK_WITH_MUTEX */ - pthread_rwlock_t rwlock; + pthread_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); +avl *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_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); +avl *avl_remove(avl_tree *t, avl *a); -/* 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)); + +void avl_traverse_lock(avl_tree_lock *t, void (*callback)(void *)); +void avl_traverse(avl_tree *t, void (*callback)(void *)); + #endif /* avl.h */ |