| 1 |
/** |
| 2 |
* collectd - src/utils_avltree.h |
| 3 |
* Copyright (C) 2006,2007 Florian octo Forster |
| 4 |
* |
| 5 |
* Permission is hereby granted, free of charge, to any person obtaining a |
| 6 |
* copy of this software and associated documentation files (the "Software"), |
| 7 |
* to deal in the Software without restriction, including without limitation |
| 8 |
* the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| 9 |
* and/or sell copies of the Software, and to permit persons to whom the |
| 10 |
* Software is furnished to do so, subject to the following conditions: |
| 11 |
* |
| 12 |
* The above copyright notice and this permission notice shall be included in |
| 13 |
* all copies or substantial portions of the Software. |
| 14 |
* |
| 15 |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 16 |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 17 |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| 18 |
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| 19 |
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| 20 |
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| 21 |
* DEALINGS IN THE SOFTWARE. |
| 22 |
* |
| 23 |
* Authors: |
| 24 |
* Florian octo Forster <octo at collectd.org> |
| 25 |
**/ |
| 26 |
|
| 27 |
#ifndef UTILS_AVLTREE_H |
| 28 |
#define UTILS_AVLTREE_H 1 |
| 29 |
|
| 30 |
struct c_avl_tree_s; |
| 31 |
typedef struct c_avl_tree_s c_avl_tree_t; |
| 32 |
|
| 33 |
struct c_avl_iterator_s; |
| 34 |
typedef struct c_avl_iterator_s c_avl_iterator_t; |
| 35 |
|
| 36 |
/* |
| 37 |
* NAME |
| 38 |
* c_avl_create |
| 39 |
* |
| 40 |
* DESCRIPTION |
| 41 |
* Allocates a new AVL-tree. |
| 42 |
* |
| 43 |
* PARAMETERS |
| 44 |
* `compare' The function-pointer `compare' is used to compare two keys. It |
| 45 |
* has to return less than zero if its first argument is smaller |
| 46 |
* then the second argument, more than zero if the first argument |
| 47 |
* is bigger than the second argument and zero if they are equal. |
| 48 |
* If your keys are char-pointers, you can use the `strcmp' |
| 49 |
* function from the libc here. |
| 50 |
* |
| 51 |
* RETURN VALUE |
| 52 |
* A c_avl_tree_t-pointer upon success or NULL upon failure. |
| 53 |
*/ |
| 54 |
c_avl_tree_t *c_avl_create(int (*compare)(const void *, const void *)); |
| 55 |
|
| 56 |
/* |
| 57 |
* NAME |
| 58 |
* c_avl_destroy |
| 59 |
* |
| 60 |
* DESCRIPTION |
| 61 |
* Deallocates an AVL-tree. Stored value- and key-pointer are lost, but of |
| 62 |
* course not freed. |
| 63 |
*/ |
| 64 |
void c_avl_destroy(c_avl_tree_t *t); |
| 65 |
|
| 66 |
/* |
| 67 |
* NAME |
| 68 |
* c_avl_insert |
| 69 |
* |
| 70 |
* DESCRIPTION |
| 71 |
* Stores the key-value-pair in the AVL-tree pointed to by `t'. |
| 72 |
* |
| 73 |
* PARAMETERS |
| 74 |
* `t' AVL-tree to store the data in. |
| 75 |
* `key' Key used to store the value under. This is used to get back to |
| 76 |
* the value again. The pointer is stored in an internal structure |
| 77 |
* and _not_ copied. So the memory pointed to may _not_ be freed |
| 78 |
* before this entry is removed. You can use the `rkey' argument |
| 79 |
* to `avl_remove' to get the original pointer back and free it. |
| 80 |
* `value' Value to be stored. |
| 81 |
* |
| 82 |
* RETURN VALUE |
| 83 |
* Zero upon success, non-zero otherwise. It's less than zero if an error |
| 84 |
* occurred or greater than zero if the key is already stored in the tree. |
| 85 |
*/ |
| 86 |
int c_avl_insert(c_avl_tree_t *t, void *key, void *value); |
| 87 |
|
| 88 |
/* |
| 89 |
* NAME |
| 90 |
* c_avl_remove |
| 91 |
* |
| 92 |
* DESCRIPTION |
| 93 |
* Removes a key-value-pair from the tree t. The stored key and value may be |
| 94 |
* returned in `rkey' and `rvalue'. |
| 95 |
* |
| 96 |
* PARAMETERS |
| 97 |
* `t' AVL-tree to remove key-value-pair from. |
| 98 |
* `key' Key to identify the entry. |
| 99 |
* `rkey' Pointer to a pointer in which to store the key. May be NULL. |
| 100 |
* Since the `key' pointer is not copied when creating an entry, |
| 101 |
* the pointer may not be available anymore from outside the tree. |
| 102 |
* You can use this argument to get the actual pointer back and |
| 103 |
* free the memory pointed to by it. |
| 104 |
* `rvalue' Pointer to a pointer in which to store the value. May be NULL. |
| 105 |
* |
| 106 |
* RETURN VALUE |
| 107 |
* Zero upon success or non-zero if the key isn't found in the tree. |
| 108 |
*/ |
| 109 |
int c_avl_remove(c_avl_tree_t *t, const void *key, void **rkey, void **rvalue); |
| 110 |
|
| 111 |
/* |
| 112 |
* NAME |
| 113 |
* c_avl_get |
| 114 |
* |
| 115 |
* DESCRIPTION |
| 116 |
* Retrieve the `value' belonging to `key'. |
| 117 |
* |
| 118 |
* PARAMETERS |
| 119 |
* `t' AVL-tree to get the value from. |
| 120 |
* `key' Key to identify the entry. |
| 121 |
* `value' Pointer to a pointer in which to store the value. May be NULL. |
| 122 |
* |
| 123 |
* RETURN VALUE |
| 124 |
* Zero upon success or non-zero if the key isn't found in the tree. |
| 125 |
*/ |
| 126 |
int c_avl_get(c_avl_tree_t *t, const void *key, void **value); |
| 127 |
|
| 128 |
/* |
| 129 |
* NAME |
| 130 |
* c_avl_pick |
| 131 |
* |
| 132 |
* DESCRIPTION |
| 133 |
* Remove a (pseudo-)random element from the tree and return its `key' and |
| 134 |
* `value'. Entries are not returned in any particular order. This function |
| 135 |
* is intended for cache-flushes that don't care about the order but simply |
| 136 |
* want to remove all elements, one at a time. |
| 137 |
* |
| 138 |
* PARAMETERS |
| 139 |
* `t' AVL-tree to get the value from. |
| 140 |
* `key' Pointer to a pointer in which to store the key. |
| 141 |
* `value' Pointer to a pointer in which to store the value. |
| 142 |
* |
| 143 |
* RETURN VALUE |
| 144 |
* Zero upon success or non-zero if the tree is empty or key or value is |
| 145 |
* NULL. |
| 146 |
*/ |
| 147 |
int c_avl_pick(c_avl_tree_t *t, void **key, void **value); |
| 148 |
|
| 149 |
c_avl_iterator_t *c_avl_get_iterator(c_avl_tree_t *t); |
| 150 |
int c_avl_iterator_next(c_avl_iterator_t *iter, void **key, void **value); |
| 151 |
int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value); |
| 152 |
void c_avl_iterator_destroy(c_avl_iterator_t *iter); |
| 153 |
|
| 154 |
/* |
| 155 |
* NAME |
| 156 |
* c_avl_size |
| 157 |
* |
| 158 |
* DESCRIPTION |
| 159 |
* Return the size (number of nodes) of the specified tree. |
| 160 |
* |
| 161 |
* PARAMETERS |
| 162 |
* `t' AVL-tree to get the size of. |
| 163 |
* |
| 164 |
* RETURN VALUE |
| 165 |
* Number of nodes in the tree, 0 if the tree is empty or NULL. |
| 166 |
*/ |
| 167 |
int c_avl_size(c_avl_tree_t *t); |
| 168 |
|
| 169 |
#endif /* UTILS_AVLTREE_H */ |