changeset
merge feature/tree_add branch
Tue, 20 Aug 2024 18:02:39 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 20 Aug 2024 18:02:39 +0200
- changeset 872
- d607a184925a
- parent 862
- 387414a7afd8 (current diff)
- parent 871
- e29c1f96646d (diff)
- child 874
- cdce47f34d48
merge feature/tree_add branch
relates to #390
--- a/src/cx/tree.h Sun Jul 07 14:56:44 2024 +0200 +++ b/src/cx/tree.h Tue Aug 20 18:02:39 2024 +0200 @@ -321,15 +321,41 @@ * positive if one of the children might contain the data, * negative if neither the node, nor the children contains the data */ -typedef int (*cx_tree_search_func)(void const *node, void const *data); +typedef int (*cx_tree_search_data_func)(void const *node, void const *data); + +/** + * Function pointer for a search function. + * + * A function of this kind shall check if the specified \p node + * contains the same \p data as \p new_node or if one of the children might + * contain the data. + * + * The function should use the returned integer to indicate how close the + * match is, where a negative number means that it does not match at all. + * + * For example if a tree stores file path information, a node that is + * describing a parent directory of a filename that is searched, shall + * return a positive number to indicate that a child node might contain the + * searched item. On the other hand, if the node denotes a path that is not a + * prefix of the searched filename, the function would return -1 to indicate + * that the search does not need to be continued in that branch. + * + * @param node the node that is currently investigated + * @param new_node a new node with the information which is searched + * + * @return 0 if \p node contains the same data as \p new_node, + * positive if one of the children might contain the data, + * negative if neither the node, nor the children contains the data + */ +typedef int (*cx_tree_search_func)(void const *node, void const *new_node); /** * Searches for data in a tree. * * When the data cannot be found exactly, the search function might return a * closest result which might be a good starting point for adding a new node - * to the tree. + * to the tree (see also #cx_tree_add()). * * Depending on the tree structure it is not necessarily guaranteed that the * "closest" match is uniquely defined. This function will search for a node @@ -348,9 +374,42 @@ * contain any node that might be related to the searched data */ __attribute__((__nonnull__)) +int cx_tree_search_data( + void const *root, + void const *data, + cx_tree_search_data_func sfunc, + void **result, + ptrdiff_t loc_children, + ptrdiff_t loc_next +); + +/** + * Searches for a node in a tree. + * + * When no node with the same data can be found, the search function might + * return a closest result which might be a good starting point for adding the + * new node to the tree (see also #cx_tree_add()). + * + * Depending on the tree structure it is not necessarily guaranteed that the + * "closest" match is uniquely defined. This function will search for a node + * with the best match according to the \p sfunc (meaning: the return value of + * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary + * node matching the criteria is returned. + * + * @param root the root node + * @param node the node to search for + * @param sfunc the search function + * @param result where the result shall be stored + * @param loc_children offset in the node struct for the children linked list + * @param loc_next offset in the node struct for the next pointer + * @return zero if the node was found exactly, positive if a node was found that + * could contain the node (but doesn't right now), negative if the tree does not + * contain any node that might be related to the searched data + */ +__attribute__((__nonnull__)) int cx_tree_search( void const *root, - void const *data, + void const *node, cx_tree_search_func sfunc, void **result, ptrdiff_t loc_children, @@ -410,6 +469,192 @@ ptrdiff_t loc_next ); +/** + * Describes a function that creates a tree node from the specified data. + * The first argument points to the data the node shall contain and + * the second argument may be used for additional data (e.g. an allocator). + * Functions of this type shall either return a new pointer to a newly + * created node or \c NULL when allocation fails. + * + * \note the function may leave the node pointers in the struct uninitialized. + * The caller is responsible to set them according to the intended use case. + */ +typedef void *(*cx_tree_node_create_func)(void const *, void *); + +/** + * The local search depth for a new subtree when adding multiple elements. + * The default value is 3. + * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to + * implement optimized insertion of multiple elements into a tree. + */ +extern unsigned int cx_tree_add_look_around_depth; + +/** + * Adds multiple elements efficiently to a tree. + * + * Once an element cannot be added to the tree, this function returns, leaving + * the iterator in a valid state pointing to the element that could not be + * added. + * Also, the pointer of the created node will be stored to \p failed. + * The integer returned by this function denotes the number of elements obtained + * from the \p iter that have been successfully processed. + * When all elements could be processed, a \c NULL pointer will be written to + * \p failed. + * + * The advantage of this function compared to multiple invocations of + * #cx_tree_add() is that the search for the insert locations is not always + * started from the root node. + * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes + * of the current insert location before starting from the root node again. + * When the variable is set to zero, only the last found location is checked + * again. + * + * Refer to the documentation of #cx_tree_add() for more details. + * + * @param iter a pointer to an arbitrary iterator + * @param sfunc a search function + * @param cfunc a node creation function + * @param cdata optional additional data + * @param root the root node of the tree + * @param failed location where the pointer to a failed node shall be stored + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @return the number of nodes created and added + * @see cx_tree_add() + */ +__attribute__((__nonnull__(1, 2, 3, 5, 6))) +size_t cx_tree_add_iter( + struct cx_iterator_base_s *iter, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **failed, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Adds multiple elements efficiently to a tree. + * + * Once an element cannot be added to the tree, this function returns, storing + * the pointer of the created node to \p failed. + * The integer returned by this function denotes the number of elements from + * the \p src array that have been successfully processed. + * When all elements could be processed, a \c NULL pointer will be written to + * \p failed. + * + * The advantage of this function compared to multiple invocations of + * #cx_tree_add() is that the search for the insert locations is not always + * started from the root node. + * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes + * of the current insert location before starting from the root node again. + * When the variable is set to zero, only the last found location is checked + * again. + * + * Refer to the documentation of #cx_tree_add() for more details. + * + * @param src a pointer to the source data array + * @param num the number of elements in the \p src array + * @param elem_size the size of each element in the \p src array + * @param sfunc a search function + * @param cfunc a node creation function + * @param cdata optional additional data + * @param failed location where the pointer to a failed node shall be stored + * @param root the root node of the tree + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @return the number of array elements successfully processed + * @see cx_tree_add() + */ +__attribute__((__nonnull__(1, 4, 5, 7, 8))) +size_t cx_tree_add_array( + void const *src, + size_t num, + size_t elem_size, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **failed, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Adds data to a tree. + * + * An adequate location where to add the new tree node is searched with the + * specified \p sfunc. + * + * When a location is found, the \p cfunc will be invoked with \p cdata. + * + * The node returned by \p cfunc will be linked into the tree. + * When \p sfunc returned a positive integer, the new node will be linked as a + * child. The other children (now siblings of the new node) are then checked + * with \p sfunc, whether they could be children of the new node and re-linked + * accordingly. + * + * When \p sfunc returned zero and the found node has a parent, the new + * node will be added as sibling - otherwise, the new node will be added + * as a child. + * + * When \p sfunc returned a negative value, the new node will not be added to + * the tree and this function returns a non-zero value. + * The caller should check if \p cnode contains a node pointer and deal with the + * node that could not be added. + * + * This function also returns a non-zero value when \p cfunc tries to allocate + * a new node but fails to do so. In that case, the pointer stored to \p cnode + * will be \c NULL. + * + * Multiple elements can be added more efficiently with + * #cx_tree_add_array() or #cx_tree_add_iter(). + * + * @param src a pointer to the data + * @param sfunc a search function + * @param cfunc a node creation function + * @param cdata optional additional data + * @param cnode the location where a pointer to the new node is stored + * @param root the root node of the tree + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @return zero when a new node was created and added to the tree, + * non-zero otherwise + */ +__attribute__((__nonnull__(1, 2, 3, 5, 6))) +int cx_tree_add( + void const *src, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **cnode, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + #ifdef __cplusplus } // extern "C" #endif
--- a/src/tree.c Sun Jul 07 14:56:44 2024 +0200 +++ b/src/tree.c Tue Aug 20 18:02:39 2024 +0200 @@ -33,13 +33,32 @@ #include <assert.h> #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) -#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) #define tree_parent(node) CX_TREE_PTR(node, loc_parent) #define tree_children(node) CX_TREE_PTR(node, loc_children) #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child) #define tree_prev(node) CX_TREE_PTR(node, loc_prev) #define tree_next(node) CX_TREE_PTR(node, loc_next) +#define cx_tree_ptr_locations \ + loc_parent, loc_children, loc_last_child, loc_prev, loc_next + +static void cx_tree_zero_pointers( + void *node, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + tree_parent(node) = NULL; + tree_prev(node) = NULL; + tree_next(node) = NULL; + tree_children(node) = NULL; + if (loc_last_child >= 0) { + tree_last_child(node) = NULL; + } +} + void cx_tree_link( void *restrict parent, void *restrict node, @@ -52,8 +71,7 @@ void *current_parent = tree_parent(node); if (current_parent == parent) return; if (current_parent != NULL) { - cx_tree_unlink(node, loc_parent, loc_children, loc_last_child, - loc_prev, loc_next); + cx_tree_unlink(node, cx_tree_ptr_locations); } if (tree_children(parent) == NULL) { @@ -117,7 +135,7 @@ int cx_tree_search( void const *root, - void const *data, + void const *node, cx_tree_search_func sfunc, void **result, ptrdiff_t loc_children, @@ -127,7 +145,7 @@ *result = NULL; // shortcut: compare root before doing anything else - ret = sfunc(root, data); + ret = sfunc(root, node); if (ret < 0) { return ret; } else if (ret == 0 || tree_children(root) == NULL) { @@ -150,33 +168,33 @@ // remember a candidate for adding the data // also remember the exact return code from sfunc - void *candidate = NULL; - int ret_candidate = -1; + void *candidate = (void *) root; + int ret_candidate = ret; // process the working stack while (work_size > 0) { // pop element - void const *node = work[--work_size]; + void const *elem = work[--work_size]; // apply the search function - ret = sfunc(node, data); + ret = sfunc(elem, node); if (ret == 0) { // if found, exit the search - *result = (void*) node; + *result = (void *) elem; work_size = 0; break; } else if (ret > 0) { // if children might contain the data, add them to the stack - void *c = tree_children(node); + void *c = tree_children(elem); while (c != NULL) { cx_array_simple_add(work, c); c = tree_next(c); } // remember this node in case no child is suitable - if (ret_candidate < 0 || ret < ret_candidate) { - candidate = (void *) node; + if (ret < ret_candidate) { + candidate = (void *) elem; ret_candidate = ret; } } @@ -193,6 +211,22 @@ return ret; } +int cx_tree_search_data( + void const *root, + void const *data, + cx_tree_search_data_func sfunc, + void **result, + ptrdiff_t loc_children, + ptrdiff_t loc_next +) { + // it is basically the same implementation + return cx_tree_search( + root, data, + (cx_tree_search_func) sfunc, + result, + loc_children, loc_next); +} + static bool cx_tree_iter_valid(void const *it) { struct cx_tree_iterator_s const *iter = it; return iter->node != NULL; @@ -426,3 +460,208 @@ return iter; } +static void cx_tree_add_link_duplicate( + void *original, void *duplicate, + ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, ptrdiff_t loc_next +) { + void *shared_parent = tree_parent(original); + if (shared_parent == NULL) { + cx_tree_link(original, duplicate, cx_tree_ptr_locations); + } else { + cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations); + } +} + +static void cx_tree_add_link_new( + void *parent, void *node, cx_tree_search_func sfunc, + ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, ptrdiff_t loc_next +) { + // check the current children one by one, + // if they could be children of the new node + void *child = tree_children(parent); + while (child != NULL) { + void *next = tree_next(child); + + if (sfunc(node, child) > 0) { + // the sibling could be a child -> re-link + cx_tree_link(node, child, cx_tree_ptr_locations); + } + + child = next; + } + + // add new node as new child + cx_tree_link(parent, node, cx_tree_ptr_locations); +} + +int cx_tree_add( + void const *src, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **cnode, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + *cnode = cfunc(src, cdata); + if (*cnode == NULL) return 1; + cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations); + + void *match = NULL; + int result = cx_tree_search( + root, + *cnode, + sfunc, + &match, + loc_children, + loc_next + ); + + if (result < 0) { + // node does not fit into the tree - return non-zero value + return 1; + } else if (result == 0) { + // data already found in the tree, link duplicate + cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations); + } else { + // closest match found, add new node + cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations); + } + + return 0; +} + +unsigned int cx_tree_add_look_around_depth = 3; + +size_t cx_tree_add_iter( + struct cx_iterator_base_s *iter, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **failed, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + // erase the failed pointer + *failed = NULL; + + // iter not valid? cancel... + if (!iter->valid(iter)) return 0; + + size_t processed = 0; + void *current_node = root; + void const *elem; + + for (void **eptr; + iter->valid(iter) && (eptr = iter->current(iter)) != NULL; + iter->next(iter)) { + elem = *eptr; + + // create the new node + void *new_node = cfunc(elem, cdata); + if (new_node == NULL) return processed; + cx_tree_zero_pointers(new_node, cx_tree_ptr_locations); + + // start searching from current node + void *match; + int result; + unsigned int look_around_retries = cx_tree_add_look_around_depth; + cx_tree_add_look_around_retry: + result = cx_tree_search( + current_node, + new_node, + sfunc, + &match, + loc_children, + loc_next + ); + + if (result < 0) { + // traverse upwards and try to find better parents + void *parent = tree_parent(current_node); + if (parent != NULL) { + if (look_around_retries > 0) { + look_around_retries--; + current_node = parent; + } else { + // look around retries exhausted, start from the root + current_node = root; + } + goto cx_tree_add_look_around_retry; + } else { + // no parents. so we failed + *failed = new_node; + return processed; + } + } else if (result == 0) { + // data already found in the tree, link duplicate + cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations); + // but stick with the original match, in case we needed a new root + current_node = match; + } else { + // closest match found, add new node as child + cx_tree_add_link_new(match, new_node, sfunc, + cx_tree_ptr_locations); + current_node = match; + } + + processed++; + } + return processed; +} + +size_t cx_tree_add_array( + void const *src, + size_t num, + size_t elem_size, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **failed, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + // erase failed pointer + *failed = NULL; + + // super special case: zero elements + if (num == 0) { + return 0; + } + + // special case: one element does not need an iterator + if (num == 1) { + void *node; + if (0 == cx_tree_add( + src, sfunc, cfunc, cdata, &node, root, + loc_parent, loc_children, loc_last_child, + loc_prev, loc_next)) { + return 1; + } else { + *failed = node; + return 0; + } + } + + // otherwise, create iterator and hand over to other function + CxIterator iter = cxIterator(src, elem_size, num); + return cx_tree_add_iter(cxIteratorRef(iter), sfunc, + cfunc, cdata, failed, root, + loc_parent, loc_children, loc_last_child, + loc_prev, loc_next); +} +
--- a/tests/test_tree.c Sun Jul 07 14:56:44 2024 +0200 +++ b/tests/test_tree.c Tue Aug 20 18:02:39 2024 +0200 @@ -49,13 +49,58 @@ int data; } tree_node2; +typedef struct tree_node_file { + struct tree_node_file *parent; + struct tree_node_file *next; + struct tree_node_file *prev; + struct tree_node_file *children; + struct tree_node_file *last_child; + char const *path; +} tree_node_file; + +static void *create_tree_node_file( + void const *dptr, + void *allocator) { + if (allocator == NULL) allocator = cxDefaultAllocator; + + tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file)); + node->path = dptr; + + // intentionally write garbage into the pointers, it's part of the test + node->parent = (void *) 0xf00ba1; + node->next = (void *) 0xf00ba2; + node->prev = (void *) 0xf00ba3; + node->children = (void *) 0xf00ba4; + node->last_child = (void *) 0xf00ba5; + + return node; +} + +static int tree_node_file_search(void const *l, void const *r) { + tree_node_file const *left = l; + tree_node_file const *right = r; + size_t len1 = strlen(left->path); + size_t len2 = strlen(right->path); + if (len1 <= len2) { + if (memcmp(left->path, right->path, len1) == 0) { + return (int) (len2 - len1); + } else { + return -1; + } + } else { + return -1; + } +} + #define tree_node_layout \ offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ offsetof(tree_node, prev), offsetof(tree_node, next) -#define tree_node2_layout \ - offsetof(tree_node2, parent), offsetof(tree_node2, children),\ - offsetof(tree_node2, last_child), \ - offsetof(tree_node2, prev), offsetof(tree_node2, next) +#define tree_node_full_layout(structname) \ + offsetof(structname, parent), offsetof(structname, children),\ + offsetof(structname, last_child), \ + offsetof(structname, prev), offsetof(structname, next) +#define tree_node2_layout tree_node_full_layout(tree_node2) +#define tree_node_file_layout tree_node_full_layout(tree_node_file) #define tree_children(type) offsetof(type, children), offsetof(type, next) @@ -376,38 +421,38 @@ CX_TEST_DO { for (unsigned i = 0 ; i <= 10 ; i++) { s = testdata[i]; - r = cx_tree_search(&root, &s, test_tree_search_function, + r = cx_tree_search_data(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r == 0); CX_TEST_ASSERT(n == testnodes[i]); } s = -5; - r = cx_tree_search(&root, &s, test_tree_search_function, + r = cx_tree_search_data(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r < 0); CX_TEST_ASSERT(n == NULL); s = 26; - r = cx_tree_search(&root, &s, test_tree_search_function, + r = cx_tree_search_data(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r > 0); CX_TEST_ASSERT(n == &ba); s = 35; - r = cx_tree_search(&root, &s, test_tree_search_function, + r = cx_tree_search_data(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r > 0); CX_TEST_ASSERT(n == &cb); s = 38; - r = cx_tree_search(&root, &s, test_tree_search_function, + r = cx_tree_search_data(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r > 0); CX_TEST_ASSERT(n == &cba); s = 42; - r = cx_tree_search(&root, &s, test_tree_search_function, + r = cx_tree_search_data(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r > 0); CX_TEST_ASSERT(n == &cc); @@ -993,6 +1038,433 @@ } } +CX_TEST(test_tree_add_one) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + + tree_node_file root = {0}; + root.path = "/"; + tree_node_file usr = {0}; + usr.path = "/usr/"; + cx_tree_link(&root, &usr, tree_node_file_layout); + tree_node_file home = {0}; + home.path = "/home/"; + cx_tree_link(&root, &home, tree_node_file_layout); + tree_node_file lib = {0}; + lib.path = "/usr/lib/"; + cx_tree_link(&usr, &lib, tree_node_file_layout); + + CX_TEST_DO { + tree_node_file *foo; + int result; + result = cx_tree_add( + "/home/foo/", + tree_node_file_search, + create_tree_node_file, alloc, + (void **) &foo, &root, + tree_node_file_layout + ); + CX_TEST_ASSERT(result == 0); + CX_TEST_ASSERT(foo != NULL); + char const *bar_path = "/home/foo/bar/"; + void *failed; + size_t added = cx_tree_add_array( + bar_path, 1, sizeof(char const *), + tree_node_file_search, + create_tree_node_file, alloc, + &failed, &root, + tree_node_file_layout + ); + CX_TEST_ASSERT(added == 1); + CX_TEST_ASSERT(failed == NULL); + tree_node_file *bar = foo->children; + CX_TEST_ASSERT(bar != NULL); + CX_TEST_ASSERT(bar->parent == foo); + CX_TEST_ASSERT(bar->path == bar_path); + CX_TEST_ASSERT(foo->parent == &home); + + tree_node_file *new_node; + result = cx_tree_add( + "newroot", + tree_node_file_search, + create_tree_node_file, alloc, + (void **) &new_node, &root, + tree_node_file_layout + ); + CX_TEST_ASSERT(0 != result); + CX_TEST_ASSERT(NULL != new_node); + CX_TEST_ASSERT(new_node->children == NULL); + CX_TEST_ASSERT(new_node->parent == NULL); + + CX_TEST_ASSERT(talloc.alloc_total == 3); + + cxFree(alloc, foo); + cxFree(alloc, bar); + cxFree(alloc, new_node); + + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +CX_TEST(test_tree_add_one_existing) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + + tree_node_file root = {0}; + root.path = "/"; + tree_node_file usr = {0}; + usr.path = "/usr/"; + cx_tree_link(&root, &usr, tree_node_file_layout); + tree_node_file home = {0}; + home.path = "/home/"; + cx_tree_link(&root, &home, tree_node_file_layout); + tree_node_file lib = {0}; + lib.path = "/usr/lib/"; + cx_tree_link(&usr, &lib, tree_node_file_layout); + + CX_TEST_DO { + tree_node_file *node; + int result = cx_tree_add( + "/usr/lib/", + tree_node_file_search, + create_tree_node_file, alloc, + (void **) &node, &root, + tree_node_file_layout + ); + CX_TEST_ASSERT(result == 0); + CX_TEST_ASSERT(node != &lib); + CX_TEST_ASSERT(node->prev == &lib); + CX_TEST_ASSERT(lib.next == node); + CX_TEST_ASSERT(node->parent == &usr); + CX_TEST_ASSERT(talloc.alloc_total == 1); + cxFree(alloc, node); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +CX_TEST(test_tree_add_one_no_match) { + tree_node_file root = {0}; + root.path = "/mnt/"; + + CX_TEST_DO { + tree_node_file *node = NULL; + int result = cx_tree_add( + "/usr/lib/", + tree_node_file_search, + create_tree_node_file, NULL, + (void **) &node, &root, + tree_node_file_layout + ); + CX_TEST_ASSERT(result != 0); + CX_TEST_ASSERT(node != NULL); + CX_TEST_ASSERT(node->parent == NULL); + CX_TEST_ASSERT(node->children == NULL); + free(node); + node = NULL; + size_t added = cx_tree_add_array( + "/", 1, sizeof(char const *), + tree_node_file_search, + create_tree_node_file, NULL, + (void **) &node, &root, + tree_node_file_layout + ); + CX_TEST_ASSERT(added == 0); + CX_TEST_ASSERT(node != NULL); + CX_TEST_ASSERT(node->parent == NULL); + CX_TEST_ASSERT(node->children == NULL); + free(node); + } +} + +CX_TEST(test_tree_add_duplicate_root) { + tree_node_file root = {0}; + root.path = "/"; + CX_TEST_DO { + tree_node_file *node; + int result = cx_tree_add( + "/", + tree_node_file_search, + create_tree_node_file, NULL, + (void **) &node, &root, + tree_node_file_layout + ); + CX_TEST_ASSERT(result == 0); + CX_TEST_ASSERT(root.children == node); + CX_TEST_ASSERT(node->parent == &root); + } +} + +CX_TEST(test_tree_add_zero) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + + tree_node_file root = {0}; + root.path = "/"; + CX_TEST_DO { + void *failed; + + size_t processed = cx_tree_add_array( + (void *) 0xc0ffee, 0, sizeof(void *), + tree_node_file_search, + create_tree_node_file, alloc, + &failed, &root, tree_node_file_layout + ); + CX_TEST_ASSERT(failed == NULL); + CX_TEST_ASSERT(processed == 0); + CX_TEST_ASSERT(talloc.alloc_total == 0); + + CxIterator iter = cxIterator(NULL, sizeof(void *), 0); + processed = cx_tree_add_iter( + cxIteratorRef(iter), + tree_node_file_search, + create_tree_node_file, alloc, + &failed, &root, tree_node_file_layout + ); + CX_TEST_ASSERT(processed == 0); + CX_TEST_ASSERT(failed == NULL); + CX_TEST_ASSERT(talloc.alloc_total == 0); + + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +CX_TEST(test_tree_add_many) { + // adds many elements to an existing tree + + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + + tree_node_file root = {0}; + root.path = "/"; + tree_node_file usr = {0}; + usr.path = "/usr/"; + cx_tree_link(&root, &usr, tree_node_file_layout); + tree_node_file home = {0}; + home.path = "/home/"; + cx_tree_link(&root, &home, tree_node_file_layout); + tree_node_file lib = {0}; + lib.path = "/usr/lib/"; + cx_tree_link(&usr, &lib, tree_node_file_layout); + + CX_TEST_DO { + void *failed; + + char const *paths[] = { + "/home/foo/", + "/home/foo/bar", + "/usr/lib64/", + "/usr/lib/foo.so" + }; + + size_t processed = cx_tree_add_array( + paths, 4, sizeof(char const *), + tree_node_file_search, + create_tree_node_file, alloc, + &failed, &root, tree_node_file_layout + ); + + CX_TEST_ASSERT(failed == NULL); + CX_TEST_ASSERT(processed == 4); + CX_TEST_ASSERT(talloc.alloc_total == 4); + + CX_TEST_ASSERT(home.children == home.last_child); + tree_node_file *foo = home.children; + CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]); + CX_TEST_ASSERT(foo->children == foo->last_child); + tree_node_file *bar = foo->children; + CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]); + CX_TEST_ASSERT(usr.children != usr.last_child); + tree_node_file *lib64 = usr.last_child; + CX_TEST_ASSERT(lib64 != NULL); + CX_TEST_ASSERT(lib64->path == paths[2]); + CX_TEST_ASSERT(lib64->prev == &lib); + CX_TEST_ASSERT(lib64->parent == &usr); + CX_TEST_ASSERT(lib.children != NULL); + tree_node_file *libfoo = lib.children; + CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]); + + cxFree(alloc, foo); + cxFree(alloc, bar); + cxFree(alloc, lib64); + cxFree(alloc, libfoo); + + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +CX_TEST(test_tree_add_many_with_dupl_and_no_match) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + + tree_node_file root = {0}; + root.path = "/mnt/"; + + CX_TEST_DO { + tree_node_file *failed; + + char const *paths[] = { + "/mnt/sdcard/", + "/mnt/foo/", + "/mnt/sdcard/", + "/home/", + "/usr/" + }; + + size_t processed = cx_tree_add_array( + paths, 5, sizeof(char const *), + tree_node_file_search, + create_tree_node_file, alloc, + (void **) &failed, &root, tree_node_file_layout + ); + + CX_TEST_ASSERT(processed == 3); + CX_TEST_ASSERT(failed != NULL); + CX_TEST_ASSERT(failed->parent == NULL); + CX_TEST_ASSERT(failed->children == NULL); + CX_TEST_ASSERT(strcmp(failed->path, "/home/") == 0); + cxFree(alloc, failed); + + CX_TEST_ASSERT(root.children != root.last_child); + CX_TEST_ASSERT(strcmp(root.children->path, "/mnt/sdcard/") == 0); + CX_TEST_ASSERT(strcmp(root.last_child->path, "/mnt/sdcard/") == 0); + CX_TEST_ASSERT(strcmp(root.children->next->path, "/mnt/foo/") == 0); + CX_TEST_ASSERT(strcmp(root.last_child->prev->path, "/mnt/foo/") == 0); + + CxTreeIterator iter = cx_tree_iterator( + &root, true, + offsetof(tree_node_file, children), + offsetof(tree_node_file, next) + ); + cx_foreach(tree_node_file *, node, iter) { + if (iter.exiting) { + if (node != &root) { + cxFree(alloc, node); + } + } + } + + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +static CX_TEST_SUBROUTINE(test_tree_add_create_from_array_impl, + CxAllocator *alloc, char const **paths) { + tree_node_file root = {0}; + root.path = "/"; + + void *failed; + size_t processed = cx_tree_add_array( + paths, 10, sizeof(char const *), + tree_node_file_search, + create_tree_node_file, alloc, + &failed, &root, tree_node_file_layout + ); + + CX_TEST_ASSERT(failed == NULL); + CX_TEST_ASSERT(processed == 10); + + char const *exp_order[] = { + "/", + "/usr/", + "/usr/lib/", + "/usr/lib/libbumm.so", + "/home/", + "/home/foo/", + "/var/", + "/var/www/", + "/var/www/vhosts/", + "/var/www/vhosts/live/", + "/var/www/vhosts/live/htdocs/" + }; + unsigned exp_depth[] = { + 1, + 2, + 3, + 4, + 2, + 3, + 2, + 3, + 4, + 5, + 6 + }; + + CxTreeIterator iter = cx_tree_iterator( + &root, true, + offsetof(tree_node_file, children), + offsetof(tree_node_file, next) + ); + cx_foreach(tree_node_file *, node, iter) { + if (iter.exiting) { + if (node != &root) { + cxFree(alloc, node); + } + } else { + CX_TEST_ASSERT(iter.counter <= 11); + CX_TEST_ASSERT(iter.depth == exp_depth[iter.counter - 1]); + CX_TEST_ASSERT(strcmp(node->path, exp_order[iter.counter - 1]) == 0); + } + } +} + +CX_TEST(test_tree_add_create_from_array) { + // creates an entirely new tree from an array + + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + + CX_TEST_DO { + char const *paths[] = { + "/usr/", + "/home/", + "/usr/lib/", + "/usr/lib/libbumm.so", + "/var/", + "/var/www/", + "/var/www/vhosts/", + "/var/www/vhosts/live/", + "/var/www/vhosts/live/htdocs/", + "/home/foo/" + }; + + char const *scrambled_paths[] = { + "/usr/", + "/home/", + "/var/www/vhosts/live/", + "/usr/lib/", + "/var/", + "/var/www/", + "/usr/lib/libbumm.so", + "/var/www/vhosts/", + "/var/www/vhosts/live/htdocs/", + "/home/foo/" + }; + + // no matter how the original array is sorted, + // the resulting tree should be the same + CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc, + paths); + CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc, + scrambled_paths); + + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + + CxTestSuite *cx_test_suite_tree_low_level(void) { CxTestSuite *suite = cx_test_suite_new("tree (low level)"); @@ -1016,6 +1488,14 @@ cx_test_register(suite, test_tree_visitor_continue); cx_test_register(suite, test_tree_iterator_continue); cx_test_register(suite, test_tree_iterator_continue_with_exit); + cx_test_register(suite, test_tree_add_one); + cx_test_register(suite, test_tree_add_one_existing); + cx_test_register(suite, test_tree_add_one_no_match); + cx_test_register(suite, test_tree_add_duplicate_root); + cx_test_register(suite, test_tree_add_zero); + cx_test_register(suite, test_tree_add_many); + cx_test_register(suite, test_tree_add_many_with_dupl_and_no_match); + cx_test_register(suite, test_tree_add_create_from_array); return suite; }
