Mercurial > hg > ucx / changeset

     1.1 --- a/test/avl_tests.c	Mon Mar 06 16:22:42 2017 +0100
     1.2 +++ b/test/avl_tests.c	Sat Jul 15 19:20:06 2017 +0200
     1.3 @@ -223,3 +223,62 @@
     1.4      ucx_avl_free(tree3);
     1.5      ucx_avl_free(tree4);
     1.6  }
     1.7 +
     1.8 +static intmax_t dist_int(void* a, void* b, void* n) {
     1.9 +    return ((intmax_t)a)-((intmax_t)b);
    1.10 +}
    1.11 +
    1.12 +UCX_TEST(test_ucx_avl_find) {
    1.13 +    UcxAVLTree *tree = ucx_avl_new(ucx_ptrcmp);
    1.14 +    
    1.15 +    size_t len = 12;
    1.16 +    int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13};
    1.17 +    
    1.18 +    for (size_t i = 0 ; i < len ; i++) {
    1.19 +        ucx_avl_put(tree, val[i], &(val[i]));
    1.20 +    }
    1.21 +    
    1.22 +    UCX_TEST_BEGIN
    1.23 +    
    1.24 +    void* ret;
    1.25 +    
    1.26 +    /* test present values */
    1.27 +    ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_CLOSEST);
    1.28 +    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find closest failed");
    1.29 +    ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_EXACT);
    1.30 +    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find exact failed");
    1.31 +    ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
    1.32 +    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed");
    1.33 +    ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    1.34 +    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find UB failed");
    1.35 +    ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_CLOSEST);
    1.36 +    UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find closest failed");
    1.37 +    ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_EXACT);
    1.38 +    UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find exact failed");
    1.39 +    ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
    1.40 +    UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find LB failed");
    1.41 +    ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    1.42 +    UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find UB failed");
    1.43 +    
    1.44 +    /* test missing values */
    1.45 +    ret = ucx_avl_find(tree,(intptr_t)-10, dist_int, UCX_AVL_FIND_CLOSEST);
    1.46 +    UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find closest failed");
    1.47 +    ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_EXACT);
    1.48 +    UCX_TEST_ASSERT(!ret, "AVL find exact failed");
    1.49 +    ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
    1.50 +    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed");
    1.51 +    ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    1.52 +    UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find UB failed");
    1.53 +    ret = ucx_avl_find(tree,(intptr_t)18, dist_int, UCX_AVL_FIND_CLOSEST);
    1.54 +    UCX_TEST_ASSERT(ret && *((int*)ret) == 20, "AVL find closest failed");
    1.55 +    ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_EXACT);
    1.56 +    UCX_TEST_ASSERT(!ret, "AVL find exact failed");
    1.57 +    ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
    1.58 +    UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed");
    1.59 +    ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    1.60 +    UCX_TEST_ASSERT(ret && *((int*)ret) == 4, "AVL find UB failed");
    1.61 +    
    1.62 +    UCX_TEST_END
    1.63 +    
    1.64 +    ucx_avl_free(tree);
    1.65 +}

     2.1 --- a/test/avl_tests.h	Mon Mar 06 16:22:42 2017 +0100
     2.2 +++ b/test/avl_tests.h	Sat Jul 15 19:20:06 2017 +0200
     2.3 @@ -38,6 +38,7 @@
     2.4  
     2.5  UCX_TEST(test_ucx_avl_put);
     2.6  UCX_TEST(test_ucx_avl_remove);
     2.7 +UCX_TEST(test_ucx_avl_find);
     2.8  
     2.9  #ifdef	__cplusplus
    2.10  }

     3.1 --- a/test/main.c	Mon Mar 06 16:22:42 2017 +0100
     3.2 +++ b/test/main.c	Sat Jul 15 19:20:06 2017 +0200
     3.3 @@ -227,6 +227,7 @@
     3.4          /* AVL Tests */
     3.5          ucx_test_register(suite, test_ucx_avl_put);
     3.6          ucx_test_register(suite, test_ucx_avl_remove);
     3.7 +        ucx_test_register(suite, test_ucx_avl_find);
     3.8  
     3.9          ucx_test_run(suite, stdout);
    3.10          fflush(stdout);

     4.1 --- a/ucx/avl.c	Mon Mar 06 16:22:42 2017 +0100
     4.2 +++ b/ucx/avl.c	Sat Jul 15 19:20:06 2017 +0200
     4.3 @@ -26,6 +26,8 @@
     4.4   * POSSIBILITY OF SUCH DAMAGE.
     4.5   */
     4.6  
     4.7 +#include <limits.h>
     4.8 +
     4.9  #include "avl.h"
    4.10  
    4.11  #define ptrcast(ptr) ((void*)(ptr))
    4.12 @@ -149,6 +151,46 @@
    4.13      return n ? n->value : NULL;
    4.14  }
    4.15  
    4.16 +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
    4.17 +        distance_func dfnc, int mode) {
    4.18 +    UcxAVLNode *n = tree->root;
    4.19 +    UcxAVLNode *closest = NULL;
    4.20 +
    4.21 +    intmax_t cmpresult;
    4.22 +    intmax_t closest_dist;
    4.23 +    closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX;
    4.24 +    
    4.25 +    while (n && (cmpresult = dfnc(
    4.26 +            ptrcast(key), ptrcast(n->key), tree->userdata))) {
    4.27 +        if (mode == UCX_AVL_FIND_CLOSEST) {
    4.28 +            intmax_t dist = cmpresult;
    4.29 +            if (dist < 0) dist *= -1;
    4.30 +            if (dist < closest_dist) {
    4.31 +                closest_dist = dist;
    4.32 +                closest = n;
    4.33 +            }
    4.34 +        } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) {
    4.35 +            if (cmpresult > closest_dist) {
    4.36 +                closest_dist = cmpresult;
    4.37 +                closest = n;
    4.38 +            }
    4.39 +        } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) {
    4.40 +            if (cmpresult < closest_dist) {
    4.41 +                closest_dist = cmpresult;
    4.42 +                closest = n;
    4.43 +            }
    4.44 +        }
    4.45 +        n = cmpresult > 0 ? n->right : n->left;
    4.46 +    }
    4.47 +    return n ? n : closest;
    4.48 +}
    4.49 +
    4.50 +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
    4.51 +        distance_func dfnc, int mode) {
    4.52 +    UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode);
    4.53 +    return n ? n->value : NULL;
    4.54 +}
    4.55 +
    4.56  int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
    4.57      return ucx_avl_put_s(tree, key, value, NULL);
    4.58  }

     5.1 --- a/ucx/avl.h	Mon Mar 06 16:22:42 2017 +0100
     5.2 +++ b/ucx/avl.h	Sat Jul 15 19:20:06 2017 +0200
     5.3 @@ -164,6 +164,68 @@
     5.4  void *ucx_avl_get(UcxAVLTree *tree, intptr_t key);
     5.5  
     5.6  /**
     5.7 + * A mode for #ucx_avl_find_node() with the same behavior as
     5.8 + * #ucx_avl_get_node().
     5.9 + */
    5.10 +#define UCX_AVL_FIND_EXACT         0
    5.11 +/**
    5.12 + * A mode for #ucx_avl_find_node() finding the node whose key is at least
    5.13 + * as large as the specified key.
    5.14 + */
    5.15 +#define UCX_AVL_FIND_LOWER_BOUNDED 1
    5.16 +/**
    5.17 + * A mode for #ucx_avl_find_node() finding the node whose key is at most
    5.18 + * as large as the specified key.
    5.19 + */
    5.20 +#define UCX_AVL_FIND_UPPER_BOUNDED 2
    5.21 +/**
    5.22 + * A mode for #ucx_avl_find_node() finding the node with a key that is as close
    5.23 + * to the specified key as possible. If the key is present, the behavior is
    5.24 + * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
    5.25 + * empty trees.
    5.26 + */
    5.27 +#define UCX_AVL_FIND_CLOSEST       3
    5.28 +
    5.29 +/**
    5.30 + * Finds a node within the tree. The following modes are supported:
    5.31 + * <ul>
    5.32 + * <li>#UCX_AVL_FIND_EXACT: the same behavior as #ucx_avl_get_node()</li>
    5.33 + * <li>#UCX_AVL_FIND_LOWER_BOUNDED: finds the node whose key is at least
    5.34 + * as large as the specified key</li>
    5.35 + * <li>#UCX_AVL_FIND_UPPER_BOUNDED: finds the node whose key is at most
    5.36 + * as large as the specified key</li>
    5.37 + * <li>#UCX_AVL_FIND_CLOSEST: finds the node with a key that is as close to
    5.38 + * the specified key as possible. If the key is present, the behavior is
    5.39 + * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
    5.40 + * empty trees.</li> 
    5.41 + * </ul>
    5.42 + * 
    5.43 + * The distance function provided MUST agree with the compare function of
    5.44 + * the AVL tree.
    5.45 + * 
    5.46 + * @param tree the UcxAVLTree
    5.47 + * @param key the key
    5.48 + * @param dfnc the distance function
    5.49 + * @param mode the find mode
    5.50 + * @return the node (or <code>NULL</code>, if no node can be found)
    5.51 + */
    5.52 +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
    5.53 +        distance_func dfnc, int mode);
    5.54 +
    5.55 +/**
    5.56 + * Finds a value within the tree.
    5.57 + * See #ucx_avl_find_node() for details.
    5.58 + * 
    5.59 + * @param tree the UcxAVLTree
    5.60 + * @param key the key
    5.61 + * @param dfnc the distance function
    5.62 + * @param mode the find mode
    5.63 + * @return the value (or <code>NULL</code>, if no value can be found)
    5.64 + */
    5.65 +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
    5.66 +        distance_func dfnc, int mode);
    5.67 +
    5.68 +/**
    5.69   * Puts a key/value pair into the tree.
    5.70   * 
    5.71   * Attention: use this function only, if a possible old value does not need
    5.72 @@ -196,7 +258,7 @@
    5.73   * 
    5.74   * Note: the specified node is logically removed. The tree implementation
    5.75   * decides which memory area is freed. In most cases the here provided node
    5.76 - * is freed, so it's further use is generally undefined.
    5.77 + * is freed, so its further use is generally undefined.
    5.78   * 
    5.79   * @param tree the UcxAVLTree
    5.80   * @param node the node to remove

     6.1 --- a/ucx/ucx.h	Mon Mar 06 16:22:42 2017 +0100
     6.2 +++ b/ucx/ucx.h	Sat Jul 15 19:20:06 2017 +0200
     6.3 @@ -40,9 +40,10 @@
     6.4  #define UCX_VERSION_MAJOR   0
     6.5  
     6.6  /** Minor UCX version as integer constant. */
     6.7 -#define UCX_VERSION_MINOR   11
     6.8 +#define UCX_VERSION_MINOR   12
     6.9  
    6.10  #include <stdlib.h>
    6.11 +#include <stdint.h>
    6.12  
    6.13  #ifdef _WIN32
    6.14  #if !(defined __ssize_t_defined || defined _SSIZE_T_)
    6.15 @@ -89,6 +90,15 @@
    6.16  typedef int(*cmp_func)(void*,void*,void*);
    6.17  
    6.18  /**
    6.19 + * Function pointer to a distance function.
    6.20 + * 
    6.21 + * The distance function shall take three arguments: the two values for which
    6.22 + * the distance shall be computed and optional additional data.
    6.23 + * The function shall then return the signed distance as integer value.
    6.24 + */
    6.25 +typedef intmax_t(*distance_func)(void*,void*,void*);
    6.26 +
    6.27 +/**
    6.28   * Function pointer to a copy function.
    6.29   * 
    6.30   * The copy function shall create a copy of the first argument and may use