src/cx/tree.h

Mon, 04 Mar 2024 09:06:15 +0100

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Mon, 04 Mar 2024 09:06:15 +0100
changeset 842
b48cbfa109d4
parent 840
4f02995ce44e
child 845
2615317311b7
permissions
-rw-r--r--

add -lm to ldflags on Solaris

816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
28 /**
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
29 * \file tree.h
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
30 * \brief Interface for tree implementations.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
31 * \author Mike Becker
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
32 * \author Olaf Wintermann
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
33 * \copyright 2-Clause BSD License
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
34 */
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
35
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
36 #ifndef UCX_TREE_H
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37 #define UCX_TREE_H
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
38
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
39 #include "common.h"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
40
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
41 #include "iterator.h"
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
42
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
43 #ifdef __cplusplus
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
44 extern "C" {
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
45 #endif
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
46
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
47 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
48 * Tree iterator.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
49 *
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
50 * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
51 * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
52 * Each node, regardless of the number of passes, is counted only once.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
53 *
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
54 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
55 * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
56 * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
57 *
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
58 * @see CxIterator
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
59 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
60 typedef struct cx_tree_iterator_s {
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
61 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
62 * The base properties of this iterator.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
63 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
64 struct cx_iterator_base_s base;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
65 /**
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
66 * Set to true, when the iterator shall visit a node again
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
67 * when all it's children have been processed.
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
68 */
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
69 bool visit_on_exit;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
70 /**
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
71 * True, if this iterator is currently leaving the node.
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
72 */
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
73 bool exiting;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
74 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
75 * Offset in the node struct for the children linked list.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
76 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
77 off_t loc_children;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
78 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
79 * Offset in the node struct for the next pointer.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
80 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
81 off_t loc_next;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
82 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
83 * The total number of distinct nodes that have been passed so far.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
84 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
85 size_t counter;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
86 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
87 * The currently observed node.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
88 *
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
89 * This is the same what cxIteratorCurrent() would return.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
90 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
91 void *node;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
92 /**
840
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 835
diff changeset
93 * Stores a copy of the next pointer of the visited node.
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 835
diff changeset
94 * Allows freeing a node on exit without corrupting the iteration.
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 835
diff changeset
95 */
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 835
diff changeset
96 void *next;
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 835
diff changeset
97 /**
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
98 * Internal stack.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
99 * Will be automatically freed once the iterator becomes invalid.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
100 *
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
101 * If you want to discard the iterator before, you need to manually
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
102 * call cxTreeIteratorDispose().
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
103 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
104 void **stack;
828
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
105 /**
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
106 * Internal capacity of the stack.
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
107 */
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
108 size_t stack_capacity;
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
109 union {
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
110 /**
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
111 * Internal stack size.
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
112 */
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
113 size_t stack_size;
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
114 /**
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
115 * The current depth in the tree.
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
116 */
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
117 size_t depth;
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
118 };
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
119 } CxTreeIterator;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
120
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
121 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
122 * Releases internal memory of the given tree iterator.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
123 * @param iter the iterator
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
124 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
125 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
126 free(iter->stack);
835
13068743197f set tree iterator stack pointer to NULL on dispose to avoid accidental double-frees
Mike Becker <universe@uap-core.de>
parents: 833
diff changeset
127 iter->stack = NULL;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
128 }
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
129
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
130 /**
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
131 * Links a node to a (new) parent.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
132 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
133 * If the node has already a parent, it is unlinked, first.
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
134 * If the parent has children already, the node is prepended to the list
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
135 * of all currently existing children.
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
136 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
137 * @param parent the parent node
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
138 * @param node the node that shall be linked
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
139 * @param loc_parent offset in the node struct for the parent pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
140 * @param loc_children offset in the node struct for the children linked list
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
141 * @param loc_prev offset in the node struct for the prev pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
142 * @param loc_next offset in the node struct for the next pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
143 * @see cx_tree_unlink()
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
144 */
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
145 __attribute__((__nonnull__))
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
146 void cx_tree_link(
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
147 void * restrict parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
148 void * restrict node,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
149 ptrdiff_t loc_parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
150 ptrdiff_t loc_children,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
151 ptrdiff_t loc_prev,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
152 ptrdiff_t loc_next
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
153 );
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
154
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
155 /**
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
156 * Unlinks a node from its parent.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
157 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
158 * If the node has no parent, this function does nothing.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
159 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
160 * @param node the node that shall be unlinked from its parent
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
161 * @param loc_parent offset in the node struct for the parent pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
162 * @param loc_children offset in the node struct for the children linked list
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
163 * @param loc_prev offset in the node struct for the prev pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
164 * @param loc_next offset in the node struct for the next pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
165 * @see cx_tree_link()
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
166 */
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
167 __attribute__((__nonnull__))
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
168 void cx_tree_unlink(
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
169 void *node,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
170 ptrdiff_t loc_parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
171 ptrdiff_t loc_children,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
172 ptrdiff_t loc_prev,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
173 ptrdiff_t loc_next
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
174 );
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
175
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
176 /**
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
177 * Function pointer for a search function.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
178 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
179 * A function of this kind shall check if the specified \p node
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
180 * contains the given \p data or if one of the children might contain
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
181 * the data.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
182 *
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
183 * The function should use the returned integer to indicate how close the
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
184 * match is, where a negative number means that it does not match at all.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
185 *
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
186 * For example if a tree stores file path information, a node that is
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
187 * describing a parent directory of a filename that is searched, shall
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
188 * return a positive number to indicate that a child node might contain the
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
189 * searched item. On the other hand, if the node denotes a path that is not a
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
190 * prefix of the searched filename, the function would return -1 to indicate
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
191 * that * the search does not need to be continued in that branch.
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
192 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
193 * @param node the node that is currently investigated
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
194 * @param data the data that is searched for
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
195 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
196 * @return 0 if the node contains the data,
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
197 * positive if one of the children might contain the data,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
198 * negative if neither the node, nor the children contains the data
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
199 */
824
a939872c284d fix missing typedef
Mike Becker <universe@uap-core.de>
parents: 823
diff changeset
200 typedef int (*cx_tree_search_func)(void const *node, void const* data);
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
201
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
202
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
203 /**
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
204 * Searches for data in a tree.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
205 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
206 * When the data cannot be found exactly, the search function might return a
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
207 * closest result which might be a good starting point for adding a new node
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
208 * to the tree.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
209 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
210 * Depending on the tree structure it is not necessarily guaranteed that the
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
211 * "closest" match is uniquely defined. This function will search for a node
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
212 * with the best match according to the \p sfunc (meaning: the return value of
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
213 * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
214 * node matching the criteria is returned.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
215 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
216 * @param root the root node
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
217 * @param data the data to search for
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
218 * @param sfunc the search function
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
219 * @param result where the result shall be stored
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
220 * @param loc_children offset in the node struct for the children linked list
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
221 * @param loc_next offset in the node struct for the next pointer
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
222 * @return zero if the node was found exactly, positive if a node was found that
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
223 * could contain the node (but doesn't right now), negative if the tree does not
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
224 * contain any node that might be related to the searched data
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
225 */
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
226 __attribute__((__nonnull__))
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
227 int cx_tree_search(
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
228 void const *root,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
229 void const *data,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
230 cx_tree_search_func sfunc,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
231 void **result,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
232 ptrdiff_t loc_children,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
233 ptrdiff_t loc_next
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
234 );
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
235
828
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
236 /**
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
237 * Creates an iterator for a tree with the specified root node.
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
238 *
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
239 * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
240 * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
241 * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
242 * the memory.
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
243 *
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
244 * @remark At the moment, the returned iterator does not support cxIteratorFlagRemoval().
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
245 *
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
246 * @param root the root node
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
247 * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
828
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
248 * @param loc_children offset in the node struct for the children linked list
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
249 * @param loc_next offset in the node struct for the next pointer
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
250 * @return the new tree iterator
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
251 * @see cxTreeIteratorDispose()
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
252 */
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
253 __attribute__((__nonnull__))
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 828
diff changeset
254 CxTreeIterator cx_tree_iterator(
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 828
diff changeset
255 void *root,
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
256 bool visit_on_exit,
828
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
257 ptrdiff_t loc_children,
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
258 ptrdiff_t loc_next
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
259 );
88fa3381206d improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents: 827
diff changeset
260
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
261 #ifdef __cplusplus
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
262 } // extern "C"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
263 #endif
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
264
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
265 #endif //UCX_TREE_H

mercurial