Tue, 20 Aug 2024 13:36:56 +0200
fix cx_tree_search() not remembering root as a valid candidate
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 | #include "cx/tree.h" |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
30 | |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
31 | #include "cx/array_list.h" |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
32 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
33 | #include <assert.h> |
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 | #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
36 | #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
37 | #define tree_parent(node) CX_TREE_PTR(node, loc_parent) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
38 | #define tree_children(node) CX_TREE_PTR(node, loc_children) |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
39 | #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child) |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
40 | #define tree_prev(node) CX_TREE_PTR(node, loc_prev) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
41 | #define tree_next(node) CX_TREE_PTR(node, loc_next) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
42 | |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
43 | #define cx_tree_ptr_locations \ |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
44 | loc_parent, loc_children, loc_last_child, loc_prev, loc_next |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
45 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
46 | static void cx_tree_zero_pointers( |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
47 | void *node, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
48 | ptrdiff_t loc_parent, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
49 | ptrdiff_t loc_children, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
50 | ptrdiff_t loc_last_child, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
51 | ptrdiff_t loc_prev, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
52 | ptrdiff_t loc_next |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
53 | ) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
54 | tree_parent(node) = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
55 | tree_prev(node) = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
56 | tree_next(node) = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
57 | tree_children(node) = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
58 | if (loc_last_child >= 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
59 | tree_last_child(node) = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
60 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
61 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
62 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
63 | void cx_tree_link( |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
64 | void *restrict parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
65 | void *restrict node, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
66 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
67 | ptrdiff_t loc_children, |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
68 | ptrdiff_t loc_last_child, |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
69 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
70 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
71 | ) { |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
72 | void *current_parent = tree_parent(node); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
73 | if (current_parent == parent) return; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
74 | if (current_parent != NULL) { |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
75 | cx_tree_unlink(node, cx_tree_ptr_locations); |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
76 | } |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
77 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
78 | if (tree_children(parent) == NULL) { |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
79 | tree_children(parent) = node; |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
80 | if (loc_last_child >= 0) { |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
81 | tree_last_child(parent) = node; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
82 | } |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
83 | } else { |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
84 | if (loc_last_child >= 0) { |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
85 | void *child = tree_last_child(parent); |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
86 | tree_prev(node) = child; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
87 | tree_next(child) = node; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
88 | tree_last_child(parent) = node; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
89 | } else { |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
90 | void *child = tree_children(parent); |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
91 | void *next; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
92 | while ((next = tree_next(child)) != NULL) { |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
93 | child = next; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
94 | } |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
95 | tree_prev(node) = child; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
96 | tree_next(child) = node; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
97 | } |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
98 | } |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
99 | tree_parent(node) = parent; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
100 | } |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
101 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
102 | void cx_tree_unlink( |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
103 | void *node, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
104 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
105 | ptrdiff_t loc_children, |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
106 | ptrdiff_t loc_last_child, |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
107 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
108 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
109 | ) { |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
110 | if (tree_parent(node) == NULL) return; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
111 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
112 | void *left = tree_prev(node); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
113 | void *right = tree_next(node); |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
114 | void *parent = tree_parent(node); |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
115 | assert(left == NULL || tree_children(parent) != node); |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
116 | assert(right == NULL || loc_last_child < 0 || |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
117 | tree_last_child(parent) != node); |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
118 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
119 | if (left == NULL) { |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
120 | tree_children(parent) = right; |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
121 | } else { |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
122 | tree_next(left) = right; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
123 | } |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
124 | if (right == NULL) { |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
125 | if (loc_last_child >= 0) { |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
126 | tree_last_child(parent) = left; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
127 | } |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
128 | } else { |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
129 | tree_prev(right) = left; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
130 | } |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
131 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
132 | tree_parent(node) = NULL; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
133 | tree_prev(node) = NULL; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
134 | tree_next(node) = NULL; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
135 | } |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
136 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
137 | int cx_tree_search( |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
138 | void const *root, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
139 | void const *data, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
140 | cx_tree_search_func sfunc, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
141 | void **result, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
142 | ptrdiff_t loc_children, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
143 | ptrdiff_t loc_next |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
144 | ) { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
145 | int ret; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
146 | *result = NULL; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
147 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
148 | // shortcut: compare root before doing anything else |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
149 | ret = sfunc(root, data); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
150 | if (ret < 0) { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
151 | return ret; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
152 | } else if (ret == 0 || tree_children(root) == NULL) { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
153 | *result = (void*)root; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
154 | return ret; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
155 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
156 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
157 | // create a working stack |
834
04c53b3c8378
capitalize cx_array_declare()
Mike Becker <universe@uap-core.de>
parents:
833
diff
changeset
|
158 | CX_ARRAY_DECLARE(void const*, work); |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
159 | cx_array_initialize(work, 32); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
160 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
161 | // add the children of root to the working stack |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
162 | { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
163 | void *c = tree_children(root); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
164 | while (c != NULL) { |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
165 | cx_array_simple_add(work, c); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
166 | c = tree_next(c); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
167 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
168 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
169 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
170 | // remember a candidate for adding the data |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
171 | // also remember the exact return code from sfunc |
869
9e7f0db6a725
fix cx_tree_search() not remembering root as a valid candidate
Mike Becker <universe@uap-core.de>
parents:
868
diff
changeset
|
172 | void *candidate = (void *) root; |
9e7f0db6a725
fix cx_tree_search() not remembering root as a valid candidate
Mike Becker <universe@uap-core.de>
parents:
868
diff
changeset
|
173 | int ret_candidate = ret; |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
174 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
175 | // process the working stack |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
176 | while (work_size > 0) { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
177 | // pop element |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
178 | void const *node = work[--work_size]; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
179 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
180 | // apply the search function |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
181 | ret = sfunc(node, data); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
182 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
183 | if (ret == 0) { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
184 | // if found, exit the search |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
185 | *result = (void*) node; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
186 | work_size = 0; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
187 | break; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
188 | } else if (ret > 0) { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
189 | // if children might contain the data, add them to the stack |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
190 | void *c = tree_children(node); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
191 | while (c != NULL) { |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
192 | cx_array_simple_add(work, c); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
193 | c = tree_next(c); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
194 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
195 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
196 | // remember this node in case no child is suitable |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
197 | if (ret_candidate < 0 || ret < ret_candidate) { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
198 | candidate = (void *) node; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
199 | ret_candidate = ret; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
200 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
201 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
202 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
203 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
204 | // not found, but was there a candidate? |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
205 | if (ret != 0 && candidate != NULL) { |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
206 | ret = ret_candidate; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
207 | *result = candidate; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
208 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
209 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
210 | // free the working queue and return |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
211 | free(work); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
212 | return ret; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
213 | } |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
214 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
215 | static bool cx_tree_iter_valid(void const *it) { |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
216 | struct cx_tree_iterator_s const *iter = it; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
217 | return iter->node != NULL; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
218 | } |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
219 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
220 | static void *cx_tree_iter_current(void const *it) { |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
221 | struct cx_tree_iterator_s const *iter = it; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
222 | return iter->node; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
223 | } |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
224 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
225 | static void cx_tree_iter_next(void *it) { |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
226 | struct cx_tree_iterator_s *iter = it; |
845 | 227 | ptrdiff_t const loc_next = iter->loc_next; |
228 | ptrdiff_t const loc_children = iter->loc_children; | |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
229 | |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
230 | void *children; |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
231 | |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
232 | // check if we are currently exiting or entering nodes |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
233 | if (iter->exiting) { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
234 | children = NULL; |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
235 | // skipping on exit is pointless, just clear the flag |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
236 | iter->skip = false; |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
237 | } else { |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
238 | if (iter->skip) { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
239 | // skip flag is set, pretend that there are no children |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
240 | iter->skip = false; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
241 | children = NULL; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
242 | } else { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
243 | // try to enter the children (if any) |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
244 | children = tree_children(iter->node); |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
245 | } |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
246 | } |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
247 | |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
248 | if (children == NULL) { |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
249 | // search for the next node |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
250 | void *next; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
251 | cx_tree_iter_search_next: |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
252 | // check if there is a sibling |
840
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
838
diff
changeset
|
253 | if (iter->exiting) { |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
254 | next = iter->node_next; |
840
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
838
diff
changeset
|
255 | } else { |
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
838
diff
changeset
|
256 | next = tree_next(iter->node); |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
257 | iter->node_next = next; |
840
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
838
diff
changeset
|
258 | } |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
259 | if (next == NULL) { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
260 | // no sibling, we are done with this node and exit |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
261 | if (iter->visit_on_exit && !iter->exiting) { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
262 | // iter is supposed to visit the node again |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
263 | iter->exiting = true; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
264 | } else { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
265 | iter->exiting = false; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
266 | if (iter->depth == 1) { |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
267 | // there is no parent - we have iterated the entire tree |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
268 | // invalidate the iterator and free the node stack |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
269 | iter->node = iter->node_next = NULL; |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
270 | iter->stack_capacity = iter->depth = 0; |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
271 | free(iter->stack); |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
272 | iter->stack = NULL; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
273 | } else { |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
274 | // the parent node can be obtained from the top of stack |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
275 | // this way we can avoid the loc_parent in the iterator |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
276 | iter->depth--; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
277 | iter->node = iter->stack[iter->depth - 1]; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
278 | // retry with the parent node to find a sibling |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
279 | goto cx_tree_iter_search_next; |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
280 | } |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
281 | } |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
282 | } else { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
283 | if (iter->visit_on_exit && !iter->exiting) { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
284 | // iter is supposed to visit the node again |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
285 | iter->exiting = true; |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
286 | } else { |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
287 | iter->exiting = false; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
288 | // move to the sibling |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
289 | iter->counter++; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
290 | iter->node = next; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
291 | // new top of stack is the sibling |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
292 | iter->stack[iter->depth - 1] = next; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
293 | } |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
294 | } |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
295 | } else { |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
296 | // node has children, push the first child onto the stack and enter it |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
297 | cx_array_simple_add(iter->stack, children); |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
298 | iter->node = children; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
299 | iter->counter++; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
300 | } |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
301 | } |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
302 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
303 | CxTreeIterator cx_tree_iterator( |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
304 | void *root, |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
305 | bool visit_on_exit, |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
306 | ptrdiff_t loc_children, |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
307 | ptrdiff_t loc_next |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
308 | ) { |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
309 | CxTreeIterator iter; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
310 | iter.loc_children = loc_children; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
311 | iter.loc_next = loc_next; |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
312 | iter.visit_on_exit = visit_on_exit; |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
313 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
314 | // allocate stack |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
315 | iter.stack_capacity = 16; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
316 | iter.stack = malloc(sizeof(void *) * 16); |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
317 | iter.depth = 0; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
318 | |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
319 | // visit the root node |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
320 | iter.node = root; |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
321 | iter.node_next = NULL; |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
322 | iter.counter = 1; |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
323 | iter.depth = 1; |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
324 | iter.stack[0] = root; |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
325 | iter.exiting = false; |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
326 | iter.skip = false; |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
327 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
328 | // assign base iterator functions |
854
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
329 | iter.base.mutating = false; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
330 | iter.base.remove = false; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
331 | iter.base.current_impl = NULL; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
332 | iter.base.valid = cx_tree_iter_valid; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
333 | iter.base.next = cx_tree_iter_next; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
334 | iter.base.current = cx_tree_iter_current; |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
335 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
336 | return iter; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
337 | } |
845 | 338 | |
339 | static bool cx_tree_visitor_valid(void const *it) { | |
340 | struct cx_tree_visitor_s const *iter = it; | |
341 | return iter->node != NULL; | |
342 | } | |
343 | ||
344 | static void *cx_tree_visitor_current(void const *it) { | |
345 | struct cx_tree_visitor_s const *iter = it; | |
346 | return iter->node; | |
347 | } | |
348 | ||
349 | __attribute__((__nonnull__)) | |
350 | static void cx_tree_visitor_enqueue_siblings( | |
351 | struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { | |
352 | node = tree_next(node); | |
353 | while (node != NULL) { | |
354 | struct cx_tree_visitor_queue_s *q; | |
355 | q = malloc(sizeof(struct cx_tree_visitor_queue_s)); | |
356 | q->depth = iter->queue_last->depth; | |
357 | q->node = node; | |
358 | iter->queue_last->next = q; | |
359 | iter->queue_last = q; | |
360 | node = tree_next(node); | |
361 | } | |
362 | iter->queue_last->next = NULL; | |
363 | } | |
364 | ||
365 | static void cx_tree_visitor_next(void *it) { | |
366 | struct cx_tree_visitor_s *iter = it; | |
367 | ptrdiff_t const loc_next = iter->loc_next; | |
368 | ptrdiff_t const loc_children = iter->loc_children; | |
369 | ||
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
370 | // add the children of the current node to the queue |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
371 | // unless the skip flag is set |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
372 | void *children; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
373 | if (iter->skip) { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
374 | iter->skip = false; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
375 | children = NULL; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
376 | } else { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
377 | children = tree_children(iter->node); |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
378 | } |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
379 | if (children != NULL) { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
380 | struct cx_tree_visitor_queue_s *q; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
381 | q = malloc(sizeof(struct cx_tree_visitor_queue_s)); |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
382 | q->depth = iter->depth + 1; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
383 | q->node = children; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
384 | if (iter->queue_last == NULL) { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
385 | assert(iter->queue_next == NULL); |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
386 | iter->queue_next = q; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
387 | } else { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
388 | iter->queue_last->next = q; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
389 | } |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
390 | iter->queue_last = q; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
391 | cx_tree_visitor_enqueue_siblings(iter, children, loc_next); |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
392 | } |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
393 | |
845 | 394 | // check if there is a next node |
395 | if (iter->queue_next == NULL) { | |
396 | iter->node = NULL; | |
397 | return; | |
398 | } | |
399 | ||
400 | // dequeue the next node | |
401 | iter->node = iter->queue_next->node; | |
402 | iter->depth = iter->queue_next->depth; | |
403 | { | |
404 | struct cx_tree_visitor_queue_s *q = iter->queue_next; | |
405 | iter->queue_next = q->next; | |
406 | if (iter->queue_next == NULL) { | |
407 | assert(iter->queue_last == q); | |
408 | iter->queue_last = NULL; | |
409 | } | |
410 | free(q); | |
411 | } | |
412 | ||
413 | // increment the node counter | |
414 | iter->counter++; | |
415 | } | |
416 | ||
417 | CxTreeVisitor cx_tree_visitor( | |
418 | void *root, | |
419 | ptrdiff_t loc_children, | |
420 | ptrdiff_t loc_next | |
421 | ) { | |
422 | CxTreeVisitor iter; | |
423 | iter.loc_children = loc_children; | |
424 | iter.loc_next = loc_next; | |
425 | ||
426 | // allocate stack | |
427 | iter.depth = 0; | |
428 | ||
429 | // visit the root node | |
430 | iter.node = root; | |
431 | iter.counter = 1; | |
432 | iter.depth = 1; | |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
433 | iter.skip = false; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
434 | iter.queue_next = NULL; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
435 | iter.queue_last = NULL; |
845 | 436 | |
437 | // assign base iterator functions | |
854
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
438 | iter.base.mutating = false; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
439 | iter.base.remove = false; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
440 | iter.base.current_impl = NULL; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
441 | iter.base.valid = cx_tree_visitor_valid; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
442 | iter.base.next = cx_tree_visitor_next; |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
443 | iter.base.current = cx_tree_visitor_current; |
845 | 444 | |
445 | return iter; | |
446 | } | |
447 | ||
867
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
448 | static void cx_tree_add_link_duplicate( |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
449 | void **root, void *original, void *duplicate, |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
450 | ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
451 | ptrdiff_t loc_prev, ptrdiff_t loc_next |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
452 | ) { |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
453 | cx_tree_zero_pointers(duplicate, cx_tree_ptr_locations); |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
454 | void *shared_parent = tree_parent(original); |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
455 | if (shared_parent == NULL) { |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
456 | cx_tree_link(duplicate, original, cx_tree_ptr_locations); |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
457 | *root = duplicate; |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
458 | } else { |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
459 | cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations); |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
460 | } |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
461 | } |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
462 | |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
463 | void *cx_tree_add( |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
464 | void const *src, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
465 | cx_tree_search_func sfunc, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
466 | cx_tree_node_create_func cfunc, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
467 | void *cdata, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
468 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
469 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
470 | ptrdiff_t loc_children, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
471 | ptrdiff_t loc_last_child, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
472 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
473 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
474 | ) { |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
475 | if (*root == NULL) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
476 | void *node = cfunc(src, NULL, cdata); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
477 | if (node == NULL) return NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
478 | cx_tree_zero_pointers(node, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
479 | *root = node; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
480 | return node; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
481 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
482 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
483 | void *match = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
484 | int result = cx_tree_search( |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
485 | *root, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
486 | src, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
487 | sfunc, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
488 | &match, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
489 | loc_children, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
490 | loc_next |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
491 | ); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
492 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
493 | void *node; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
494 | if (result < 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
495 | // new node is created as new parent |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
496 | node = cfunc(src, NULL, cdata); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
497 | if (node == NULL) return NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
498 | cx_tree_zero_pointers(node, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
499 | cx_tree_link(node, *root, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
500 | *root = node; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
501 | } else if (result == 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
502 | // data already found in the tree, let cfunc decide |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
503 | node = cfunc(src, match, cdata); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
504 | if (node == NULL) return NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
505 | if (node != match) { |
867
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
506 | cx_tree_add_link_duplicate( |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
507 | root, match, node, cx_tree_ptr_locations); |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
508 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
509 | } else { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
510 | // closest match found, add new node as child |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
511 | node = cfunc(src, NULL, cdata); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
512 | if (node == NULL) return NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
513 | cx_tree_zero_pointers(node, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
514 | cx_tree_link(match, node, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
515 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
516 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
517 | return node; |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
518 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
519 | |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
520 | unsigned int cx_tree_add_look_around_depth = 3; |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
521 | |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
522 | size_t cx_tree_add_iter( |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
523 | struct cx_iterator_base_s *iter, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
524 | cx_tree_search_func sfunc, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
525 | cx_tree_node_create_func cfunc, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
526 | void *cdata, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
527 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
528 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
529 | ptrdiff_t loc_children, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
530 | ptrdiff_t loc_last_child, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
531 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
532 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
533 | ) { |
868
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
534 | // iter not valid? cancel... |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
535 | if (!iter->valid(iter)) return 0; |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
536 | |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
537 | size_t processed = 0; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
538 | void *current_node = *root; |
868
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
539 | void *elem; |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
540 | |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
541 | // if there is no root, yet - process the first node from the iter |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
542 | // as the new root node |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
543 | if (current_node == NULL) { |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
544 | elem = *(void **) (iter->current(iter)); |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
545 | // no node in tree, yet - add a new one |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
546 | current_node = cfunc(elem, NULL, cdata); |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
547 | // node creation failed - stop processing |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
548 | if (current_node == NULL) return 0; |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
549 | cx_tree_zero_pointers(current_node, cx_tree_ptr_locations); |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
550 | *root = current_node; |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
551 | processed++; |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
552 | iter->next(iter); |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
553 | } |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
554 | |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
555 | for (void **eptr; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
556 | iter->valid(iter) && (eptr = iter->current(iter)) != NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
557 | iter->next(iter)) { |
868
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
558 | elem = *eptr; |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
559 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
560 | // start searching from current node |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
561 | void *match; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
562 | int result; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
563 | unsigned int look_around_retries = cx_tree_add_look_around_depth; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
564 | cx_tree_add_look_around_retry: |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
565 | result = cx_tree_search( |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
566 | current_node, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
567 | elem, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
568 | sfunc, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
569 | &match, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
570 | loc_children, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
571 | loc_next |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
572 | ); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
573 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
574 | void *node; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
575 | if (result < 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
576 | // traverse upwards and try to find better parents |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
577 | void *parent = tree_parent(current_node); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
578 | if (parent != NULL) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
579 | if (look_around_retries > 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
580 | look_around_retries--; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
581 | current_node = parent; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
582 | } else { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
583 | // look around retries exhausted, start from the root |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
584 | current_node = *root; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
585 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
586 | goto cx_tree_add_look_around_retry; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
587 | } else { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
588 | // no parents. so we (try to) create a new root node |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
589 | void *new_root = cfunc(elem, NULL, cdata); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
590 | if (new_root == NULL) return processed; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
591 | cx_tree_zero_pointers(new_root, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
592 | cx_tree_link(new_root, current_node, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
593 | current_node = new_root; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
594 | *root = new_root; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
595 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
596 | } else if (result == 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
597 | // data already found in the tree, let cfunc decide |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
598 | node = cfunc(elem, match, cdata); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
599 | if (node == NULL) return processed; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
600 | if (node != match) { |
867
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
601 | cx_tree_add_link_duplicate( |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
602 | root, match, node, cx_tree_ptr_locations); |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
603 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
604 | current_node = node; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
605 | } else { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
606 | // closest match found, add new node as child |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
607 | node = cfunc(elem, NULL, cdata); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
608 | if (node == NULL) return processed; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
609 | cx_tree_zero_pointers(node, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
610 | cx_tree_link(match, node, cx_tree_ptr_locations); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
611 | // but make the match current and not the new node |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
612 | // (usually saves one traversal when a lot of siblings are added) |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
613 | current_node = match; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
614 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
615 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
616 | processed++; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
617 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
618 | return processed; |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
619 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
620 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
621 | size_t cx_tree_add_array( |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
622 | void const *src, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
623 | size_t num, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
624 | size_t elem_size, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
625 | cx_tree_search_func sfunc, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
626 | cx_tree_node_create_func cfunc, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
627 | void *cdata, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
628 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
629 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
630 | ptrdiff_t loc_children, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
631 | ptrdiff_t loc_last_child, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
632 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
633 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
634 | ) { |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
635 | // super special case: zero elements |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
636 | if (num == 0) { |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
637 | return 0; |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
638 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
639 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
640 | // special case: one element does not need an iterator |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
641 | if (num == 1) { |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
642 | if (NULL != cx_tree_add( |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
643 | src, sfunc, cfunc, cdata, root, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
644 | loc_parent, loc_children, loc_last_child, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
645 | loc_prev, loc_next)) { |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
646 | return 1; |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
647 | } else { |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
648 | return 0; |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
649 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
650 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
651 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
652 | // otherwise, create iterator and hand over to other function |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
653 | CxIterator iter = cxIterator(src, elem_size, num); |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
654 | return cx_tree_add_iter(cxIteratorRef(iter), sfunc, cfunc, cdata, root, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
655 | loc_parent, loc_children, loc_last_child, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
656 | loc_prev, loc_next); |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
657 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
658 |