src/cx/tree.h

Sun, 03 Nov 2024 16:08:15 +0100

author
Mike Becker <universe@uap-core.de>
date
Sun, 03 Nov 2024 16:08:15 +0100
changeset 980
98af3fbc847f
parent 930
6540096c17b7
permissions
-rw-r--r--

remove obsolete reference to previously removed cxPropertiesInput()

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
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
41 #include "collection.h"
827
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 /**
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
48 * A depth-first tree iterator.
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
49 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
50 * This iterator is not position-aware in a strict sense, as it does not assume
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
51 * a particular order of elements in the tree. However, the iterator keeps track
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
52 * of the number of nodes it has passed in a counter variable.
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
53 * 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
54 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
55 * @note Objects that are pointed to by an iterator are mutable through that
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
56 * iterator. However, if the
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
57 * underlying data structure is mutated by other means than this iterator (e.g.
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
58 * elements added or removed), the iterator becomes invalid (regardless of what
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
59 * cxIteratorValid() returns).
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
60 *
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
61 * @see CxIterator
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
62 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
63 typedef struct cx_tree_iterator_s {
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
64 /**
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
65 * Base members.
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
66 */
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
67 CX_ITERATOR_BASE;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
68 /**
848
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
69 * Indicates whether the subtree below the current node shall be skipped.
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
70 */
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
71 bool skip;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
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 * 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
74 * 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
75 */
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
76 bool visit_on_exit;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
77 /**
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
78 * 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
79 */
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
80 bool exiting;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
81 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
82 * 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
83 */
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
84 ptrdiff_t loc_children;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
85 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
86 * 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
87 */
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
88 ptrdiff_t loc_next;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
89 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
90 * 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
91 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
92 size_t counter;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
93 /**
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
94 * The currently observed node.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
95 *
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
96 * 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
97 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
98 void *node;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
99 /**
840
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 835
diff changeset
100 * 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
101 * 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
102 */
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 848
diff changeset
103 void *node_next;
840
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 835
diff changeset
104 /**
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
105 * Internal stack.
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
106 * 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
107 *
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
108 * 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
109 * call cxTreeIteratorDispose().
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
110 */
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
111 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
112 /**
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
113 * 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
114 */
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
115 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
116 union {
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
117 /**
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
118 * Internal stack size.
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
119 */
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
120 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
121 /**
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
122 * 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
123 */
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
124 size_t depth;
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
125 };
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
126 } CxTreeIterator;
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
127
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
128 /**
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
129 * An element in a visitor queue.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
130 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
131 struct cx_tree_visitor_queue_s {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
132 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
133 * The tree node to visit.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
134 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
135 void *node;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
136 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
137 * The depth of the node.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
138 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
139 size_t depth;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
140 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
141 * The next element in the queue or \c NULL.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
142 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
143 struct cx_tree_visitor_queue_s *next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
144 };
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
145
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
146 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
147 * A breadth-first tree iterator.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
148 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
149 * This iterator needs to maintain a visitor queue that will be automatically
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
150 * freed once the iterator becomes invalid.
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
151 * If you want to discard the iterator before, you MUST manually call
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
152 * cxTreeVisitorDispose().
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
153 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
154 * This iterator is not position-aware in a strict sense, as it does not assume
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
155 * a particular order of elements in the tree. However, the iterator keeps track
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
156 * of the number of nodes it has passed in a counter variable.
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
157 * Each node, regardless of the number of passes, is counted only once.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
158 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
159 * @note Objects that are pointed to by an iterator are mutable through that
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
160 * iterator. However, if the
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
161 * underlying data structure is mutated by other means than this iterator (e.g.
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
162 * elements added or removed), the iterator becomes invalid (regardless of what
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
163 * cxIteratorValid() returns).
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
164 *
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
165 * @see CxIterator
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
166 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
167 typedef struct cx_tree_visitor_s {
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
168 /**
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
169 * Base members.
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
170 */
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
171 CX_ITERATOR_BASE;
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
172 /**
848
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
173 * Indicates whether the subtree below the current node shall be skipped.
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
174 */
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
175 bool skip;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
176 /**
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
177 * Offset in the node struct for the children linked list.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
178 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
179 ptrdiff_t loc_children;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
180 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
181 * Offset in the node struct for the next pointer.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
182 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
183 ptrdiff_t loc_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
184 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
185 * The total number of distinct nodes that have been passed so far.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
186 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
187 size_t counter;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
188 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
189 * The currently observed node.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
190 *
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
191 * This is the same what cxIteratorCurrent() would return.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
192 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
193 void *node;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
194 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
195 * The current depth in the tree.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
196 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
197 size_t depth;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
198 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
199 * The next element in the visitor queue.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
200 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
201 struct cx_tree_visitor_queue_s *queue_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
202 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
203 * The last element in the visitor queue.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
204 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
205 struct cx_tree_visitor_queue_s *queue_last;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
206 } CxTreeVisitor;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
207
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
208 /**
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
209 * 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
210 * @param iter the iterator
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
211 */
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
212 __attribute__((__nonnull__))
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
213 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
214 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
215 iter->stack = NULL;
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
216 }
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
217
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
218 /**
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
219 * Releases internal memory of the given tree visitor.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
220 * @param visitor the visitor
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
221 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
222 __attribute__((__nonnull__))
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
223 static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
224 struct cx_tree_visitor_queue_s *q = visitor->queue_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
225 while (q != NULL) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
226 struct cx_tree_visitor_queue_s *next = q->next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
227 free(q);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
228 q = next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
229 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
230 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
231
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
232 /**
848
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
233 * Advises the iterator to skip the subtree below the current node and
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
234 * also continues the current loop.
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
235 *
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
236 * @param iterator the iterator
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
237 */
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
238 #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
239
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
240 /**
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
241 * Advises the visitor to skip the subtree below the current node and
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
242 * also continues the current loop.
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
243 *
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
244 * @param visitor the visitor
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
245 */
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
246 #define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
247
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
248 /**
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
249 * Links a node to a (new) parent.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
250 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
251 * If the node has already a parent, it is unlinked, first.
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
252 * If the parent has children already, the node is \em appended to the list
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
253 * of all currently existing children.
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
254 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
255 * @param parent the parent node
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
256 * @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
257 * @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
258 * @param loc_children offset in the node struct for the children linked list
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
259 * @param loc_last_child optional offset in the node struct for the pointer to
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
260 * the last child in the linked list (negative if there is no such pointer)
921
5a7aa9cf9c3a make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents: 918
diff changeset
261 * @param loc_prev optional offset in the node struct for the prev pointer
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
262 * @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
263 * @see cx_tree_unlink()
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
264 */
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
265 __attribute__((__nonnull__))
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
266 void cx_tree_link(
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
267 void *restrict parent,
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
268 void *restrict node,
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
269 ptrdiff_t loc_parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
270 ptrdiff_t loc_children,
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
271 ptrdiff_t loc_last_child,
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
272 ptrdiff_t loc_prev,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
273 ptrdiff_t loc_next
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
274 );
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
275
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
276 /**
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
277 * Unlinks a node from its parent.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
278 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
279 * 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
280 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
281 * @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
282 * @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
283 * @param loc_children offset in the node struct for the children linked list
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
284 * @param loc_last_child optional offset in the node struct for the pointer to
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
285 * the last child in the linked list (negative if there is no such pointer)
921
5a7aa9cf9c3a make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents: 918
diff changeset
286 * @param loc_prev optional offset in the node struct for the prev pointer
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
287 * @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
288 * @see cx_tree_link()
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
289 */
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
290 __attribute__((__nonnull__))
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
291 void cx_tree_unlink(
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
292 void *node,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
293 ptrdiff_t loc_parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
294 ptrdiff_t loc_children,
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
295 ptrdiff_t loc_last_child,
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
296 ptrdiff_t loc_prev,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
297 ptrdiff_t loc_next
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
298 );
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
299
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
300 /**
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
301 * Macro that can be used instead of the magic value for infinite search depth.
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
302 */
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
303 #define CX_TREE_SEARCH_INFINITE_DEPTH 0
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
304
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
305 /**
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
306 * Function pointer for a search function.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
307 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
308 * 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
309 * 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
310 * the data.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
311 *
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
312 * 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
313 * match is, where a negative number means that it does not match at all.
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
314 * Zero means exact match and a positive number is an implementation defined
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
315 * measure for the distance to an exact match.
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
316 *
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
317 * 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
318 * 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
319 * 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
320 * 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
321 * prefix of the searched filename, the function would return -1 to indicate
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
322 * 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
323 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
324 * @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
325 * @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
326 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
327 * @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
328 * 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
329 * 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
330 */
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
331 typedef int (*cx_tree_search_data_func)(const void *node, const void *data);
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
332
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
333
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
334 /**
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
335 * Function pointer for a search function.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
336 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
337 * A function of this kind shall check if the specified \p node
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
338 * contains the same \p data as \p new_node or if one of the children might
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
339 * contain the data.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
340 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
341 * The function should use the returned integer to indicate how close the
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
342 * match is, where a negative number means that it does not match at all.
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
343 * Zero means exact match and a positive number is an implementation defined
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
344 * measure for the distance to an exact match.
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
345 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
346 * For example if a tree stores file path information, a node that is
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
347 * describing a parent directory of a filename that is searched, shall
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
348 * return a positive number to indicate that a child node might contain the
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
349 * searched item. On the other hand, if the node denotes a path that is not a
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
350 * prefix of the searched filename, the function would return -1 to indicate
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
351 * that the search does not need to be continued in that branch.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
352 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
353 * @param node the node that is currently investigated
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
354 * @param new_node a new node with the information which is searched
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
355 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
356 * @return 0 if \p node contains the same data as \p new_node,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
357 * positive if one of the children might contain the data,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
358 * negative if neither the node, nor the children contains the data
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
359 */
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
360 typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
361
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
362 /**
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
363 * Searches for data in a tree.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
364 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
365 * 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
366 * closest result which might be a good starting point for adding a new node
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
367 * to the tree (see also #cx_tree_add()).
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
368 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
369 * 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
370 * "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
371 * 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
372 * \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
373 * node matching the criteria is returned.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
374 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
375 * @param root the root node
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
376 * @param depth the maximum depth (zero=indefinite, one=just root)
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
377 * @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
378 * @param sfunc the search function
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
379 * @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
380 * @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
381 * @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
382 * @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
383 * 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
384 * 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
385 */
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
386 __attribute__((__nonnull__))
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
387 int cx_tree_search_data(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
388 const void *root,
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
389 size_t depth,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
390 const void *data,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
391 cx_tree_search_data_func sfunc,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
392 void **result,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
393 ptrdiff_t loc_children,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
394 ptrdiff_t loc_next
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
395 );
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
396
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
397 /**
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
398 * Searches for a node in a tree.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
399 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
400 * When no node with the same data can be found, the search function might
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
401 * return a closest result which might be a good starting point for adding the
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
402 * new node to the tree (see also #cx_tree_add()).
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
403 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
404 * Depending on the tree structure it is not necessarily guaranteed that the
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
405 * "closest" match is uniquely defined. This function will search for a node
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
406 * with the best match according to the \p sfunc (meaning: the return value of
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
407 * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
408 * node matching the criteria is returned.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
409 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
410 * @param root the root node
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
411 * @param depth the maximum depth (zero=indefinite, one=just root)
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
412 * @param node the node to search for
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
413 * @param sfunc the search function
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
414 * @param result where the result shall be stored
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
415 * @param loc_children offset in the node struct for the children linked list
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
416 * @param loc_next offset in the node struct for the next pointer
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
417 * @return zero if the node was found exactly, positive if a node was found that
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
418 * could contain the node (but doesn't right now), negative if the tree does not
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
419 * contain any node that might be related to the searched data
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
420 */
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
421 __attribute__((__nonnull__))
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
422 int cx_tree_search(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
423 const void *root,
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
424 size_t depth,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
425 const void *node,
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
426 cx_tree_search_func sfunc,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
427 void **result,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
428 ptrdiff_t loc_children,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
429 ptrdiff_t loc_next
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
430 );
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
431
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
432 /**
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
433 * Creates a depth-first iterator for a tree with the specified root node.
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
434 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
435 * @note A tree iterator needs to maintain a stack of visited nodes, which is
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
436 * allocated using stdlib malloc().
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
437 * When the iterator becomes invalid, this memory is automatically released.
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
438 * However, if you wish to cancel the iteration before the iterator becomes
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
439 * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
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
440 * 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
441 *
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
442 * @remark The returned iterator does not support cxIteratorFlagRemoval().
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
443 *
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
444 * @param root the root node
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
445 * @param visit_on_exit set to true, when the iterator shall visit a node again
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
446 * 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
447 * @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
448 * @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
449 * @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
450 * @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
451 */
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 828
diff changeset
452 CxTreeIterator cx_tree_iterator(
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 828
diff changeset
453 void *root,
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
454 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
455 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
456 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
457 );
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
458
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
459 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
460 * Creates a breadth-first iterator for a tree with the specified root node.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
461 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
462 * @note A tree visitor needs to maintain a queue of to be visited nodes, which
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
463 * is allocated using stdlib malloc().
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
464 * When the visitor becomes invalid, this memory is automatically released.
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
465 * However, if you wish to cancel the iteration before the visitor becomes
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
466 * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
467 * the memory.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
468 *
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
469 * @remark The returned iterator does not support cxIteratorFlagRemoval().
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
470 *
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
471 * @param root the root node
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
472 * @param loc_children offset in the node struct for the children linked list
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
473 * @param loc_next offset in the node struct for the next pointer
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
474 * @return the new tree visitor
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
475 * @see cxTreeVisitorDispose()
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
476 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
477 CxTreeVisitor cx_tree_visitor(
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
478 void *root,
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
479 ptrdiff_t loc_children,
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
480 ptrdiff_t loc_next
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
481 );
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
482
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
483 /**
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
484 * Describes a function that creates a tree node from the specified data.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
485 * The first argument points to the data the node shall contain and
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
486 * the second argument may be used for additional data (e.g. an allocator).
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
487 * Functions of this type shall either return a new pointer to a newly
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
488 * created node or \c NULL when allocation fails.
865
4b325b639117 fix return type of cx_tree_node_create_func
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
489 *
4b325b639117 fix return type of cx_tree_node_create_func
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
490 * \note the function may leave the node pointers in the struct uninitialized.
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
491 * The caller is responsible to set them according to the intended use case.
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
492 */
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
493 typedef void *(*cx_tree_node_create_func)(const void *, void *);
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
494
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
495 /**
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
496 * The local search depth for a new subtree when adding multiple elements.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
497 * The default value is 3.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
498 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
499 * implement optimized insertion of multiple elements into a tree.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
500 */
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
501 extern unsigned int cx_tree_add_look_around_depth;
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
502
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
503 /**
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
504 * Adds multiple elements efficiently to a tree.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
505 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
506 * Once an element cannot be added to the tree, this function returns, leaving
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
507 * the iterator in a valid state pointing to the element that could not be
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
508 * added.
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
509 * Also, the pointer of the created node will be stored to \p failed.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
510 * The integer returned by this function denotes the number of elements obtained
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
511 * from the \p iter that have been successfully processed.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
512 * When all elements could be processed, a \c NULL pointer will be written to
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
513 * \p failed.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
514 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
515 * The advantage of this function compared to multiple invocations of
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
516 * #cx_tree_add() is that the search for the insert locations is not always
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
517 * started from the root node.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
518 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
519 * of the current insert location before starting from the root node again.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
520 * When the variable is set to zero, only the last found location is checked
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
521 * again.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
522 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
523 * Refer to the documentation of #cx_tree_add() for more details.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
524 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
525 * @param iter a pointer to an arbitrary iterator
893
0a2b328f5b91 add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
526 * @param num the maximum number of elements to obtain from the iterator
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
527 * @param sfunc a search function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
528 * @param cfunc a node creation function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
529 * @param cdata optional additional data
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
530 * @param root the root node of the tree
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
531 * @param failed location where the pointer to a failed node shall be stored
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
532 * @param loc_parent offset in the node struct for the parent pointer
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
533 * @param loc_children offset in the node struct for the children linked list
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
534 * @param loc_last_child optional offset in the node struct for the pointer to
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
535 * the last child in the linked list (negative if there is no such pointer)
921
5a7aa9cf9c3a make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents: 918
diff changeset
536 * @param loc_prev optional offset in the node struct for the prev pointer
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
537 * @param loc_next offset in the node struct for the next pointer
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
538 * @return the number of nodes created and added
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
539 * @see cx_tree_add()
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
540 */
893
0a2b328f5b91 add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
541 __attribute__((__nonnull__(1, 3, 4, 6, 7)))
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
542 size_t cx_tree_add_iter(
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
543 struct cx_iterator_base_s *iter,
893
0a2b328f5b91 add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
544 size_t num,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
545 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
546 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
547 void *cdata,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
548 void **failed,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
549 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
550 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
551 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
552 ptrdiff_t loc_last_child,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
553 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
554 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
555 );
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
556
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
557 /**
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
558 * Adds multiple elements efficiently to a tree.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
559 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
560 * Once an element cannot be added to the tree, this function returns, storing
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
561 * the pointer of the created node to \p failed.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
562 * The integer returned by this function denotes the number of elements from
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
563 * the \p src array that have been successfully processed.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
564 * When all elements could be processed, a \c NULL pointer will be written to
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
565 * \p failed.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
566 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
567 * The advantage of this function compared to multiple invocations of
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
568 * #cx_tree_add() is that the search for the insert locations is not always
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
569 * started from the root node.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
570 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
571 * of the current insert location before starting from the root node again.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
572 * When the variable is set to zero, only the last found location is checked
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
573 * again.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
574 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
575 * Refer to the documentation of #cx_tree_add() for more details.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
576 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
577 * @param src a pointer to the source data array
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
578 * @param num the number of elements in the \p src array
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
579 * @param elem_size the size of each element in the \p src array
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
580 * @param sfunc a search function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
581 * @param cfunc a node creation function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
582 * @param cdata optional additional data
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
583 * @param failed location where the pointer to a failed node shall be stored
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
584 * @param root the root node of the tree
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
585 * @param loc_parent offset in the node struct for the parent pointer
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
586 * @param loc_children offset in the node struct for the children linked list
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
587 * @param loc_last_child optional offset in the node struct for the pointer to
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
588 * the last child in the linked list (negative if there is no such pointer)
921
5a7aa9cf9c3a make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents: 918
diff changeset
589 * @param loc_prev optional offset in the node struct for the prev pointer
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
590 * @param loc_next offset in the node struct for the next pointer
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
591 * @return the number of array elements successfully processed
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
592 * @see cx_tree_add()
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
593 */
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
594 __attribute__((__nonnull__(1, 4, 5, 7, 8)))
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
595 size_t cx_tree_add_array(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
596 const void *src,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
597 size_t num,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
598 size_t elem_size,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
599 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
600 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
601 void *cdata,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
602 void **failed,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
603 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
604 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
605 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
606 ptrdiff_t loc_last_child,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
607 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
608 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
609 );
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
610
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
611 /**
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
612 * Adds data to a tree.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
613 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
614 * An adequate location where to add the new tree node is searched with the
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
615 * specified \p sfunc.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
616 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
617 * When a location is found, the \p cfunc will be invoked with \p cdata.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
618 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
619 * The node returned by \p cfunc will be linked into the tree.
867
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 865
diff changeset
620 * When \p sfunc returned a positive integer, the new node will be linked as a
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
621 * child. The other children (now siblings of the new node) are then checked
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
622 * with \p sfunc, whether they could be children of the new node and re-linked
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
623 * accordingly.
867
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 865
diff changeset
624 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
625 * When \p sfunc returned zero and the found node has a parent, the new
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
626 * node will be added as sibling - otherwise, the new node will be added
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
627 * as a child.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
628 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
629 * When \p sfunc returned a negative value, the new node will not be added to
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
630 * the tree and this function returns a non-zero value.
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
631 * The caller should check if \p cnode contains a node pointer and deal with the
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
632 * node that could not be added.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
633 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
634 * This function also returns a non-zero value when \p cfunc tries to allocate
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
635 * a new node but fails to do so. In that case, the pointer stored to \p cnode
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
636 * will be \c NULL.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
637 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
638 * Multiple elements can be added more efficiently with
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
639 * #cx_tree_add_array() or #cx_tree_add_iter().
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
640 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
641 * @param src a pointer to the data
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
642 * @param sfunc a search function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
643 * @param cfunc a node creation function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
644 * @param cdata optional additional data
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
645 * @param cnode the location where a pointer to the new node is stored
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
646 * @param root the root node of the tree
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
647 * @param loc_parent offset in the node struct for the parent pointer
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
648 * @param loc_children offset in the node struct for the children linked list
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
649 * @param loc_last_child optional offset in the node struct for the pointer to
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
650 * the last child in the linked list (negative if there is no such pointer)
921
5a7aa9cf9c3a make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents: 918
diff changeset
651 * @param loc_prev optional offset in the node struct for the prev pointer
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
652 * @param loc_next offset in the node struct for the next pointer
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
653 * @return zero when a new node was created and added to the tree,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
654 * non-zero otherwise
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
655 */
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
656 __attribute__((__nonnull__(1, 2, 3, 5, 6)))
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
657 int cx_tree_add(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
658 const void *src,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
659 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
660 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
661 void *cdata,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
662 void **cnode,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
663 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
664 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
665 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
666 ptrdiff_t loc_last_child,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
667 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
668 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
669 );
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
670
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
671
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
672 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
673 * Tree class type.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
674 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
675 typedef struct cx_tree_class_s cx_tree_class;
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
676
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
677 /**
897
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
678 * Base structure that can be used for tree nodes in a #CxTree.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
679 */
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
680 struct cx_tree_node_base_s {
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
681 /**
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
682 * Pointer to the parent.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
683 */
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
684 struct cx_tree_node_base_s *parent;
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
685 /**
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
686 * Pointer to the first child.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
687 */
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
688 struct cx_tree_node_base_s *children;
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
689 /**
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
690 * Pointer to the last child.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
691 */
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
692 struct cx_tree_node_base_s *last_child;
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
693 /**
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
694 * Pointer to the previous sibling.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
695 */
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
696 struct cx_tree_node_base_s *prev;
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
697 /**
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
698 * Pointer to the next sibling.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
699 */
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
700 struct cx_tree_node_base_s *next;
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
701 };
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
702
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
703 /**
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
704 * Structure for holding the base data of a tree.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
705 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
706 struct cx_tree_s {
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
707 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
708 * The tree class definition.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
709 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
710 const cx_tree_class *cl;
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
711
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
712 /**
897
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
713 * Allocator to allocate new nodes.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
714 */
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
715 const CxAllocator *allocator;
897
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
716
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
717 /**
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
718 * A pointer to the root node.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
719 *
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
720 * Will be \c NULL when \c size is 0.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
721 */
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
722 void *root;
897
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
723
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
724 /**
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
725 * A function to create new nodes.
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
726 *
897
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
727 * Invocations to this function will receive a pointer to this tree
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
728 * structure as second argument.
0936916856a2 add allocator and root node pointer to tree structure
Mike Becker <universe@uap-core.de>
parents: 896
diff changeset
729 *
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
730 * Nodes MAY use #cx_tree_node_base_s as base layout, but do not need to.
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
731 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
732 cx_tree_node_create_func node_create;
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
733
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
734 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
735 * An optional simple destructor for the tree nodes.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
736 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
737 cx_destructor_func simple_destructor;
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
738
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
739 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
740 * An optional advanced destructor for the tree nodes.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
741 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
742 cx_destructor_func2 advanced_destructor;
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
743
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
744 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
745 * The pointer to additional data that is passed to the advanced destructor.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
746 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
747 void *destructor_data;
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
748
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
749 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
750 * A function to compare two nodes.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
751 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
752 cx_tree_search_func search;
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
753
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
754 /**
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
755 * A function to compare a node with data.
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
756 */
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
757 cx_tree_search_data_func search_data;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
758
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
759 /**
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
760 * The number of currently stored elements.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
761 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
762 size_t size;
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
763
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
764 /**
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
765 * Offset in the node struct for the parent pointer.
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
766 */
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
767 ptrdiff_t loc_parent;
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
768
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
769 /**
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
770 * Offset in the node struct for the children linked list.
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
771 */
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
772 ptrdiff_t loc_children;
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
773
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
774 /**
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
775 * Optional offset in the node struct for the pointer to the last child
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
776 * in the linked list (negative if there is no such pointer).
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
777 */
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
778 ptrdiff_t loc_last_child;
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
779
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
780 /**
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
781 * Offset in the node struct for the previous sibling pointer.
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
782 */
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
783 ptrdiff_t loc_prev;
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
784
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
785 /**
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
786 * Offset in the node struct for the next sibling pointer.
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
787 */
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
788 ptrdiff_t loc_next;
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
789 };
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
790
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
791 /**
895
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
792 * Macro to roll out the #cx_tree_node_base_s structure with a custom
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
793 * node type.
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
794 */
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
795 #define CX_TREE_NODE_BASE(type) \
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
796 type *parent; \
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
797 type *children;\
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
798 type *last_child;\
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
799 type *prev;\
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
800 type *next
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
801
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
802 /**
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
803 * Macro for specifying the layout of a base node tree.
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
804 */
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
805 #define cx_tree_node_base_layout \
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
806 offsetof(struct cx_tree_node_base_s, parent),\
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
807 offsetof(struct cx_tree_node_base_s, children),\
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
808 offsetof(struct cx_tree_node_base_s, last_child),\
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
809 offsetof(struct cx_tree_node_base_s, prev), \
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
810 offsetof(struct cx_tree_node_base_s, next)
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
811
ea1ac0e8225c provide a default tree node layout, but do not make it mandatory
Mike Becker <universe@uap-core.de>
parents: 894
diff changeset
812 /**
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
813 * Macro for obtaining the node pointer layout for a specific tree.
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
814 */
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
815 #define cx_tree_node_layout(tree) \
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
816 (tree)->loc_parent,\
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
817 (tree)->loc_children,\
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
818 (tree)->loc_last_child,\
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
819 (tree)->loc_prev, \
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
820 (tree)->loc_next
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
821
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
822 /**
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
823 * The class definition for arbitrary trees.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
824 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
825 struct cx_tree_class_s {
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
826 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
827 * Member function for inserting a single element.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
828 *
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
829 * Implementations SHALL NOT simply invoke \p insert_many as this comes
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
830 * with too much overhead.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
831 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
832 int (*insert_element)(
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
833 struct cx_tree_s *tree,
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
834 const void *data
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
835 );
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
836
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
837 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
838 * Member function for inserting multiple elements.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
839 *
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
840 * Implementations SHALL avoid to perform a full search in the tree for
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
841 * every element even though the source data MAY be unsorted.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
842 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
843 size_t (*insert_many)(
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
844 struct cx_tree_s *tree,
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
845 struct cx_iterator_base_s *iter,
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
846 size_t n
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
847 );
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
848
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
849 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
850 * Member function for finding a node.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
851 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
852 void *(*find)(
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
853 struct cx_tree_s *tree,
896
7e09c76390c3 allow find() member function to start in an arbitrary subtree
Mike Becker <universe@uap-core.de>
parents: 895
diff changeset
854 const void *subtree,
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
855 const void *data,
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
856 size_t depth
894
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
857 );
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
858 };
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
859
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
860 /**
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
861 * Common type for all tree implementations.
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
862 */
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
863 typedef struct cx_tree_s CxTree;
89cd8dfdc3c2 first draft of a class for high level trees
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
864
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
865 /**
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
866 * Creates a new tree structure based on the specified layout.
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
867 *
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
868 * The specified \p allocator will be used for creating the tree struct
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
869 * and SHALL be used by \p create_func to allocate memory for the nodes.
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
870 *
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
871 * \note This function will also register an advanced destructor which
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
872 * will free the nodes with the allocator's free() method.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
873 *
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
874 * @param allocator the allocator that shall be used
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
875 * @param create_func a function that creates new nodes
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
876 * @param search_func a function that compares two nodes
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
877 * @param search_data_func a function that compares a node with data
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
878 * @param loc_parent offset in the node struct for the parent pointer
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
879 * @param loc_children offset in the node struct for the children linked list
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
880 * @param loc_last_child optional offset in the node struct for the pointer to
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
881 * the last child in the linked list (negative if there is no such pointer)
921
5a7aa9cf9c3a make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents: 918
diff changeset
882 * @param loc_prev optional offset in the node struct for the prev pointer
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
883 * @param loc_next offset in the node struct for the next pointer
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
884 * @return the new tree
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
885 * @see cxTreeCreateSimple()
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
886 * @see cxTreeCreateWrapped()
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
887 */
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
888 __attribute__((__nonnull__, __warn_unused_result__))
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
889 CxTree *cxTreeCreate(
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
890 const CxAllocator *allocator,
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
891 cx_tree_node_create_func create_func,
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
892 cx_tree_search_func search_func,
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
893 cx_tree_search_data_func search_data_func,
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
894 ptrdiff_t loc_parent,
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
895 ptrdiff_t loc_children,
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
896 ptrdiff_t loc_last_child,
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
897 ptrdiff_t loc_prev,
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
898 ptrdiff_t loc_next
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
899 );
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
900
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
901 /**
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
902 * Creates a new tree structure based on a default layout.
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
903 *
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
904 * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
905 * member (or at least respect the default offsets specified in the tree
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
906 * struct) and they MUST be allocated with the specified allocator.
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
907 *
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
908 * \note This function will also register an advanced destructor which
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
909 * will free the nodes with the allocator's free() method.
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
910 *
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
911 * @param allocator the allocator that shall be used
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
912 * @param create_func a function that creates new nodes
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
913 * @param search_func a function that compares two nodes
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
914 * @param search_data_func a function that compares a node with data
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
915 * @return the new tree
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
916 * @see cxTreeCreate()
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
917 */
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
918 __attribute__((__nonnull__, __warn_unused_result__))
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
919 static inline CxTree *cxTreeCreateSimple(
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
920 const CxAllocator *allocator,
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
921 cx_tree_node_create_func create_func,
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
922 cx_tree_search_func search_func,
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
923 cx_tree_search_data_func search_data_func
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
924 ) {
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
925 return cxTreeCreate(
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
926 allocator,
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
927 create_func,
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
928 search_func,
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
929 search_data_func,
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
930 cx_tree_node_base_layout
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
931 );
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
932 }
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
933
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
934 /**
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
935 * Creates a new tree structure based on an existing tree.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
936 *
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
937 * The specified \p allocator will be used for creating the tree struct.
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
938 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
939 * \attention This function will create an incompletely defined tree structure
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
940 * where neither the create function, the search function, nor a destructor
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
941 * will be set. If you wish to use any of this functionality for the wrapped
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
942 * tree, you need to specify those functions afterwards.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
943 *
927
71e7e9ba4b97 fix missing parameter doc
Mike Becker <universe@uap-core.de>
parents: 921
diff changeset
944 * @param allocator the allocator that was used for nodes of the wrapped tree
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
945 * @param root the root node of the tree that shall be wrapped
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
946 * @param loc_parent offset in the node struct for the parent pointer
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
947 * @param loc_children offset in the node struct for the children linked list
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
948 * @param loc_last_child optional offset in the node struct for the pointer to
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
949 * the last child in the linked list (negative if there is no such pointer)
921
5a7aa9cf9c3a make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents: 918
diff changeset
950 * @param loc_prev optional offset in the node struct for the prev pointer
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
951 * @param loc_next offset in the node struct for the next pointer
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
952 * @return the new tree
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
953 * @see cxTreeCreate()
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
954 */
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
955 __attribute__((__nonnull__, __warn_unused_result__))
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
956 CxTree *cxTreeCreateWrapped(
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
957 const CxAllocator *allocator,
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
958 void *root,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
959 ptrdiff_t loc_parent,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
960 ptrdiff_t loc_children,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
961 ptrdiff_t loc_last_child,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
962 ptrdiff_t loc_prev,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
963 ptrdiff_t loc_next
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
964 );
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
965
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
966 /**
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
967 * Inserts data into the tree.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
968 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
969 * \remark For this function to work, the tree needs specified search and
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
970 * create functions, which might not be available for wrapped trees
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
971 * (see #cxTreeCreateWrapped()).
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
972 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
973 * @param tree the tree
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
974 * @param data the data to insert
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
975 * @return zero on success, non-zero on failure
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
976 */
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
977 __attribute__((__nonnull__))
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
978 static inline int cxTreeInsert(
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
979 CxTree *tree,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
980 const void *data
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
981 ) {
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
982 return tree->cl->insert_element(tree, data);
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
983 }
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
984
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
985 /**
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
986 * Inserts elements provided by an iterator efficiently into the tree.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
987 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
988 * \remark For this function to work, the tree needs specified search and
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
989 * create functions, which might not be available for wrapped trees
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
990 * (see #cxTreeCreateWrapped()).
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
991 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
992 * @param tree the tree
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
993 * @param iter the iterator providing the elements
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
994 * @param n the maximum number of elements to insert
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
995 * @return the number of elements that could be successfully inserted
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
996 */
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
997 __attribute__((__nonnull__))
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
998 static inline size_t cxTreeInsertIter(
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
999 CxTree *tree,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1000 struct cx_iterator_base_s *iter,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1001 size_t n
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1002 ) {
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1003 return tree->cl->insert_many(tree, iter, n);
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1004 }
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1005
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1006 /**
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1007 * Inserts an array of data efficiently into the tree.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1008 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1009 * \remark For this function to work, the tree needs specified search and
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1010 * create functions, which might not be available for wrapped trees
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1011 * (see #cxTreeCreateWrapped()).
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1012 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1013 * @param tree the tree
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1014 * @param data the array of data to insert
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1015 * @param elem_size the size of each element in the array
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1016 * @param n the number of elements in the array
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1017 * @return the number of elements that could be successfully inserted
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1018 */
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1019 __attribute__((__nonnull__))
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1020 static inline size_t cxTreeInsertArray(
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1021 CxTree *tree,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1022 const void *data,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1023 size_t elem_size,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1024 size_t n
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1025 ) {
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1026 if (n == 0) return 0;
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1027 if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1028 CxIterator iter = cxIterator(data, elem_size, n);
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
1029 return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1030 }
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1031
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1032 /**
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1033 * Searches the data in the specified tree.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1034 *
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1035 * \remark For this function to work, the tree needs a specified \c search_data
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1036 * function, which might not be available wrapped trees
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1037 * (see #cxTreeCreateWrapped()).
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1038 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1039 * @param tree the tree
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1040 * @param data the data to search for
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1041 * @return the first matching node, or \c NULL when the data cannot be found
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1042 */
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1043 __attribute__((__nonnull__))
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1044 static inline void *cxTreeFind(
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1045 CxTree *tree,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1046 const void *data
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1047 ) {
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1048 return tree->cl->find(tree, tree->root, data, 0);
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1049 }
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1050
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1051 /**
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1052 * Searches the data in the specified subtree.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1053 *
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1054 * When \p max_depth is zero, the depth is not limited.
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1055 * The \p subtree_root itself is on depth 1 and its children have depth 2.
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1056 *
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1057 * \note When \p subtree_root is not part of the \p tree, the behavior is
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1058 * undefined.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1059 *
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1060 * \remark For this function to work, the tree needs a specified \c search_data
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1061 * function, which might not be the case for wrapped trees
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1062 * (see #cxTreeCreateWrapped()).
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1063 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1064 * @param tree the tree
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1065 * @param data the data to search for
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1066 * @param subtree_root the node where to start
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1067 * @param max_depth the maximum search depth
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1068 * @return the first matching node, or \c NULL when the data cannot be found
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1069 */
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1070 __attribute__((__nonnull__))
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1071 static inline void *cxTreeFindInSubtree(
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1072 CxTree *tree,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1073 const void *data,
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1074 void *subtree_root,
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1075 size_t max_depth
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1076 ) {
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1077 return tree->cl->find(tree, subtree_root, data, max_depth);
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1078 }
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1079
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1080 /**
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1081 * Determines the size of the specified subtree.
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1082 *
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1083 * @param tree the tree
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1084 * @param subtree_root the root node of the subtree
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1085 * @return the number of nodes in the specified subtree
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1086 */
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1087 __attribute__((__nonnull__))
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1088 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1089
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
1090 /**
903
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1091 * Determines the depth of the specified subtree.
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1092 *
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1093 * @param tree the tree
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1094 * @param subtree_root the root node of the subtree
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1095 * @return the tree depth including the \p subtree_root
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1096 */
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1097 __attribute__((__nonnull__))
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1098 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1099
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
1100 /**
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1101 * Determines the depth of the entire tree.
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1102 *
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1103 * @param tree the tree
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1104 * @return the tree depth, counting the root as one
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1105 */
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1106 __attribute__((__nonnull__))
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1107 size_t cxTreeDepth(CxTree *tree);
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1108
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1109 /**
917
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1110 * Creates a depth-first iterator for the specified tree starting in \p node.
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1111 *
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1112 * If the node is not part of the tree, the behavior is undefined.
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1113 *
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1114 * @param tree the tree to iterate
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1115 * @param node the node where to start
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1116 * @param visit_on_exit true, if the iterator shall visit a node again when
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1117 * leaving the subtree
917
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1118 * @return a tree iterator (depth-first)
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1119 * @see cxTreeVisit()
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1120 */
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1121 __attribute__((__nonnull__, __warn_unused_result__))
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1122 static inline CxTreeIterator cxTreeIterateSubtree(
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1123 CxTree *tree,
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1124 void *node,
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1125 bool visit_on_exit
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1126 ) {
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1127 return cx_tree_iterator(
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1128 node, visit_on_exit,
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1129 tree->loc_children, tree->loc_next
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1130 );
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1131 }
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1132
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1133 /**
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1134 * Creates a breadth-first iterator for the specified tree starting in \p node.
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1135 *
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1136 * If the node is not part of the tree, the behavior is undefined.
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1137 *
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1138 * @param tree the tree to iterate
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1139 * @param node the node where to start
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1140 * @return a tree visitor (a.k.a. breadth-first iterator)
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1141 * @see cxTreeIterate()
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1142 */
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1143 __attribute__((__nonnull__, __warn_unused_result__))
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1144 static inline CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1145 return cx_tree_visitor(
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1146 node, tree->loc_children, tree->loc_next
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1147 );
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1148 }
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1149
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1150 /**
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1151 * Creates a depth-first iterator for the specified tree.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1152 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1153 * @param tree the tree to iterate
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1154 * @param visit_on_exit true, if the iterator shall visit a node again when
930
6540096c17b7 add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents: 927
diff changeset
1155 * leaving the subtree
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1156 * @return a tree iterator (depth-first)
917
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1157 * @see cxTreeVisit()
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1158 */
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1159 __attribute__((__nonnull__, __warn_unused_result__))
917
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1160 static inline CxTreeIterator cxTreeIterate(
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1161 CxTree *tree,
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1162 bool visit_on_exit
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1163 ) {
917
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1164 return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1165 }
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1166
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1167 /**
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1168 * Creates a breadth-first iterator for the specified tree.
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1169 *
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1170 * @param tree the tree to iterate
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1171 * @return a tree visitor (a.k.a. breadth-first iterator)
917
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1172 * @see cxTreeIterate()
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1173 */
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1174 __attribute__((__nonnull__, __warn_unused_result__))
917
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1175 static inline CxTreeVisitor cxTreeVisit(CxTree *tree) {
ff8ad2c9e1bd add functions to start iteration in a subtree
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
1176 return cxTreeVisitSubtree(tree, tree->root);
899
303a981e6834 more prototypes for tree functions
Mike Becker <universe@uap-core.de>
parents: 898
diff changeset
1177 }
898
9b2c12494ccf prototypes for create and destroy functions
Mike Becker <universe@uap-core.de>
parents: 897
diff changeset
1178
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1179 /**
918
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1180 * Sets the (new) parent of the specified child.
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1181 *
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1182 * If the \p child is not already member of the tree, this function behaves
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1183 * as #cxTreeAddChildNode().
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1184 *
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1185 * @param tree the tree
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1186 * @param parent the (new) parent of the child
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1187 * @param child the node to add
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1188 * @see cxTreeAddChildNode()
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1189 */
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1190 __attribute__((__nonnull__))
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1191 void cxTreeSetParent(
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1192 CxTree *tree,
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1193 void *parent,
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1194 void *child
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1195 );
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1196
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1197 /**
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1198 * Adds a new node to the tree.
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1199 *
918
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1200 * If the \p child is already member of the tree, the behavior is undefined.
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1201 * Use #cxTreeSetParent() if you want to move a subtree to another location.
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1202 *
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1203 * \attention The node may be externally created, but MUST obey the same rules
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1204 * as if it was created by the tree itself with #cxTreeAddChild() (e.g. use
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1205 * the same allocator).
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1206 *
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1207 * @param tree the tree
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1208 * @param parent the parent of the node to add
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1209 * @param child the node to add
918
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1210 * @see cxTreeSetParent()
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1211 */
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1212 __attribute__((__nonnull__))
918
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1213 void cxTreeAddChildNode(
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1214 CxTree *tree,
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1215 void *parent,
918
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1216 void *child
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 917
diff changeset
1217 );
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1218
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1219 /**
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1220 * Creates a new node and adds it to the tree.
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1221 *
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1222 * With this function you can decide where exactly the new node shall be added.
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1223 * If you specified an appropriate search function, you may want to consider
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1224 * leaving this task to the tree by using #cxTreeInsert().
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1225 *
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1226 * Be aware that adding nodes at arbitrary locations in the tree might cause
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1227 * wrong or undesired results when subsequently invoking #cxTreeInsert() and
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1228 * the invariant imposed by the search function does not hold any longer.
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1229 *
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1230 * @param tree the tree
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1231 * @param parent the parent node of the new node
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1232 * @param data the data that will be submitted to the create function
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1233 * @return zero when the new node was created, non-zero on allocation failure
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1234 * @see cxTreeInsert()
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1235 */
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1236 __attribute__((__nonnull__))
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1237 int cxTreeAddChild(
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1238 CxTree *tree,
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1239 void *parent,
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1240 const void *data
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1241 );
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1242
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1243 /**
909
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1244 * A function that is invoked when a node needs to be re-linked to a new parent.
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1245 *
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1246 * When a node is re-linked, sometimes the contents need to be updated.
913
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1247 * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1248 * so that those updates can be applied when re-linking the children of the
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1249 * removed node.
909
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1250 *
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1251 * @param node the affected node
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1252 * @param old_parent the old parent of the node
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1253 * @param new_parent the new parent of the node
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1254 */
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1255 typedef void (*cx_tree_relink_func)(
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1256 void *node,
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1257 const void *old_parent,
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1258 const void *new_parent
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1259 );
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1260
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1261 /**
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1262 * Removes a node and re-links its children to its former parent.
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1263 *
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1264 * If the node is not part of the tree, the behavior is undefined.
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1265 *
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1266 * \note The destructor function, if any, will \em not be invoked. That means
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1267 * you will need to free the removed node by yourself, eventually.
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1268 *
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1269 * @param tree the tree
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1270 * @param node the node to remove (must not be the root node)
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1271 * @param relink_func optional callback to update the content of each re-linked
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1272 * node
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1273 * @return zero on success, non-zero if \p node is the root node of the tree
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1274 */
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1275 __attribute__((__nonnull__(1,2)))
913
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1276 int cxTreeRemoveNode(
909
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1277 CxTree *tree,
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1278 void *node,
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1279 cx_tree_relink_func relink_func
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1280 );
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1281
f4e00bb3f3b2 implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents: 908
diff changeset
1282 /**
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1283 * Removes a node and it's subtree from the tree.
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1284 *
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1285 * If the node is not part of the tree, the behavior is undefined.
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1286 *
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1287 * \note The destructor function, if any, will \em not be invoked. That means
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
1288 * you will need to free the removed subtree by yourself, eventually.
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1289 *
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1290 * @param tree the tree
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1291 * @param node the node to remove
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1292 */
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1293 __attribute__((__nonnull__))
908
f49f8a7060aa rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents: 905
diff changeset
1294 void cxTreeRemoveSubtree(CxTree *tree, void *node);
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 900
diff changeset
1295
913
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1296 /**
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1297 * Destroys a node and re-links its children to its former parent.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1298 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1299 * If the node is not part of the tree, the behavior is undefined.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1300 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1301 * It is guaranteed that the simple destructor is invoked before
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1302 * the advanced destructor.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1303 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1304 * \attention This function will not free the memory of the node with the
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1305 * tree's allocator, because that is usually done by the advanced destructor
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1306 * and would therefore result in a double-free.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1307 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1308 * @param tree the tree
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1309 * @param node the node to destroy (must not be the root node)
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1310 * @param relink_func optional callback to update the content of each re-linked
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1311 * node
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1312 * @return zero on success, non-zero if \p node is the root node of the tree
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1313 */
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1314 __attribute__((__nonnull__(1,2)))
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1315 int cxTreeDestroyNode(
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1316 CxTree *tree,
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1317 void *node,
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1318 cx_tree_relink_func relink_func
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1319 );
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1320
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1321 /**
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1322 * Destroys a node and it's subtree.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1323 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1324 * It is guaranteed that the simple destructor is invoked before
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1325 * the advanced destructor, starting with the leaf nodes of the subtree.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1326 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1327 * When this function is invoked on the root node of the tree, it destroys the
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1328 * tree contents, but - in contrast to #cxTreeDestroy() - not the tree
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1329 * structure, leaving an empty tree behind.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1330 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1331 * \note The destructor function, if any, will \em not be invoked. That means
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1332 * you will need to free the removed subtree by yourself, eventually.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1333 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1334 * \attention This function will not free the memory of the nodes with the
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1335 * tree's allocator, because that is usually done by the advanced destructor
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1336 * and would therefore result in a double-free.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1337 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1338 * @param tree the tree
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1339 * @param node the node to remove
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1340 * @see cxTreeDestroy()
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1341 */
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1342 __attribute__((__nonnull__))
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1343 void cxTreeDestroySubtree(CxTree *tree, void *node);
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1344
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1345
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1346 /**
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1347 * Destroys the tree contents.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1348 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1349 * It is guaranteed that the simple destructor is invoked before
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1350 * the advanced destructor, starting with the leaf nodes of the subtree.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1351 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1352 * This is a convenience macro for invoking #cxTreeDestroySubtree() on the
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1353 * root node of the tree.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1354 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1355 * \attention Be careful when calling this function when no destructor function
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1356 * is registered that actually frees the memory of nodes. In that case you will
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1357 * need a reference to the (former) root node of the tree somewhere or
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1358 * otherwise you will be leaking memory.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1359 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1360 * @param tree the tree
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1361 * @see cxTreeDestroySubtree()
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1362 */
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1363 #define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1364
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1365 /**
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1366 * Destroys the tree structure.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1367 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1368 * The destructor functions are invoked for each node, starting with the leaf
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1369 * nodes.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1370 * It is guaranteed that for each node the simple destructor is invoked before
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1371 * the advanced destructor.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1372 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1373 * \attention This function will only invoke the destructor functions
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1374 * on the nodes.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1375 * It will NOT additionally free the nodes with the tree's allocator, because
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1376 * that would cause a double-free in most scenarios where the advanced
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1377 * destructor is already freeing the memory.
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1378 *
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1379 * @param tree the tree to destroy
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1380 */
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1381 __attribute__((__nonnull__))
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1382 static inline void cxTreeDestroy(CxTree *tree) {
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1383 if (tree->root != NULL) {
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1384 cxTreeDestroySubtree(tree, tree->root);
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1385 }
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1386 cxFree(tree->allocator, tree);
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1387 }
72db8e42b95e implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents: 909
diff changeset
1388
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1389 #ifdef __cplusplus
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1390 } // extern "C"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1391 #endif
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1392
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1393 #endif //UCX_TREE_H

mercurial