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 #endif /* AVL_WITHOUT_PTHREADS */
  21
  22 // #define AVL_LOCK_WITH_MUTEX 1
  23
  24 /* Data structures */
  25
  26 /* One element of the AVL tree */
  27 typedef struct avl {
  28         struct avl* left;
  29         struct avl* right;
  30         signed char balance;
  31 } avl;
  32
  33 /* An AVL tree */
  34 typedef struct avl_tree {
  35         avl* root;
  36         int (*compar)(void* a, void* b);
  37
  38 #ifndef AVL_WITHOUT_PTHREADS
  39 #ifdef AVL_LOCK_WITH_MUTEX
  40         pthread_mutex_t mutex;
  41 #else /* AVL_LOCK_WITH_MUTEX */
  42         pthread_rwlock_t rwlock;
  43 #endif /* AVL_LOCK_WITH_MUTEX */
  44 #endif /* AVL_WITHOUT_PTHREADS */
  45 } avl_tree;
  46
  47 /* Public methods */
  48
  49 /* Insert element a into the AVL tree t
  50  * returns 1 if the depth of the tree has grown
  51  * Warning: do not insert elements already present
  52  */
  53 int avl_insert(avl_tree* t, avl* a);
  54
  55 /* Remove an element a from the AVL tree t
  56  * returns -1 if the depth of the tree has shrunk
  57  * Warning: if the element is not present in the tree,
  58  *          returns 0 as if it had been removed succesfully.
  59  */
  60 int avl_remove(avl_tree* t, avl* a);
  61
  62 /* Remove the root of the AVL tree t
  63  * Warning: dumps core if t is empty
  64  */
  65 int avl_removeroot(avl_tree* t);
  66
  67 /* Iterate through elements in t from a range between a and b (inclusive)
  68  * for each element calls iter(a) until it returns 0
  69  * returns the last value returned by iterator or 0 if there were no calls
  70  * Warning: a<=b must hold
  71  */
  72 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret);
  73
  74 /* Iterate through elements in t equal to a
  75  * for each element calls iter(a) until it returns 0
  76  * returns the last value returned by iterator or 0 if there were no calls
  77  */
  78 int avl_search(avl_tree* t, avl* a, int (*iter)(avl*), avl** ret);
  79
  80 /* Initialize the avl_tree
  81  */
  82 void avl_init(avl_tree* t, int (*compar)(void* a, void* b));
  83
  84 #endif /* avl.h */