comparison: ucx/avl.h
ucx/avl.h
- changeset 204
- 4477987d40cd
- parent 199
- e25dc68336ec
- child 205
- 54a7ceb9151f
equal
deleted
inserted
replaced
| 203:3d999ea3f780 | 204:4477987d40cd |
|---|---|
| 31 * @file avl.h | 31 * @file avl.h |
| 32 * | 32 * |
| 33 * AVL tree implementation. | 33 * AVL tree implementation. |
| 34 * | 34 * |
| 35 * This binary search tree implementation allows average O(1) insertion and | 35 * This binary search tree implementation allows average O(1) insertion and |
| 36 * removal of elements. | 36 * removal of elements (excluding binary search time). |
| 37 * | 37 * |
| 38 * @author Mike Becker | 38 * @author Mike Becker |
| 39 * @author Olaf Wintermann | 39 * @author Olaf Wintermann |
| 40 */ | 40 */ |
| 41 | 41 |
| 146 * @return a new default UcxAVLTree object | 146 * @return a new default UcxAVLTree object |
| 147 */ | 147 */ |
| 148 #define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator()) | 148 #define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator()) |
| 149 | 149 |
| 150 /** | 150 /** |
| 151 * Gets the node from the tree, that is associated with the specified key. | |
| 152 * @param tree the UcxAVLTree | |
| 153 * @param key the key | |
| 154 * @return the node (or <code>NULL</code>, if the key is not present) | |
| 155 */ | |
| 156 UcxAVLNode *ucx_avl_getn(UcxAVLTree *tree, intptr_t key); | |
| 157 | |
| 158 /** | |
| 151 * Gets the value from the tree, that is associated with the specified key. | 159 * Gets the value from the tree, that is associated with the specified key. |
| 152 * @param tree the UcxAVLTree | 160 * @param tree the UcxAVLTree |
| 153 * @param key the key | 161 * @param key the key |
| 154 * @return the value (or <code>NULL</code>, if the key is not present) | 162 * @return the value (or <code>NULL</code>, if the key is not present) |
| 155 */ | 163 */ |
| 156 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key); | 164 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key); |
| 157 | 165 |
| 158 /** | 166 /** |
| 159 * Puts a key/value pair into the tree. | 167 * Puts a key/value pair into the tree. |
| 168 * | |
| 169 * Attention: use this function only, if a possible old value does not need | |
| 170 * to be preserved. | |
| 171 * | |
| 160 * @param tree the UcxAVLTree | 172 * @param tree the UcxAVLTree |
| 161 * @param key the key | 173 * @param key the key |
| 162 * @param value the new value | 174 * @param value the new value |
| 163 * @return the replaced value (or <code>NULL</code>, if the key is new to the | 175 * @return zero, if and only if the operation succeeded |
| 164 * tree) | 176 */ |
| 165 */ | 177 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value); |
| 166 void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value); | 178 |
| 179 /** | |
| 180 * Puts a key/value pair into the tree. | |
| 181 * | |
| 182 * This is a secure function which saves the old value to the variable pointed | |
| 183 * at by oldvalue. | |
| 184 * | |
| 185 * @param tree the UcxAVLTree | |
| 186 * @param key the key | |
| 187 * @param value the new value | |
| 188 * @param oldvalue optional: a pointer to the location where a possible old | |
| 189 * value shall be stored | |
| 190 * @return zero, if and only if the operation succeeded | |
| 191 */ | |
| 192 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue); | |
| 193 | |
| 194 /** | |
| 195 * Removes a node from the AVL tree. | |
| 196 * | |
| 197 * Note: the specified node is logically removed. The tree implementation | |
| 198 * decides which memory area is freed. In most cases the here provided node | |
| 199 * is freed, so it's further use is generally undefined. | |
| 200 * | |
| 201 * @param tree the UcxAVLTree | |
| 202 * @param node the node to remove | |
| 203 * @return zero, if and only if an element has been removed | |
| 204 */ | |
| 205 int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node); | |
| 167 | 206 |
| 168 /** | 207 /** |
| 169 * Removes an element from the AVL tree. | 208 * Removes an element from the AVL tree. |
| 170 * @param tree the UcxAVLTree | 209 * |
| 171 * @param key the key | 210 * @param tree the UcxAVLTree |
| 172 * @return the removed value (or <code>NULL</code>, if the key was not present) | 211 * @param key the key |
| 173 */ | 212 * @return zero, if and only if an element has been removed |
| 174 void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key); | 213 */ |
| 214 int ucx_avl_remove(UcxAVLTree *tree, intptr_t key); | |
| 215 | |
| 216 /** | |
| 217 * Removes an element from the AVL tree. | |
| 218 * | |
| 219 * This is a secure function which saves the old key and value data from node | |
| 220 * to the variables at the location of oldkey and oldvalue (if specified), so | |
| 221 * they can be freed afterwards (if necessary). | |
| 222 * | |
| 223 * Note: the returned key in oldkey is possibly not the same as the provided | |
| 224 * key for the lookup (in terms of memory location). | |
| 225 * | |
| 226 * @param tree the UcxAVLTree | |
| 227 * @param key the key of the element to remove | |
| 228 * @param oldkey optional: a pointer to the location where the old key shall be | |
| 229 * stored | |
| 230 * @param oldvalue optional: a pointer to the location where the old value | |
| 231 * shall be stored | |
| 232 * @return zero, if and only if an element has been removed | |
| 233 */ | |
| 234 int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, | |
| 235 intptr_t *oldkey, void **oldvalue); | |
| 175 | 236 |
| 176 /** | 237 /** |
| 177 * Counts the nodes in the specified UcxAVLTree. | 238 * Counts the nodes in the specified UcxAVLTree. |
| 178 * @param tree the AVL tree | 239 * @param tree the AVL tree |
| 179 * @return the node count | 240 * @return the node count |
