Mercurial > hg > ucx / changeset

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

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

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

--- 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 <limits.h>
+
 #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);
 }

--- 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 <code>NULL</code> on
+ * empty trees.
+ */
+#define UCX_AVL_FIND_CLOSEST       3
+
+/**
+ * Finds a node within the tree. The following modes are supported:
+ * <ul>
+ * <li>#UCX_AVL_FIND_EXACT: the same behavior as #ucx_avl_get_node()</li>
+ * <li>#UCX_AVL_FIND_LOWER_BOUNDED: finds the node whose key is at least
+ * as large as the specified key</li>
+ * <li>#UCX_AVL_FIND_UPPER_BOUNDED: finds the node whose key is at most
+ * as large as the specified key</li>
+ * <li>#UCX_AVL_FIND_CLOSEST: finds 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 <code>NULL</code> on
+ * empty trees.</li> 
+ * </ul>
+ * 
+ * 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 <code>NULL</code>, 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 <code>NULL</code>, 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

--- 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 <stdlib.h>
+#include <stdint.h>
 
 #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