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 NETDATA_MUTEX_INITIALIZER
  17 #else /* AVL_LOCK_WITH_MUTEX */
  18 #define AVL_LOCK_INITIALIZER NETDATA_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     netdata_mutex_t mutex;
  45 #else /* AVL_LOCK_WITH_MUTEX */
  46     netdata_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 the added element a, or a pointer the
  55  * element that is equal to a (as returned by t->compar())
  56  * a is linked directly to the tree, so it has to
  57  * be properly allocated by the caller.
  58  */
  59 avl *avl_insert_lock(avl_tree_lock *t, avl *a) NEVERNULL WARNUNUSED;
  60 avl *avl_insert(avl_tree *t, avl *a) NEVERNULL WARNUNUSED;
  61
  62 /* Remove an element a from the AVL tree t
  63  * returns a pointer to the removed element
  64  * or NULL if an element equal to a is not found
  65  * (equal as returned by t->compar())
  66  */
  67 avl *avl_remove_lock(avl_tree_lock *t, avl *a) WARNUNUSED;
  68 avl *avl_remove(avl_tree *t, avl *a) WARNUNUSED;
  69
  70 /* Find the element into the tree that equal to a
  71  * (equal as returned by t->compar())
  72  * returns NULL is no element is equal to a
  73  */
  74 avl *avl_search_lock(avl_tree_lock *t, avl *a);
  75 avl *avl_search(avl_tree *t, avl *a);
  76
  77 /* Initialize the avl_tree_lock
  78  */
  79 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b));
  80 void avl_init(avl_tree *t, int (*compar)(void *a, void *b));
  81
  82
  83 int avl_traverse_lock(avl_tree_lock *t, int (*callback)(void *entry, void *data), void *data);
  84 int avl_traverse(avl_tree *t, int (*callback)(void *entry, void *data), void *data);
  85
  86 #endif /* avl.h */