# HG changeset patch # User Mike Becker # Date 1632660351 -7200 # Node ID ec92b4ed23aaa7fcfb3c98bf750041c16fa05066 # Parent 4cea6e50175b3536f32263543b10259210958199# Parent 9aa38cd4c992f456099d80edbe960cd397cbf393 Automated merge diff -r 4cea6e50175b -r ec92b4ed23aa src/CMakeLists.txt --- a/src/CMakeLists.txt Sun Sep 26 14:45:42 2021 +0200 +++ b/src/CMakeLists.txt Sun Sep 26 14:45:51 2021 +0200 @@ -2,6 +2,7 @@ allocator.c list.c linked_list.c + tree.c ) set(headers cx/allocator.h diff -r 4cea6e50175b -r ec92b4ed23aa src/cx/tree.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/cx/tree.h Sun Sep 26 14:45:51 2021 +0200 @@ -0,0 +1,59 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef UCX_TREE_H +#define UCX_TREE_H + +#include +#include +#include "allocator.h" + +#ifdef __cplusplus +extern "C" { +#endif + +void* cx_tree_last(void *node, ptrdiff_t loc_next); + +int cx_tree_add_node(void *node, ptrdiff_t loc_parent, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); + +int cx_tree_add_child_node( + void *parent, + ptrdiff_t loc_parent, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void **children_begin, + void **children_end, + void *new_node); + + +#ifdef __cplusplus +} +#endif + +#endif /* UCX_TREE_H */ + diff -r 4cea6e50175b -r ec92b4ed23aa src/tree.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/tree.c Sun Sep 26 14:45:51 2021 +0200 @@ -0,0 +1,70 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/tree.h" + +#define CX_TR_PTR(cur, off) ((void**)(((char*)cur)+off)) + +void* cx_tree_last(void *node, ptrdiff_t loc_next) { + void *last; + do { + last = node; + } while ((node = *CX_TR_PTR(node, loc_next)) != NULL); + return last; +} + +int cx_tree_add_node(void *node, ptrdiff_t loc_parent, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { + void *last = cx_tree_last(node, loc_next); + if(!last) + return 1; + + // next pointer must be present + *CX_TR_PTR(last, loc_next) = new_node; + + // optional fields + if(loc_parent >= 0) { + *CX_TR_PTR(new_node, loc_parent) = *CX_TR_PTR(node, loc_parent); + } + if(loc_prev >= 0) { + *CX_TR_PTR(new_node, loc_prev) = last; + } + + return 0; +} + +int cx_tree_add_child_node( + void *parent, + ptrdiff_t loc_parent, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void **children_begin, + void **children_end, + void *new_node) +{ + return 1; +} diff -r 4cea6e50175b -r ec92b4ed23aa test/CMakeLists.txt --- a/test/CMakeLists.txt Sun Sep 26 14:45:42 2021 +0200 +++ b/test/CMakeLists.txt Sun Sep 26 14:45:51 2021 +0200 @@ -10,6 +10,7 @@ set(TESTS test_allocator test_list + test_tree ) foreach(test ${TESTS}) diff -r 4cea6e50175b -r ec92b4ed23aa test/test_tree.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/test_tree.c Sun Sep 26 14:45:51 2021 +0200 @@ -0,0 +1,114 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/tree.h" +#include "test_config.h" + +#include + +typedef struct TestNode TestNode; + +struct TestNode { + TestNode *parent; + TestNode *prev; + TestNode *next; + + TestNode *children_begin; + TestNode *children_end; + + int content; +}; + +void test_cx_tree_add_node() { + // prepare test tree + TestNode root; + memset(&root, 0, sizeof(TestNode)); + + TestNode a; + memset(&a, 0, sizeof(TestNode)); + root.children_begin = &a; + root.children_end = &a; + a.parent = &root; + a.content = 1; + + // new test nodes + TestNode b; + memset(&b, 0, sizeof(TestNode)); + TestNode c; + memset(&c, 0, sizeof(TestNode)); + + // test + b.content = 2; + int ret = cx_tree_add_node(&a, offsetof(TestNode, parent), offsetof(TestNode, prev), offsetof(TestNode, next), &b); + CU_ASSERT_EQUAL(ret, 0); + CU_ASSERT_PTR_EQUAL(b.parent, &root); + CU_ASSERT_PTR_EQUAL(b.prev, &a); + CU_ASSERT_PTR_EQUAL(b.next, NULL); + CU_ASSERT_PTR_EQUAL(a.next, &b); + + c.content = 3; + ret = cx_tree_add_node(&a, -1, -1, offsetof(TestNode, next), &c); + CU_ASSERT_EQUAL(ret, 0); + CU_ASSERT_PTR_EQUAL(c.parent, NULL); + CU_ASSERT_PTR_EQUAL(c.prev, NULL); + CU_ASSERT_PTR_EQUAL(c.next, NULL); + CU_ASSERT_PTR_EQUAL(b.next, &c); +} + +int main() { + CU_pSuite suite = NULL; + + if (CUE_SUCCESS != CU_initialize_registry()) { + return CU_get_error(); + } + + suite = CU_add_suite("tree suite", NULL, NULL); + if (NULL == suite) { + CU_cleanup_registry(); + return CU_get_error(); + } + + if ( + !CU_add_test(suite, "ll add tree node", test_cx_tree_add_node) + ) { + CU_cleanup_registry(); + return CU_get_error(); + } + + + CU_basic_set_mode(UCX_CU_BRM); + + int exitcode; + if (CU_basic_run_tests()) { + exitcode = CU_get_error(); + } else { + exitcode = CU_get_number_of_failures() == 0 ? 0 : 1; + } + CU_cleanup_registry(); + return exitcode; +}