changeset
merge logo change
Wed, 31 Dec 2025 14:58:52 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Wed, 31 Dec 2025 14:58:52 +0100
- changeset 1691
- 5e608d0e5bd1
- parent 1690
- 7d41291b3095 (diff)
- parent 1686
- d08b63b8c93a (current diff)
- child 1692
- 56731bb98508
merge logo change
--- a/docs/Writerside/topics/collection.h.md Wed Dec 31 14:15:17 2025 +0100 +++ b/docs/Writerside/topics/collection.h.md Wed Dec 31 14:58:52 2025 +0100 @@ -106,6 +106,7 @@ // use in your collection's implementation cx_invoke_destructor(c, elem) +cx_invoke_destructor_raw(c, elem) // the following two can be used to optimize loops cx_invoke_simple_destructor(c, elem) @@ -120,12 +121,13 @@ is removed from your collection _without_ being returned to the caller. This macro will invoke a simple destructor, if one is assigned, first, and then the advanced destructor (again, if assigned). -> Destructor functions are always invoked with a pointer to the element in your collection. +> Destructor functions are invoked with a pointer to the element in your collection, unless you use `cx_invoke_destructor_raw()`. > If your collection is storing pointers (i.e. `cxCollectionStoresPointers()` returns `true`) > the `cx_invoke_destructor()` will make sure that the pointer to the element is dereferenced first, > so that the destructor functions are _always_ invoked with a pointer to the actual element. > > This is different to how [comparator functions](#comparator-functions) work. +> If you want the same behavior as for comparators, use `cx_invoke_destructor_raw()`. {style="note"} <seealso>
--- a/docs/Writerside/topics/tree.h.md Wed Dec 31 14:15:17 2025 +0100 +++ b/docs/Writerside/topics/tree.h.md Wed Dec 31 14:58:52 2025 +0100 @@ -124,15 +124,26 @@ ptrdiff_t loc_children, ptrdiff_t loc_last_child, ptrdiff_t loc_prev, ptrdiff_t loc_next); +void *cxTreeCreateRootData(CxTree *tree, const void *data); + +void *cxTreeCreateRoot(CxTree *tree, void *child); + +void *cxTreeCreateNode(CxTree *tree, void *parent); + void *cxTreeAddData(CxTree *tree, void *parent, const void *data); void cxTreeAddNode(CxTree *tree, void *parent, void *child); void cxTreeSetParent(CxTree *tree, void *parent, void *child); + +void *cxTreeSetRoot(CxTree *tree, void *root); ``` The low-level function `cx_tree_add()` adds a `node` to a new `parent`, unlinking it from its previous parent, if required. +When you have created a high-level tree that is still empty, you can create a root node with `cxTreeCreateRoot()` or `cxTreeCreateRootData()`. +Both functions return an existing root node, if present, and `NULL` when the allocation of a new node failed. + The functions `cxTreeAddData()`, `cxTreeAddNode()`, and `cxTreeSetParent()` are similar to `cx_tree_add()`. The difference between `cxTreeAddData()` and `cxTreeAddNode()` is, that `cxTreeAddData()` uses the allocator of the `CxTree` to create the node first, before adding it. @@ -140,11 +151,19 @@ The difference between `cxTreeSetParent()` and `cxTreeAddNode()` is, that `cxTreeSetParent()` does not increase the tree size, when `child` already had a parent. +When you want to use `cxTreeCreateRootData()` or `cxTreeAddData()`, +the `loc_data` parameter of `cxTreeCreate()` must have been set to a non-negative value. +Otherwise, the functions will return `NULL`. + > Use `cxTreeAddNode()` to add _new_ nodes to the tree and `cxTreeSetParent()` > to relink a subtree of the `tree` with a new parent. > > Using `cxTreeSetParent()` on a `child` which already has a parent in a _different_ tree is a mistake. +The function `cxTreeSetRoot()` returns the current root node of the tree, +or `NULL` when the tree is empty, and sets a new root node. +It is up to the caller to take care of a possibly necessary deallocation of the old tree nodes. +Also, keep in mind that the tree might have destructors registered which will be applied to the nodes belonging to the new root. ## Size and Depth
--- a/src/cx/collection.h Wed Dec 31 14:15:17 2025 +0100 +++ b/src/cx/collection.h Wed Dec 31 14:58:52 2025 +0100 @@ -312,4 +312,22 @@ if ((c)->collection.simple_destructor) cx_invoke_simple_destructor(c,e); \ if ((c)->collection.advanced_destructor) cx_invoke_advanced_destructor(c,e) +/** + * Invokes all available destructor functions for a specific element. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. + * + * In contrast to cx_invoke_destructor(), this macro does not automatically + * dereference pointers to the elements when cxCollectionStoresPointers() + * returns true. + * + * @param c a pointer to a struct that contains #CX_COLLECTION_BASE + * @param e pointer to the element + */ +#define cx_invoke_destructor_raw(c, e) \ + if ((c)->collection.simple_destructor) (c)->collection.simple_destructor(e); \ + if ((c)->collection.advanced_destructor) (c)->collection.advanced_destructor((c)->collection.destructor_data, e) + + #endif // UCX_COLLECTION_H
--- a/src/cx/tree.h Wed Dec 31 14:15:17 2025 +0100 +++ b/src/cx/tree.h Wed Dec 31 14:58:52 2025 +0100 @@ -484,6 +484,12 @@ * The specified @p allocator will be used for creating the tree struct * @em and the nodes. * + * When you do not specify an existing @p root, the tree will be created + * empty. Additionally, cxFree() is registered as the advanced destructor for + * the tree so that all nodes that you will add to the tree are automatically + * freed together with the tree. + * When @p root is not @c NULL, no destructors are registered automatically. + * * @param allocator the allocator to use * (if @c NULL, the cxDefaultAllocator is assumed) * @param node_size the complete size of one node @@ -720,12 +726,55 @@ CX_EXTERN CX_NONNULL void *cxTreeAddData(CxTree *tree, void *parent, const void *data); -CX_EXTERN CX_NODISCARD +/** + * Creates a new node and adds it to the tree. + * + * @param tree the tree + * @param parent the parent node of the new node + * @return the added node or @c NULL when the allocation failed + */ +CX_EXTERN CX_NODISCARD CX_NONNULL +void *cxTreeCreateNode(CxTree *tree, void *parent); + +/** + * Creates a new root node or returns the existing root node. + * + * @param tree the tree + * @return the new root node, the existing root node, or @c NULL when the allocation failed + * @see cxTreeCreateRootData() + */ +CX_EXTERN CX_NODISCARD CX_NONNULL void *cxTreeCreateRoot(CxTree *tree); -CX_EXTERN CX_NODISCARD +/** + * Creates a new root node or uses the existing root node and writes the specified data to that node. + * + * @note This function immediately returns @c NULL when @c loc_data was not initialized with a positive value. + * + * @param tree the tree + * @param data the data for the root node + * @return the new root node, the existing root node, + * or @c NULL when the allocation failed or the data location is not known + * @see cxTreeCreateRoot() + */ +CX_EXTERN CX_NODISCARD CX_NONNULL void *cxTreeCreateRootData(CxTree *tree, const void *data); +/** + * Exchanges the root of the tree. + * + * @attention The old tree nodes might need to be deallocated by the caller. + * On the other hand, when the tree has destructors registered, keep in mind + * that they will be applied to the new tree. + * In particular, using cxTreeCreate() with a @c NULL root and setting the + * root with this function is @em not equivalent to creating the tree with + * a reference to an existing root because trees created without a root will + * have destructors registered. + * + * @param tree the tree + * @param new_root the new root node + * @return the old root node (or @c NULL when the tree was empty) + */ CX_EXTERN CX_NONNULL_ARG(1) CX_NODISCARD void *cxTreeSetRoot(CxTree *tree, void *new_root);
--- a/src/json.c Wed Dec 31 14:15:17 2025 +0100 +++ b/src/json.c Wed Dec 31 14:58:52 2025 +0100 @@ -1427,7 +1427,7 @@ CxBuffer buffer; if (cxBufferInit(&buffer, allocator, NULL, 128, CX_BUFFER_AUTO_EXTEND | CX_BUFFER_DO_NOT_FREE)) { - return CX_NULLSTR; + return CX_NULLSTR; // LCOV_EXCL_LINE } if (cx_json_write_rec(&buffer, value, cxBufferWriteFunc, writer, 0) || cxBufferTerminate(&buffer)) { @@ -1485,8 +1485,7 @@ return cx_vcmp_double(json->number, cxJsonAsDouble(other)); case CX_JSON_LITERAL: return json->literal == other->literal ? 0 : -1; - default: - // LCOV_EXCL_START + default: // LCOV_EXCL_START // unreachable assert(false); return -1; @@ -1536,8 +1535,7 @@ arr->array.size = elem_count; for (size_t i = 0 ; i < elem_count ; i++) { CxJsonValue *e = cx_json_clone_func(NULL, source->array.data[i], allocator, NULL); - if (e == NULL) { - // LCOV_EXCL_START + if (e == NULL) { // LCOV_EXCL_START cxJsonValueFree(arr); return NULL; // LCOV_EXCL_STOP @@ -1554,8 +1552,7 @@ return_value(cxJsonCreateNumber(allocator, source->number)); case CX_JSON_LITERAL: return_value(cxJsonCreateLiteral(allocator, source->literal)); - default: - // LCOV_EXCL_START + default: // LCOV_EXCL_START // unreachable assert(false); return NULL;
--- a/src/tree.c Wed Dec 31 14:15:17 2025 +0100 +++ b/src/tree.c Wed Dec 31 14:58:52 2025 +0100 @@ -314,7 +314,7 @@ // node has children, push the first child onto the stack and enter it if (iter->depth >= iter->stack_capacity) { const size_t newcap = iter->stack_capacity + 8; - if (cxReallocArrayDefault(&iter->stack, newcap, sizeof(void*))) { + if (cxReallocateArrayDefault(&iter->stack, newcap, sizeof(void*))) { // we cannot return an error in this function abort(); // LCOV_EXCL_LINE } @@ -458,6 +458,7 @@ ) { CxTreeIterator ret; ret.visit_on_exit = false; + ret.exiting = false; ret.use_dfs = false; ret.loc_children = loc_children; ret.loc_next = loc_next; @@ -567,8 +568,18 @@ tree->collection.size++; } +void *cxTreeCreateNode(CxTree *tree, void *parent) { + void *node = cxZalloc(tree->collection.allocator, tree->node_size); + if (node == NULL) return NULL; // LCOV_EXCL_LINE + cx_tree_add(parent, node, tree_layout(tree)); + tree->collection.size++; + return node; +} + void *cxTreeAddData(CxTree *tree, void *parent, const void *data) { - void *node = cxZalloc(tree->collection.allocator, tree->node_size); + if (tree->loc_data < 0) return NULL; + + void *node = cxTreeCreateNode(tree, parent); if (node == NULL) return NULL; // LCOV_EXCL_LINE char *dst = node; @@ -576,8 +587,6 @@ const void *src = cxCollectionStoresPointers(tree) ? (const void*)&data : data; memcpy(dst, src, tree->collection.elem_size); - cx_tree_add(parent, node, tree_layout(tree)); - tree->collection.size++; return node; } @@ -734,7 +743,7 @@ ) { int result = cxTreeRemoveNode(tree, node, relink_func); if (result == 0) { - cx_invoke_destructor(tree, node); + cx_invoke_destructor_raw(tree, node); return 0; } else { return result; @@ -749,7 +758,8 @@ ); cx_foreach(void *, child, iter) { if (iter.exiting) { - cx_invoke_destructor(tree, child); + // always call the destructors with the node! + cx_invoke_destructor_raw(tree, child); } } tree->collection.size -= iter.counter;
--- a/tests/test_buffer.c Wed Dec 31 14:15:17 2025 +0100 +++ b/tests/test_buffer.c Wed Dec 31 14:58:52 2025 +0100 @@ -326,7 +326,7 @@ CX_TEST_ASSERT(buf.capacity == 16); CX_TEST_ASSERT(talloc.alloc_total == 0); // reserve to grow - cxBufferReserve(&buf, 32); + CX_TEST_ASSERT(0 == cxBufferReserve(&buf, 32)); CX_TEST_ASSERT(buf.capacity == 32); CX_TEST_ASSERT(buf.size == 8); CX_TEST_ASSERT(memcmp(buf.space, "Testing", 8) == 0); @@ -334,12 +334,17 @@ CX_TEST_ASSERT((buf.flags & CX_BUFFER_COPY_ON_EXTEND) == 0); // reserve to shrink buf.size = 24; - cxBufferReserve(&buf, 16); + CX_TEST_ASSERT(0 == cxBufferReserve(&buf, 16)); + CX_TEST_ASSERT(buf.capacity == 16); + CX_TEST_ASSERT(buf.size == 16); + CX_TEST_ASSERT(memcmp(buf.space, "Testing", 8) == 0); + // reserve no-op + CX_TEST_ASSERT(0 == cxBufferReserve(&buf, 16)); CX_TEST_ASSERT(buf.capacity == 16); CX_TEST_ASSERT(buf.size == 16); CX_TEST_ASSERT(memcmp(buf.space, "Testing", 8) == 0); // reserve to free - cxBufferReserve(&buf, 0); + CX_TEST_ASSERT(0 == cxBufferReserve(&buf, 0)); CX_TEST_ASSERT(buf.capacity == 0); CX_TEST_ASSERT(buf.size == 0); CX_TEST_ASSERT(buf.space == NULL);
--- a/tests/test_json.c Wed Dec 31 14:15:17 2025 +0100 +++ b/tests/test_json.c Wed Dec 31 14:58:52 2025 +0100 @@ -175,7 +175,7 @@ CX_TEST_ASSERT(value); CX_TEST_ASSERT(cxJsonIsArray(value)); CX_TEST_ASSERT(value->array.size == 3); - for(int i=0;i<3;i++) { + for (unsigned i = 0; i < 3; i++) { CxJsonValue *v = cxJsonArrGet(value, i); CX_TEST_ASSERT(v); CX_TEST_ASSERT(cxJsonIsInteger(v)); @@ -797,8 +797,8 @@ CxJsonStatus result; CxJson json; CxJsonValue *obj = NULL; - - for(int i=0;i<5;i++) { + + for (unsigned i = 0; i < cx_nmemb(tests); i++) { cxJsonInit(&json, NULL); cxJsonFill(&json, tests[i]); result = cxJsonNext(&json, &obj); @@ -1336,7 +1336,9 @@ } CX_TEST(test_json_compare_primitives) { - CxJsonValue *a[14]; + CxJsonValue *a[15]; + CxJsonValue nothing1, nothing2; + nothing1.type = nothing2.type = CX_JSON_NOTHING; a[0] = cxJsonCreateLiteral(NULL, CX_JSON_NULL); a[1] = cxJsonCreateLiteral(NULL, CX_JSON_TRUE); a[2] = cxJsonCreateLiteral(NULL, CX_JSON_FALSE); @@ -1344,15 +1346,16 @@ a[4] = cxJsonCreateInteger(NULL, 5432); a[5] = cxJsonCreateInteger(NULL, -10); a[6] = cxJsonCreateInteger(NULL, 0); - a[7] = cxJsonCreateNumber(NULL, 0.0f); - a[8] = cxJsonCreateNumber(NULL, 13.37f); - a[9] = cxJsonCreateNumber(NULL, -123.456f); - a[10] = cxJsonCreateNumber(NULL, 1234.0f); - a[11] = cxJsonCreateNumber(NULL, -10.3f); + a[7] = cxJsonCreateNumber(NULL, 0.0); + a[8] = cxJsonCreateNumber(NULL, 13.37); + a[9] = cxJsonCreateNumber(NULL, -123.456); + a[10] = cxJsonCreateNumber(NULL, 1234.0); + a[11] = cxJsonCreateNumber(NULL, -10.3); a[12] = cxJsonCreateString(NULL, "hello"); a[13] = cxJsonCreateString(NULL, "world"); + a[14] = ¬hing1; - CxJsonValue *b[14]; + CxJsonValue *b[15]; b[0] = cxJsonCreateLiteral(NULL, CX_JSON_NULL); b[1] = cxJsonCreateLiteral(NULL, CX_JSON_TRUE); b[2] = cxJsonCreateLiteral(NULL, CX_JSON_FALSE); @@ -1360,28 +1363,24 @@ b[4] = cxJsonCreateInteger(NULL, 5432); b[5] = cxJsonCreateInteger(NULL, -10); b[6] = cxJsonCreateInteger(NULL, 0); - b[7] = cxJsonCreateNumber(NULL, 0.0f); - b[8] = cxJsonCreateNumber(NULL, 13.37f); - b[9] = cxJsonCreateNumber(NULL, -123.456f); - b[10] = cxJsonCreateNumber(NULL, 1234.0f); - b[11] = cxJsonCreateNumber(NULL, -10.3f); + b[7] = cxJsonCreateNumber(NULL, 0.0); + b[8] = cxJsonCreateNumber(NULL, 13.37); + b[9] = cxJsonCreateNumber(NULL, -123.456); + b[10] = cxJsonCreateNumber(NULL, 1234.0); + b[11] = cxJsonCreateNumber(NULL, -10.3); b[12] = cxJsonCreateString(NULL, "hello"); b[13] = cxJsonCreateString(NULL, "world"); + b[14] = ¬hing2; CX_TEST_DO { - for(int i=0;i<12;i++) { - for(int j=0;j<12;j++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { + for (unsigned j = 0; j < cx_nmemb(b); j++) { int ret = cxJsonCompare(a[i], b[j]); if(i == j) { CX_TEST_ASSERT(ret == 0); } else { if(cxJsonIsNumber(a[i]) && cxJsonIsNumber(b[j])) { - double diff = fabs(cxJsonAsDouble(a[i]) - cxJsonAsDouble(b[j])); - if(diff < 0.001) { - CX_TEST_ASSERT(ret == 0); - } else { - CX_TEST_ASSERT(ret != 0); - } + CX_TEST_ASSERT(ret == cx_vcmp_double(cxJsonAsDouble(a[i]), cxJsonAsDouble(b[j]))); } else { CX_TEST_ASSERT(ret != 0); } @@ -1390,8 +1389,10 @@ } } - for(int i=0;i<14;i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { cxJsonValueFree(a[i]); + } + for (unsigned i = 0; i < cx_nmemb(b); i++) { cxJsonValueFree(b[i]); } } @@ -1510,17 +1511,17 @@ CxJsonValue *a[6]; CxJsonValue *b[6]; - for(int i=0;i<6;i++) { + for (unsigned i = 0; i < 6; i++) { cxJsonFromString(NULL, str[i], &a[i]); cxJsonFromString(NULL, str[i], &b[i]); } CX_TEST_DO { - for(int i=0;i<6;i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { // make sure the test values are arrays CX_TEST_ASSERT(cxJsonIsArray(a[i])); - - for(int j=0;j<6;j++) { + + for (unsigned j = 0; j < cx_nmemb(b); j++) { int ret = cxJsonCompare(a[i], b[j]); CX_TEST_ASSERT(i == j ? ret == 0 : ret != 0); } @@ -1564,8 +1565,10 @@ cxJsonValueFree(value2); } - for(int i=0;i<6;i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { cxJsonValueFree(a[i]); + } + for (unsigned i = 0; i < cx_nmemb(b); i++) { cxJsonValueFree(b[i]); } } @@ -1592,7 +1595,7 @@ CX_TEST_ASSERT(n != NULL); CX_TEST_ASSERT(n->type == CX_JSON_NOTHING); - for(int i=0;i<14;i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { // make sure the test setup is not broken CX_TEST_ASSERT(a[i]->type != CX_JSON_NOTHING); @@ -1621,7 +1624,7 @@ cxJsonValueFree(nan2); } - for(int i=0;i<14;i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { cxJsonValueFree(a[i]); } } @@ -1660,7 +1663,7 @@ a[9] = cxJsonCreateObj(NULL); // fill the very large object (a[9]) - for(int i=0;i<TEST_CLONE_OBJECTS_LARGE_OBJ;i++) { + for (unsigned i = 0; i < TEST_CLONE_OBJECTS_LARGE_OBJ; i++) { char buf[32]; snprintf(buf, 32, "int%d", i); cxJsonObjPutInteger(a[9], buf, i); @@ -1668,7 +1671,7 @@ CxJsonValue *arr = cxJsonCreateArr(NULL, TEST_CLONE_OBJECTS_LARGE_ARR); int64_t *ints = calloc(TEST_CLONE_OBJECTS_LARGE_ARR, sizeof(int64_t)); - for(int n=0;n<TEST_CLONE_OBJECTS_LARGE_ARR;n++) { + for (unsigned n = 0; n < TEST_CLONE_OBJECTS_LARGE_ARR; n++) { ints[i] = n; } cxJsonArrAddIntegers(arr, ints, TEST_CLONE_OBJECTS_LARGE_ARR); @@ -1677,7 +1680,7 @@ } CX_TEST_DO { - for(unsigned i=0;i<cx_nmemb(a);i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { CX_TEST_ASSERT(cxJsonIsObject(a[i])); CxJsonValue *b = cxJsonClone(a[i], NULL); @@ -1696,7 +1699,7 @@ } } - for(int i=0;i<10;i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { cxJsonValueFree(a[i]); } } @@ -1711,7 +1714,7 @@ cxJsonFromString(NULL, "[ { \"array\": [ 1,2,3 ]} ]", &a[5]); CX_TEST_DO { - for(unsigned i=0;i<cx_nmemb(a);i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { CX_TEST_ASSERT(cxJsonIsArray(a[i])); CxJsonValue *b = cxJsonClone(a[i], NULL); @@ -1729,7 +1732,7 @@ } } - for(int i=0;i<6;i++) { + for (unsigned i = 0; i < cx_nmemb(a); i++) { cxJsonValueFree(a[i]); } }
--- a/tests/test_tree.c Wed Dec 31 14:15:17 2025 +0100 +++ b/tests/test_tree.c Wed Dec 31 14:58:52 2025 +0100 @@ -443,6 +443,14 @@ int r; tree_node *n; CX_TEST_DO { + // special case: search an empty tree + n = (void*)0x1337; + r = cx_tree_search(NULL, 0, &s, test_tree_search_function, + (void **) &n, tree_children(tree_node)); + CX_TEST_ASSERT(r < 0); + CX_TEST_ASSERT(n == NULL); + + // search for the test data (exact matches) for (unsigned i = 0 ; i <= 10 ; i++) { s = testdata[i]; r = cx_tree_search(&root, 0, &s, test_tree_search_function, @@ -1049,6 +1057,26 @@ } } +CX_TEST(test_tree_visitor_create_for_empty_tree) { + CX_TEST_DO { + CxTreeIterator iter = cx_tree_visitor(NULL, tree_children(tree_node)); + CX_TEST_ASSERT(!iter.visit_on_exit); + CX_TEST_ASSERT(!iter.exiting); + CX_TEST_ASSERT(iter.counter == 0); + CX_TEST_ASSERT(iter.node == NULL); + CX_TEST_ASSERT(!iter.base.allow_remove); + CX_TEST_ASSERT(!iter.base.remove); + CX_TEST_ASSERT(iter.queue_next == NULL); + CX_TEST_ASSERT(iter.queue_last == 0); + CX_TEST_ASSERT(iter.depth == 0); + CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); + CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); + CX_TEST_ASSERT(!cxIteratorValid(iter)); + // disposing this iterator should also be harmless + cxTreeIteratorDispose(&iter); + } +} + CX_TEST(test_tree_visitor_no_children) { tree_node root = {0}; @@ -1373,6 +1401,80 @@ cx_testing_allocator_destroy(&talloc); } +CX_TEST(test_tree_high_create_root) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CX_TEST_DO { + CxTree *tree = cxTreeCreate( + &talloc.base, + sizeof(tree_node_file), + CX_STORE_POINTERS, + NULL, -1, + cx_tree_node_layout(tree_node_file) + ); + + CX_TEST_ASSERT(tree->root == NULL); + // create root without data + tree_node_file *root = cxTreeCreateRoot(tree); + CX_TEST_ASSERT(root != NULL); + CX_TEST_ASSERT(root == tree->root); + // re-create same root (does nothing) + tree_node_file *root2 = cxTreeCreateRoot(tree); + CX_TEST_ASSERT(root2 == root); + + // next test + cxTreeClear(tree); + + // try to create with data, but loc_data is not known + root = cxTreeCreateRootData(tree, "/"); + CX_TEST_ASSERT(root == NULL); + + // set the loc_data + tree->loc_data = offsetof(tree_node_file, path); + root = cxTreeCreateRootData(tree, "/"); + CX_TEST_ASSERT(root != NULL); + CX_TEST_ASSERT(strcmp(root->path, "/") == 0); + + cxTreeFree(tree); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } +} + +CX_TEST(test_tree_high_set_root) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CX_TEST_DO { + CxTree *tree = cxTreeCreate( + &talloc.base, + sizeof(tree_node_file), + CX_STORE_POINTERS, + NULL, -1, + cx_tree_node_layout(tree_node_file) + ); + + CX_TEST_ASSERT(tree->root == NULL); + + tree_node_file *root = cxTreeCreateRoot(tree); + CX_TEST_ASSERT(root != NULL); + CX_TEST_ASSERT(root == tree->root); + + // create a different root externally + tree_node_file *root2 = cxZalloc(&talloc.base, sizeof(tree_node_file)); + + // replace the root + tree_node_file *old = cxTreeSetRoot(tree, root2); + CX_TEST_ASSERT(old == root); + + // free the tree, check that there is memory leaking + cxTreeFree(tree); + CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); + + // free the old root, check that memory is fine + cxFree(&talloc.base, old); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } +} + CX_TEST(test_tree_high_tree_depth) { tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; cx_tree_add(&root, &child1, tree_node_layout); @@ -1618,6 +1720,123 @@ cx_testing_allocator_destroy(&talloc); } +CX_TEST(test_tree_high_add_find_without_loc_data) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + CX_TEST_DO { + CxTree *tree = cxTreeCreate(alloc, + sizeof(tree_node_file), + CX_STORE_POINTERS, + NULL, offsetof(tree_node_file, path), + cx_tree_node_layout(tree_node_file) + ); + cxSetCompareFunc(tree, strcmp); + tree_node_file *root = cxTreeCreateRootData(tree, "/"); + tree_node_file *home = cxTreeAddData(tree, root, "/home/"); + tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/"); + cxTreeAddData(tree, foo, "/home/foo/bar/"); + tree_node_file *usr = cxTreeAddData(tree, root, "/usr/"); + cxTreeAddData(tree, usr, "/usr/lib/"); + + void *found = cxTreeFind(tree, "/home/foo/", true); + CX_TEST_ASSERT(found == foo); + + // now remove the loc_data + tree->loc_data = -1; + found = cxTreeFind(tree, "/home/foo/", true); + CX_TEST_ASSERT(found == NULL); + + CX_TEST_ASSERT(NULL == cxTreeAddData(tree, root, "/usr/local/")); + + cxTreeFree(tree); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +CX_TEST(test_tree_high_find_max_depth) { + CxTree *tree = cxTreeCreate(NULL, + sizeof(tree_node_file), + CX_STORE_POINTERS, + NULL, offsetof(tree_node_file, path), + cx_tree_node_layout(tree_node_file) + ); + cxSetCompareFunc(tree, strcmp); + tree_node_file *root = cxTreeCreateRootData(tree, "/"); + tree_node_file *home = cxTreeAddData(tree, root, "/home/"); + tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/"); + tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/"); + tree_node_file *usr = cxTreeAddData(tree, root, "/usr/"); + cxTreeAddData(tree, usr, "/usr/lib/"); + CX_TEST_DO { + CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 4, true)); + CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 3, true)); + CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 3, true)); + CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 2, true)); + } + cxTreeFree(tree); +} + +CX_TEST(test_tree_high_find_fast) { + CxTree *tree = cxTreeCreate(NULL, + sizeof(tree_node_file), + CX_STORE_POINTERS, + NULL, offsetof(tree_node_file, path), + cx_tree_node_layout(tree_node_file) + ); + cxSetCompareFunc(tree, strcmp); + tree_node_file *root = cxTreeCreateRootData(tree, "/"); + tree_node_file *home = cxTreeAddData(tree, root, "/home/"); + tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/"); + tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/"); + tree_node_file *baz = cxTreeAddData(tree, home, "/home/baz/"); + tree_node_file *usr = cxTreeAddData(tree, root, "/usr/"); + tree_node_file *lib = cxTreeAddData(tree, usr, "/usr/lib/"); + CX_TEST_DO { + // test that loc_data not needed for FindFast! + tree->loc_data = -1; + + // find from root + CX_TEST_ASSERT(root == cxTreeFindFast(tree, "/", + tree_node_file_search_func)); + CX_TEST_ASSERT(home == cxTreeFindFast(tree, "/home/", + tree_node_file_search_func)); + CX_TEST_ASSERT(foo == cxTreeFindFast(tree, "/home/foo/", + tree_node_file_search_func)); + CX_TEST_ASSERT(bar == cxTreeFindFast(tree, "/home/foo/bar/", + tree_node_file_search_func)); + CX_TEST_ASSERT(usr == cxTreeFindFast(tree, "/usr/", + tree_node_file_search_func)); + CX_TEST_ASSERT(lib == cxTreeFindFast(tree, "/usr/lib/", + tree_node_file_search_func)); + + // find from correct subtree + CX_TEST_ASSERT(foo == cxTreeFindFastInSubtree(tree, "/home/foo/", + tree_node_file_search_func, home, 0)); + CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", + tree_node_file_search_func, home, 0)); + CX_TEST_ASSERT(lib == cxTreeFindFastInSubtree(tree, "/usr/lib/", + tree_node_file_search_func, usr, 0)); + + // find in wrong subtree + CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/", + tree_node_file_search_func, usr, 0)); + CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", + tree_node_file_search_func, baz, 0)); + CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/usr/lib/", + tree_node_file_search_func, home, 0)); + + // some tests with max depth + // ------------------------- + CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 4)); + CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 3)); + CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 3)); + CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 2)); + } + cxTreeFree(tree); +} + CX_TEST(test_tree_high_remove_or_destroy_root) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); @@ -1733,6 +1952,44 @@ cxTreeFree(tree); } +CX_TEST(test_tree_high_iterator_large_depth) { + CxTree *tree = cxTreeCreate(NULL, + sizeof(tree_node), + sizeof(int), + NULL, offsetof(tree_node, data), + tree_node_layout + ); + int c = 0; + tree_node *root = cxTreeCreateRootData(tree, &c); + unsigned depths[6] = {10, 20, 15, 30, 25, 5}; + for (unsigned b = 0 ; b < 3 ; b++) { + c++; + tree_node *branch = cxTreeAddData(tree, root, &c); + tree_node *p = branch; + for (unsigned d = 0; d < depths[b*2+0] ; d++) { + c++; + p = cxTreeAddData(tree, p, &c); + } + p = branch; + for (unsigned d = 0; d < depths[b*2+1] ; d++) { + c++; + p = cxTreeAddData(tree, p, &c); + } + } + CX_TEST_DO { + CX_TEST_ASSERT(cxTreeSize(tree) == 109); + CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root) == 109); + CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children) == 1+depths[0]+depths[1]); + CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next) == 1+depths[2]+depths[3]); + CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next->next) == 1+depths[4]+depths[5]); + CxTreeIterator iter = cxTreeIterate(tree, false); + cx_foreach(tree_node*, n, iter) { + CX_TEST_ASSERT((size_t)n->data == iter.counter - 1); + } + } + cxTreeFree(tree); +} + CX_TEST(test_tree_high_visitor) { CxTree *tree = cxTreeCreate(NULL, sizeof(tree_node_file), @@ -1798,6 +2055,7 @@ cx_test_register(suite, test_tree_iterator_free_nodes); cx_test_register(suite, test_tree_visitor_create_and_dispose); cx_test_register(suite, test_tree_visitor); + cx_test_register(suite, test_tree_visitor_create_for_empty_tree); cx_test_register(suite, test_tree_visitor_no_children); cx_test_register(suite, test_tree_visitor_no_branching); cx_test_register(suite, test_tree_visitor_subtree); @@ -1812,14 +2070,20 @@ CxTestSuite *suite = cx_test_suite_new("tree (high level)"); cx_test_register(suite, test_tree_high_create); + cx_test_register(suite, test_tree_high_create_root); + cx_test_register(suite, test_tree_high_set_root); cx_test_register(suite, test_tree_high_tree_depth); - // cx_test_register(suite, test_tree_high_set_parent); - // cx_test_register(suite, test_tree_high_add_find_remove_nodes); - // cx_test_register(suite, test_tree_high_add_find_destroy_nodes); - // cx_test_register(suite, test_tree_high_remove_or_destroy_root); - // cx_test_register(suite, test_tree_high_simple_destructor); - // cx_test_register(suite, test_tree_high_iterator); - // cx_test_register(suite, test_tree_high_visitor); + cx_test_register(suite, test_tree_high_set_parent); + cx_test_register(suite, test_tree_high_add_find_remove_nodes); + cx_test_register(suite, test_tree_high_add_find_destroy_nodes); + cx_test_register(suite, test_tree_high_add_find_without_loc_data); + cx_test_register(suite, test_tree_high_find_max_depth); + cx_test_register(suite, test_tree_high_find_fast); + cx_test_register(suite, test_tree_high_remove_or_destroy_root); + cx_test_register(suite, test_tree_high_simple_destructor); + cx_test_register(suite, test_tree_high_iterator); + cx_test_register(suite, test_tree_high_iterator_large_depth); + cx_test_register(suite, test_tree_high_visitor); return suite; }
