1.1 --- a/src/cx/tree.h Tue Jun 20 19:13:31 2023 +0200
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,136 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
1.8 - *
1.9 - * Redistribution and use in source and binary forms, with or without
1.10 - * modification, are permitted provided that the following conditions are met:
1.11 - *
1.12 - * 1. Redistributions of source code must retain the above copyright
1.13 - * notice, this list of conditions and the following disclaimer.
1.14 - *
1.15 - * 2. Redistributions in binary form must reproduce the above copyright
1.16 - * notice, this list of conditions and the following disclaimer in the
1.17 - * documentation and/or other materials provided with the distribution.
1.18 - *
1.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 - * POSSIBILITY OF SUCH DAMAGE.
1.30 - */
1.31 -/**
1.32 - * \file tree.h
1.33 - * \brief Interface for tree implementations.
1.34 - * \author Olaf Wintermann
1.35 - * \author Mike Becker
1.36 - * \version 3.0
1.37 - * \copyright 2-Clause BSD License
1.38 - */
1.39 -
1.40 -#ifndef UCX_TREE_H
1.41 -#define UCX_TREE_H
1.42 -
1.43 -#include "common.h"
1.44 -#include "allocator.h"
1.45 -
1.46 -#ifdef __cplusplus
1.47 -extern "C" {
1.48 -#endif
1.49 -
1.50 -/**
1.51 - * Adds a sibling to the current tree node.
1.52 - *
1.53 - * In case your struct does not have a \p prev or a \p parent pointer,
1.54 - * specify a negative location. The location of the \p next pointer is
1.55 - * mandatory.
1.56 - *
1.57 - * \attention Do not use this function to add siblings in a tree where the
1.58 - * nodes store a pointer to the last sibling because that would not be modified by this function.
1.59 - *
1.60 - * \remark If yo do not provide a location to the parent pointer, a call to this function is
1.61 - * effectively the same as a call to cx_linked_list_add().
1.62 - *
1.63 - * @param node a pointer to the node
1.64 - * @param loc_prev the location of a \c prev pointer within your node struct
1.65 - * @param loc_next the location of a \c next pointer within your node struct
1.66 - * @param loc_parent the location of a \c parent pointer within your node struct
1.67 - * @param new_node the new node that shall be added as a sibling
1.68 - */
1.69 -void cx_tree_add_sibling(void *node,
1.70 - ptrdiff_t loc_prev, ptrdiff_t loc_next,
1.71 - ptrdiff_t loc_parent,
1.72 - void *new_node)
1.73 -__attribute__((__nonnull__));
1.74 -
1.75 -/**
1.76 - * Adds a node to the list of children.
1.77 - *
1.78 - * \par Example with a full structure
1.79 - * A full tree node structure may look like this:
1.80 - * \code
1.81 - * typedef struct MyTreeNode MyTreeNode;
1.82 - * struct MyTreeNode {
1.83 - * MyTreeNode* parent;
1.84 - * MyTreeNode* first_child;
1.85 - * MyTreeNode* last_child;
1.86 - * MyTreeNode* prev_sibling;
1.87 - * MyTreeNode* next_sibling;
1.88 - * // ...contents...
1.89 - * }
1.90 - * \endcode
1.91 - * Adding a new child to a node with the above structure can be performed with the following call:
1.92 - * \code
1.93 - * MyTreeNode *node, *child; // given
1.94 - * cx_tree_add_child(&node->first_child, &node->last_child,
1.95 - * offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling),
1.96 - * child, offsetof(MyTreeNode, parent), node);
1.97 - * \endcode
1.98 - *
1.99 - * \par Example with a reduced structure
1.100 - * The minimal reasonable structure with parent pointer looks like this:
1.101 - * \code
1.102 - * typedef struct MyTreeNode MyTreeNode;
1.103 - * struct MyTreeNode {
1.104 - * MyTreeNode* parent;
1.105 - * MyTreeNode* children;
1.106 - * MyTreeNode* next_sibling;
1.107 - * // ...contents...
1.108 - * }
1.109 - * \endcode
1.110 - * This simplifies the function call to:
1.111 - * \code
1.112 - * MyTreeNode *node, *child; // given
1.113 - * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling),
1.114 - * child, offsetof(MyTreeNode, parent), node);
1.115 - * \endcode
1.116 - *
1.117 - * \remark If your tree structure does not possess a parent pointer, a call to this function is
1.118 - * effectively the same as a call to cx_linked_list_add().
1.119 - *
1.120 - * @param children_begin a pointer to the begin node pointer (if your list has one)
1.121 - * @param children_end a pointer to the end node pointer (if your list has one)
1.122 - * @param loc_prev the location of a \c prev pointer within your node struct
1.123 - * @param loc_next the location of a \c next pointer within your node struct
1.124 - * @param new_node a pointer to the node that shall be appended
1.125 - * @param loc_parent the location of a \c parent pointer within your node struct
1.126 - * @param parent the parent node
1.127 - */
1.128 -void cx_tree_add_child(void **children_begin, void **children_end,
1.129 - ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node,
1.130 - ptrdiff_t loc_parent, void *parent)
1.131 -__attribute__((__nonnull__ (5)));
1.132 -
1.133 -
1.134 -#ifdef __cplusplus
1.135 -} // extern "C"
1.136 -#endif
1.137 -
1.138 -#endif // UCX_TREE_H
1.139 -
