Mercurial > hg > ucx / changeset

--- a/test/avl_tests.c	Mon May 18 20:39:04 2015 +0200
+++ b/test/avl_tests.c	Tue May 19 16:47:54 2015 +0200
@@ -157,19 +157,21 @@
     ucx_avl_put(tree1, 2, (char*)data2);
     ucx_avl_put(tree1, 1, (char*)data1);
     ucx_avl_put(tree1, 3, (char*)data3);
-    void *val = ucx_avl_remove(tree1, 3);
+    void *val;
+    ucx_avl_remove_s(tree1, 3, NULL, &val);
     
     UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
-    UCX_TEST_ASSERT(
-            val == data3,
+    UCX_TEST_ASSERT(val == data3,
             "wrong return value for key: 1 (tree1)");
     UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)");
-    UCX_TEST_ASSERT(
-            ucx_avl_remove(tree1, 2) == data2,
+    
+    ucx_avl_remove_s(tree1, 2, NULL, &val);
+    UCX_TEST_ASSERT(val == data2,
             "wrong return value for key: 2 (tree1)");
     UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
-    UCX_TEST_ASSERT(
-            ucx_avl_remove(tree1, 1) == data1,
+    
+    ucx_avl_remove_s(tree1, 1, NULL, &val);
+    UCX_TEST_ASSERT(val == data1,
             "wrong return value for key: 1 (tree1)");
     UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
     UCX_TEST_ASSERT(tree1->root == NULL, "root not NULL (tree1)");
@@ -185,13 +187,13 @@
         }
     }
     
-    UCX_TEST_ASSERT(
-            ucx_avl_remove(tree2, 10) == data3,
+    ucx_avl_remove_s(tree2, 10, NULL, &val);
+    UCX_TEST_ASSERT(val == data3,
             "wrong return value for key: 10 (tree2)");
     UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
     
-    UCX_TEST_ASSERT(
-            ucx_avl_remove(tree2, 15) == data2,
+    ucx_avl_remove_s(tree2, 15, NULL, &val);
+    UCX_TEST_ASSERT(val == data2,
             "wrong return value for key: 15 (tree2)");
     UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
     

--- 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;
     }
 }
 

--- 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 zero, if and only if the operation succeeded
+ */
+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
- * @return the replaced value (or <code>NULL</code>, if the key is new to the
- * tree)
+ * @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
  */
-void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
+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.