src/avl.h

   1 /*
   2  * ANSI C Library for maintainance of AVL Balanced Trees
   3  *
   4  * ref.:
   5  *  G. M. Adelson-Velskij & E. M. Landis
   6  *  Doklady Akad. Nauk SSSR 146 (1962), 263-266
   7  *
   8  * see also:
   9  *  D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
  10  *
  11  * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
  12  * Released under GNU General Public License (GPL) version 2
  13  *
  14  */
  15 #ifndef _AVL_H
  16 #define _AVL_H 1
  17
  18 #ifndef AVL_WITHOUT_PTHREADS
  19 #include <pthread.h>
  20
  21 // #define AVL_LOCK_WITH_MUTEX 1
  22
  23 #ifdef AVL_LOCK_WITH_MUTEX
  24 #define AVL_LOCK_INITIALIZER PTHREAD_MUTEX_INITIALIZER
  25 #else /* AVL_LOCK_WITH_MUTEX */
  26 #define AVL_LOCK_INITIALIZER PTHREAD_RWLOCK_INITIALIZER
  27 #endif /* AVL_LOCK_WITH_MUTEX */
  28
  29 #else /* AVL_WITHOUT_PTHREADS */
  30 #define AVL_LOCK_INITIALIZER
  31 #endif /* AVL_WITHOUT_PTHREADS */
  32
  33 /* Data structures */
  34
  35 /* One element of the AVL tree */
  36 typedef struct avl {
  37         struct avl* left;
  38         struct avl* right;
  39         signed char balance;
  40 } avl;
  41
  42 /* An AVL tree */
  43 typedef struct avl_tree {
  44         avl *root;
  45
  46         int (*compar)(void *a, void *b);
  47 } avl_tree;
  48
  49 typedef struct avl_tree_lock {
  50         avl_tree avl_tree;
  51
  52 #ifndef AVL_WITHOUT_PTHREADS
  53 #ifdef AVL_LOCK_WITH_MUTEX
  54         pthread_mutex_t mutex;
  55 #else /* AVL_LOCK_WITH_MUTEX */
  56         pthread_rwlock_t rwlock;
  57 #endif /* AVL_LOCK_WITH_MUTEX */
  58 #endif /* AVL_WITHOUT_PTHREADS */
  59 } avl_tree_lock;
  60
  61 /* Public methods */
  62
  63 /* Insert element a into the AVL tree t
  64  * returns 1 if the depth of the tree has grown
  65  * Warning: do not insert elements already present
  66  */
  67 int avl_insert_lock(avl_tree_lock *t, avl *a);
  68 int avl_insert(avl_tree *t, avl *a);
  69
  70 /* Remove an element a from the AVL tree t
  71  * returns -1 if the depth of the tree has shrunk
  72  * Warning: if the element is not present in the tree,
  73  *          returns 0 as if it had been removed succesfully.
  74  */
  75 int avl_remove_lock(avl_tree_lock *t, avl *a);
  76 int avl_remove(avl_tree *t, avl *a);
  77
  78 /* Remove the root of the AVL tree t
  79  * Warning: dumps core if t is empty
  80  */
  81 int avl_removeroot_lock(avl_tree_lock *t);
  82 int avl_removeroot(avl_tree *t);
  83
  84 /* Iterate through elements in t from a range between a and b (inclusive)
  85  * for each element calls iter(a) until it returns 0
  86  * returns the last value returned by iterator or 0 if there were no calls
  87  * Warning: a<=b must hold
  88  */
  89 int avl_range_lock(avl_tree_lock *t, avl *a, avl *b, int (*iter)(avl *), avl **ret);
  90 int avl_range(avl_tree *t, avl *a, avl *b, int (*iter)(avl *), avl **ret);
  91
  92 /* Iterate through elements in t equal to a
  93  * for each element calls iter(a) until it returns 0
  94  * returns the last value returned by iterator or 0 if there were no calls
  95  */
  96 #define avl_search_lock(t, a, iter, ret) avl_range_lock(t, a, a, iter, ret)
  97 #define avl_search(t, a, iter, ret) avl_range(t, a, a, iter, ret)
  98
  99 /* Initialize the avl_tree_lock
 100  */
 101 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b));
 102 void avl_init(avl_tree *t, int (*compar)(void *a, void *b));
 103
 104 #endif /* avl.h */