1.1 --- a/ucx/avl.h Mon May 18 20:39:04 2015 +0200
1.2 +++ b/ucx/avl.h Tue May 19 16:47:54 2015 +0200
1.3 @@ -33,7 +33,7 @@
1.4 * AVL tree implementation.
1.5 *
1.6 * This binary search tree implementation allows average O(1) insertion and
1.7 - * removal of elements.
1.8 + * removal of elements (excluding binary search time).
1.9 *
1.10 * @author Mike Becker
1.11 * @author Olaf Wintermann
1.12 @@ -148,6 +148,14 @@
1.13 #define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator())
1.14
1.15 /**
1.16 + * Gets the node from the tree, that is associated with the specified key.
1.17 + * @param tree the UcxAVLTree
1.18 + * @param key the key
1.19 + * @return the node (or <code>NULL</code>, if the key is not present)
1.20 + */
1.21 +UcxAVLNode *ucx_avl_getn(UcxAVLTree *tree, intptr_t key);
1.22 +
1.23 +/**
1.24 * Gets the value from the tree, that is associated with the specified key.
1.25 * @param tree the UcxAVLTree
1.26 * @param key the key
1.27 @@ -157,21 +165,74 @@
1.28
1.29 /**
1.30 * Puts a key/value pair into the tree.
1.31 + *
1.32 + * Attention: use this function only, if a possible old value does not need
1.33 + * to be preserved.
1.34 + *
1.35 * @param tree the UcxAVLTree
1.36 * @param key the key
1.37 * @param value the new value
1.38 - * @return the replaced value (or <code>NULL</code>, if the key is new to the
1.39 - * tree)
1.40 + * @return zero, if and only if the operation succeeded
1.41 */
1.42 -void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
1.43 +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
1.44 +
1.45 +/**
1.46 + * Puts a key/value pair into the tree.
1.47 + *
1.48 + * This is a secure function which saves the old value to the variable pointed
1.49 + * at by oldvalue.
1.50 + *
1.51 + * @param tree the UcxAVLTree
1.52 + * @param key the key
1.53 + * @param value the new value
1.54 + * @param oldvalue optional: a pointer to the location where a possible old
1.55 + * value shall be stored
1.56 + * @return zero, if and only if the operation succeeded
1.57 + */
1.58 +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue);
1.59 +
1.60 +/**
1.61 + * Removes a node from the AVL tree.
1.62 + *
1.63 + * Note: the specified node is logically removed. The tree implementation
1.64 + * decides which memory area is freed. In most cases the here provided node
1.65 + * is freed, so it's further use is generally undefined.
1.66 + *
1.67 + * @param tree the UcxAVLTree
1.68 + * @param node the node to remove
1.69 + * @return zero, if and only if an element has been removed
1.70 + */
1.71 +int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node);
1.72
1.73 /**
1.74 * Removes an element from the AVL tree.
1.75 + *
1.76 * @param tree the UcxAVLTree
1.77 * @param key the key
1.78 - * @return the removed value (or <code>NULL</code>, if the key was not present)
1.79 + * @return zero, if and only if an element has been removed
1.80 */
1.81 -void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
1.82 +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
1.83 +
1.84 +/**
1.85 + * Removes an element from the AVL tree.
1.86 + *
1.87 + * This is a secure function which saves the old key and value data from node
1.88 + * to the variables at the location of oldkey and oldvalue (if specified), so
1.89 + * they can be freed afterwards (if necessary).
1.90 + *
1.91 + * Note: the returned key in oldkey is possibly not the same as the provided
1.92 + * key for the lookup (in terms of memory location).
1.93 + *
1.94 + * @param tree the UcxAVLTree
1.95 + * @param key the key of the element to remove
1.96 + * @param oldkey optional: a pointer to the location where the old key shall be
1.97 + * stored
1.98 + * @param oldvalue optional: a pointer to the location where the old value
1.99 + * shall be stored
1.100 + * @return zero, if and only if an element has been removed
1.101 + */
1.102 +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
1.103 + intptr_t *oldkey, void **oldvalue);
1.104
1.105 /**
1.106 * Counts the nodes in the specified UcxAVLTree.
