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