changeset
add first basic low level tree functions
Mon, 22 Jan 2024 19:34:38 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 22 Jan 2024 19:34:38 +0100
- changeset 816
- 425234b05dff
- parent 815
- b0c4750cecd8
- child 817
- 949908c97474
add first basic low level tree functions
relates to #165 tested by issue #167
| src/Makefile | file | annotate | diff | comparison | revisions | |
| src/cx/tree.h | file | annotate | diff | comparison | revisions | |
| src/tree.c | file | annotate | diff | comparison | revisions | |
| tests/Makefile | file | annotate | diff | comparison | revisions | |
| tests/test_tree.c | file | annotate | diff | comparison | revisions | |
| tests/ucxtest.c | file | annotate | diff | comparison | revisions |
1.1 --- a/src/Makefile Sat Jan 20 16:02:04 2024 +0100 1.2 +++ b/src/Makefile Mon Jan 22 19:34:38 2024 +0100 1.3 @@ -24,7 +24,7 @@ 1.4 include ../config.mk 1.5 1.6 SRC = allocator.c array_list.c buffer.c compare.c hash_key.c hash_map.c \ 1.7 - linked_list.c list.c map.c mempool.c printf.c string.c utils.c 1.8 + linked_list.c list.c map.c tree.c mempool.c printf.c string.c utils.c 1.9 1.10 OBJ_EXT=.o 1.11 OBJ=$(SRC:%.c=$(build_dir)/%$(OBJ_EXT)) 1.12 @@ -124,6 +124,10 @@ 1.13 @echo "Compiling $<" 1.14 $(CC) -o $@ $(CFLAGS) -c $< 1.15 1.16 +$(build_dir)/tree$(OBJ_EXT): tree.c cx/tree.h cx/common.h 1.17 + @echo "Compiling $<" 1.18 + $(CC) -o $@ $(CFLAGS) -c $< 1.19 + 1.20 $(build_dir)/utils$(OBJ_EXT): utils.c cx/utils.h cx/common.h 1.21 @echo "Compiling $<" 1.22 $(CC) -o $@ $(CFLAGS) -c $<
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/src/cx/tree.h Mon Jan 22 19:34:38 2024 +0100 2.3 @@ -0,0 +1,69 @@ 2.4 +/* 2.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2.6 + * 2.7 + * Copyright 2024 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 + * \file tree.h 2.33 + * \brief Interface for tree implementations. 2.34 + * \author Mike Becker 2.35 + * \author Olaf Wintermann 2.36 + * \copyright 2-Clause BSD License 2.37 + */ 2.38 + 2.39 +#ifndef UCX_TREE_H 2.40 +#define UCX_TREE_H 2.41 + 2.42 +#include "common.h" 2.43 + 2.44 +#ifdef __cplusplus 2.45 +extern "C" { 2.46 +#endif 2.47 + 2.48 + 2.49 +__attribute__((__nonnull__)) 2.50 +void cx_tree_link( 2.51 + void * restrict parent, 2.52 + void * restrict node, 2.53 + ptrdiff_t loc_parent, 2.54 + ptrdiff_t loc_children, 2.55 + ptrdiff_t loc_prev, 2.56 + ptrdiff_t loc_next 2.57 +); 2.58 + 2.59 +__attribute__((__nonnull__)) 2.60 +void cx_tree_unlink( 2.61 + void *node, 2.62 + ptrdiff_t loc_parent, 2.63 + ptrdiff_t loc_children, 2.64 + ptrdiff_t loc_prev, 2.65 + ptrdiff_t loc_next 2.66 +); 2.67 + 2.68 +#ifdef __cplusplus 2.69 +} // extern "C" 2.70 +#endif 2.71 + 2.72 +#endif //UCX_TREE_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/src/tree.c Mon Jan 22 19:34:38 2024 +0100 3.3 @@ -0,0 +1,87 @@ 3.4 +/* 3.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 3.6 + * 3.7 + * Copyright 2024 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 +#include <assert.h> 3.35 + 3.36 +#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 3.37 +#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 3.38 +#define tree_parent(node) CX_TREE_PTR(node, loc_parent) 3.39 +#define tree_children(node) CX_TREE_PTR(node, loc_children) 3.40 +#define tree_prev(node) CX_TREE_PTR(node, loc_prev) 3.41 +#define tree_next(node) CX_TREE_PTR(node, loc_next) 3.42 + 3.43 +void cx_tree_link( 3.44 + void *restrict parent, 3.45 + void *restrict node, 3.46 + ptrdiff_t loc_parent, 3.47 + ptrdiff_t loc_children, 3.48 + ptrdiff_t loc_prev, 3.49 + ptrdiff_t loc_next 3.50 +) { 3.51 + void *current_parent = tree_parent(node); 3.52 + if (current_parent == parent) return; 3.53 + if (current_parent != NULL) { 3.54 + cx_tree_unlink(node, loc_parent, loc_children, 3.55 + loc_prev, loc_next); 3.56 + } 3.57 + 3.58 + if (tree_children(parent) == NULL) { 3.59 + tree_children(parent) = node; 3.60 + } else { 3.61 + void *children = tree_children(parent); 3.62 + tree_prev(children) = node; 3.63 + tree_next(node) = children; 3.64 + tree_children(parent) = node; 3.65 + } 3.66 + tree_parent(node) = parent; 3.67 +} 3.68 + 3.69 +void cx_tree_unlink( 3.70 + void *node, 3.71 + ptrdiff_t loc_parent, 3.72 + ptrdiff_t loc_children, 3.73 + ptrdiff_t loc_prev, 3.74 + ptrdiff_t loc_next 3.75 +) { 3.76 + if (tree_parent(node) == NULL) return; 3.77 + 3.78 + void *left = tree_prev(node); 3.79 + void *right = tree_next(node); 3.80 + assert(left == NULL || tree_children(tree_parent(node)) != node); 3.81 + if (left == NULL) { 3.82 + tree_children(tree_parent(node)) = right; 3.83 + } else { 3.84 + tree_next(left) = right; 3.85 + } 3.86 + if (right != NULL) tree_prev(right) = left; 3.87 + tree_parent(node) = NULL; 3.88 + tree_prev(node) = NULL; 3.89 + tree_next(node) = NULL; 3.90 +}
4.1 --- a/tests/Makefile Sat Jan 20 16:02:04 2024 +0100 4.2 +++ b/tests/Makefile Mon Jan 22 19:34:38 2024 +0100 4.3 @@ -28,7 +28,7 @@ 4.4 TEST_DIR=$(build_dir)/tests 4.5 4.6 SRC = util_allocator.c test_utils.c test_hash_key.c test_allocator.c \ 4.7 - test_compare.c test_string.c test_buffer.c test_list.c \ 4.8 + test_compare.c test_string.c test_buffer.c test_list.c test_tree.c \ 4.9 test_printf.c test_mempool.c test_hash_map.c ucxtest.c 4.10 4.11 OBJ_EXT=.o 4.12 @@ -79,8 +79,9 @@ 4.13 4.14 $(TEST_DIR)/test_list$(OBJ_EXT): test_list.c ../src/cx/test.h \ 4.15 util_allocator.h ../src/cx/allocator.h ../src/cx/common.h \ 4.16 - ../src/cx/array_list.h ../src/cx/list.h ../src/cx/collection.h \ 4.17 - ../src/cx/allocator.h ../src/cx/iterator.h ../src/cx/linked_list.h 4.18 + ../src/cx/compare.h ../src/cx/utils.h ../src/cx/array_list.h \ 4.19 + ../src/cx/list.h ../src/cx/collection.h ../src/cx/allocator.h \ 4.20 + ../src/cx/iterator.h ../src/cx/linked_list.h 4.21 @echo "Compiling $<" 4.22 $(CC) -o $@ $(CFLAGS) -c $< 4.23 4.24 @@ -103,6 +104,11 @@ 4.25 @echo "Compiling $<" 4.26 $(CC) -o $@ $(CFLAGS) -c $< 4.27 4.28 +$(TEST_DIR)/test_tree$(OBJ_EXT): test_tree.c ../src/cx/tree.h \ 4.29 + ../src/cx/common.h ../src/cx/test.h 4.30 + @echo "Compiling $<" 4.31 + $(CC) -o $@ $(CFLAGS) -c $< 4.32 + 4.33 $(TEST_DIR)/test_utils$(OBJ_EXT): test_utils.c ../src/cx/test.h \ 4.34 ../src/cx/utils.h ../src/cx/common.h ../src/cx/buffer.h \ 4.35 ../src/cx/allocator.h ../src/szmul.c
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 5.2 +++ b/tests/test_tree.c Mon Jan 22 19:34:38 2024 +0100 5.3 @@ -0,0 +1,172 @@ 5.4 +/* 5.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 5.6 + * 5.7 + * Copyright 2023 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 + 5.34 +#include "cx/test.h" 5.35 + 5.36 +typedef struct tree_node { 5.37 + struct tree_node *parent; 5.38 + struct tree_node *next; 5.39 + struct tree_node *prev; 5.40 + struct tree_node *children; 5.41 + int data; 5.42 +} tree_node; 5.43 + 5.44 +#define tree_node_layout \ 5.45 + offsetof(tree_node, parent), offsetof(tree_node, children), \ 5.46 + offsetof(tree_node, prev), offsetof(tree_node, next) 5.47 + 5.48 +CX_TEST(test_tree_link_new_child) { 5.49 + tree_node parent = {0}; 5.50 + tree_node child = {0}; 5.51 + 5.52 + CX_TEST_DO { 5.53 + cx_tree_link(&parent, &child, tree_node_layout); 5.54 + CX_TEST_ASSERT(parent.next == NULL); 5.55 + CX_TEST_ASSERT(parent.prev == NULL); 5.56 + CX_TEST_ASSERT(parent.parent == NULL); 5.57 + CX_TEST_ASSERT(parent.children == &child); 5.58 + CX_TEST_ASSERT(child.parent == &parent); 5.59 + CX_TEST_ASSERT(child.next == NULL); 5.60 + CX_TEST_ASSERT(child.prev == NULL); 5.61 + CX_TEST_ASSERT(child.children == NULL); 5.62 + } 5.63 +} 5.64 + 5.65 +CX_TEST(test_tree_link_add_child) { 5.66 + tree_node parent = {0}; 5.67 + tree_node child1 = {0}; 5.68 + tree_node child2 = {0}; 5.69 + tree_node child3 = {0}; 5.70 + 5.71 + CX_TEST_DO { 5.72 + cx_tree_link(&parent, &child1, tree_node_layout); 5.73 + cx_tree_link(&parent, &child2, tree_node_layout); 5.74 + cx_tree_link(&parent, &child3, tree_node_layout); 5.75 + CX_TEST_ASSERT(parent.next == NULL); 5.76 + CX_TEST_ASSERT(parent.prev == NULL); 5.77 + CX_TEST_ASSERT(parent.parent == NULL); 5.78 + CX_TEST_ASSERT(parent.children == &child3); 5.79 + 5.80 + CX_TEST_ASSERT(child1.parent == &parent); 5.81 + CX_TEST_ASSERT(child2.parent == &parent); 5.82 + CX_TEST_ASSERT(child3.parent == &parent); 5.83 + CX_TEST_ASSERT(child1.children == NULL); 5.84 + CX_TEST_ASSERT(child2.children == NULL); 5.85 + CX_TEST_ASSERT(child3.children == NULL); 5.86 + 5.87 + CX_TEST_ASSERT(child3.prev == NULL); 5.88 + CX_TEST_ASSERT(child3.next == &child2); 5.89 + CX_TEST_ASSERT(child2.prev == &child3); 5.90 + CX_TEST_ASSERT(child2.next == &child1); 5.91 + CX_TEST_ASSERT(child1.prev == &child2); 5.92 + CX_TEST_ASSERT(child1.next == NULL); 5.93 + } 5.94 +} 5.95 + 5.96 +CX_TEST(test_tree_link_move_to_other_parent) { 5.97 + tree_node parent = {0}; 5.98 + tree_node child1 = {0}; 5.99 + tree_node child2 = {0}; 5.100 + tree_node child3 = {0}; 5.101 + cx_tree_link(&parent, &child1, tree_node_layout); 5.102 + cx_tree_link(&parent, &child2, tree_node_layout); 5.103 + cx_tree_link(&parent, &child3, tree_node_layout); 5.104 + 5.105 + CX_TEST_DO { 5.106 + cx_tree_link(&child3, &child2, tree_node_layout); 5.107 + 5.108 + CX_TEST_ASSERT(parent.next == NULL); 5.109 + CX_TEST_ASSERT(parent.prev == NULL); 5.110 + CX_TEST_ASSERT(parent.parent == NULL); 5.111 + CX_TEST_ASSERT(parent.children == &child3); 5.112 + 5.113 + CX_TEST_ASSERT(child1.parent == &parent); 5.114 + CX_TEST_ASSERT(child2.parent == &child3); 5.115 + CX_TEST_ASSERT(child3.parent == &parent); 5.116 + CX_TEST_ASSERT(child1.children == NULL); 5.117 + CX_TEST_ASSERT(child2.children == NULL); 5.118 + CX_TEST_ASSERT(child3.children == &child2); 5.119 + 5.120 + CX_TEST_ASSERT(child3.prev == NULL); 5.121 + CX_TEST_ASSERT(child3.next == &child1); 5.122 + CX_TEST_ASSERT(child1.prev == &child3); 5.123 + CX_TEST_ASSERT(child1.next == NULL); 5.124 + 5.125 + CX_TEST_ASSERT(child2.prev == NULL); 5.126 + CX_TEST_ASSERT(child2.next == NULL); 5.127 + } 5.128 +} 5.129 + 5.130 +CX_TEST(test_tree_unlink) { 5.131 + tree_node parent = {0}; 5.132 + tree_node child1 = {0}; 5.133 + tree_node child2 = {0}; 5.134 + tree_node child3 = {0}; 5.135 + cx_tree_link(&parent, &child1, tree_node_layout); 5.136 + cx_tree_link(&parent, &child3, tree_node_layout); 5.137 + cx_tree_link(&child3, &child2, tree_node_layout); 5.138 + 5.139 + CX_TEST_DO { 5.140 + cx_tree_unlink(&child3, tree_node_layout); 5.141 + 5.142 + CX_TEST_ASSERT(parent.next == NULL); 5.143 + CX_TEST_ASSERT(parent.prev == NULL); 5.144 + CX_TEST_ASSERT(parent.parent == NULL); 5.145 + CX_TEST_ASSERT(parent.children == &child1); 5.146 + 5.147 + CX_TEST_ASSERT(child1.parent == &parent); 5.148 + CX_TEST_ASSERT(child1.children == NULL); 5.149 + CX_TEST_ASSERT(child1.prev == NULL); 5.150 + CX_TEST_ASSERT(child1.next == NULL); 5.151 + 5.152 + // child 3 is unlinked 5.153 + CX_TEST_ASSERT(child3.parent == NULL); 5.154 + CX_TEST_ASSERT(child3.prev == NULL); 5.155 + CX_TEST_ASSERT(child3.next == NULL); 5.156 + 5.157 + // child 2 is still child of the unlinked child 3 5.158 + CX_TEST_ASSERT(child3.children == &child2); 5.159 + CX_TEST_ASSERT(child2.parent == &child3); 5.160 + CX_TEST_ASSERT(child2.children == NULL); 5.161 + CX_TEST_ASSERT(child2.prev == NULL); 5.162 + CX_TEST_ASSERT(child2.next == NULL); 5.163 + } 5.164 +} 5.165 + 5.166 +CxTestSuite *cx_test_suite_tree_low_level(void) { 5.167 + CxTestSuite *suite = cx_test_suite_new("tree (low level)"); 5.168 + 5.169 + cx_test_register(suite, test_tree_link_new_child); 5.170 + cx_test_register(suite, test_tree_link_add_child); 5.171 + cx_test_register(suite, test_tree_link_move_to_other_parent); 5.172 + cx_test_register(suite, test_tree_unlink); 5.173 + 5.174 + return suite; 5.175 +}
6.1 --- a/tests/ucxtest.c Sat Jan 20 16:02:04 2024 +0100 6.2 +++ b/tests/ucxtest.c Mon Jan 22 19:34:38 2024 +0100 6.3 @@ -39,6 +39,7 @@ 6.4 CxTestSuite *cx_test_suite_empty_list(void); 6.5 CxTestSuite *cx_test_suite_array_list(void); 6.6 CxTestSuite *cx_test_suite_linked_list(void); 6.7 +CxTestSuite *cx_test_suite_tree_low_level(void); 6.8 CxTestSuite *cx_test_suite_mempool(void); 6.9 CxTestSuite *cx_test_suite_hash_map(void); 6.10 6.11 @@ -62,6 +63,7 @@ 6.12 cx_test_suite_empty_list(), 6.13 cx_test_suite_array_list(), 6.14 cx_test_suite_linked_list(), 6.15 + cx_test_suite_tree_low_level(), 6.16 cx_test_suite_mempool(), 6.17 cx_test_suite_hash_map() 6.18 );
