diff -r 3d999ea3f780 -r 4477987d40cd ucx/avl.h
--- a/ucx/avl.h	Mon May 18 20:39:04 2015 +0200
+++ b/ucx/avl.h	Tue May 19 16:47:54 2015 +0200
@@ -33,7 +33,7 @@
  * AVL tree implementation.
  * 
  * This binary search tree implementation allows average O(1) insertion and
- * removal of elements.
+ * removal of elements (excluding binary search time).
  * 
  * @author Mike Becker
  * @author Olaf Wintermann
@@ -148,6 +148,14 @@
 #define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator())
 
 /**
+ * Gets the node from the tree, that is associated with the specified key.
+ * @param tree the UcxAVLTree
+ * @param key the key
+ * @return the node (or <code>NULL</code>, if the key is not present)
+ */
+UcxAVLNode *ucx_avl_getn(UcxAVLTree *tree, intptr_t key);
+
+/**
  * Gets the value from the tree, that is associated with the specified key.
  * @param tree the UcxAVLTree
  * @param key the key
@@ -157,21 +165,74 @@
 
 /**
  * Puts a key/value pair into the tree.
+ * 
+ * Attention: use this function only, if a possible old value does not need
+ * to be preserved.
+ * 
  * @param tree the UcxAVLTree
  * @param key the key
  * @param value the new value
- * @return the replaced value (or <code>NULL</code>, if the key is new to the
- * tree)
+ * @return zero, if and only if the operation succeeded
  */
-void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
+int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
+
+/**
+ * Puts a key/value pair into the tree.
+ * 
+ * This is a secure function which saves the old value to the variable pointed
+ * at by oldvalue.
+ * 
+ * @param tree the UcxAVLTree
+ * @param key the key
+ * @param value the new value
+ * @param oldvalue optional: a pointer to the location where a possible old
+ * value shall be stored
+ * @return zero, if and only if the operation succeeded
+ */
+int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue);
+
+/**
+ * Removes a node from the AVL tree.
+ * 
+ * Note: the specified node is logically removed. The tree implementation
+ * decides which memory area is freed. In most cases the here provided node
+ * is freed, so it's further use is generally undefined.
+ * 
+ * @param tree the UcxAVLTree
+ * @param node the node to remove
+ * @return zero, if and only if an element has been removed
+ */
+int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node);
 
 /**
  * Removes an element from the AVL tree.
+ * 
  * @param tree the UcxAVLTree
  * @param key the key
- * @return the removed value (or <code>NULL</code>, if the key was not present)
+ * @return zero, if and only if an element has been removed
  */
-void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
+int ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
+
+/**
+ * Removes an element from the AVL tree.
+ * 
+ * This is a secure function which saves the old key and value data from node
+ * to the variables at the location of oldkey and oldvalue (if specified), so
+ * they can be freed afterwards (if necessary).
+ * 
+ * Note: the returned key in oldkey is possibly not the same as the provided
+ * key for the lookup (in terms of memory location).
+ * 
+ * @param tree the UcxAVLTree
+ * @param key the key of the element to remove
+ * @param oldkey optional: a pointer to the location where the old key shall be
+ * stored
+ * @param oldvalue optional: a pointer to the location where the old value
+ * shall be stored
+ * @return zero, if and only if an element has been removed
+ */
+int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
+        intptr_t *oldkey, void **oldvalue);
 
 /**
  * Counts the nodes in the specified UcxAVLTree.