# HG changeset patch # User Mike Becker # Date 1687281651 -7200 # Node ID cf2f209b9da26071fd11d7c5b9741984fb52f5f6 # Parent aa17be68fc667062f4e8ee943b8172cf9d731a71 remove trees from UCX 3.0 diff -r aa17be68fc66 -r cf2f209b9da2 src/CMakeLists.txt --- a/src/CMakeLists.txt Tue Jun 20 19:13:31 2023 +0200 +++ b/src/CMakeLists.txt Tue Jun 20 19:20:51 2023 +0200 @@ -5,7 +5,6 @@ list.c array_list.c linked_list.c - tree.c buffer.c map.c hash_key.c @@ -24,7 +23,6 @@ cx/list.h cx/array_list.h cx/linked_list.h - cx/tree.h cx/buffer.h cx/map.h cx/hash_key.h diff -r aa17be68fc66 -r cf2f209b9da2 src/cx/tree.h --- a/src/cx/tree.h Tue Jun 20 19:13:31 2023 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,136 +0,0 @@ -/* - * 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. - */ -/** - * \file tree.h - * \brief Interface for tree implementations. - * \author Olaf Wintermann - * \author Mike Becker - * \version 3.0 - * \copyright 2-Clause BSD License - */ - -#ifndef UCX_TREE_H -#define UCX_TREE_H - -#include "common.h" -#include "allocator.h" - -#ifdef __cplusplus -extern "C" { -#endif - -/** - * Adds a sibling to the current tree node. - * - * In case your struct does not have a \p prev or a \p parent pointer, - * specify a negative location. The location of the \p next pointer is - * mandatory. - * - * \attention Do not use this function to add siblings in a tree where the - * nodes store a pointer to the last sibling because that would not be modified by this function. - * - * \remark If yo do not provide a location to the parent pointer, a call to this function is - * effectively the same as a call to cx_linked_list_add(). - * - * @param node a pointer to the node - * @param loc_prev the location of a \c prev pointer within your node struct - * @param loc_next the location of a \c next pointer within your node struct - * @param loc_parent the location of a \c parent pointer within your node struct - * @param new_node the new node that shall be added as a sibling - */ -void cx_tree_add_sibling(void *node, - ptrdiff_t loc_prev, ptrdiff_t loc_next, - ptrdiff_t loc_parent, - void *new_node) -__attribute__((__nonnull__)); - -/** - * Adds a node to the list of children. - * - * \par Example with a full structure - * A full tree node structure may look like this: - * \code - * typedef struct MyTreeNode MyTreeNode; - * struct MyTreeNode { - * MyTreeNode* parent; - * MyTreeNode* first_child; - * MyTreeNode* last_child; - * MyTreeNode* prev_sibling; - * MyTreeNode* next_sibling; - * // ...contents... - * } - * \endcode - * Adding a new child to a node with the above structure can be performed with the following call: - * \code - * MyTreeNode *node, *child; // given - * cx_tree_add_child(&node->first_child, &node->last_child, - * offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling), - * child, offsetof(MyTreeNode, parent), node); - * \endcode - * - * \par Example with a reduced structure - * The minimal reasonable structure with parent pointer looks like this: - * \code - * typedef struct MyTreeNode MyTreeNode; - * struct MyTreeNode { - * MyTreeNode* parent; - * MyTreeNode* children; - * MyTreeNode* next_sibling; - * // ...contents... - * } - * \endcode - * This simplifies the function call to: - * \code - * MyTreeNode *node, *child; // given - * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling), - * child, offsetof(MyTreeNode, parent), node); - * \endcode - * - * \remark If your tree structure does not possess a parent pointer, a call to this function is - * effectively the same as a call to cx_linked_list_add(). - * - * @param children_begin a pointer to the begin node pointer (if your list has one) - * @param children_end a pointer to the end node pointer (if your list has one) - * @param loc_prev the location of a \c prev pointer within your node struct - * @param loc_next the location of a \c next pointer within your node struct - * @param new_node a pointer to the node that shall be appended - * @param loc_parent the location of a \c parent pointer within your node struct - * @param parent the parent node - */ -void cx_tree_add_child(void **children_begin, void **children_end, - ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, - ptrdiff_t loc_parent, void *parent) -__attribute__((__nonnull__ (5))); - - -#ifdef __cplusplus -} // extern "C" -#endif - -#endif // UCX_TREE_H - diff -r aa17be68fc66 -r cf2f209b9da2 src/tree.c --- a/src/tree.c Tue Jun 20 19:13:31 2023 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,52 +0,0 @@ -/* - * 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 "cx/linked_list.h" - -#define CX_TR_PTR(cur, off) *((void**)(((char*)(cur))+(off))) - -void cx_tree_add_sibling(void *node, ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_parent, void *new_node) { - cx_linked_list_add(&node, NULL, loc_prev, loc_next, new_node); - - // optional parent link - if (loc_parent >= 0) { - CX_TR_PTR(new_node, loc_parent) = CX_TR_PTR(node, loc_parent); - } -} - -void cx_tree_add_child(void **children_begin, void **children_end, - ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, - ptrdiff_t loc_parent, void *parent) { - cx_linked_list_add(children_begin, children_end, loc_prev, loc_next, new_node); - - // optional parent link - if (loc_parent >= 0) { - CX_TR_PTR(new_node, loc_parent) = parent; - } -} diff -r aa17be68fc66 -r cf2f209b9da2 tests/CMakeLists.txt --- a/tests/CMakeLists.txt Tue Jun 20 19:13:31 2023 +0200 +++ b/tests/CMakeLists.txt Tue Jun 20 19:20:51 2023 +0200 @@ -23,7 +23,6 @@ test_string.cpp test_buffer.cpp test_list.cpp - test_tree.cpp test_hash_key.cpp test_map.cpp test_map_generics.c diff -r aa17be68fc66 -r cf2f209b9da2 tests/test_tree.cpp --- a/tests/test_tree.cpp Tue Jun 20 19:13:31 2023 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,122 +0,0 @@ -/* - * 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 - -struct TestNode { - TestNode *parent = nullptr; - TestNode *prev = nullptr; - TestNode *next = nullptr; - - TestNode *children_begin = nullptr; - TestNode *children_end = nullptr; -}; - -TEST(Tree, cx_tree_add_sibling) { - // prepare test tree - TestNode root, a; - root.children_begin = &a; - root.children_end = &a; - a.parent = &root; - - // new test nodes - TestNode b, c; - - // test - cx_tree_add_sibling(&a, offsetof(TestNode, prev), offsetof(TestNode, next), offsetof(TestNode, parent), &b); - EXPECT_EQ(b.parent, &root); - EXPECT_EQ(b.prev, &a); - EXPECT_EQ(b.next, nullptr); - EXPECT_EQ(a.next, &b); - - cx_tree_add_sibling(&a, -1, offsetof(TestNode, next), -1, &c); - EXPECT_EQ(c.parent, nullptr); - EXPECT_EQ(c.prev, nullptr); - EXPECT_EQ(c.next, nullptr); - EXPECT_EQ(b.next, &c); -} - -TEST(Tree, cx_tree_add_child) { - TestNode root, a, b, c, a1; - - cx_tree_add_child( - (void **) &root.children_begin, - (void **) &root.children_end, - offsetof(TestNode, prev), - offsetof(TestNode, next), - &a, - offsetof(TestNode, parent), - &root); - EXPECT_EQ(root.children_begin, &a); - EXPECT_EQ(root.children_end, &a); - EXPECT_EQ(a.parent, &root); - EXPECT_EQ(a.prev, nullptr); - EXPECT_EQ(a.next, nullptr); - - cx_tree_add_child( - (void **) &root.children_begin, - (void **) &root.children_end, - offsetof(TestNode, prev), - offsetof(TestNode, next), - &b, - offsetof(TestNode, parent), - &root); - EXPECT_EQ(root.children_begin, &a); - EXPECT_EQ(root.children_begin->next, &b); - EXPECT_EQ(root.children_end, &b); - EXPECT_EQ(b.parent, &root); - EXPECT_EQ(b.prev, &a); - - cx_tree_add_child( - (void **) &root.children_begin, - nullptr, - -1, - offsetof(TestNode, next), - &c, - -1, - &root); - EXPECT_EQ(root.children_end, &b); // children_end unchanged - EXPECT_EQ(b.next, &c); - EXPECT_EQ(c.prev, nullptr); - EXPECT_EQ(c.next, nullptr); - EXPECT_EQ(c.parent, nullptr); - - cx_tree_add_child( - (void **) &a.children_begin, - (void **) &a.children_end, - offsetof(TestNode, prev), - offsetof(TestNode, next), - &a1, - offsetof(TestNode, parent), - &a); - EXPECT_EQ(a.children_begin, &a1); - EXPECT_EQ(a1.parent, &a); - EXPECT_EQ(root.children_begin, &a); - EXPECT_EQ(root.children_begin->children_begin, &a1); -}