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