Tue, 20 Jun 2023 19:20:51 +0200
remove trees from UCX 3.0
src/CMakeLists.txt | file | annotate | diff | comparison | revisions | |
src/cx/tree.h | file | annotate | diff | comparison | revisions | |
src/tree.c | file | annotate | diff | comparison | revisions | |
tests/CMakeLists.txt | file | annotate | diff | comparison | revisions | |
tests/test_tree.cpp | file | annotate | diff | comparison | revisions |
1.1 --- a/src/CMakeLists.txt Tue Jun 20 19:13:31 2023 +0200 1.2 +++ b/src/CMakeLists.txt Tue Jun 20 19:20:51 2023 +0200 1.3 @@ -5,7 +5,6 @@ 1.4 list.c 1.5 array_list.c 1.6 linked_list.c 1.7 - tree.c 1.8 buffer.c 1.9 map.c 1.10 hash_key.c 1.11 @@ -24,7 +23,6 @@ 1.12 cx/list.h 1.13 cx/array_list.h 1.14 cx/linked_list.h 1.15 - cx/tree.h 1.16 cx/buffer.h 1.17 cx/map.h 1.18 cx/hash_key.h
2.1 --- a/src/cx/tree.h Tue Jun 20 19:13:31 2023 +0200 2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 2.3 @@ -1,136 +0,0 @@ 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 - * \file tree.h 2.33 - * \brief Interface for tree implementations. 2.34 - * \author Olaf Wintermann 2.35 - * \author Mike Becker 2.36 - * \version 3.0 2.37 - * \copyright 2-Clause BSD License 2.38 - */ 2.39 - 2.40 -#ifndef UCX_TREE_H 2.41 -#define UCX_TREE_H 2.42 - 2.43 -#include "common.h" 2.44 -#include "allocator.h" 2.45 - 2.46 -#ifdef __cplusplus 2.47 -extern "C" { 2.48 -#endif 2.49 - 2.50 -/** 2.51 - * Adds a sibling to the current tree node. 2.52 - * 2.53 - * In case your struct does not have a \p prev or a \p parent pointer, 2.54 - * specify a negative location. The location of the \p next pointer is 2.55 - * mandatory. 2.56 - * 2.57 - * \attention Do not use this function to add siblings in a tree where the 2.58 - * nodes store a pointer to the last sibling because that would not be modified by this function. 2.59 - * 2.60 - * \remark If yo do not provide a location to the parent pointer, a call to this function is 2.61 - * effectively the same as a call to cx_linked_list_add(). 2.62 - * 2.63 - * @param node a pointer to the node 2.64 - * @param loc_prev the location of a \c prev pointer within your node struct 2.65 - * @param loc_next the location of a \c next pointer within your node struct 2.66 - * @param loc_parent the location of a \c parent pointer within your node struct 2.67 - * @param new_node the new node that shall be added as a sibling 2.68 - */ 2.69 -void cx_tree_add_sibling(void *node, 2.70 - ptrdiff_t loc_prev, ptrdiff_t loc_next, 2.71 - ptrdiff_t loc_parent, 2.72 - void *new_node) 2.73 -__attribute__((__nonnull__)); 2.74 - 2.75 -/** 2.76 - * Adds a node to the list of children. 2.77 - * 2.78 - * \par Example with a full structure 2.79 - * A full tree node structure may look like this: 2.80 - * \code 2.81 - * typedef struct MyTreeNode MyTreeNode; 2.82 - * struct MyTreeNode { 2.83 - * MyTreeNode* parent; 2.84 - * MyTreeNode* first_child; 2.85 - * MyTreeNode* last_child; 2.86 - * MyTreeNode* prev_sibling; 2.87 - * MyTreeNode* next_sibling; 2.88 - * // ...contents... 2.89 - * } 2.90 - * \endcode 2.91 - * Adding a new child to a node with the above structure can be performed with the following call: 2.92 - * \code 2.93 - * MyTreeNode *node, *child; // given 2.94 - * cx_tree_add_child(&node->first_child, &node->last_child, 2.95 - * offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling), 2.96 - * child, offsetof(MyTreeNode, parent), node); 2.97 - * \endcode 2.98 - * 2.99 - * \par Example with a reduced structure 2.100 - * The minimal reasonable structure with parent pointer looks like this: 2.101 - * \code 2.102 - * typedef struct MyTreeNode MyTreeNode; 2.103 - * struct MyTreeNode { 2.104 - * MyTreeNode* parent; 2.105 - * MyTreeNode* children; 2.106 - * MyTreeNode* next_sibling; 2.107 - * // ...contents... 2.108 - * } 2.109 - * \endcode 2.110 - * This simplifies the function call to: 2.111 - * \code 2.112 - * MyTreeNode *node, *child; // given 2.113 - * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling), 2.114 - * child, offsetof(MyTreeNode, parent), node); 2.115 - * \endcode 2.116 - * 2.117 - * \remark If your tree structure does not possess a parent pointer, a call to this function is 2.118 - * effectively the same as a call to cx_linked_list_add(). 2.119 - * 2.120 - * @param children_begin a pointer to the begin node pointer (if your list has one) 2.121 - * @param children_end a pointer to the end node pointer (if your list has one) 2.122 - * @param loc_prev the location of a \c prev pointer within your node struct 2.123 - * @param loc_next the location of a \c next pointer within your node struct 2.124 - * @param new_node a pointer to the node that shall be appended 2.125 - * @param loc_parent the location of a \c parent pointer within your node struct 2.126 - * @param parent the parent node 2.127 - */ 2.128 -void cx_tree_add_child(void **children_begin, void **children_end, 2.129 - ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, 2.130 - ptrdiff_t loc_parent, void *parent) 2.131 -__attribute__((__nonnull__ (5))); 2.132 - 2.133 - 2.134 -#ifdef __cplusplus 2.135 -} // extern "C" 2.136 -#endif 2.137 - 2.138 -#endif // UCX_TREE_H 2.139 -
3.1 --- a/src/tree.c Tue Jun 20 19:13:31 2023 +0200 3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 3.3 @@ -1,52 +0,0 @@ 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 -#include "cx/linked_list.h" 3.34 - 3.35 -#define CX_TR_PTR(cur, off) *((void**)(((char*)(cur))+(off))) 3.36 - 3.37 -void cx_tree_add_sibling(void *node, ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_parent, void *new_node) { 3.38 - cx_linked_list_add(&node, NULL, loc_prev, loc_next, new_node); 3.39 - 3.40 - // optional parent link 3.41 - if (loc_parent >= 0) { 3.42 - CX_TR_PTR(new_node, loc_parent) = CX_TR_PTR(node, loc_parent); 3.43 - } 3.44 -} 3.45 - 3.46 -void cx_tree_add_child(void **children_begin, void **children_end, 3.47 - ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, 3.48 - ptrdiff_t loc_parent, void *parent) { 3.49 - cx_linked_list_add(children_begin, children_end, loc_prev, loc_next, new_node); 3.50 - 3.51 - // optional parent link 3.52 - if (loc_parent >= 0) { 3.53 - CX_TR_PTR(new_node, loc_parent) = parent; 3.54 - } 3.55 -}
4.1 --- a/tests/CMakeLists.txt Tue Jun 20 19:13:31 2023 +0200 4.2 +++ b/tests/CMakeLists.txt Tue Jun 20 19:20:51 2023 +0200 4.3 @@ -23,7 +23,6 @@ 4.4 test_string.cpp 4.5 test_buffer.cpp 4.6 test_list.cpp 4.7 - test_tree.cpp 4.8 test_hash_key.cpp 4.9 test_map.cpp 4.10 test_map_generics.c
5.1 --- a/tests/test_tree.cpp Tue Jun 20 19:13:31 2023 +0200 5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 5.3 @@ -1,122 +0,0 @@ 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 <gtest/gtest.h> 5.34 - 5.35 -struct TestNode { 5.36 - TestNode *parent = nullptr; 5.37 - TestNode *prev = nullptr; 5.38 - TestNode *next = nullptr; 5.39 - 5.40 - TestNode *children_begin = nullptr; 5.41 - TestNode *children_end = nullptr; 5.42 -}; 5.43 - 5.44 -TEST(Tree, cx_tree_add_sibling) { 5.45 - // prepare test tree 5.46 - TestNode root, a; 5.47 - root.children_begin = &a; 5.48 - root.children_end = &a; 5.49 - a.parent = &root; 5.50 - 5.51 - // new test nodes 5.52 - TestNode b, c; 5.53 - 5.54 - // test 5.55 - cx_tree_add_sibling(&a, offsetof(TestNode, prev), offsetof(TestNode, next), offsetof(TestNode, parent), &b); 5.56 - EXPECT_EQ(b.parent, &root); 5.57 - EXPECT_EQ(b.prev, &a); 5.58 - EXPECT_EQ(b.next, nullptr); 5.59 - EXPECT_EQ(a.next, &b); 5.60 - 5.61 - cx_tree_add_sibling(&a, -1, offsetof(TestNode, next), -1, &c); 5.62 - EXPECT_EQ(c.parent, nullptr); 5.63 - EXPECT_EQ(c.prev, nullptr); 5.64 - EXPECT_EQ(c.next, nullptr); 5.65 - EXPECT_EQ(b.next, &c); 5.66 -} 5.67 - 5.68 -TEST(Tree, cx_tree_add_child) { 5.69 - TestNode root, a, b, c, a1; 5.70 - 5.71 - cx_tree_add_child( 5.72 - (void **) &root.children_begin, 5.73 - (void **) &root.children_end, 5.74 - offsetof(TestNode, prev), 5.75 - offsetof(TestNode, next), 5.76 - &a, 5.77 - offsetof(TestNode, parent), 5.78 - &root); 5.79 - EXPECT_EQ(root.children_begin, &a); 5.80 - EXPECT_EQ(root.children_end, &a); 5.81 - EXPECT_EQ(a.parent, &root); 5.82 - EXPECT_EQ(a.prev, nullptr); 5.83 - EXPECT_EQ(a.next, nullptr); 5.84 - 5.85 - cx_tree_add_child( 5.86 - (void **) &root.children_begin, 5.87 - (void **) &root.children_end, 5.88 - offsetof(TestNode, prev), 5.89 - offsetof(TestNode, next), 5.90 - &b, 5.91 - offsetof(TestNode, parent), 5.92 - &root); 5.93 - EXPECT_EQ(root.children_begin, &a); 5.94 - EXPECT_EQ(root.children_begin->next, &b); 5.95 - EXPECT_EQ(root.children_end, &b); 5.96 - EXPECT_EQ(b.parent, &root); 5.97 - EXPECT_EQ(b.prev, &a); 5.98 - 5.99 - cx_tree_add_child( 5.100 - (void **) &root.children_begin, 5.101 - nullptr, 5.102 - -1, 5.103 - offsetof(TestNode, next), 5.104 - &c, 5.105 - -1, 5.106 - &root); 5.107 - EXPECT_EQ(root.children_end, &b); // children_end unchanged 5.108 - EXPECT_EQ(b.next, &c); 5.109 - EXPECT_EQ(c.prev, nullptr); 5.110 - EXPECT_EQ(c.next, nullptr); 5.111 - EXPECT_EQ(c.parent, nullptr); 5.112 - 5.113 - cx_tree_add_child( 5.114 - (void **) &a.children_begin, 5.115 - (void **) &a.children_end, 5.116 - offsetof(TestNode, prev), 5.117 - offsetof(TestNode, next), 5.118 - &a1, 5.119 - offsetof(TestNode, parent), 5.120 - &a); 5.121 - EXPECT_EQ(a.children_begin, &a1); 5.122 - EXPECT_EQ(a1.parent, &a); 5.123 - EXPECT_EQ(root.children_begin, &a); 5.124 - EXPECT_EQ(root.children_begin->children_begin, &a1); 5.125 -}