changeset
rework cx_tree_add() API to allow insertion of edge nodes
Tue, 20 Aug 2024 18:01:03 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 20 Aug 2024 18:01:03 +0200
- branch
- feature/tree_add
- changeset 871
- e29c1f96646d
- parent 870
- af0092d8789a
- child 872
- d607a184925a
- child 873
- d248794bad7e
rework cx_tree_add() API to allow insertion of edge nodes
closes #390
| src/cx/tree.h | file | annotate | diff | comparison | revisions | |
| src/tree.c | file | annotate | diff | comparison | revisions | |
| tests/test_tree.c | file | annotate | diff | comparison | revisions |
--- a/src/cx/tree.h Tue Aug 20 13:53:18 2024 +0200 +++ b/src/cx/tree.h Tue Aug 20 18:01:03 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, @@ -413,21 +472,14 @@ /** * 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, optional, argument points to an existing node that already - * contains the data. - * The third argument may be used for additional data (e.g. an allocator). + * 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, a pointer to the existing node, or \c NULL when allocation - * fails. - * Returning a pointer to the existing node means, that the function decides - * not to create a new node for the data and that the caller shall continue to - * use the existing node. + * 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 where the node will be - * added to the tree. + * The caller is responsible to set them according to the intended use case. */ -typedef void *(*cx_tree_node_create_func)(void const *, void const *, void *); +typedef void *(*cx_tree_node_create_func)(void const *, void *); /** * The local search depth for a new subtree when adding multiple elements. @@ -440,13 +492,14 @@ /** * Adds multiple elements efficiently to a tree. * - * This function returns the number of elements successfully obtained from the - * iterator, which is not necessarily the number of new nodes created (depending - * on the implementation of \p cfunc). - * * 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 @@ -462,23 +515,25 @@ * @param sfunc a search function * @param cfunc a node creation function * @param cdata optional additional data - * @param root the location where a pointer to the root node is stored + * @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 elements obtained from the iterator + * @return the number of nodes created and added * @see cx_tree_add() */ -__attribute__((__nonnull__(1, 2, 3, 5))) +__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 **root, + void **failed, + void *root, ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, @@ -489,13 +544,12 @@ /** * Adds multiple elements efficiently to a tree. * - * This function returns the number of elements successfully processed which - * is not necessarily the number of new nodes created (depending on the - * implementation of \p cfunc). - * - * Once an element cannot be added to the tree, this function returns. - * That means, the integer \c n returned by this function means, that the first - * \c n elements of \p src will be definitely in the 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 @@ -513,7 +567,8 @@ * @param sfunc a search function * @param cfunc a node creation function * @param cdata optional additional data - * @param root the location where a pointer to the root node is stored + * @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 @@ -523,7 +578,7 @@ * @return the number of array elements successfully processed * @see cx_tree_add() */ -__attribute__((__nonnull__(1, 4, 5, 7))) +__attribute__((__nonnull__(1, 4, 5, 7, 8))) size_t cx_tree_add_array( void const *src, size_t num, @@ -531,7 +586,8 @@ cx_tree_search_func sfunc, cx_tree_node_create_func cfunc, void *cdata, - void **root, + void **failed, + void *root, ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, @@ -545,26 +601,26 @@ * 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 and, - * in case \p sfunc returned a direct match, the already found node. + * When a location is found, the \p cfunc will be invoked with \p cdata. * - * If \p cfunc returns a new node pointer, it will be linked into the tree. + * 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. 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 the new root. - * When \p sfunc returned a negative value, the new node will always be the - * new root. + * 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. * - * If \p cfunc returns an existing node found by \p sfunc, this function just - * returns the found node without modifying the tree. + * 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. * - * This function may return \c NULL when \p cfunc tries to allocate a new node - * but fails to do so. + * 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. * - * The \p root argument shall point to a location where the pointer to the root - * node is stored. The pointer to the root node may be \c NULL in which case - * this function will instantly create a new node and write the location to - * \p root. + * 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(). @@ -573,22 +629,25 @@ * @param sfunc a search function * @param cfunc a node creation function * @param cdata optional additional data - * @param root the location where a pointer to the root node is stored + * @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 a pointer to the new node, to an existing node, or \c NULL + * @return zero when a new node was created and added to the tree, + * non-zero otherwise */ -__attribute__((__nonnull__(1, 2, 3, 5))) -void *cx_tree_add( +__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 **root, + void **cnode, + void *root, ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
--- a/src/tree.c Tue Aug 20 13:53:18 2024 +0200 +++ b/src/tree.c Tue Aug 20 18:01:03 2024 +0200 @@ -33,7 +33,6 @@ #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) @@ -136,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, @@ -146,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) { @@ -175,19 +174,19 @@ // 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); @@ -195,7 +194,7 @@ // remember this node in case no child is suitable if (ret < ret_candidate) { - candidate = (void *) node; + candidate = (void *) elem; ret_candidate = ret; } } @@ -212,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; @@ -446,75 +461,80 @@ } static void cx_tree_add_link_duplicate( - void **root, void *original, void *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 ) { - cx_tree_zero_pointers(duplicate, cx_tree_ptr_locations); void *shared_parent = tree_parent(original); if (shared_parent == NULL) { - cx_tree_link(duplicate, original, cx_tree_ptr_locations); - *root = duplicate; + cx_tree_link(original, duplicate, cx_tree_ptr_locations); } else { cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations); } } -void *cx_tree_add( +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 **root, + 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 ) { - if (*root == NULL) { - void *node = cfunc(src, NULL, cdata); - if (node == NULL) return NULL; - cx_tree_zero_pointers(node, cx_tree_ptr_locations); - *root = node; - return node; - } + *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, - src, + root, + *cnode, sfunc, &match, loc_children, loc_next ); - void *node; if (result < 0) { - // new node is created as new parent - node = cfunc(src, NULL, cdata); - if (node == NULL) return NULL; - cx_tree_zero_pointers(node, cx_tree_ptr_locations); - cx_tree_link(node, *root, cx_tree_ptr_locations); - *root = node; + // node does not fit into the tree - return non-zero value + return 1; } else if (result == 0) { - // data already found in the tree, let cfunc decide - node = cfunc(src, match, cdata); - if (node == NULL) return NULL; - if (node != match) { - cx_tree_add_link_duplicate( - root, match, node, cx_tree_ptr_locations); - } + // 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 as child - node = cfunc(src, NULL, cdata); - if (node == NULL) return NULL; - cx_tree_zero_pointers(node, cx_tree_ptr_locations); - cx_tree_link(match, node, cx_tree_ptr_locations); + // closest match found, add new node + cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations); } - return node; + return 0; } unsigned int cx_tree_add_look_around_depth = 3; @@ -524,39 +544,34 @@ cx_tree_search_func sfunc, cx_tree_node_create_func cfunc, void *cdata, - void **root, + 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 *elem; - - // if there is no root, yet - process the first node from the iter - // as the new root node - if (current_node == NULL) { - elem = *(void **) (iter->current(iter)); - // no node in tree, yet - add a new one - current_node = cfunc(elem, NULL, cdata); - // node creation failed - stop processing - if (current_node == NULL) return 0; - cx_tree_zero_pointers(current_node, cx_tree_ptr_locations); - *root = current_node; - processed++; - iter->next(iter); - } + 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; @@ -564,14 +579,13 @@ cx_tree_add_look_around_retry: result = cx_tree_search( current_node, - elem, + new_node, sfunc, &match, loc_children, loc_next ); - void *node; if (result < 0) { // traverse upwards and try to find better parents void *parent = tree_parent(current_node); @@ -581,35 +595,23 @@ current_node = parent; } else { // look around retries exhausted, start from the root - current_node = *root; + current_node = root; } goto cx_tree_add_look_around_retry; } else { - // no parents. so we (try to) create a new root node - void *new_root = cfunc(elem, NULL, cdata); - if (new_root == NULL) return processed; - cx_tree_zero_pointers(new_root, cx_tree_ptr_locations); - cx_tree_link(new_root, current_node, cx_tree_ptr_locations); - current_node = new_root; - *root = new_root; + // no parents. so we failed + *failed = new_node; + return processed; } } else if (result == 0) { - // data already found in the tree, let cfunc decide - node = cfunc(elem, match, cdata); - if (node == NULL) return processed; - if (node != match) { - cx_tree_add_link_duplicate( - root, match, node, cx_tree_ptr_locations); - } - current_node = node; + // 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 - node = cfunc(elem, NULL, cdata); - if (node == NULL) return processed; - cx_tree_zero_pointers(node, cx_tree_ptr_locations); - cx_tree_link(match, node, cx_tree_ptr_locations); - // but make the match current and not the new node - // (usually saves one traversal when a lot of siblings are added) + cx_tree_add_link_new(match, new_node, sfunc, + cx_tree_ptr_locations); current_node = match; } @@ -625,13 +627,17 @@ cx_tree_search_func sfunc, cx_tree_node_create_func cfunc, void *cdata, - void **root, + 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; @@ -639,19 +645,22 @@ // special case: one element does not need an iterator if (num == 1) { - if (NULL != cx_tree_add( - src, sfunc, cfunc, cdata, root, + 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, root, + 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 Tue Aug 20 13:53:18 2024 +0200 +++ b/tests/test_tree.c Tue Aug 20 18:01:03 2024 +0200 @@ -60,37 +60,29 @@ static void *create_tree_node_file( void const *dptr, - void const *nptr, void *allocator) { if (allocator == NULL) allocator = cxDefaultAllocator; - char const *data = dptr; - tree_node_file const *existing = nptr; - - if (existing != NULL && strcmp(existing->path, data) == 0) { - return (void *) existing; - } else { - tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file)); - - node->path = data; + 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; + // 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; - } + return node; } -static int tree_node_file_search(void const *nptr, void const *data) { - tree_node_file const *node = nptr; - size_t len1 = strlen(node->path); - size_t len2 = strlen(data); +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(node->path, data, len1) == 0) { + if (memcmp(left->path, right->path, len1) == 0) { return (int) (len2 - len1); } else { return -1; @@ -429,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); @@ -1064,60 +1056,58 @@ cx_tree_link(&usr, &lib, tree_node_file_layout); CX_TEST_DO { - void *newroot = &root; - - tree_node_file *foo = cx_tree_add( + tree_node_file *foo; + int result; + result = cx_tree_add( "/home/foo/", tree_node_file_search, create_tree_node_file, alloc, - &newroot, tree_node_file_layout + (void **) &foo, &root, + tree_node_file_layout ); - CX_TEST_ASSERT(newroot == &root); - tree_node_file *bar = cx_tree_add( - "/home/foo/bar/", + 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, - &newroot, tree_node_file_layout + &failed, &root, + tree_node_file_layout ); - CX_TEST_ASSERT(newroot == &root); - + 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); - CX_TEST_ASSERT(talloc.alloc_total == 2); + 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); - cxFree(&talloc.base, foo); - cxFree(&talloc.base, bar); + 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_to_empty_tree) { - tree_node_file *node = NULL; - CX_TEST_DO { - tree_node_file *root = NULL; - char const *data = "/home/foo/bar/"; - - node = cx_tree_add( - data, - tree_node_file_search, - create_tree_node_file, NULL, - (void **) &root, tree_node_file_layout - ); - - CX_TEST_ASSERT(root != NULL); - CX_TEST_ASSERT(root->path == data); - CX_TEST_ASSERT(root->next == NULL); - CX_TEST_ASSERT(root->prev == NULL); - CX_TEST_ASSERT(root->children == NULL); - CX_TEST_ASSERT(root->last_child == NULL); - CX_TEST_ASSERT(root->parent == NULL); - } - free(node); -} - CX_TEST(test_tree_add_one_existing) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); @@ -1136,28 +1126,109 @@ cx_tree_link(&usr, &lib, tree_node_file_layout); CX_TEST_DO { - void *newroot = &root; - tree_node_file *node; - node = cx_tree_add( + int result = cx_tree_add( "/usr/lib/", tree_node_file_search, create_tree_node_file, alloc, - &newroot, tree_node_file_layout + (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(newroot == &root); - CX_TEST_ASSERT(node == &lib); + 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); + } +} - node = cx_tree_add( - "/home/", +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, - &newroot, tree_node_file_layout + &failed, &root, tree_node_file_layout ); - CX_TEST_ASSERT(newroot == &root); - CX_TEST_ASSERT(node == &home); + 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); @@ -1183,7 +1254,7 @@ cx_tree_link(&usr, &lib, tree_node_file_layout); CX_TEST_DO { - void *newroot = &root; + void *failed; char const *paths[] = { "/home/foo/", @@ -1196,10 +1267,10 @@ paths, 4, sizeof(char const *), tree_node_file_search, create_tree_node_file, alloc, - &newroot, tree_node_file_layout + &failed, &root, tree_node_file_layout ); - CX_TEST_ASSERT(newroot == &root); + CX_TEST_ASSERT(failed == NULL); CX_TEST_ASSERT(processed == 4); CX_TEST_ASSERT(talloc.alloc_total == 4); @@ -1219,83 +1290,180 @@ tree_node_file *libfoo = lib.children; CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]); - cxFree(&talloc.base, foo); - cxFree(&talloc.base, bar); - cxFree(&talloc.base, lib64); - cxFree(&talloc.base, libfoo); + 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); } -CX_TEST(test_tree_add_many_skip_duplicates) { - // adds many elements to an existing tree +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; - 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 *newroot = &root; - char const *paths[] = { - "/home/foo/", - "/home/foo/bar", + "/usr/", + "/home/", "/usr/lib/", - "/usr/lib/foo.so" + "/usr/lib/libbumm.so", + "/var/", + "/var/www/", + "/var/www/vhosts/", + "/var/www/vhosts/live/", + "/var/www/vhosts/live/htdocs/", + "/home/foo/" }; - size_t processed = cx_tree_add_array( - paths, 4, sizeof(char const *), - tree_node_file_search, - create_tree_node_file, alloc, - &newroot, tree_node_file_layout - ); - CX_TEST_ASSERT(newroot == &root); - - CX_TEST_ASSERT(processed == 4); - CX_TEST_ASSERT(talloc.alloc_total == 3); + 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/" + }; - 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); - CX_TEST_ASSERT(usr.children == &lib); - CX_TEST_ASSERT(lib.children != NULL); - tree_node_file *libfoo = lib.children; - CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]); - - cxFree(&talloc.base, foo); - cxFree(&talloc.base, bar); - cxFree(&talloc.base, libfoo); + // 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); } -CX_TEST(test_tree_add_create_from_array) { - // creates an entirely new tree from an array - CX_TEST_DO { - - } -} - CxTestSuite *cx_test_suite_tree_low_level(void) { CxTestSuite *suite = cx_test_suite_new("tree (low level)"); @@ -1322,9 +1490,11 @@ 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_to_empty_tree); + 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_skip_duplicates); + 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;
