src/utils_avltree.h

   1 /**
   2  * collectd - src/utils_avltree.h
   3  * Copyright (C) 2006,2007  Florian octo Forster
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; either version 2 of the License, or (at your
   8  * option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  18  *
  19  * Authors:
  20  *   Florian octo Forster <octo at verplant.org>
  21  **/
  22
  23 #ifndef UTILS_AVLTREE_H
  24 #define UTILS_AVLTREE_H 1
  25
  26 struct avl_tree_s;
  27 typedef struct avl_tree_s avl_tree_t;
  28
  29 struct avl_iterator_s;
  30 typedef struct avl_iterator_s avl_iterator_t;
  31
  32 /*
  33  * NAME
  34  *   avl_create
  35  *
  36  * DESCRIPTION
  37  *   Allocates a new AVL-tree.
  38  *
  39  * PARAMETERS
  40  *   `compare'  The function-pointer `compare' is used to compare two keys. It
  41  *              has to return less than zero if it's first argument is smaller
  42  *              then the second argument, more than zero if the first argument
  43  *              is bigger than the second argument and zero if they are equal.
  44  *              If your keys are char-pointers, you can use the `strcmp'
  45  *              function from the libc here.
  46  *
  47  * RETURN VALUE
  48  *   A avl_tree_t-pointer upon success or NULL upon failure.
  49  */
  50 avl_tree_t *avl_create (int (*compare) (const void *, const void *));
  51
  52
  53 /*
  54  * NAME
  55  *   avl_destroy
  56  *
  57  * DESCRIPTION
  58  *   Deallocates an AVL-tree. Stored value- and key-pointer are lost, but of
  59  *   course not freed.
  60  */
  61 void avl_destroy (avl_tree_t *t);
  62
  63 /*
  64  * NAME
  65  *   avl_insert
  66  *
  67  * DESCRIPTION
  68  *   Stores the key-value-pair in the AVL-tree pointed to by `t'.
  69  *
  70  * PARAMETERS
  71  *   `t'        AVL-tree to store the data in.
  72  *   `key'      Key used to store the value under. This is used to get back to
  73  *              the value again.
  74  *   `value'    Value to be stored.
  75  *
  76  * RETURN VALUE
  77  *   Zero upon success and non-zero upon failure and if the key is already
  78  *   stored in the tree.
  79  */
  80 int avl_insert (avl_tree_t *t, void *key, void *value);
  81
  82 /*
  83  * NAME
  84  *   avl_remove
  85  *
  86  * DESCRIPTION
  87  *   Removes a key-value-pair from the tree t. The stored key and value may be
  88  *   returned in `rkey' and `rvalue'.
  89  *
  90  * PARAMETERS
  91  *   `t'        AVL-tree to remove key-value-pair from.
  92  *   `key'      Key to identify the entry.
  93  *   `rkey'     Pointer to a pointer in which to store the key. May be NULL.
  94  *   `rvalue'   Pointer to a pointer in which to store the value. May be NULL.
  95  *
  96  * RETURN VALUE
  97  *   Zero upon success or non-zero if the key isn't found in the tree.
  98  */
  99 int avl_remove (avl_tree_t *t, const void *key, void **rkey, void **rvalue);
 100
 101 /*
 102  * NAME
 103  *   avl_get
 104  *
 105  * DESCRIPTION
 106  *   Retrieve the `value' belonging to `key'.
 107  *
 108  * PARAMETERS
 109  *   `t'        AVL-tree to get the value from.
 110  *   `key'      Key to identify the entry.
 111  *   `value'    Pointer to a pointer in which to store the value. May be NULL.
 112  *
 113  * RETURN VALUE
 114  *   Zero upon success or non-zero if the key isn't found in the tree.
 115  */
 116 int avl_get (avl_tree_t *t, const void *key, void **value);
 117
 118 /*
 119  * NAME
 120  *   avl_pick
 121  *
 122  * DESCRIPTION
 123  *   Remove a (pseudo-)random element from the tree and return it's `key' and
 124  *   `value'. Entries are not returned in any particular order. This function
 125  *   is intended for cache-flushes that don't care about the order but simply
 126  *   want to remove all elements, one at a time.
 127  *
 128  * PARAMETERS
 129  *   `t'        AVL-tree to get the value from.
 130  *   `key'      Pointer to a pointer in which to store the key.
 131  *   `value'    Pointer to a pointer in which to store the value.
 132  *
 133  * RETURN VALUE
 134  *   Zero upon success or non-zero if the tree is empty or key or value is
 135  *   NULL.
 136  */
 137 int avl_pick (avl_tree_t *t, void **key, void **value);
 138
 139 avl_iterator_t *avl_get_iterator (avl_tree_t *t);
 140 int avl_iterator_next (avl_iterator_t *iter, void **key, void **value);
 141 int avl_iterator_prev (avl_iterator_t *iter, void **key, void **value);
 142 void avl_iterator_destroy (avl_iterator_t *iter);
 143
 144 #endif /* UTILS_AVLTREE_H */