# HG changeset patch # User Mike Becker # Date 1432046874 -7200 # Node ID 4477987d40cd48a6071dfe8ac0608e4d2a1ea034 # Parent 3d999ea3f780a2a2ba73eaa8546adcdbe11a51d7 better and better and better AVL API diff -r 3d999ea3f780 -r 4477987d40cd test/avl_tests.c --- 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)"); 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; } } 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 NULL, 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 NULL, 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 NULL, 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.