Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/tree.h	Wed Feb 14 22:32:13 2024 +0100
     1.2 +++ b/src/cx/tree.h	Thu Feb 15 21:54:43 2024 +0100
     1.3 @@ -47,6 +47,8 @@
     1.4   * Links a node to a (new) parent.
     1.5   *
     1.6   * If the node has already a parent, it is unlinked, first.
     1.7 + * If the parent has children already, the node is prepended to the list
     1.8 + * of all currently existing children.
     1.9   *
    1.10   * @param parent the parent node
    1.11   * @param node the node that shall be linked
    1.12 @@ -94,22 +96,59 @@
    1.13   * contains the given \p data or if one of the children might contain
    1.14   * the data.
    1.15   *
    1.16 + * The function should use the returned integer to indicate how close the
    1.17 + * match is, where a negative number means that it does not match at all.
    1.18 + *
    1.19   * For example if a tree stores file path information, a node that is
    1.20   * describing a parent directory of a filename that is searched, shall
    1.21 - * return 1 to indicate that a child node might contain the searched item.
    1.22 - * On the other hand, if the node denotes a path that is not a prefix of
    1.23 - * the searched filename, the function would return -1 to indicate that
    1.24 - * the search does not need to be continued in that branch.
    1.25 + * return a positive number to indicate that a child node might contain the
    1.26 + * searched item. On the other hand, if the node denotes a path that is not a
    1.27 + * prefix of the searched filename, the function would return -1 to indicate
    1.28 + * that * the search does not need to be continued in that branch.
    1.29   *
    1.30   * @param node the node that is currently investigated
    1.31   * @param data the data that is searched for
    1.32   *
    1.33   * @return 0 if the node contains the data,
    1.34 - * 1 if one of the children might contain the data,
    1.35 - * -1 if neither the node, nor the children contains the data
    1.36 + * positive if one of the children might contain the data,
    1.37 + * negative if neither the node, nor the children contains the data
    1.38   */
    1.39  typedef int (*cx_tree_search_func)(void const *node, void const* data);
    1.40  
    1.41 +
    1.42 +/**
    1.43 + * Searches for data in a tree.
    1.44 + *
    1.45 + * When the data cannot be found exactly, the search function might return a
    1.46 + * closest result which might be a good starting point for adding a new node
    1.47 + * to the tree.
    1.48 + *
    1.49 + * Depending on the tree structure it is not necessarily guaranteed that the
    1.50 + * "closest" match is uniquely defined. This function will search for a node
    1.51 + * with the best match according to the \p sfunc (meaning: the return value of
    1.52 + * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
    1.53 + * node matching the criteria is returned.
    1.54 + *
    1.55 + * @param root the root node
    1.56 + * @param data the data to search for
    1.57 + * @param sfunc the search function
    1.58 + * @param result where the result shall be stored
    1.59 + * @param loc_children offset in the node struct for the children linked list
    1.60 + * @param loc_next offset in the node struct for the next pointer
    1.61 + * @return zero if the node was found exactly, positive if a node was found that
    1.62 + * could contain the node (but doesn't right now), negative if the tree does not
    1.63 + * contain any node that might be related to the searched data
    1.64 + */
    1.65 +__attribute__((__nonnull__))
    1.66 +int cx_tree_search(
    1.67 +        void const *root,
    1.68 +        void const *data,
    1.69 +        cx_tree_search_func sfunc,
    1.70 +        void **result,
    1.71 +        ptrdiff_t loc_children,
    1.72 +        ptrdiff_t loc_next
    1.73 +);
    1.74 +
    1.75  #ifdef __cplusplus
    1.76  } // extern "C"
    1.77  #endif

     2.1 --- a/src/tree.c	Wed Feb 14 22:32:13 2024 +0100
     2.2 +++ b/src/tree.c	Thu Feb 15 21:54:43 2024 +0100
     2.3 @@ -28,6 +28,8 @@
     2.4  
     2.5  #include "cx/tree.h"
     2.6  
     2.7 +#include "cx/array_list.h"
     2.8 +
     2.9  #include <assert.h>
    2.10  
    2.11  #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
    2.12 @@ -85,3 +87,85 @@
    2.13      tree_prev(node) = NULL;
    2.14      tree_next(node) = NULL;
    2.15  }
    2.16 +
    2.17 +int cx_tree_search(
    2.18 +        void const *root,
    2.19 +        void const *data,
    2.20 +        cx_tree_search_func sfunc,
    2.21 +        void **result,
    2.22 +        ptrdiff_t loc_children,
    2.23 +        ptrdiff_t loc_next
    2.24 +) {
    2.25 +    int ret;
    2.26 +    *result = NULL;
    2.27 +
    2.28 +    // shortcut: compare root before doing anything else
    2.29 +    ret = sfunc(root, data);
    2.30 +    if (ret < 0) {
    2.31 +        return ret;
    2.32 +    } else if (ret == 0 || tree_children(root) == NULL) {
    2.33 +        *result = (void*)root;
    2.34 +        return ret;
    2.35 +    }
    2.36 +
    2.37 +    // create a working stack
    2.38 +    size_t work_cap = 32;
    2.39 +    size_t work_size = 0;
    2.40 +    void const **work = malloc(sizeof(void*) * work_cap);
    2.41 +    #define work_add(node) cx_array_add(&work, &work_size, &work_cap, \
    2.42 +        sizeof(void*), &(node), cx_array_default_reallocator)
    2.43 +
    2.44 +    // add the children of root to the working stack
    2.45 +    {
    2.46 +        void *c = tree_children(root);
    2.47 +        while (c != NULL) {
    2.48 +            work_add(c);
    2.49 +            c = tree_next(c);
    2.50 +        }
    2.51 +    }
    2.52 +
    2.53 +    // remember a candidate for adding the data
    2.54 +    // also remember the exact return code from sfunc
    2.55 +    void *candidate = NULL;
    2.56 +    int ret_candidate = -1;
    2.57 +
    2.58 +    // process the working stack
    2.59 +    while (work_size > 0) {
    2.60 +        // pop element
    2.61 +        void const *node = work[--work_size];
    2.62 +
    2.63 +        // apply the search function
    2.64 +        ret = sfunc(node, data);
    2.65 +
    2.66 +        if (ret == 0) {
    2.67 +            // if found, exit the search
    2.68 +            *result = (void*) node;
    2.69 +            work_size = 0;
    2.70 +            break;
    2.71 +        } else if (ret > 0) {
    2.72 +            // if children might contain the data, add them to the stack
    2.73 +            void *c = tree_children(node);
    2.74 +            while (c != NULL) {
    2.75 +                work_add(c);
    2.76 +                c = tree_next(c);
    2.77 +            }
    2.78 +
    2.79 +            // remember this node in case no child is suitable
    2.80 +            if (ret_candidate < 0 || ret < ret_candidate) {
    2.81 +                candidate = (void *) node;
    2.82 +                ret_candidate = ret;
    2.83 +            }
    2.84 +        }
    2.85 +    }
    2.86 +
    2.87 +    // not found, but was there a candidate?
    2.88 +    if (ret != 0 && candidate != NULL) {
    2.89 +        ret = ret_candidate;
    2.90 +        *result = candidate;
    2.91 +    }
    2.92 +
    2.93 +    // free the working queue and return
    2.94 +    #undef workq_add
    2.95 +    free(work);
    2.96 +    return ret;
    2.97 +}

     3.1 --- a/tests/test_tree.c	Wed Feb 14 22:32:13 2024 +0100
     3.2 +++ b/tests/test_tree.c	Thu Feb 15 21:54:43 2024 +0100
     3.3 @@ -42,6 +42,8 @@
     3.4      offsetof(tree_node, parent), offsetof(tree_node, children), \
     3.5      offsetof(tree_node, prev), offsetof(tree_node, next)
     3.6  
     3.7 +#define tree_child_list offsetof(tree_node, children),offsetof(tree_node, next)
     3.8 +
     3.9  CX_TEST(test_tree_link_new_child) {
    3.10      tree_node parent = {0};
    3.11      tree_node child = {0};
    3.12 @@ -160,6 +162,94 @@
    3.13      }
    3.14  }
    3.15  
    3.16 +static int test_tree_search_function(void const *n, void const *d) {
    3.17 +    tree_node const *node = n;
    3.18 +    int data = *((int const*)d);
    3.19 +
    3.20 +    if (data < node->data) return -1;
    3.21 +    else if (data == node->data) return 0;
    3.22 +    else return data - node->data;
    3.23 +}
    3.24 +
    3.25 +CX_TEST(test_tree_search) {
    3.26 +    tree_node root = {0};
    3.27 +    tree_node a = {0};
    3.28 +    tree_node b = {0};
    3.29 +    tree_node c = {0};
    3.30 +    tree_node aa = {0};
    3.31 +    tree_node ab = {0};
    3.32 +    tree_node ba = {0};
    3.33 +    tree_node ca = {0};
    3.34 +    tree_node cb = {0};
    3.35 +    tree_node cc = {0};
    3.36 +    tree_node cba = {0};
    3.37 +
    3.38 +    int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40};
    3.39 +    tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc};
    3.40 +
    3.41 +    for (unsigned i = 0 ; i <= 10 ; i++) {
    3.42 +        testnodes[i]->data = testdata[i];
    3.43 +    }
    3.44 +
    3.45 +    cx_tree_link(&root, &a, tree_node_layout);
    3.46 +    cx_tree_link(&root, &b, tree_node_layout);
    3.47 +    cx_tree_link(&root, &c, tree_node_layout);
    3.48 +
    3.49 +    cx_tree_link(&a, &aa, tree_node_layout);
    3.50 +    cx_tree_link(&a, &ab, tree_node_layout);
    3.51 +
    3.52 +    cx_tree_link(&b, &ba, tree_node_layout);
    3.53 +
    3.54 +    cx_tree_link(&c, &ca, tree_node_layout);
    3.55 +    cx_tree_link(&c, &cb, tree_node_layout);
    3.56 +    cx_tree_link(&c, &cc, tree_node_layout);
    3.57 +
    3.58 +    cx_tree_link(&cb, &cba, tree_node_layout);
    3.59 +
    3.60 +    int s;
    3.61 +    int r;
    3.62 +    tree_node *n;
    3.63 +    CX_TEST_DO {
    3.64 +        for (unsigned i = 0 ; i <= 10 ; i++) {
    3.65 +            s = testdata[i];
    3.66 +            r = cx_tree_search(&root, &s, test_tree_search_function,
    3.67 +                               (void **) &n, tree_child_list);
    3.68 +            CX_TEST_ASSERT(r == 0);
    3.69 +            CX_TEST_ASSERT(n == testnodes[i]);
    3.70 +        }
    3.71 +
    3.72 +        s = -5;
    3.73 +        r = cx_tree_search(&root, &s, test_tree_search_function,
    3.74 +                           (void **) &n, tree_child_list);
    3.75 +        CX_TEST_ASSERT(r < 0);
    3.76 +        CX_TEST_ASSERT(n == NULL);
    3.77 +
    3.78 +        s = 26;
    3.79 +        r = cx_tree_search(&root, &s, test_tree_search_function,
    3.80 +                           (void **) &n, tree_child_list);
    3.81 +        CX_TEST_ASSERT(r > 0);
    3.82 +        CX_TEST_ASSERT(n == &ba);
    3.83 +
    3.84 +        s = 35;
    3.85 +        r = cx_tree_search(&root, &s, test_tree_search_function,
    3.86 +                           (void **) &n, tree_child_list);
    3.87 +        CX_TEST_ASSERT(r > 0);
    3.88 +        CX_TEST_ASSERT(n == &cb);
    3.89 +
    3.90 +        s = 38;
    3.91 +        r = cx_tree_search(&root, &s, test_tree_search_function,
    3.92 +                           (void **) &n, tree_child_list);
    3.93 +        CX_TEST_ASSERT(r > 0);
    3.94 +        CX_TEST_ASSERT(n == &cba);
    3.95 +
    3.96 +        s = 42;
    3.97 +        r = cx_tree_search(&root, &s, test_tree_search_function,
    3.98 +                           (void **) &n, tree_child_list);
    3.99 +        CX_TEST_ASSERT(r > 0);
   3.100 +        CX_TEST_ASSERT(n == &cc);
   3.101 +    }
   3.102 +}
   3.103 +
   3.104  CxTestSuite *cx_test_suite_tree_low_level(void) {
   3.105      CxTestSuite *suite = cx_test_suite_new("tree (low level)");
   3.106  
   3.107 @@ -167,6 +257,7 @@
   3.108      cx_test_register(suite, test_tree_link_add_child);
   3.109      cx_test_register(suite, test_tree_link_move_to_other_parent);
   3.110      cx_test_register(suite, test_tree_unlink);
   3.111 +    cx_test_register(suite, test_tree_search);
   3.112  
   3.113      return suite;
   3.114  }