comparison: src/cx/tree.h
src/cx/tree.h
- changeset 453
- bb144d08cd44
- parent 442
- 310019ddfe4e
- child 484
- 9e6900b1cf9d
equal
deleted
inserted
replaced
| 452:a10c3e127050 | 453:bb144d08cd44 |
|---|---|
| 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 /** | |
| 29 * \file tree.h | |
| 30 * \brief Interface for tree implementations. | |
| 31 * \author Olaf Wintermann | |
| 32 * \author Mike Becker | |
| 33 * \version 3.0 | |
| 34 * \copyright 2-Clause BSD License | |
| 35 */ | |
| 28 | 36 |
| 29 #ifndef UCX_TREE_H | 37 #ifndef UCX_TREE_H |
| 30 #define UCX_TREE_H | 38 #define UCX_TREE_H |
| 31 | 39 |
| 32 #include <stddef.h> | 40 #include <stddef.h> |
| 34 #include "allocator.h" | 42 #include "allocator.h" |
| 35 | 43 |
| 36 #ifdef __cplusplus | 44 #ifdef __cplusplus |
| 37 extern "C" { | 45 extern "C" { |
| 38 #endif | 46 #endif |
| 39 | |
| 40 void* cx_tree_last(void *node, ptrdiff_t loc_next); | |
| 41 | |
| 42 int cx_tree_add_node(void *node, ptrdiff_t loc_parent, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); | |
| 43 | 47 |
| 44 int cx_tree_add_child_node( | 48 /** |
| 45 void *parent, | 49 * Adds a sibling to the current tree node. |
| 46 ptrdiff_t loc_parent, | 50 * |
| 47 ptrdiff_t loc_prev, | 51 * In case your struct does not have a \p prev or a \p parent pointer, |
| 48 ptrdiff_t loc_next, | 52 * specify a negative location. The location of the \p next pointer is |
| 49 void **children_begin, | 53 * mandatory. |
| 50 void **children_end, | 54 * |
| 51 void *new_node); | 55 * \attention Do not use this function to add siblings in a tree where the |
| 56 * nodes store a pointer to the last sibling because that would not be modified by this function. | |
| 57 * | |
| 58 * \remark If yo do not provide a location to the parent pointer, a call to this function is | |
| 59 * effectively the same as a call to cx_linked_list_add(). | |
| 60 * | |
| 61 * @param node a pointer to the node | |
| 62 * @param loc_prev the location of a \c prev pointer within your node struct | |
| 63 * @param loc_next the location of a \c next pointer within your node struct | |
| 64 * @param loc_parent the location of a \c parent pointer within your node struct | |
| 65 * @param new_node the new node that shall be added as a sibling | |
| 66 */ | |
| 67 void cx_tree_add_sibling(void *node, | |
| 68 ptrdiff_t loc_prev, ptrdiff_t loc_next, | |
| 69 ptrdiff_t loc_parent, | |
| 70 void *new_node) | |
| 71 __attribute__((__nonnull__)); | |
| 72 | |
| 73 /** | |
| 74 * Adds a node to the list of children. | |
| 75 * | |
| 76 * \par Example with a full structure | |
| 77 * A full tree node structure may look like this: | |
| 78 * \code | |
| 79 * typedef struct MyTreeNode MyTreeNode; | |
| 80 * struct MyTreeNode { | |
| 81 * MyTreeNode* parent; | |
| 82 * MyTreeNode* first_child; | |
| 83 * MyTreeNode* last_child; | |
| 84 * MyTreeNode* prev_sibling; | |
| 85 * MyTreeNode* next_sibling; | |
| 86 * // ...contents... | |
| 87 * } | |
| 88 * \endcode | |
| 89 * Adding a new child to a node with the above structure can be performed with the following call: | |
| 90 * \code | |
| 91 * MyTreeNode *node, *child; // given | |
| 92 * cx_tree_add_child(&node->first_child, &node->last_child, | |
| 93 * offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling), | |
| 94 * child, offsetof(MyTreeNode, parent), node); | |
| 95 * \endcode | |
| 96 * | |
| 97 * \par Example with a reduced structure | |
| 98 * The minimal reasonable structure with parent pointer looks like this: | |
| 99 * \code | |
| 100 * typedef struct MyTreeNode MyTreeNode; | |
| 101 * struct MyTreeNode { | |
| 102 * MyTreeNode* parent; | |
| 103 * MyTreeNode* children; | |
| 104 * MyTreeNode* next_sibling; | |
| 105 * // ...contents... | |
| 106 * } | |
| 107 * \endcode | |
| 108 * This simplifies the function call to: | |
| 109 * \code | |
| 110 * MyTreeNode *node, *child; // given | |
| 111 * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling), | |
| 112 * child, offsetof(MyTreeNode, parent), node); | |
| 113 * \endcode | |
| 114 * | |
| 115 * \remark If your tree structure does not possess a parent pointer, a call to this function is | |
| 116 * effectively the same as a call to cx_linked_list_add(). | |
| 117 * | |
| 118 * @param children_begin a pointer to the begin node pointer (if your list has one) | |
| 119 * @param children_end a pointer to the end node pointer (if your list has one) | |
| 120 * @param loc_prev the location of a \c prev pointer within your node struct | |
| 121 * @param loc_next the location of a \c next pointer within your node struct | |
| 122 * @param new_node a pointer to the node that shall be appended | |
| 123 * @param loc_parent the location of a \c parent pointer within your node struct | |
| 124 * @param parent the parent node | |
| 125 */ | |
| 126 void cx_tree_add_child(void **children_begin, void **children_end, | |
| 127 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, | |
| 128 ptrdiff_t loc_parent, void *parent) | |
| 129 __attribute__((__nonnull__ (5))); | |
| 52 | 130 |
| 53 | 131 |
| 54 #ifdef __cplusplus | 132 #ifdef __cplusplus |
| 55 } | 133 } /* extern "C" */ |
| 56 #endif | 134 #endif |
| 57 | 135 |
| 58 #endif /* UCX_TREE_H */ | 136 #endif /* UCX_TREE_H */ |
| 59 | 137 |
