diff -r 3d999ea3f780 -r 4477987d40cd ucx/avl.c
--- a/ucx/avl.c	Mon May 18 20:39:04 2015 +0200
+++ b/ucx/avl.c	Tue May 19 16:47:54 2015 +0200
@@ -132,17 +132,27 @@
     alfree(al, tree);
 }
 
-void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
+UcxAVLNode *ucx_avl_getn(UcxAVLTree *tree, intptr_t key) {
     UcxAVLNode *n = tree->root;
     int cmpresult;
     while (n && (cmpresult = tree->cmpfunc(
             ptrcast(key), ptrcast(n->key), tree->userdata))) {
         n = cmpresult > 0 ? n->right : n->left;
     }
+    return n;
+}
+
+void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
+    UcxAVLNode *n = ucx_avl_getn(tree, key);
     return n ? n->value : NULL;
 }
 
-void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
+int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
+    return ucx_avl_put_s(tree, key, value, NULL);
+}
+
+int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value,
+        void **oldvalue) {
     if (tree->root) {
         UcxAVLNode *n = tree->root;
         int cmpresult;
@@ -158,26 +168,51 @@
 
         if (cmpresult) {
             UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode));
-            e->key = key; e->value = value; e->height = 1;
-            e->parent = e->left = e->right = NULL;
-            ucx_avl_connect(tree, n, e, 0);
-            ucx_avl_balance(tree, n);
-            return NULL;
+            if (e) {
+                e->key = key; e->value = value; e->height = 1;
+                e->parent = e->left = e->right = NULL;
+                ucx_avl_connect(tree, n, e, 0);
+                ucx_avl_balance(tree, n);
+                return 0;
+            } else {
+                return 1;
+            }
         } else {
-            void *prevval = n->value;
+            if (oldvalue) {
+                *oldvalue = n->value;
+            }
             n->value = value;
-            return prevval;
+            return 0;
         }
     } else {
         tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode));
-        tree->root->key = key; tree->root->value = value;
-        tree->root->height = 1;
-        tree->root->parent = tree->root->left = tree->root->right = NULL;
-        return NULL;
+        if (tree->root) {
+            tree->root->key = key; tree->root->value = value;
+            tree->root->height = 1;
+            tree->root->parent = tree->root->left = tree->root->right = NULL;
+            
+            if (oldvalue) {
+                *oldvalue = NULL;
+            }
+            
+            return 0;
+        } else {
+            return 1;
+        }
     }
 }
 
-void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
+int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
+    return ucx_avl_remove_s(tree, key, NULL, NULL);
+}
+    
+int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node) {
+    return ucx_avl_remove_s(tree, node->key, NULL, NULL);
+}
+
+int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
+        intptr_t *oldkey, void **oldvalue) {
+    
     UcxAVLNode *n = tree->root;
     int cmpresult;
     while (n && (cmpresult = tree->cmpfunc(
@@ -185,7 +220,13 @@
         n = cmpresult > 0 ? n->right : n->left;
     }
     if (n) {
-        void *prevval = n->value;
+        if (oldkey) {
+            *oldkey = n->key;
+        }
+        if (oldvalue) {
+            *oldvalue = n->value;
+        }
+        
         UcxAVLNode *p = n->parent;
         if (n->left && n->right) {
             UcxAVLNode *s = n->right;
@@ -211,9 +252,10 @@
         if (p) {
             ucx_avl_balance(tree, p);
         }
-        return prevval;
+        
+        return 0;
     } else {
-        return NULL;
+        return 1;
     }
 }