Mercurial > hg > ucx / changeset

     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 -}