changeset
Automated merge
Sun, 26 Sep 2021 14:45:51 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sun, 26 Sep 2021 14:45:51 +0200
- changeset 427
- ec92b4ed23aa
- parent 423
- 4cea6e50175b (current diff)
- parent 426
- 9aa38cd4c992 (diff)
- child 428
- da66264af8ad
Automated merge
| test/CMakeLists.txt | file | annotate | diff | comparison | revisions |
1.1 --- a/src/CMakeLists.txt Sun Sep 26 14:45:42 2021 +0200 1.2 +++ b/src/CMakeLists.txt Sun Sep 26 14:45:51 2021 +0200 1.3 @@ -2,6 +2,7 @@ 1.4 allocator.c 1.5 list.c 1.6 linked_list.c 1.7 + tree.c 1.8 ) 1.9 set(headers 1.10 cx/allocator.h
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/src/cx/tree.h Sun Sep 26 14:45:51 2021 +0200 2.3 @@ -0,0 +1,59 @@ 2.4 +/* 2.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2.6 + * 2.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. 2.8 + * 2.9 + * Redistribution and use in source and binary forms, with or without 2.10 + * modification, are permitted provided that the following conditions are met: 2.11 + * 2.12 + * 1. Redistributions of source code must retain the above copyright 2.13 + * notice, this list of conditions and the following disclaimer. 2.14 + * 2.15 + * 2. Redistributions in binary form must reproduce the above copyright 2.16 + * notice, this list of conditions and the following disclaimer in the 2.17 + * documentation and/or other materials provided with the distribution. 2.18 + * 2.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 2.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 2.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 2.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 2.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 2.29 + * POSSIBILITY OF SUCH DAMAGE. 2.30 + */ 2.31 + 2.32 +#ifndef UCX_TREE_H 2.33 +#define UCX_TREE_H 2.34 + 2.35 +#include <stddef.h> 2.36 +#include <stdlib.h> 2.37 +#include "allocator.h" 2.38 + 2.39 +#ifdef __cplusplus 2.40 +extern "C" { 2.41 +#endif 2.42 + 2.43 +void* cx_tree_last(void *node, ptrdiff_t loc_next); 2.44 + 2.45 +int cx_tree_add_node(void *node, ptrdiff_t loc_parent, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); 2.46 + 2.47 +int cx_tree_add_child_node( 2.48 + void *parent, 2.49 + ptrdiff_t loc_parent, 2.50 + ptrdiff_t loc_prev, 2.51 + ptrdiff_t loc_next, 2.52 + void **children_begin, 2.53 + void **children_end, 2.54 + void *new_node); 2.55 + 2.56 + 2.57 +#ifdef __cplusplus 2.58 +} 2.59 +#endif 2.60 + 2.61 +#endif /* UCX_TREE_H */ 2.62 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/src/tree.c Sun Sep 26 14:45:51 2021 +0200 3.3 @@ -0,0 +1,70 @@ 3.4 +/* 3.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 3.6 + * 3.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. 3.8 + * 3.9 + * Redistribution and use in source and binary forms, with or without 3.10 + * modification, are permitted provided that the following conditions are met: 3.11 + * 3.12 + * 1. Redistributions of source code must retain the above copyright 3.13 + * notice, this list of conditions and the following disclaimer. 3.14 + * 3.15 + * 2. Redistributions in binary form must reproduce the above copyright 3.16 + * notice, this list of conditions and the following disclaimer in the 3.17 + * documentation and/or other materials provided with the distribution. 3.18 + * 3.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 3.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 3.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 3.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 3.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 3.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 3.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 3.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 3.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 3.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 3.29 + * POSSIBILITY OF SUCH DAMAGE. 3.30 + */ 3.31 + 3.32 +#include "cx/tree.h" 3.33 + 3.34 +#define CX_TR_PTR(cur, off) ((void**)(((char*)cur)+off)) 3.35 + 3.36 +void* cx_tree_last(void *node, ptrdiff_t loc_next) { 3.37 + void *last; 3.38 + do { 3.39 + last = node; 3.40 + } while ((node = *CX_TR_PTR(node, loc_next)) != NULL); 3.41 + return last; 3.42 +} 3.43 + 3.44 +int cx_tree_add_node(void *node, ptrdiff_t loc_parent, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { 3.45 + void *last = cx_tree_last(node, loc_next); 3.46 + if(!last) 3.47 + return 1; 3.48 + 3.49 + // next pointer must be present 3.50 + *CX_TR_PTR(last, loc_next) = new_node; 3.51 + 3.52 + // optional fields 3.53 + if(loc_parent >= 0) { 3.54 + *CX_TR_PTR(new_node, loc_parent) = *CX_TR_PTR(node, loc_parent); 3.55 + } 3.56 + if(loc_prev >= 0) { 3.57 + *CX_TR_PTR(new_node, loc_prev) = last; 3.58 + } 3.59 + 3.60 + return 0; 3.61 +} 3.62 + 3.63 +int cx_tree_add_child_node( 3.64 + void *parent, 3.65 + ptrdiff_t loc_parent, 3.66 + ptrdiff_t loc_prev, 3.67 + ptrdiff_t loc_next, 3.68 + void **children_begin, 3.69 + void **children_end, 3.70 + void *new_node) 3.71 +{ 3.72 + return 1; 3.73 +}
4.1 --- a/test/CMakeLists.txt Sun Sep 26 14:45:42 2021 +0200 4.2 +++ b/test/CMakeLists.txt Sun Sep 26 14:45:51 2021 +0200 4.3 @@ -10,6 +10,7 @@ 4.4 set(TESTS 4.5 test_allocator 4.6 test_list 4.7 + test_tree 4.8 ) 4.9 4.10 foreach(test ${TESTS})
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 5.2 +++ b/test/test_tree.c Sun Sep 26 14:45:51 2021 +0200 5.3 @@ -0,0 +1,114 @@ 5.4 +/* 5.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 5.6 + * 5.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. 5.8 + * 5.9 + * Redistribution and use in source and binary forms, with or without 5.10 + * modification, are permitted provided that the following conditions are met: 5.11 + * 5.12 + * 1. Redistributions of source code must retain the above copyright 5.13 + * notice, this list of conditions and the following disclaimer. 5.14 + * 5.15 + * 2. Redistributions in binary form must reproduce the above copyright 5.16 + * notice, this list of conditions and the following disclaimer in the 5.17 + * documentation and/or other materials provided with the distribution. 5.18 + * 5.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 5.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 5.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 5.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 5.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 5.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 5.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 5.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 5.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 5.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 5.29 + * POSSIBILITY OF SUCH DAMAGE. 5.30 + */ 5.31 + 5.32 +#include "cx/tree.h" 5.33 +#include "test_config.h" 5.34 + 5.35 +#include <stddef.h> 5.36 + 5.37 +typedef struct TestNode TestNode; 5.38 + 5.39 +struct TestNode { 5.40 + TestNode *parent; 5.41 + TestNode *prev; 5.42 + TestNode *next; 5.43 + 5.44 + TestNode *children_begin; 5.45 + TestNode *children_end; 5.46 + 5.47 + int content; 5.48 +}; 5.49 + 5.50 +void test_cx_tree_add_node() { 5.51 + // prepare test tree 5.52 + TestNode root; 5.53 + memset(&root, 0, sizeof(TestNode)); 5.54 + 5.55 + TestNode a; 5.56 + memset(&a, 0, sizeof(TestNode)); 5.57 + root.children_begin = &a; 5.58 + root.children_end = &a; 5.59 + a.parent = &root; 5.60 + a.content = 1; 5.61 + 5.62 + // new test nodes 5.63 + TestNode b; 5.64 + memset(&b, 0, sizeof(TestNode)); 5.65 + TestNode c; 5.66 + memset(&c, 0, sizeof(TestNode)); 5.67 + 5.68 + // test 5.69 + b.content = 2; 5.70 + int ret = cx_tree_add_node(&a, offsetof(TestNode, parent), offsetof(TestNode, prev), offsetof(TestNode, next), &b); 5.71 + CU_ASSERT_EQUAL(ret, 0); 5.72 + CU_ASSERT_PTR_EQUAL(b.parent, &root); 5.73 + CU_ASSERT_PTR_EQUAL(b.prev, &a); 5.74 + CU_ASSERT_PTR_EQUAL(b.next, NULL); 5.75 + CU_ASSERT_PTR_EQUAL(a.next, &b); 5.76 + 5.77 + c.content = 3; 5.78 + ret = cx_tree_add_node(&a, -1, -1, offsetof(TestNode, next), &c); 5.79 + CU_ASSERT_EQUAL(ret, 0); 5.80 + CU_ASSERT_PTR_EQUAL(c.parent, NULL); 5.81 + CU_ASSERT_PTR_EQUAL(c.prev, NULL); 5.82 + CU_ASSERT_PTR_EQUAL(c.next, NULL); 5.83 + CU_ASSERT_PTR_EQUAL(b.next, &c); 5.84 +} 5.85 + 5.86 +int main() { 5.87 + CU_pSuite suite = NULL; 5.88 + 5.89 + if (CUE_SUCCESS != CU_initialize_registry()) { 5.90 + return CU_get_error(); 5.91 + } 5.92 + 5.93 + suite = CU_add_suite("tree suite", NULL, NULL); 5.94 + if (NULL == suite) { 5.95 + CU_cleanup_registry(); 5.96 + return CU_get_error(); 5.97 + } 5.98 + 5.99 + if ( 5.100 + !CU_add_test(suite, "ll add tree node", test_cx_tree_add_node) 5.101 + ) { 5.102 + CU_cleanup_registry(); 5.103 + return CU_get_error(); 5.104 + } 5.105 + 5.106 + 5.107 + CU_basic_set_mode(UCX_CU_BRM); 5.108 + 5.109 + int exitcode; 5.110 + if (CU_basic_run_tests()) { 5.111 + exitcode = CU_get_error(); 5.112 + } else { 5.113 + exitcode = CU_get_number_of_failures() == 0 ? 0 : 1; 5.114 + } 5.115 + CU_cleanup_registry(); 5.116 + return exitcode; 5.117 +}
