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 c_avl_tree_s;
  27 typedef struct c_avl_tree_s c_avl_tree_t;
  28
  29 struct c_avl_iterator_s;
  30 typedef struct c_avl_iterator_s c_avl_iterator_t;
  31
  32 /*
  33  * NAME
  34  *   c_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 c_avl_tree_t-pointer upon success or NULL upon failure.
  49  */
  50 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *));
  51
  52
  53 /*
  54  * NAME
  55  *   c_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 c_avl_destroy (c_avl_tree_t *t);
  62
  63 /*
  64  * NAME
  65  *   c_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. The pointer is stored in an internal structure
  74  *              and _not_ copied. So the memory pointed to may _not_ be freed
  75  *              before this entry is removed. You can use the `rkey' argument
  76  *              to `avl_remove' to get the original pointer back and free it.
  77  *   `value'    Value to be stored.
  78  *
  79  * RETURN VALUE
  80  *   Zero upon success, non-zero otherwise. It's less than zero if an error
  81  *   occurred or greater than zero if the key is already stored in the tree.
  82  */
  83 int c_avl_insert (c_avl_tree_t *t, void *key, void *value);
  84
  85 /*
  86  * NAME
  87  *   c_avl_remove
  88  *
  89  * DESCRIPTION
  90  *   Removes a key-value-pair from the tree t. The stored key and value may be
  91  *   returned in `rkey' and `rvalue'.
  92  *
  93  * PARAMETERS
  94  *   `t'        AVL-tree to remove key-value-pair from.
  95  *   `key'      Key to identify the entry.
  96  *   `rkey'     Pointer to a pointer in which to store the key. May be NULL.
  97  *              Since the `key' pointer is not copied when creating an entry,
  98  *              the pointer may not be available anymore from outside the tree.
  99  *              You can use this argument to get the actual pointer back and
 100  *              free the memory pointed to by it.
 101  *   `rvalue'   Pointer to a pointer in which to store the value. May be NULL.
 102  *
 103  * RETURN VALUE
 104  *   Zero upon success or non-zero if the key isn't found in the tree.
 105  */
 106 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue);
 107
 108 /*
 109  * NAME
 110  *   c_avl_get
 111  *
 112  * DESCRIPTION
 113  *   Retrieve the `value' belonging to `key'.
 114  *
 115  * PARAMETERS
 116  *   `t'        AVL-tree to get the value from.
 117  *   `key'      Key to identify the entry.
 118  *   `value'    Pointer to a pointer in which to store the value. May be NULL.
 119  *
 120  * RETURN VALUE
 121  *   Zero upon success or non-zero if the key isn't found in the tree.
 122  */
 123 int c_avl_get (c_avl_tree_t *t, const void *key, void **value);
 124
 125 /*
 126  * NAME
 127  *   c_avl_pick
 128  *
 129  * DESCRIPTION
 130  *   Remove a (pseudo-)random element from the tree and return it's `key' and
 131  *   `value'. Entries are not returned in any particular order. This function
 132  *   is intended for cache-flushes that don't care about the order but simply
 133  *   want to remove all elements, one at a time.
 134  *
 135  * PARAMETERS
 136  *   `t'        AVL-tree to get the value from.
 137  *   `key'      Pointer to a pointer in which to store the key.
 138  *   `value'    Pointer to a pointer in which to store the value.
 139  *
 140  * RETURN VALUE
 141  *   Zero upon success or non-zero if the tree is empty or key or value is
 142  *   NULL.
 143  */
 144 int c_avl_pick (c_avl_tree_t *t, void **key, void **value);
 145
 146 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t);
 147 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value);
 148 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value);
 149 void c_avl_iterator_destroy (c_avl_iterator_t *iter);
 150
 151 /*
 152  * NAME
 153  *   c_avl_size
 154  *
 155  * DESCRIPTION
 156  *   Return the size (number of nodes) of the specified tree.
 157  *
 158  * PARAMETERS
 159  *   `t'        AVL-tree to get the size of.
 160  *
 161  * RETURN VALUE
 162  *   Number of nodes in the tree, 0 if the tree is empty or NULL.
 163  */
 164 int c_avl_size (c_avl_tree_t *t);
 165
 166 #endif /* UTILS_AVLTREE_H */