# HG changeset patch # User Mike Becker # Date 1500139206 -7200 # Node ID 2e74828c5e94cc4f5f210f859f874030302eaf13 # Parent a3597d704421efa10171fbc24d872ce579448a5a adds distance function and ucx_avl_find_node() diff -r a3597d704421 -r 2e74828c5e94 test/avl_tests.c --- a/test/avl_tests.c Mon Mar 06 16:22:42 2017 +0100 +++ b/test/avl_tests.c Sat Jul 15 19:20:06 2017 +0200 @@ -223,3 +223,62 @@ ucx_avl_free(tree3); ucx_avl_free(tree4); } + +static intmax_t dist_int(void* a, void* b, void* n) { + return ((intmax_t)a)-((intmax_t)b); +} + +UCX_TEST(test_ucx_avl_find) { + UcxAVLTree *tree = ucx_avl_new(ucx_ptrcmp); + + size_t len = 12; + int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13}; + + for (size_t i = 0 ; i < len ; i++) { + ucx_avl_put(tree, val[i], &(val[i])); + } + + UCX_TEST_BEGIN + + void* ret; + + /* test present values */ + ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_CLOSEST); + UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find closest failed"); + ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_EXACT); + UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find exact failed"); + ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); + UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed"); + ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); + UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find UB failed"); + ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_CLOSEST); + UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find closest failed"); + ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_EXACT); + UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find exact failed"); + ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); + UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find LB failed"); + ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); + UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find UB failed"); + + /* test missing values */ + ret = ucx_avl_find(tree,(intptr_t)-10, dist_int, UCX_AVL_FIND_CLOSEST); + UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find closest failed"); + ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_EXACT); + UCX_TEST_ASSERT(!ret, "AVL find exact failed"); + ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); + UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed"); + ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); + UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find UB failed"); + ret = ucx_avl_find(tree,(intptr_t)18, dist_int, UCX_AVL_FIND_CLOSEST); + UCX_TEST_ASSERT(ret && *((int*)ret) == 20, "AVL find closest failed"); + ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_EXACT); + UCX_TEST_ASSERT(!ret, "AVL find exact failed"); + ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); + UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed"); + ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); + UCX_TEST_ASSERT(ret && *((int*)ret) == 4, "AVL find UB failed"); + + UCX_TEST_END + + ucx_avl_free(tree); +} diff -r a3597d704421 -r 2e74828c5e94 test/avl_tests.h --- a/test/avl_tests.h Mon Mar 06 16:22:42 2017 +0100 +++ b/test/avl_tests.h Sat Jul 15 19:20:06 2017 +0200 @@ -38,6 +38,7 @@ UCX_TEST(test_ucx_avl_put); UCX_TEST(test_ucx_avl_remove); +UCX_TEST(test_ucx_avl_find); #ifdef __cplusplus } diff -r a3597d704421 -r 2e74828c5e94 test/main.c --- a/test/main.c Mon Mar 06 16:22:42 2017 +0100 +++ b/test/main.c Sat Jul 15 19:20:06 2017 +0200 @@ -227,6 +227,7 @@ /* AVL Tests */ ucx_test_register(suite, test_ucx_avl_put); ucx_test_register(suite, test_ucx_avl_remove); + ucx_test_register(suite, test_ucx_avl_find); ucx_test_run(suite, stdout); fflush(stdout); diff -r a3597d704421 -r 2e74828c5e94 ucx/avl.c --- a/ucx/avl.c Mon Mar 06 16:22:42 2017 +0100 +++ b/ucx/avl.c Sat Jul 15 19:20:06 2017 +0200 @@ -26,6 +26,8 @@ * POSSIBILITY OF SUCH DAMAGE. */ +#include + #include "avl.h" #define ptrcast(ptr) ((void*)(ptr)) @@ -149,6 +151,46 @@ return n ? n->value : NULL; } +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, + distance_func dfnc, int mode) { + UcxAVLNode *n = tree->root; + UcxAVLNode *closest = NULL; + + intmax_t cmpresult; + intmax_t closest_dist; + closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX; + + while (n && (cmpresult = dfnc( + ptrcast(key), ptrcast(n->key), tree->userdata))) { + if (mode == UCX_AVL_FIND_CLOSEST) { + intmax_t dist = cmpresult; + if (dist < 0) dist *= -1; + if (dist < closest_dist) { + closest_dist = dist; + closest = n; + } + } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) { + if (cmpresult > closest_dist) { + closest_dist = cmpresult; + closest = n; + } + } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) { + if (cmpresult < closest_dist) { + closest_dist = cmpresult; + closest = n; + } + } + n = cmpresult > 0 ? n->right : n->left; + } + return n ? n : closest; +} + +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, + distance_func dfnc, int mode) { + UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode); + return n ? n->value : NULL; +} + int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { return ucx_avl_put_s(tree, key, value, NULL); } diff -r a3597d704421 -r 2e74828c5e94 ucx/avl.h --- a/ucx/avl.h Mon Mar 06 16:22:42 2017 +0100 +++ b/ucx/avl.h Sat Jul 15 19:20:06 2017 +0200 @@ -164,6 +164,68 @@ void *ucx_avl_get(UcxAVLTree *tree, intptr_t key); /** + * A mode for #ucx_avl_find_node() with the same behavior as + * #ucx_avl_get_node(). + */ +#define UCX_AVL_FIND_EXACT 0 +/** + * A mode for #ucx_avl_find_node() finding the node whose key is at least + * as large as the specified key. + */ +#define UCX_AVL_FIND_LOWER_BOUNDED 1 +/** + * A mode for #ucx_avl_find_node() finding the node whose key is at most + * as large as the specified key. + */ +#define UCX_AVL_FIND_UPPER_BOUNDED 2 +/** + * A mode for #ucx_avl_find_node() finding the node with a key that is as close + * to the specified key as possible. If the key is present, the behavior is + * like #ucx_avl_get_node(). This mode only returns NULL on + * empty trees. + */ +#define UCX_AVL_FIND_CLOSEST 3 + +/** + * Finds a node within the tree. The following modes are supported: + * + * + * The distance function provided MUST agree with the compare function of + * the AVL tree. + * + * @param tree the UcxAVLTree + * @param key the key + * @param dfnc the distance function + * @param mode the find mode + * @return the node (or NULL, if no node can be found) + */ +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, + distance_func dfnc, int mode); + +/** + * Finds a value within the tree. + * See #ucx_avl_find_node() for details. + * + * @param tree the UcxAVLTree + * @param key the key + * @param dfnc the distance function + * @param mode the find mode + * @return the value (or NULL, if no value can be found) + */ +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, + distance_func dfnc, int mode); + +/** * Puts a key/value pair into the tree. * * Attention: use this function only, if a possible old value does not need @@ -196,7 +258,7 @@ * * 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. + * is freed, so its further use is generally undefined. * * @param tree the UcxAVLTree * @param node the node to remove diff -r a3597d704421 -r 2e74828c5e94 ucx/ucx.h --- a/ucx/ucx.h Mon Mar 06 16:22:42 2017 +0100 +++ b/ucx/ucx.h Sat Jul 15 19:20:06 2017 +0200 @@ -40,9 +40,10 @@ #define UCX_VERSION_MAJOR 0 /** Minor UCX version as integer constant. */ -#define UCX_VERSION_MINOR 11 +#define UCX_VERSION_MINOR 12 #include +#include #ifdef _WIN32 #if !(defined __ssize_t_defined || defined _SSIZE_T_) @@ -89,6 +90,15 @@ typedef int(*cmp_func)(void*,void*,void*); /** + * Function pointer to a distance function. + * + * The distance function shall take three arguments: the two values for which + * the distance shall be computed and optional additional data. + * The function shall then return the signed distance as integer value. + */ +typedef intmax_t(*distance_func)(void*,void*,void*); + +/** * Function pointer to a copy function. * * The copy function shall create a copy of the first argument and may use