src/avl.h

   1
   2 #ifndef _AVL_H
   3 #define _AVL_H 1
   4
   5 /* Maximum AVL tree height. */
   6 #ifndef AVL_MAX_HEIGHT
   7 #define AVL_MAX_HEIGHT 92
   8 #endif
   9
  10 #ifndef AVL_WITHOUT_PTHREADS
  11 #include <pthread.h>
  12
  13 // #define AVL_LOCK_WITH_MUTEX 1
  14
  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 */
  20
  21 #else /* AVL_WITHOUT_PTHREADS */
  22 #define AVL_LOCK_INITIALIZER
  23 #endif /* AVL_WITHOUT_PTHREADS */
  24
  25 /* Data structures */
  26
  27 /* One element of the AVL tree */
  28 typedef struct avl {
  29     struct avl *avl_link[2];  /* Subtrees. */
  30     signed char avl_balance;       /* Balance factor. */
  31 } avl;
  32
  33 /* An AVL tree */
  34 typedef struct avl_tree {
  35         avl *root;
  36         int (*compar)(void *a, void *b);
  37 } avl_tree;
  38
  39 typedef struct avl_tree_lock {
  40         avl_tree avl_tree;
  41
  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 */
  49 } avl_tree_lock;
  50
  51 /* Public methods */
  52
  53 /* Insert element a into the AVL tree t
  54  * returns 1 if the depth of the tree has grown
  55  * Warning: do not insert elements already present
  56  */
  57 avl *avl_insert_lock(avl_tree_lock *t, avl *a);
  58 avl *avl_insert(avl_tree *t, avl *a);
  59
  60 /* Remove an element a from the AVL tree t
  61  * returns -1 if the depth of the tree has shrunk
  62  * Warning: if the element is not present in the tree,
  63  *          returns 0 as if it had been removed succesfully.
  64  */
  65 avl *avl_remove_lock(avl_tree_lock *t, avl *a);
  66 avl *avl_remove(avl_tree *t, avl *a);
  67
  68 /* Iterate through elements in t equal to a
  69  * for each element calls iter(a) until it returns 0
  70  * returns the last value returned by iterator or 0 if there were no calls
  71  */
  72 avl *avl_search_lock(avl_tree_lock *t, avl *a);
  73 avl *avl_search(avl_tree *t, avl *a);
  74
  75 /* Initialize the avl_tree_lock
  76  */
  77 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b));
  78 void avl_init(avl_tree *t, int (*compar)(void *a, void *b));
  79
  80 #endif /* avl.h */