Sun, 06 Mar 2022 13:57:36 +0100
remove test code duplication for cxListAdd
olaf@424 | 1 | /* |
olaf@424 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
olaf@424 | 3 | * |
olaf@424 | 4 | * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
olaf@424 | 5 | * |
olaf@424 | 6 | * Redistribution and use in source and binary forms, with or without |
olaf@424 | 7 | * modification, are permitted provided that the following conditions are met: |
olaf@424 | 8 | * |
olaf@424 | 9 | * 1. Redistributions of source code must retain the above copyright |
olaf@424 | 10 | * notice, this list of conditions and the following disclaimer. |
olaf@424 | 11 | * |
olaf@424 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
olaf@424 | 13 | * notice, this list of conditions and the following disclaimer in the |
olaf@424 | 14 | * documentation and/or other materials provided with the distribution. |
olaf@424 | 15 | * |
olaf@424 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
olaf@424 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
olaf@424 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
olaf@424 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
olaf@424 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
olaf@424 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
olaf@424 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
olaf@424 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
olaf@424 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
olaf@424 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
olaf@424 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
olaf@424 | 27 | */ |
universe@453 | 28 | /** |
universe@453 | 29 | * \file tree.h |
universe@453 | 30 | * \brief Interface for tree implementations. |
universe@453 | 31 | * \author Olaf Wintermann |
universe@453 | 32 | * \author Mike Becker |
universe@453 | 33 | * \version 3.0 |
universe@453 | 34 | * \copyright 2-Clause BSD License |
universe@453 | 35 | */ |
olaf@424 | 36 | |
olaf@424 | 37 | #ifndef UCX_TREE_H |
olaf@424 | 38 | #define UCX_TREE_H |
olaf@424 | 39 | |
universe@484 | 40 | #include "common.h" |
olaf@424 | 41 | #include "allocator.h" |
olaf@424 | 42 | |
olaf@424 | 43 | #ifdef __cplusplus |
olaf@424 | 44 | extern "C" { |
olaf@424 | 45 | #endif |
olaf@424 | 46 | |
universe@453 | 47 | /** |
universe@453 | 48 | * Adds a sibling to the current tree node. |
universe@453 | 49 | * |
universe@453 | 50 | * In case your struct does not have a \p prev or a \p parent pointer, |
universe@453 | 51 | * specify a negative location. The location of the \p next pointer is |
universe@453 | 52 | * mandatory. |
universe@453 | 53 | * |
universe@453 | 54 | * \attention Do not use this function to add siblings in a tree where the |
universe@453 | 55 | * nodes store a pointer to the last sibling because that would not be modified by this function. |
universe@453 | 56 | * |
universe@453 | 57 | * \remark If yo do not provide a location to the parent pointer, a call to this function is |
universe@453 | 58 | * effectively the same as a call to cx_linked_list_add(). |
universe@453 | 59 | * |
universe@453 | 60 | * @param node a pointer to the node |
universe@453 | 61 | * @param loc_prev the location of a \c prev pointer within your node struct |
universe@453 | 62 | * @param loc_next the location of a \c next pointer within your node struct |
universe@453 | 63 | * @param loc_parent the location of a \c parent pointer within your node struct |
universe@453 | 64 | * @param new_node the new node that shall be added as a sibling |
universe@453 | 65 | */ |
universe@453 | 66 | void cx_tree_add_sibling(void *node, |
universe@453 | 67 | ptrdiff_t loc_prev, ptrdiff_t loc_next, |
universe@453 | 68 | ptrdiff_t loc_parent, |
universe@453 | 69 | void *new_node) |
universe@453 | 70 | __attribute__((__nonnull__)); |
universe@453 | 71 | |
universe@453 | 72 | /** |
universe@453 | 73 | * Adds a node to the list of children. |
universe@453 | 74 | * |
universe@453 | 75 | * \par Example with a full structure |
universe@453 | 76 | * A full tree node structure may look like this: |
universe@453 | 77 | * \code |
universe@453 | 78 | * typedef struct MyTreeNode MyTreeNode; |
universe@453 | 79 | * struct MyTreeNode { |
universe@453 | 80 | * MyTreeNode* parent; |
universe@453 | 81 | * MyTreeNode* first_child; |
universe@453 | 82 | * MyTreeNode* last_child; |
universe@453 | 83 | * MyTreeNode* prev_sibling; |
universe@453 | 84 | * MyTreeNode* next_sibling; |
universe@453 | 85 | * // ...contents... |
universe@453 | 86 | * } |
universe@453 | 87 | * \endcode |
universe@453 | 88 | * Adding a new child to a node with the above structure can be performed with the following call: |
universe@453 | 89 | * \code |
universe@453 | 90 | * MyTreeNode *node, *child; // given |
universe@453 | 91 | * cx_tree_add_child(&node->first_child, &node->last_child, |
universe@453 | 92 | * offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling), |
universe@453 | 93 | * child, offsetof(MyTreeNode, parent), node); |
universe@453 | 94 | * \endcode |
universe@453 | 95 | * |
universe@453 | 96 | * \par Example with a reduced structure |
universe@453 | 97 | * The minimal reasonable structure with parent pointer looks like this: |
universe@453 | 98 | * \code |
universe@453 | 99 | * typedef struct MyTreeNode MyTreeNode; |
universe@453 | 100 | * struct MyTreeNode { |
universe@453 | 101 | * MyTreeNode* parent; |
universe@453 | 102 | * MyTreeNode* children; |
universe@453 | 103 | * MyTreeNode* next_sibling; |
universe@453 | 104 | * // ...contents... |
universe@453 | 105 | * } |
universe@453 | 106 | * \endcode |
universe@453 | 107 | * This simplifies the function call to: |
universe@453 | 108 | * \code |
universe@453 | 109 | * MyTreeNode *node, *child; // given |
universe@453 | 110 | * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling), |
universe@453 | 111 | * child, offsetof(MyTreeNode, parent), node); |
universe@453 | 112 | * \endcode |
universe@453 | 113 | * |
universe@453 | 114 | * \remark If your tree structure does not possess a parent pointer, a call to this function is |
universe@453 | 115 | * effectively the same as a call to cx_linked_list_add(). |
universe@453 | 116 | * |
universe@453 | 117 | * @param children_begin a pointer to the begin node pointer (if your list has one) |
universe@453 | 118 | * @param children_end a pointer to the end node pointer (if your list has one) |
universe@453 | 119 | * @param loc_prev the location of a \c prev pointer within your node struct |
universe@453 | 120 | * @param loc_next the location of a \c next pointer within your node struct |
universe@453 | 121 | * @param new_node a pointer to the node that shall be appended |
universe@453 | 122 | * @param loc_parent the location of a \c parent pointer within your node struct |
universe@453 | 123 | * @param parent the parent node |
universe@453 | 124 | */ |
universe@453 | 125 | void cx_tree_add_child(void **children_begin, void **children_end, |
universe@453 | 126 | ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, |
universe@453 | 127 | ptrdiff_t loc_parent, void *parent) |
universe@453 | 128 | __attribute__((__nonnull__ (5))); |
olaf@424 | 129 | |
olaf@424 | 130 | |
olaf@424 | 131 | #ifdef __cplusplus |
universe@453 | 132 | } /* extern "C" */ |
olaf@424 | 133 | #endif |
olaf@424 | 134 | |
olaf@424 | 135 | #endif /* UCX_TREE_H */ |
olaf@424 | 136 |