5 /* Maximum AVL tree height. */
7 #define AVL_MAX_HEIGHT 92
10 #ifndef AVL_WITHOUT_PTHREADS
13 // #define AVL_LOCK_WITH_MUTEX 1
15 #ifdef AVL_LOCK_WITH_MUTEX
16 #define AVL_LOCK_INITIALIZER PTHREAD_MUTEX_INITIALIZER
17 #else /* AVL_LOCK_WITH_MUTEX */
18 #define AVL_LOCK_INITIALIZER PTHREAD_RWLOCK_INITIALIZER
19 #endif /* AVL_LOCK_WITH_MUTEX */
21 #else /* AVL_WITHOUT_PTHREADS */
22 #define AVL_LOCK_INITIALIZER
23 #endif /* AVL_WITHOUT_PTHREADS */
27 /* One element of the AVL tree */
29 struct avl *avl_link[2]; /* Subtrees. */
30 signed char avl_balance; /* Balance factor. */
34 typedef struct avl_tree {
36 int (*compar)(void *a, void *b);
39 typedef struct avl_tree_lock {
42 #ifndef AVL_WITHOUT_PTHREADS
43 #ifdef AVL_LOCK_WITH_MUTEX
44 pthread_mutex_t mutex;
45 #else /* AVL_LOCK_WITH_MUTEX */
46 pthread_rwlock_t rwlock;
47 #endif /* AVL_LOCK_WITH_MUTEX */
48 #endif /* AVL_WITHOUT_PTHREADS */
53 /* Insert element a into the AVL tree t
54 * returns the added element a, or a pointer the
55 * element that is equal to a (as returned by t->compar())
56 * a is linked directly to the tree, so it has to
57 * be properly allocated by the caller.
59 avl *avl_insert_lock(avl_tree_lock *t, avl *a) NEVERNULL WARNUNUSED;
60 avl *avl_insert(avl_tree *t, avl *a) NEVERNULL WARNUNUSED;
62 /* Remove an element a from the AVL tree t
63 * returns a pointer to the removed element
64 * or NULL if an element equal to a is not found
65 * (equal as returned by t->compar())
67 avl *avl_remove_lock(avl_tree_lock *t, avl *a) WARNUNUSED;
68 avl *avl_remove(avl_tree *t, avl *a) WARNUNUSED;
70 /* Find the element into the tree that equal to a
71 * (equal as returned by t->compar())
72 * returns NULL is no element is equal to a
74 avl *avl_search_lock(avl_tree_lock *t, avl *a);
75 avl *avl_search(avl_tree *t, avl *a);
77 /* Initialize the avl_tree_lock
79 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b));
80 void avl_init(avl_tree *t, int (*compar)(void *a, void *b));
83 int avl_traverse_lock(avl_tree_lock *t, int (*callback)(void *entry, void *data), void *data);
84 int avl_traverse(avl_tree *t, int (*callback)(void *entry, void *data), void *data);