src/cx/tree.h

Mon, 16 Sep 2024 19:52:17 +0200

author
Mike Becker <universe@uap-core.de>
date
Mon, 16 Sep 2024 19:52:17 +0200
changeset 881
1dbbf8c1c42f
parent 871
e29c1f96646d
child 890
54565fd74e74
permissions
-rw-r--r--

add optimized implementation of insert_sorted for array lists

relates to #416

816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
28 /**
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
29 * \file tree.h
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
30 * \brief Interface for tree implementations.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
31 * \author Mike Becker
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
32 * \author Olaf Wintermann
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
33 * \copyright 2-Clause BSD License
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
34 */
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
35
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
36 #ifndef UCX_TREE_H
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37 #define UCX_TREE_H
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
38
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
39 #include "common.h"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
40
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
41 #include "iterator.h"
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
42
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
43 #ifdef __cplusplus
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
44 extern "C" {
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
45 #endif
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
46
827
13b40a598d16 first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
47 /**
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)
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
261 * @param loc_prev offset in the node struct for the prev pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
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)
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
286 * @param loc_prev offset in the node struct for the prev pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
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 /**
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
301 * Function pointer for a search function.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
302 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
303 * 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
304 * 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
305 * the data.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
306 *
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
307 * 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
308 * match is, where a negative number means that it does not match at all.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
309 *
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
310 * 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
311 * 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
312 * 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
313 * 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
314 * 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
315 * 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
316 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
317 * @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
318 * @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
319 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
320 * @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
321 * 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
322 * 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
323 */
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
324 typedef int (*cx_tree_search_data_func)(void const *node, void const *data);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
325
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
326
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
327 /**
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
328 * 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
329 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
330 * 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
331 * 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
332 * 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
333 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
334 * 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
335 * match is, where a negative number means that it does not match at all.
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 * 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
338 * 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
339 * 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
340 * 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
341 * 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
342 * 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
343 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
344 * @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
345 * @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
346 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
347 * @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
348 * 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
349 * 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
350 */
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
351 typedef int (*cx_tree_search_func)(void const *node, void const *new_node);
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
352
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
353 /**
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
354 * Searches for data in a tree.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
355 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
356 * 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
357 * 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
358 * 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
359 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
360 * 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
361 * "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
362 * 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
363 * \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
364 * node matching the criteria is returned.
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
365 *
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
366 * @param root the root node
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
367 * @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
368 * @param sfunc the search function
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
369 * @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
370 * @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
371 * @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
372 * @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
373 * 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
374 * 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
375 */
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
376 __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
377 int cx_tree_search_data(
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
378 void const *root,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
379 void const *data,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
380 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
381 void **result,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
382 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
383 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
384 );
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
385
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
386 /**
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
387 * 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
388 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
389 * 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
390 * 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
391 * 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
392 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
393 * 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
394 * "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
395 * 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
396 * \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
397 * 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
398 *
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
399 * @param root the root node
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
400 * @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
401 * @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
402 * @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
403 * @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
404 * @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
405 * @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
406 * 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
407 * 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
408 */
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
409 __attribute__((__nonnull__))
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
410 int cx_tree_search(
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
411 void const *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 void const *node,
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
413 cx_tree_search_func sfunc,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
414 void **result,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
415 ptrdiff_t loc_children,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
416 ptrdiff_t loc_next
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
417 );
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 824
diff changeset
418
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
419 /**
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
420 * 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
421 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
422 * @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
423 * allocated using stdlib malloc().
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
424 * When the iterator becomes invalid, this memory is automatically released.
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
425 * 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
426 * 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
427 * 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
428 *
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
429 * @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
430 *
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
431 * @param root the root node
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
432 * @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
433 * 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
434 * @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
435 * @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
436 * @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
437 * @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
438 */
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
439 __attribute__((__nonnull__))
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 828
diff changeset
440 CxTreeIterator cx_tree_iterator(
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 828
diff changeset
441 void *root,
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
442 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
443 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
444 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
445 );
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
446
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
447 /**
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
448 * 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
449 *
859
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
450 * @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
451 * is allocated using stdlib malloc().
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
452 * When the visitor becomes invalid, this memory is automatically released.
6367456bf2d9 minor doc fixes
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
453 * 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
454 * 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
455 * the memory.
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
456 *
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
457 * @remark The returned iterator does not support cxIteratorFlagRemoval().
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
458 *
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
459 * @param root the root node
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
460 * @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
461 * @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
462 * @return the new tree visitor
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
463 * @see cxTreeVisitorDispose()
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
464 */
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
465 __attribute__((__nonnull__))
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
466 CxTreeVisitor cx_tree_visitor(
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
467 void *root,
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
468 ptrdiff_t loc_children,
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
469 ptrdiff_t loc_next
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
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
472 /**
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
473 * 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
474 * 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
475 * 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
476 * 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
477 * 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
478 *
4b325b639117 fix return type of cx_tree_node_create_func
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
479 * \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
480 * 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
481 */
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
482 typedef void *(*cx_tree_node_create_func)(void const *, void *);
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
483
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
484 /**
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
485 * 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
486 * The default value is 3.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
487 * 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
488 * 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
489 */
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
490 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
491
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
492 /**
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
493 * Adds multiple elements efficiently to a tree.
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 * 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
496 * 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
497 * added.
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
498 * 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
499 * 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
500 * 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
501 * 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
502 * \p failed.
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 * 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
505 * #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
506 * started from the root node.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
507 * 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
508 * 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
509 * 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
510 * again.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
511 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
512 * 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
513 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
514 * @param iter a pointer to an arbitrary iterator
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
515 * @param sfunc a search function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
516 * @param cfunc a node creation function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
517 * @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
518 * @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
519 * @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
520 * @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
521 * @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
522 * @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
523 * the last child in the linked list (negative if there is no such pointer)
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
524 * @param loc_prev offset in the node struct for the prev pointer
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
525 * @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
526 * @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
527 * @see cx_tree_add()
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
528 */
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
529 __attribute__((__nonnull__(1, 2, 3, 5, 6)))
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
530 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
531 struct cx_iterator_base_s *iter,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
532 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
533 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
534 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
535 void **failed,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
536 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
537 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
538 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
539 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
540 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
541 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
542 );
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
543
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
544 /**
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
545 * Adds multiple elements efficiently to a tree.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
546 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
547 * 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
548 * 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
549 * 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
550 * 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
551 * 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
552 * \p failed.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
553 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
554 * 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
555 * #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
556 * started from the root node.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
557 * 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
558 * 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
559 * 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
560 * again.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
561 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
562 * 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
563 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
564 * @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
565 * @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
566 * @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
567 * @param sfunc a search function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
568 * @param cfunc a node creation function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
569 * @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
570 * @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
571 * @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
572 * @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
573 * @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
574 * @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
575 * the last child in the linked list (negative if there is no such pointer)
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
576 * @param loc_prev offset in the node struct for the prev pointer
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
577 * @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
578 * @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
579 * @see cx_tree_add()
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
580 */
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
581 __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
582 size_t cx_tree_add_array(
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
583 void const *src,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
584 size_t num,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
585 size_t elem_size,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
586 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
587 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
588 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
589 void **failed,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
590 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
591 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
592 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
593 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
594 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
595 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
596 );
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
597
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
598 /**
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
599 * Adds data to a tree.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
600 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
601 * 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
602 * specified \p sfunc.
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
603 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
604 * 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
605 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
606 * 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
607 * 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
608 * 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
609 * 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
610 * accordingly.
867
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 865
diff changeset
611 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
612 * 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
613 * 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
614 * as a child.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
615 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
616 * 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
617 * 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
618 * 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
619 * node that could not be added.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
620 *
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
621 * 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
622 * 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
623 * will be \c NULL.
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
624 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
625 * 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
626 * #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
627 *
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
628 * @param src a pointer to the data
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
629 * @param sfunc a search function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
630 * @param cfunc a node creation function
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
631 * @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
632 * @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
633 * @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
634 * @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
635 * @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
636 * @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
637 * the last child in the linked list (negative if there is no such pointer)
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
638 * @param loc_prev offset in the node struct for the prev pointer
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
639 * @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
640 * @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
641 * non-zero otherwise
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
642 */
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
643 __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
644 int cx_tree_add(
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
645 void const *src,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
646 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
647 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
648 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
649 void **cnode,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
650 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
651 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
652 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
653 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
654 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
655 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
656 );
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 859
diff changeset
657
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
658 #ifdef __cplusplus
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
659 } // extern "C"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
660 #endif
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
661
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
662 #endif //UCX_TREE_H

mercurial