# HG changeset patch # User Mike Becker # Date 1727962685 -7200 # Node ID 5ed7f634f04620cb57935cc8b204fef7482efc9c # Parent 109567325fe7a8b9a728475e09cea357852e44a2 implement cxTreeCreate family of functions relates to #166 diff -r 109567325fe7 -r 5ed7f634f046 src/cx/tree.h --- a/src/cx/tree.h Wed Oct 02 19:11:40 2024 +0200 +++ b/src/cx/tree.h Thu Oct 03 15:38:05 2024 +0200 @@ -701,14 +701,14 @@ /** * Allocator to allocate new nodes. */ - CxAllocator *allocator; + const CxAllocator *allocator; /** * A pointer to the root node. * * Will be \c NULL when \c size is 0. */ - struct cx_tree_node_base_s *root; + void *root; /** * A function to create new nodes. @@ -872,7 +872,7 @@ * The specified \p allocator will be used for creating the tree struct * and SHALL be used by \p create_func to allocate memory for the nodes. * - * \note This function will also register a simple destructor which + * \note This function will also register an advanced destructor which * will free the nodes with the allocator's free() method. * * @param allocator the allocator that shall be used @@ -907,8 +907,8 @@ * member (or at least respect the default offsets specified in the tree * struct) and they MUST be allocated with the default stdlib allocator. * - * \note This function will also register a simple destructor which - * will free the nodes with the default stdlib allocator. + * \note This function will also register an advanced destructor which + * will free the nodes with the #cxDefaultAllocator. * * @param create_func a function that creates new nodes * @param search_func a function that compares two nodes @@ -1081,6 +1081,16 @@ } /** + * Determines the size of the specified subtree. + * + * @param tree the tree + * @param subtree_root the root node of the subtree + * @return the number of nodes in the specified subtree + */ +__attribute__((__nonnull__)) +size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); + +/** * Creates a depth-first iterator for the specified tree. * * @param tree the tree to iterate diff -r 109567325fe7 -r 5ed7f634f046 src/tree.c --- a/src/tree.c Wed Oct 02 19:11:40 2024 +0200 +++ b/src/tree.c Thu Oct 03 15:38:05 2024 +0200 @@ -666,6 +666,91 @@ loc_prev, loc_next); } +static void cx_tree_default_destructor(CxTree *tree) { + // TODO: destroy the nodes + cxFree(tree->allocator, tree); +} + +static CxTreeIterator cx_tree_default_iterator( + CxTree *tree, + bool visit_on_exit +) { + return cx_tree_iterator( + tree->root, visit_on_exit, + tree->loc_children, tree->loc_next + ); +} + +static CxTreeVisitor cx_tree_default_visitor(CxTree *tree) { + return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next); +} + +static cx_tree_class cx_tree_default_class = { + cx_tree_default_destructor, + NULL, + NULL, + NULL, + cx_tree_default_iterator, + cx_tree_default_visitor +}; + +CxTree *cxTreeCreate( + const CxAllocator *allocator, + cx_tree_node_create_func create_func, + cx_tree_search_func search_func, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); + if (tree == NULL) return NULL; + + tree->cl = &cx_tree_default_class; + tree->allocator = allocator; + tree->node_create = create_func; + tree->search = search_func; + tree->advanced_destructor = (cx_destructor_func2) cxFree; + tree->destructor_data = (void *) allocator; + tree->loc_parent = loc_parent; + tree->loc_children = loc_children; + tree->loc_last_child = loc_last_child; + tree->loc_prev = loc_prev; + tree->loc_next = loc_next; + tree->root = NULL; + tree->size = 0; + + return tree; +} + +CxTree *cxTreeCreateWrapped( + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + CxTree *tree = malloc(sizeof(CxTree)); + if (tree == NULL) return NULL; + + tree->cl = &cx_tree_default_class; + // set the allocator anyway, just in case... + tree->allocator = cxDefaultAllocator; + tree->node_create = NULL; + tree->search = NULL; + tree->advanced_destructor = NULL; + tree->destructor_data = NULL; + tree->loc_parent = loc_parent; + tree->loc_children = loc_children; + tree->loc_last_child = loc_last_child; + tree->loc_prev = loc_prev; + tree->loc_next = loc_next; + tree->root = root; + tree->size = cxTreeSubtreeSize(tree, root); + return tree; +} int cxTreeAddChild( CxTree *tree, @@ -678,3 +763,15 @@ tree->size++; return 0; } + +size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) { + CxTreeVisitor visitor = cx_tree_visitor( + subtree_root, + tree->loc_children, + tree->loc_next + ); + while (cxIteratorValid(visitor)) { + cxIteratorNext(visitor); + } + return visitor.counter; +} diff -r 109567325fe7 -r 5ed7f634f046 tests/test_tree.c --- a/tests/test_tree.c Wed Oct 02 19:11:40 2024 +0200 +++ b/tests/test_tree.c Thu Oct 03 15:38:05 2024 +0200 @@ -54,7 +54,7 @@ const char *path; } tree_node_file; -static void *create_tree_node_file( +static void *tree_node_file_create( const void *dptr, void *allocator) { if (allocator == NULL) allocator = cxDefaultAllocator; @@ -1057,7 +1057,7 @@ result = cx_tree_add( "/home/foo/", tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, (void **) &foo, &root, tree_node_file_layout ); @@ -1068,7 +1068,7 @@ size_t added = cx_tree_add_array( bar_path, 1, sizeof(const char *), tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); @@ -1084,7 +1084,7 @@ result = cx_tree_add( "newroot", tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, (void **) &new_node, &root, tree_node_file_layout ); @@ -1126,7 +1126,7 @@ int result = cx_tree_add( "/usr/lib/", tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, (void **) &node, &root, tree_node_file_layout ); @@ -1151,7 +1151,7 @@ int result = cx_tree_add( "/usr/lib/", tree_node_file_search, - create_tree_node_file, NULL, + tree_node_file_create, NULL, (void **) &node, &root, tree_node_file_layout ); @@ -1164,7 +1164,7 @@ size_t added = cx_tree_add_array( "/", 1, sizeof(const char *), tree_node_file_search, - create_tree_node_file, NULL, + tree_node_file_create, NULL, (void **) &node, &root, tree_node_file_layout ); @@ -1184,7 +1184,7 @@ int result = cx_tree_add( "/", tree_node_file_search, - create_tree_node_file, NULL, + tree_node_file_create, NULL, (void **) &node, &root, tree_node_file_layout ); @@ -1207,7 +1207,7 @@ size_t processed = cx_tree_add_array( (void *) 0xc0ffee, 0, sizeof(void *), tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(failed == NULL); @@ -1219,7 +1219,7 @@ cxIteratorRef(iter), 10, // deliberately specify more than the iter has tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(processed == 0); @@ -1263,7 +1263,7 @@ size_t processed = cx_tree_add_array( paths, 4, sizeof(const char *), tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); @@ -1328,7 +1328,7 @@ size_t processed = cx_tree_add_iter( cxIteratorRef(iter), 3, tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); @@ -1384,7 +1384,7 @@ size_t processed = cx_tree_add_array( paths, 5, sizeof(const char *), tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, (void **) &failed, &root, tree_node_file_layout ); @@ -1428,7 +1428,7 @@ size_t processed = cx_tree_add_array( paths, 10, sizeof(const char *), tree_node_file_search, - create_tree_node_file, alloc, + tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); @@ -1526,6 +1526,88 @@ cx_testing_allocator_destroy(&talloc); } +CX_TEST(test_tree_high_create) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CX_TEST_DO { + CxTree *tree = cxTreeCreate( + &talloc.base, + tree_node_file_create, + 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->search == tree_node_file_search); + CX_TEST_ASSERT(tree->size == 0); + CX_TEST_ASSERT(tree->simple_destructor == NULL); + CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree); + CX_TEST_ASSERT(tree->destructor_data == &talloc.base); + CX_TEST_ASSERT(tree->root == NULL); + CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node_file, parent)); + CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node_file, children)); + CX_TEST_ASSERT(tree->loc_last_child == offsetof(tree_node_file, last_child)); + CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node_file, prev)); + CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node_file, next)); + + CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); + CX_TEST_ASSERT(talloc.alloc_total == 1); + + cxTreeDestroy(tree); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +CX_TEST(test_tree_high_create_simple) { + CX_TEST_DO { + CxTree *tree = cxTreeCreateSimple( + tree_node_file_create, + 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->search == tree_node_file_search); + CX_TEST_ASSERT(tree->size == 0); + CX_TEST_ASSERT(tree->simple_destructor == NULL); + CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree); + CX_TEST_ASSERT(tree->destructor_data == cxDefaultAllocator); + CX_TEST_ASSERT(tree->root == NULL); + CX_TEST_ASSERT(tree->loc_parent == offsetof(struct cx_tree_node_base_s, parent)); + CX_TEST_ASSERT(tree->loc_children == offsetof(struct cx_tree_node_base_s, children)); + CX_TEST_ASSERT(tree->loc_last_child == offsetof(struct cx_tree_node_base_s, last_child)); + CX_TEST_ASSERT(tree->loc_prev == offsetof(struct cx_tree_node_base_s, prev)); + CX_TEST_ASSERT(tree->loc_next == offsetof(struct cx_tree_node_base_s, next)); + cxTreeDestroy(tree); + } +} + +CX_TEST(test_tree_high_create_wrapped) { + tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; + cx_tree_link(&root, &child1, tree_node_layout); + cx_tree_link(&root, &child2, tree_node_layout); + cx_tree_link(&child1, &child3, tree_node_layout); + CX_TEST_DO { + CxTree *tree = cxTreeCreateWrapped(&root, tree_node_layout); + CX_TEST_ASSERT(tree->cl != NULL); + CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator); + CX_TEST_ASSERT(tree->node_create == NULL); + CX_TEST_ASSERT(tree->search == NULL); + CX_TEST_ASSERT(tree->root == &root); + CX_TEST_ASSERT(tree->size == 4); + CX_TEST_ASSERT(tree->simple_destructor == NULL); + CX_TEST_ASSERT(tree->advanced_destructor == NULL); + CX_TEST_ASSERT(tree->destructor_data == NULL); + CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node, parent)); + CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node, children)); + CX_TEST_ASSERT(tree->loc_last_child == -1); + CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node, prev)); + CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next)); + cxTreeDestroy(tree); + } +} CxTestSuite *cx_test_suite_tree_low_level(void) { CxTestSuite *suite = cx_test_suite_new("tree (low level)"); @@ -1562,3 +1644,13 @@ return suite; } + +CxTestSuite *cx_test_suite_tree_high_level(void) { + 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_simple); + cx_test_register(suite, test_tree_high_create_wrapped); + + return suite; +} diff -r 109567325fe7 -r 5ed7f634f046 tests/ucxtest.c --- a/tests/ucxtest.c Wed Oct 02 19:11:40 2024 +0200 +++ b/tests/ucxtest.c Thu Oct 03 15:38:05 2024 +0200 @@ -40,11 +40,10 @@ CxTestSuite *cx_test_suite_empty_list(void); CxTestSuite *cx_test_suite_array_list(void); CxTestSuite *cx_test_suite_linked_list(void); - CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void); - CxTestSuite *cx_test_suite_linked_list_defaulted_funcs(void); CxTestSuite *cx_test_suite_tree_low_level(void); +CxTestSuite *cx_test_suite_tree_high_level(void); CxTestSuite *cx_test_suite_mempool(void); CxTestSuite *cx_test_suite_hash_map(void); @@ -72,6 +71,7 @@ cx_test_suite_array_list_defaulted_funcs(), cx_test_suite_linked_list_defaulted_funcs(), cx_test_suite_tree_low_level(), + cx_test_suite_tree_high_level(), cx_test_suite_mempool(), cx_test_suite_hash_map() );