# HG changeset patch # User Mike Becker # Date 1727965869 -7200 # Node ID cdc49211d87fc5e0e12d7c623cf95a8f7c201584 # Parent a018f5916d3baf2fbcb19e9bc52e8efd70c1c318 implement cxTreeInsert family of functions relates to #166 diff -r a018f5916d3b -r cdc49211d87f src/cx/tree.h --- a/src/cx/tree.h Thu Oct 03 15:42:35 2024 +0200 +++ b/src/cx/tree.h Thu Oct 03 16:31:09 2024 +0200 @@ -905,11 +905,12 @@ * * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first * member (or at least respect the default offsets specified in the tree - * struct) and they MUST be allocated with the default stdlib allocator. + * struct) and they MUST be allocated with the specified allocator. * * \note This function will also register an advanced destructor which - * will free the nodes with the #cxDefaultAllocator. + * will free the nodes with the allocator's free() method. * + * @param allocator the allocator that shall be used * @param create_func a function that creates new nodes * @param search_func a function that compares two nodes * @return the new tree @@ -917,11 +918,16 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline CxTree *cxTreeCreateSimple( + const CxAllocator *allocator, cx_tree_node_create_func create_func, cx_tree_search_func search_func ) { - return cxTreeCreate(cxDefaultAllocator, - create_func, search_func, cx_tree_node_base_layout); + return cxTreeCreate( + allocator, + create_func, + search_func, + cx_tree_node_base_layout + ); } /** @@ -960,9 +966,8 @@ * * \attention This function will only invoke the destructor functions * on the nodes, if specified. - * It will NOT automatically free the nodes with the allocator, because that - * will cause a double-free in scenarios where this tree structure is wrapping - * a tree which memory is managed by someone else. + * It will NOT additionally free the nodes with the tree's allocator, because + * that would cause a double-free in most scenarios. * * @param tree the tree to destroy */ @@ -1034,7 +1039,7 @@ if (n == 0) return 0; if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0; CxIterator iter = cxIterator(data, elem_size, n); - return tree->cl->insert_many(tree, cxIteratorRef(iter), n); + return cxTreeInsertIter(tree, cxIteratorRef(iter), n); } /** diff -r a018f5916d3b -r cdc49211d87f src/tree.c --- a/src/tree.c Thu Oct 03 15:42:35 2024 +0200 +++ b/src/tree.c Thu Oct 03 16:31:09 2024 +0200 @@ -667,7 +667,19 @@ } static void cx_tree_default_destructor(CxTree *tree) { - // TODO: destroy the nodes + if (tree->simple_destructor != NULL || tree->advanced_destructor != NULL) { + CxTreeIterator iter = tree->cl->iterator(tree, true); + cx_foreach(void *, node, iter) { + if (iter.exiting) { + if (tree->simple_destructor) { + tree->simple_destructor(node); + } + if (tree->advanced_destructor) { + tree->advanced_destructor(tree->destructor_data, node); + } + } + } + } cxFree(tree->allocator, tree); } @@ -685,10 +697,60 @@ return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next); } +static int cx_tree_default_insert_element( + CxTree *tree, + const void *data +) { + void *node; + if (tree->root == NULL) { + node = tree->node_create(data, tree); + if (node == NULL) return 1; + cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); + tree->root = node; + tree->size = 1; + return 0; + } + int result = cx_tree_add(data, tree->search, tree->node_create, + tree, &node, tree->root, cx_tree_node_layout(tree)); + if (0 == result) { + tree->size++; + } else { + cxFree(tree->allocator, node); + } + return result; +} + +static size_t cx_tree_default_insert_many( + CxTree *tree, + struct cx_iterator_base_s *iter, + size_t n +) { + size_t ins = 0; + if (!iter->valid(iter)) return 0; + if (tree->root == NULL) { + // use the first element from the iter to create the root node + void **eptr = iter->current(iter); + void *node = tree->node_create(*eptr, tree); + if (node == NULL) return 0; + cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); + tree->root = node; + ins = 1; + iter->next(iter); + } + void *failed; + ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create, + tree, &failed, tree->root, cx_tree_node_layout(tree)); + tree->size += ins; + if (ins < n) { + cxFree(tree->allocator, failed); + } + return ins; +} + static cx_tree_class cx_tree_default_class = { cx_tree_default_destructor, - NULL, - NULL, + cx_tree_default_insert_element, + cx_tree_default_insert_many, NULL, cx_tree_default_iterator, cx_tree_default_visitor diff -r a018f5916d3b -r cdc49211d87f tests/test_tree.c --- a/tests/test_tree.c Thu Oct 03 15:42:35 2024 +0200 +++ b/tests/test_tree.c Thu Oct 03 16:31:09 2024 +0200 @@ -72,6 +72,12 @@ return node; } +static void *tree_node_file_create_hl( + const void *dptr, + void *tree) { + return tree_node_file_create(dptr, (void*)((CxTree*)tree)->allocator); +} + static int tree_node_file_search(const void *l, const void *r) { const tree_node_file *left = l; const tree_node_file *right = r; @@ -1532,13 +1538,13 @@ CX_TEST_DO { CxTree *tree = cxTreeCreate( &talloc.base, - tree_node_file_create, + tree_node_file_create_hl, tree_node_file_search, tree_node_file_layout ); CX_TEST_ASSERT(tree->cl != NULL); CX_TEST_ASSERT(tree->allocator == &talloc.base); - CX_TEST_ASSERT(tree->node_create == tree_node_file_create); + CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); CX_TEST_ASSERT(tree->search == tree_node_file_search); CX_TEST_ASSERT(tree->size == 0); CX_TEST_ASSERT(tree->simple_destructor == NULL); @@ -1563,12 +1569,13 @@ CX_TEST(test_tree_high_create_simple) { CX_TEST_DO { CxTree *tree = cxTreeCreateSimple( - tree_node_file_create, + cxDefaultAllocator, + tree_node_file_create_hl, tree_node_file_search ); CX_TEST_ASSERT(tree->cl != NULL); CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator); - CX_TEST_ASSERT(tree->node_create == tree_node_file_create); + CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); CX_TEST_ASSERT(tree->search == tree_node_file_search); CX_TEST_ASSERT(tree->size == 0); CX_TEST_ASSERT(tree->simple_destructor == NULL); @@ -1624,6 +1631,70 @@ cxTreeDestroy(tree); } +CX_TEST(test_tree_high_insert_one) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + + CX_TEST_DO { + CxTree *tree = cxTreeCreate( + alloc, tree_node_file_create_hl, tree_node_file_search, + tree_node_file_layout + ); + + int result = 0; + result |= cxTreeInsert(tree, "/"); + result |= cxTreeInsert(tree, "/usr/"); + result |= cxTreeInsert(tree, "/home/"); + result |= cxTreeInsert(tree, "/usr/lib/"); + result |= cxTreeInsert(tree, "/home/foo/"); + CX_TEST_ASSERT(result == 0); + CX_TEST_ASSERT(1 == cxTreeInsertArray(tree, "/home/foo/bar/", sizeof(const char*), 1)); + CX_TEST_ASSERT(tree->size == 6); + CX_TEST_ASSERT(0 != cxTreeInsert(tree, "newroot")); + CX_TEST_ASSERT(tree->size == 6); + + CX_TEST_ASSERT(talloc.alloc_total == 8); + CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added + + cxTreeDestroy(tree); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +CX_TEST(test_tree_high_insert_many) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *alloc = &talloc.base; + + CX_TEST_DO { + CxTree *tree = cxTreeCreate( + alloc, tree_node_file_create_hl, tree_node_file_search, + tree_node_file_layout + ); + + const char *paths[] = { + "/", + "/usr/", + "/home/", + "/usr/lib/", + "/home/foo/", + "/home/foo/bar/", + "newroot" + }; + CX_TEST_ASSERT(6 == cxTreeInsertArray(tree, paths, sizeof(const char*), 7)); + CX_TEST_ASSERT(tree->size == 6); + + CX_TEST_ASSERT(talloc.alloc_total == 8); + CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added + + cxTreeDestroy(tree); + 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)"); @@ -1667,6 +1738,8 @@ cx_test_register(suite, test_tree_high_create_simple); cx_test_register(suite, test_tree_high_create_wrapped); cx_test_register(suite, test_tree_high_subtree_depth); + cx_test_register(suite, test_tree_high_insert_one); + cx_test_register(suite, test_tree_high_insert_many); return suite; }