Mercurial > hg > ucx / changeset

     1.1 --- a/test/avl_tests.c	Mon May 18 20:39:04 2015 +0200
     1.2 +++ b/test/avl_tests.c	Tue May 19 16:47:54 2015 +0200
     1.3 @@ -157,19 +157,21 @@
     1.4      ucx_avl_put(tree1, 2, (char*)data2);
     1.5      ucx_avl_put(tree1, 1, (char*)data1);
     1.6      ucx_avl_put(tree1, 3, (char*)data3);
     1.7 -    void *val = ucx_avl_remove(tree1, 3);
     1.8 +    void *val;
     1.9 +    ucx_avl_remove_s(tree1, 3, NULL, &val);
    1.10      
    1.11      UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
    1.12 -    UCX_TEST_ASSERT(
    1.13 -            val == data3,
    1.14 +    UCX_TEST_ASSERT(val == data3,
    1.15              "wrong return value for key: 1 (tree1)");
    1.16      UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)");
    1.17 -    UCX_TEST_ASSERT(
    1.18 -            ucx_avl_remove(tree1, 2) == data2,
    1.19 +    
    1.20 +    ucx_avl_remove_s(tree1, 2, NULL, &val);
    1.21 +    UCX_TEST_ASSERT(val == data2,
    1.22              "wrong return value for key: 2 (tree1)");
    1.23      UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
    1.24 -    UCX_TEST_ASSERT(
    1.25 -            ucx_avl_remove(tree1, 1) == data1,
    1.26 +    
    1.27 +    ucx_avl_remove_s(tree1, 1, NULL, &val);
    1.28 +    UCX_TEST_ASSERT(val == data1,
    1.29              "wrong return value for key: 1 (tree1)");
    1.30      UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
    1.31      UCX_TEST_ASSERT(tree1->root == NULL, "root not NULL (tree1)");
    1.32 @@ -185,13 +187,13 @@
    1.33          }
    1.34      }
    1.35      
    1.36 -    UCX_TEST_ASSERT(
    1.37 -            ucx_avl_remove(tree2, 10) == data3,
    1.38 +    ucx_avl_remove_s(tree2, 10, NULL, &val);
    1.39 +    UCX_TEST_ASSERT(val == data3,
    1.40              "wrong return value for key: 10 (tree2)");
    1.41      UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
    1.42      
    1.43 -    UCX_TEST_ASSERT(
    1.44 -            ucx_avl_remove(tree2, 15) == data2,
    1.45 +    ucx_avl_remove_s(tree2, 15, NULL, &val);
    1.46 +    UCX_TEST_ASSERT(val == data2,
    1.47              "wrong return value for key: 15 (tree2)");
    1.48      UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
    1.49      

     2.1 --- a/ucx/avl.c	Mon May 18 20:39:04 2015 +0200
     2.2 +++ b/ucx/avl.c	Tue May 19 16:47:54 2015 +0200
     2.3 @@ -132,17 +132,27 @@
     2.4      alfree(al, tree);
     2.5  }
     2.6  
     2.7 -void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
     2.8 +UcxAVLNode *ucx_avl_getn(UcxAVLTree *tree, intptr_t key) {
     2.9      UcxAVLNode *n = tree->root;
    2.10      int cmpresult;
    2.11      while (n && (cmpresult = tree->cmpfunc(
    2.12              ptrcast(key), ptrcast(n->key), tree->userdata))) {
    2.13          n = cmpresult > 0 ? n->right : n->left;
    2.14      }
    2.15 +    return n;
    2.16 +}
    2.17 +
    2.18 +void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
    2.19 +    UcxAVLNode *n = ucx_avl_getn(tree, key);
    2.20      return n ? n->value : NULL;
    2.21  }
    2.22  
    2.23 -void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
    2.24 +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
    2.25 +    return ucx_avl_put_s(tree, key, value, NULL);
    2.26 +}
    2.27 +
    2.28 +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value,
    2.29 +        void **oldvalue) {
    2.30      if (tree->root) {
    2.31          UcxAVLNode *n = tree->root;
    2.32          int cmpresult;
    2.33 @@ -158,26 +168,51 @@
    2.34  
    2.35          if (cmpresult) {
    2.36              UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode));
    2.37 -            e->key = key; e->value = value; e->height = 1;
    2.38 -            e->parent = e->left = e->right = NULL;
    2.39 -            ucx_avl_connect(tree, n, e, 0);
    2.40 -            ucx_avl_balance(tree, n);
    2.41 -            return NULL;
    2.42 +            if (e) {
    2.43 +                e->key = key; e->value = value; e->height = 1;
    2.44 +                e->parent = e->left = e->right = NULL;
    2.45 +                ucx_avl_connect(tree, n, e, 0);
    2.46 +                ucx_avl_balance(tree, n);
    2.47 +                return 0;
    2.48 +            } else {
    2.49 +                return 1;
    2.50 +            }
    2.51          } else {
    2.52 -            void *prevval = n->value;
    2.53 +            if (oldvalue) {
    2.54 +                *oldvalue = n->value;
    2.55 +            }
    2.56              n->value = value;
    2.57 -            return prevval;
    2.58 +            return 0;
    2.59          }
    2.60      } else {
    2.61          tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode));
    2.62 -        tree->root->key = key; tree->root->value = value;
    2.63 -        tree->root->height = 1;
    2.64 -        tree->root->parent = tree->root->left = tree->root->right = NULL;
    2.65 -        return NULL;
    2.66 +        if (tree->root) {
    2.67 +            tree->root->key = key; tree->root->value = value;
    2.68 +            tree->root->height = 1;
    2.69 +            tree->root->parent = tree->root->left = tree->root->right = NULL;
    2.70 +            
    2.71 +            if (oldvalue) {
    2.72 +                *oldvalue = NULL;
    2.73 +            }
    2.74 +            
    2.75 +            return 0;
    2.76 +        } else {
    2.77 +            return 1;
    2.78 +        }
    2.79      }
    2.80  }
    2.81  
    2.82 -void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
    2.83 +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
    2.84 +    return ucx_avl_remove_s(tree, key, NULL, NULL);
    2.85 +}
    2.86 +    
    2.87 +int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node) {
    2.88 +    return ucx_avl_remove_s(tree, node->key, NULL, NULL);
    2.89 +}
    2.90 +
    2.91 +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
    2.92 +        intptr_t *oldkey, void **oldvalue) {
    2.93 +    
    2.94      UcxAVLNode *n = tree->root;
    2.95      int cmpresult;
    2.96      while (n && (cmpresult = tree->cmpfunc(
    2.97 @@ -185,7 +220,13 @@
    2.98          n = cmpresult > 0 ? n->right : n->left;
    2.99      }
   2.100      if (n) {
   2.101 -        void *prevval = n->value;
   2.102 +        if (oldkey) {
   2.103 +            *oldkey = n->key;
   2.104 +        }
   2.105 +        if (oldvalue) {
   2.106 +            *oldvalue = n->value;
   2.107 +        }
   2.108 +        
   2.109          UcxAVLNode *p = n->parent;
   2.110          if (n->left && n->right) {
   2.111              UcxAVLNode *s = n->right;
   2.112 @@ -211,9 +252,10 @@
   2.113          if (p) {
   2.114              ucx_avl_balance(tree, p);
   2.115          }
   2.116 -        return prevval;
   2.117 +        
   2.118 +        return 0;
   2.119      } else {
   2.120 -        return NULL;
   2.121 +        return 1;
   2.122      }
   2.123  }
   2.124  

     3.1 --- a/ucx/avl.h	Mon May 18 20:39:04 2015 +0200
     3.2 +++ b/ucx/avl.h	Tue May 19 16:47:54 2015 +0200
     3.3 @@ -33,7 +33,7 @@
     3.4   * AVL tree implementation.
     3.5   * 
     3.6   * This binary search tree implementation allows average O(1) insertion and
     3.7 - * removal of elements.
     3.8 + * removal of elements (excluding binary search time).
     3.9   * 
    3.10   * @author Mike Becker
    3.11   * @author Olaf Wintermann
    3.12 @@ -148,6 +148,14 @@
    3.13  #define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator())
    3.14  
    3.15  /**
    3.16 + * Gets the node from the tree, that is associated with the specified key.
    3.17 + * @param tree the UcxAVLTree
    3.18 + * @param key the key
    3.19 + * @return the node (or <code>NULL</code>, if the key is not present)
    3.20 + */
    3.21 +UcxAVLNode *ucx_avl_getn(UcxAVLTree *tree, intptr_t key);
    3.22 +
    3.23 +/**
    3.24   * Gets the value from the tree, that is associated with the specified key.
    3.25   * @param tree the UcxAVLTree
    3.26   * @param key the key
    3.27 @@ -157,21 +165,74 @@
    3.28  
    3.29  /**
    3.30   * Puts a key/value pair into the tree.
    3.31 + * 
    3.32 + * Attention: use this function only, if a possible old value does not need
    3.33 + * to be preserved.
    3.34 + * 
    3.35   * @param tree the UcxAVLTree
    3.36   * @param key the key
    3.37   * @param value the new value
    3.38 - * @return the replaced value (or <code>NULL</code>, if the key is new to the
    3.39 - * tree)
    3.40 + * @return zero, if and only if the operation succeeded
    3.41   */
    3.42 -void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
    3.43 +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
    3.44 +
    3.45 +/**
    3.46 + * Puts a key/value pair into the tree.
    3.47 + * 
    3.48 + * This is a secure function which saves the old value to the variable pointed
    3.49 + * at by oldvalue.
    3.50 + * 
    3.51 + * @param tree the UcxAVLTree
    3.52 + * @param key the key
    3.53 + * @param value the new value
    3.54 + * @param oldvalue optional: a pointer to the location where a possible old
    3.55 + * value shall be stored
    3.56 + * @return zero, if and only if the operation succeeded
    3.57 + */
    3.58 +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue);
    3.59 +
    3.60 +/**
    3.61 + * Removes a node from the AVL tree.
    3.62 + * 
    3.63 + * Note: the specified node is logically removed. The tree implementation
    3.64 + * decides which memory area is freed. In most cases the here provided node
    3.65 + * is freed, so it's further use is generally undefined.
    3.66 + * 
    3.67 + * @param tree the UcxAVLTree
    3.68 + * @param node the node to remove
    3.69 + * @return zero, if and only if an element has been removed
    3.70 + */
    3.71 +int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node);
    3.72  
    3.73  /**
    3.74   * Removes an element from the AVL tree.
    3.75 + * 
    3.76   * @param tree the UcxAVLTree
    3.77   * @param key the key
    3.78 - * @return the removed value (or <code>NULL</code>, if the key was not present)
    3.79 + * @return zero, if and only if an element has been removed
    3.80   */
    3.81 -void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
    3.82 +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
    3.83 +
    3.84 +/**
    3.85 + * Removes an element from the AVL tree.
    3.86 + * 
    3.87 + * This is a secure function which saves the old key and value data from node
    3.88 + * to the variables at the location of oldkey and oldvalue (if specified), so
    3.89 + * they can be freed afterwards (if necessary).
    3.90 + * 
    3.91 + * Note: the returned key in oldkey is possibly not the same as the provided
    3.92 + * key for the lookup (in terms of memory location).
    3.93 + * 
    3.94 + * @param tree the UcxAVLTree
    3.95 + * @param key the key of the element to remove
    3.96 + * @param oldkey optional: a pointer to the location where the old key shall be
    3.97 + * stored
    3.98 + * @param oldvalue optional: a pointer to the location where the old value
    3.99 + * shall be stored
   3.100 + * @return zero, if and only if an element has been removed
   3.101 + */
   3.102 +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
   3.103 +        intptr_t *oldkey, void **oldvalue);
   3.104  
   3.105  /**
   3.106   * Counts the nodes in the specified UcxAVLTree.