Sun, 22 Dec 2024 11:10:11 +0100
fix missing errno.h include
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 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
|
37 | #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
|
38 | #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
|
39 | #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
|
40 | #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
|
41 | |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
42 | #define cx_tree_ptr_locations \ |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
43 | 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
|
44 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
45 | static void cx_tree_zero_pointers( |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
46 | void *node, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
47 | ptrdiff_t loc_parent, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
48 | ptrdiff_t loc_children, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
49 | ptrdiff_t loc_last_child, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
50 | ptrdiff_t loc_prev, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
51 | ptrdiff_t loc_next |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
52 | ) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
53 | tree_parent(node) = NULL; |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
54 | if (loc_prev >= 0) { |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
55 | tree_prev(node) = NULL; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
56 | } |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
57 | tree_next(node) = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
58 | tree_children(node) = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
59 | if (loc_last_child >= 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
60 | tree_last_child(node) = NULL; |
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 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
63 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
64 | void cx_tree_link( |
988
15b3ca7ee33f
make ucx C++ compatible again (and add tests for it) - fixes #486
Mike Becker <universe@uap-core.de>
parents:
930
diff
changeset
|
65 | void *parent, |
15b3ca7ee33f
make ucx C++ compatible again (and add tests for it) - fixes #486
Mike Becker <universe@uap-core.de>
parents:
930
diff
changeset
|
66 | void *node, |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
67 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
68 | 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
|
69 | ptrdiff_t loc_last_child, |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
70 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
71 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
72 | ) { |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
73 | assert(loc_parent >= 0); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
74 | assert(loc_children >= 0); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
75 | assert(loc_next >= 0); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
76 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
77 | void *current_parent = tree_parent(node); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
78 | if (current_parent == parent) return; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
79 | if (current_parent != NULL) { |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
80 | 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
|
81 | } |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
82 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
83 | if (tree_children(parent) == NULL) { |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
84 | 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
|
85 | 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
|
86 | 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
|
87 | } |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
88 | } else { |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
89 | void *child; |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
90 | if (loc_last_child >= 0) { |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
91 | child = tree_last_child(parent); |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
92 | 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
|
93 | } else { |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
94 | child = tree_children(parent); |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
95 | void *next; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
96 | 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
|
97 | child = next; |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
98 | } |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
99 | } |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
100 | if (loc_prev >= 0) { |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
101 | 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
|
102 | } |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
103 | tree_next(child) = node; |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
104 | } |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
105 | tree_parent(node) = parent; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
106 | } |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
107 | |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
108 | static void *cx_tree_node_prev( |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
109 | ptrdiff_t loc_parent, |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
110 | ptrdiff_t loc_children, |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
111 | ptrdiff_t loc_next, |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
112 | const void *node |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
113 | ) { |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
114 | void *parent = tree_parent(node); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
115 | void *begin = tree_children(parent); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
116 | if (begin == node) return NULL; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
117 | const void *cur = begin; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
118 | const void *next; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
119 | while (1) { |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
120 | next = tree_next(cur); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
121 | if (next == node) return (void *) cur; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
122 | cur = next; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
123 | } |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
124 | } |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
125 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
126 | void cx_tree_unlink( |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
127 | void *node, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
128 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
129 | 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
|
130 | ptrdiff_t loc_last_child, |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
131 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
132 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
133 | ) { |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
134 | if (tree_parent(node) == NULL) return; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
135 | |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
136 | assert(loc_children >= 0); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
137 | assert(loc_next >= 0); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
138 | assert(loc_parent >= 0); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
139 | void *left; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
140 | if (loc_prev >= 0) { |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
141 | left = tree_prev(node); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
142 | } else { |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
143 | left = cx_tree_node_prev(loc_parent, loc_children, loc_next, node); |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
144 | } |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
145 | 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
|
146 | 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
|
147 | 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
|
148 | 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
|
149 | 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
|
150 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
151 | 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
|
152 | tree_children(parent) = right; |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
153 | } else { |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
154 | tree_next(left) = right; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
155 | } |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
156 | 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
|
157 | 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
|
158 | 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
|
159 | } |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
160 | } else { |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
161 | if (loc_prev >= 0) { |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
162 | tree_prev(right) = left; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
163 | } |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
164 | } |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
165 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
166 | tree_parent(node) = NULL; |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
167 | tree_next(node) = NULL; |
921
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
168 | if (loc_prev >= 0) { |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
169 | tree_prev(node) = NULL; |
5a7aa9cf9c3a
make loc_prev in trees optional - fixes #433
Mike Becker <universe@uap-core.de>
parents:
918
diff
changeset
|
170 | } |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
171 | } |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
172 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
173 | int cx_tree_search( |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
174 | const void *root, |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
175 | size_t depth, |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
176 | const void *node, |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
177 | cx_tree_search_func sfunc, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
178 | void **result, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
179 | ptrdiff_t loc_children, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
180 | ptrdiff_t loc_next |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
181 | ) { |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
182 | // help avoiding bugs due to uninitialized memory |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
183 | assert(result != NULL); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
184 | *result = NULL; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
185 | |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
186 | // remember return value for best match |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
187 | int ret = sfunc(root, node); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
188 | if (ret < 0) { |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
189 | // not contained, exit |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
190 | return -1; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
191 | } |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
192 | *result = (void*) root; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
193 | // if root is already exact match, exit |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
194 | if (ret == 0) { |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
195 | return 0; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
196 | } |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
197 | |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
198 | // when depth is one, we are already done |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
199 | if (depth == 1) { |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
200 | return ret; |
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 | |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
203 | // special case: indefinite depth |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
204 | if (depth == 0) { |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
205 | depth = SIZE_MAX; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
206 | } |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
207 | |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
208 | // create an iterator |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
209 | CxTreeIterator iter = cx_tree_iterator( |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
210 | (void*) root, false, loc_children, loc_next |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
211 | ); |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
212 | |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
213 | // skip root, we already handled it |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
214 | cxIteratorNext(iter); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
215 | |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
216 | // loop through the remaining tree |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
217 | cx_foreach(void *, elem, iter) { |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
218 | // investigate the current node |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
219 | int ret_elem = sfunc(elem, node); |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
220 | if (ret_elem == 0) { |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
221 | // if found, exit the search |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
222 | *result = (void *) elem; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
223 | ret = 0; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
224 | break; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
225 | } else if (ret_elem > 0 && ret_elem < ret) { |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
226 | // new distance is better |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
227 | *result = elem; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
228 | ret = ret_elem; |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
229 | } else { |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
230 | // not contained or distance is worse, skip entire subtree |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
231 | cxTreeIteratorContinue(iter); |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
232 | } |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
233 | |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
234 | // when we reached the max depth, skip the subtree |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
235 | if (iter.depth == depth) { |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
236 | cxTreeIteratorContinue(iter); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
237 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
238 | } |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
239 | |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
240 | // dispose the iterator as we might have exited the loop early |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
241 | cxTreeIteratorDispose(&iter); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
242 | |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
243 | assert(ret < 0 || *result != NULL); |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
244 | return ret; |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
245 | } |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
246 | |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
247 | int cx_tree_search_data( |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
248 | const void *root, |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
249 | size_t depth, |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
250 | const void *data, |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
251 | cx_tree_search_data_func sfunc, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
252 | void **result, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
253 | ptrdiff_t loc_children, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
254 | ptrdiff_t loc_next |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
255 | ) { |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
256 | // it is basically the same implementation |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
257 | return cx_tree_search( |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
258 | root, depth, data, |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
259 | (cx_tree_search_func) sfunc, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
260 | result, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
261 | loc_children, loc_next); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
262 | } |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
263 | |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
264 | static bool cx_tree_iter_valid(const void *it) { |
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
265 | const struct cx_tree_iterator_s *iter = it; |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
266 | return iter->node != NULL; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
267 | } |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
268 | |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
269 | static void *cx_tree_iter_current(const void *it) { |
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
270 | const struct cx_tree_iterator_s *iter = it; |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
271 | return iter->node; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
272 | } |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
273 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
274 | 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
|
275 | struct cx_tree_iterator_s *iter = it; |
845 | 276 | ptrdiff_t const loc_next = iter->loc_next; |
277 | ptrdiff_t const loc_children = iter->loc_children; | |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
278 | // protect us from misuse |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
279 | if (!iter->base.valid(iter)) return; |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
280 | |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
281 | void *children; |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
282 | |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
283 | // 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
|
284 | if (iter->exiting) { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
285 | children = NULL; |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
286 | // 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
|
287 | iter->skip = false; |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
288 | } else { |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
289 | if (iter->skip) { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
290 | // 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
|
291 | iter->skip = false; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
292 | children = NULL; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
293 | } else { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
294 | // try to enter the children (if any) |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
295 | children = tree_children(iter->node); |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
296 | } |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
297 | } |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
298 | |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
299 | if (children == NULL) { |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
300 | // search for the next node |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
301 | void *next; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
302 | cx_tree_iter_search_next: |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
303 | // 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
|
304 | if (iter->exiting) { |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
305 | next = iter->node_next; |
840
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
838
diff
changeset
|
306 | } else { |
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
838
diff
changeset
|
307 | next = tree_next(iter->node); |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
308 | iter->node_next = next; |
840
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
838
diff
changeset
|
309 | } |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
310 | if (next == NULL) { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
311 | // 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
|
312 | 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
|
313 | // 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
|
314 | iter->exiting = true; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
315 | } else { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
316 | iter->exiting = false; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
317 | if (iter->depth == 1) { |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
318 | // 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
|
319 | // invalidate the iterator and free the node stack |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
320 | 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
|
321 | iter->stack_capacity = iter->depth = 0; |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
322 | free(iter->stack); |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
323 | iter->stack = NULL; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
324 | } else { |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
325 | // 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
|
326 | // 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
|
327 | iter->depth--; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
328 | 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
|
329 | // 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
|
330 | goto cx_tree_iter_search_next; |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
331 | } |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
332 | } |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
333 | } else { |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
334 | 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
|
335 | // 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
|
336 | iter->exiting = true; |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
337 | } else { |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
338 | iter->exiting = false; |
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
339 | // move to the sibling |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
340 | iter->counter++; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
341 | iter->node = next; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
342 | // new top of stack is the sibling |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
343 | iter->stack[iter->depth - 1] = next; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
344 | } |
838
1ce90ab4fab9
add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents:
836
diff
changeset
|
345 | } |
836
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
346 | } else { |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
347 | // 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
|
348 | cx_array_simple_add(iter->stack, children); |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
349 | iter->node = children; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
350 | iter->counter++; |
2672a2f79484
implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents:
834
diff
changeset
|
351 | } |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
352 | } |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
353 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
354 | CxTreeIterator cx_tree_iterator( |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
355 | void *root, |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
356 | bool visit_on_exit, |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
357 | ptrdiff_t loc_children, |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
358 | ptrdiff_t loc_next |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
359 | ) { |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
360 | CxTreeIterator iter; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
361 | iter.loc_children = loc_children; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
362 | 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
|
363 | 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
|
364 | |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
365 | // initialize members |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
366 | 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
|
367 | iter.exiting = false; |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
368 | iter.skip = false; |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
369 | |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
370 | // 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
|
371 | 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
|
372 | 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
|
373 | 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
|
374 | 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
|
375 | 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
|
376 | 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
|
377 | |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
378 | // visit the root node |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
379 | iter.node = root; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
380 | if (root != NULL) { |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
381 | iter.stack_capacity = 16; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
382 | iter.stack = malloc(sizeof(void *) * 16); |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
383 | iter.stack[0] = root; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
384 | iter.counter = 1; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
385 | iter.depth = 1; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
386 | } else { |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
387 | iter.stack_capacity = 0; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
388 | iter.stack = NULL; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
389 | iter.counter = 0; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
390 | iter.depth = 0; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
391 | } |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
392 | |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
393 | return iter; |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
394 | } |
845 | 395 | |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
396 | static bool cx_tree_visitor_valid(const void *it) { |
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
397 | const struct cx_tree_visitor_s *iter = it; |
845 | 398 | return iter->node != NULL; |
399 | } | |
400 | ||
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
401 | static void *cx_tree_visitor_current(const void *it) { |
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
402 | const struct cx_tree_visitor_s *iter = it; |
845 | 403 | return iter->node; |
404 | } | |
405 | ||
1040
1ecf4dbbc60c
add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents:
989
diff
changeset
|
406 | cx_attr_nonnull |
845 | 407 | static void cx_tree_visitor_enqueue_siblings( |
408 | struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { | |
409 | node = tree_next(node); | |
410 | while (node != NULL) { | |
411 | struct cx_tree_visitor_queue_s *q; | |
412 | q = malloc(sizeof(struct cx_tree_visitor_queue_s)); | |
413 | q->depth = iter->queue_last->depth; | |
414 | q->node = node; | |
415 | iter->queue_last->next = q; | |
416 | iter->queue_last = q; | |
417 | node = tree_next(node); | |
418 | } | |
419 | iter->queue_last->next = NULL; | |
420 | } | |
421 | ||
422 | static void cx_tree_visitor_next(void *it) { | |
423 | struct cx_tree_visitor_s *iter = it; | |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
424 | // protect us from misuse |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
425 | if (!iter->base.valid(iter)) return; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
426 | |
845 | 427 | ptrdiff_t const loc_next = iter->loc_next; |
428 | ptrdiff_t const loc_children = iter->loc_children; | |
429 | ||
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
430 | // 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
|
431 | // unless the skip flag is set |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
432 | void *children; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
433 | if (iter->skip) { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
434 | iter->skip = false; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
435 | children = NULL; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
436 | } else { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
437 | children = tree_children(iter->node); |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
438 | } |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
439 | if (children != NULL) { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
440 | struct cx_tree_visitor_queue_s *q; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
441 | 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
|
442 | q->depth = iter->depth + 1; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
443 | q->node = children; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
444 | if (iter->queue_last == NULL) { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
445 | assert(iter->queue_next == NULL); |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
446 | iter->queue_next = q; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
447 | } else { |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
448 | iter->queue_last->next = q; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
449 | } |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
450 | iter->queue_last = q; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
451 | 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
|
452 | } |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
453 | |
845 | 454 | // check if there is a next node |
455 | if (iter->queue_next == NULL) { | |
456 | iter->node = NULL; | |
457 | return; | |
458 | } | |
459 | ||
460 | // dequeue the next node | |
461 | iter->node = iter->queue_next->node; | |
462 | iter->depth = iter->queue_next->depth; | |
463 | { | |
464 | struct cx_tree_visitor_queue_s *q = iter->queue_next; | |
465 | iter->queue_next = q->next; | |
466 | if (iter->queue_next == NULL) { | |
467 | assert(iter->queue_last == q); | |
468 | iter->queue_last = NULL; | |
469 | } | |
470 | free(q); | |
471 | } | |
472 | ||
473 | // increment the node counter | |
474 | iter->counter++; | |
475 | } | |
476 | ||
477 | CxTreeVisitor cx_tree_visitor( | |
478 | void *root, | |
479 | ptrdiff_t loc_children, | |
480 | ptrdiff_t loc_next | |
481 | ) { | |
482 | CxTreeVisitor iter; | |
483 | iter.loc_children = loc_children; | |
484 | iter.loc_next = loc_next; | |
485 | ||
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
486 | // initialize members |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
487 | iter.skip = false; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
488 | iter.queue_next = NULL; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
489 | iter.queue_last = NULL; |
845 | 490 | |
491 | // 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
|
492 | 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
|
493 | 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
|
494 | 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
|
495 | 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
|
496 | 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
|
497 | iter.base.current = cx_tree_visitor_current; |
845 | 498 | |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
499 | // visit the root node |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
500 | iter.node = root; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
501 | if (root != NULL) { |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
502 | iter.counter = 1; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
503 | iter.depth = 1; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
504 | } else { |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
505 | iter.counter = 0; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
506 | iter.depth = 0; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
507 | } |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
508 | |
845 | 509 | return iter; |
510 | } | |
511 | ||
867
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
512 | static void cx_tree_add_link_duplicate( |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
513 | void *original, void *duplicate, |
867
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
514 | 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
|
515 | 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
|
516 | ) { |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
517 | 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
|
518 | if (shared_parent == NULL) { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
519 | cx_tree_link(original, duplicate, cx_tree_ptr_locations); |
867
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
520 | } else { |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
521 | 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
|
522 | } |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
523 | } |
471c714d5b6f
cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents:
866
diff
changeset
|
524 | |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
525 | static void cx_tree_add_link_new( |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
526 | void *parent, void *node, cx_tree_search_func sfunc, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
527 | ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
528 | ptrdiff_t loc_prev, ptrdiff_t loc_next |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
529 | ) { |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
530 | // check the current children one by one, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
531 | // if they could be children of the new node |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
532 | void *child = tree_children(parent); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
533 | while (child != NULL) { |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
534 | void *next = tree_next(child); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
535 | |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
536 | if (sfunc(node, child) > 0) { |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
537 | // the sibling could be a child -> re-link |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
538 | cx_tree_link(node, child, cx_tree_ptr_locations); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
539 | } |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
540 | |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
541 | child = next; |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
542 | } |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
543 | |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
544 | // add new node as new child |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
545 | cx_tree_link(parent, node, cx_tree_ptr_locations); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
546 | } |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
547 | |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
548 | int cx_tree_add( |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
549 | const void *src, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
550 | cx_tree_search_func sfunc, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
551 | cx_tree_node_create_func cfunc, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
552 | void *cdata, |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
553 | void **cnode, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
554 | void *root, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
555 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
556 | ptrdiff_t loc_children, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
557 | 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
|
558 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
559 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
560 | ) { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
561 | *cnode = cfunc(src, cdata); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
562 | if (*cnode == NULL) return 1; |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
563 | cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations); |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
564 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
565 | void *match = NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
566 | int result = cx_tree_search( |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
567 | root, |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
568 | 0, |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
569 | *cnode, |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
570 | sfunc, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
571 | &match, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
572 | loc_children, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
573 | loc_next |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
574 | ); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
575 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
576 | if (result < 0) { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
577 | // node does not fit into the tree - return non-zero value |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
578 | return 1; |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
579 | } else if (result == 0) { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
580 | // data already found in the tree, link duplicate |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
581 | cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations); |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
582 | } else { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
583 | // closest match found, add new node |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
584 | cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations); |
866
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 | |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
587 | return 0; |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
588 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
589 | |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
590 | 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
|
591 | |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
592 | 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
|
593 | struct cx_iterator_base_s *iter, |
893
0a2b328f5b91
add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents:
890
diff
changeset
|
594 | size_t num, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
595 | cx_tree_search_func sfunc, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
596 | cx_tree_node_create_func cfunc, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
597 | void *cdata, |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
598 | void **failed, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
599 | void *root, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
600 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
601 | ptrdiff_t loc_children, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
602 | 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
|
603 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
604 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
605 | ) { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
606 | // erase the failed pointer |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
607 | *failed = NULL; |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
608 | |
868
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
609 | // iter not valid? cancel... |
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
610 | 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
|
611 | |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
612 | size_t processed = 0; |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
613 | void *current_node = root; |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
614 | const void *elem; |
868
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
615 | |
893
0a2b328f5b91
add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents:
890
diff
changeset
|
616 | for (void **eptr; processed < num && |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
617 | iter->valid(iter) && (eptr = iter->current(iter)) != NULL; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
618 | iter->next(iter)) { |
868
56a908924510
cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents:
867
diff
changeset
|
619 | elem = *eptr; |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
620 | |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
621 | // create the new node |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
622 | void *new_node = cfunc(elem, cdata); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
623 | if (new_node == NULL) return processed; |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
624 | cx_tree_zero_pointers(new_node, cx_tree_ptr_locations); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
625 | |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
626 | // start searching from current node |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
627 | void *match; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
628 | int result; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
629 | 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
|
630 | cx_tree_add_look_around_retry: |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
631 | result = cx_tree_search( |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
632 | current_node, |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
633 | 0, |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
634 | new_node, |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
635 | sfunc, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
636 | &match, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
637 | loc_children, |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
638 | loc_next |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
639 | ); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
640 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
641 | if (result < 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
642 | // traverse upwards and try to find better parents |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
643 | void *parent = tree_parent(current_node); |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
644 | if (parent != NULL) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
645 | if (look_around_retries > 0) { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
646 | look_around_retries--; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
647 | current_node = parent; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
648 | } else { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
649 | // look around retries exhausted, start from the root |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
650 | current_node = root; |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
651 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
652 | goto cx_tree_add_look_around_retry; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
653 | } else { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
654 | // no parents. so we failed |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
655 | *failed = new_node; |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
656 | return processed; |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
657 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
658 | } else if (result == 0) { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
659 | // data already found in the tree, link duplicate |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
660 | cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations); |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
661 | // but stick with the original match, in case we needed a new root |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
662 | current_node = match; |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
663 | } else { |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
664 | // closest match found, add new node as child |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
665 | cx_tree_add_link_new(match, new_node, sfunc, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
666 | cx_tree_ptr_locations); |
866
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
667 | current_node = match; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
668 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
669 | |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
670 | processed++; |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
671 | } |
1f636de4a63f
complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents:
864
diff
changeset
|
672 | return processed; |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
673 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
674 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
675 | size_t cx_tree_add_array( |
890
54565fd74e74
move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents:
871
diff
changeset
|
676 | const void *src, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
677 | size_t num, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
678 | size_t elem_size, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
679 | cx_tree_search_func sfunc, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
680 | cx_tree_node_create_func cfunc, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
681 | void *cdata, |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
682 | void **failed, |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
683 | void *root, |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
684 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
685 | ptrdiff_t loc_children, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
686 | 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
|
687 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
688 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
689 | ) { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
690 | // erase failed pointer |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
691 | *failed = NULL; |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
692 | |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
693 | // 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
|
694 | if (num == 0) { |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
695 | return 0; |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
696 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
697 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
698 | // 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
|
699 | if (num == 1) { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
700 | void *node; |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
701 | if (0 == cx_tree_add( |
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
702 | src, sfunc, cfunc, cdata, &node, root, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
703 | loc_parent, loc_children, loc_last_child, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
704 | 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
|
705 | return 1; |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
706 | } else { |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
707 | *failed = node; |
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
708 | return 0; |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
709 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
710 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
711 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
712 | // 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
|
713 | CxIterator iter = cxIterator(src, elem_size, num); |
893
0a2b328f5b91
add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents:
890
diff
changeset
|
714 | return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc, |
871
e29c1f96646d
rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents:
870
diff
changeset
|
715 | cfunc, cdata, failed, root, |
864
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
716 | loc_parent, loc_children, loc_last_child, |
7d3061f212cb
complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents:
863
diff
changeset
|
717 | 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
|
718 | } |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
854
diff
changeset
|
719 | |
904
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
720 | static int cx_tree_default_insert_element( |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
721 | CxTree *tree, |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
722 | const void *data |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
723 | ) { |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
724 | void *node; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
725 | if (tree->root == NULL) { |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
726 | node = tree->node_create(data, tree); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
727 | if (node == NULL) return 1; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
728 | cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
729 | tree->root = node; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
730 | tree->size = 1; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
731 | return 0; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
732 | } |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
733 | int result = cx_tree_add(data, tree->search, tree->node_create, |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
734 | tree, &node, tree->root, cx_tree_node_layout(tree)); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
735 | if (0 == result) { |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
736 | tree->size++; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
737 | } else { |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
738 | cxFree(tree->allocator, node); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
739 | } |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
740 | return result; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
741 | } |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
742 | |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
743 | static size_t cx_tree_default_insert_many( |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
744 | CxTree *tree, |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
745 | struct cx_iterator_base_s *iter, |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
746 | size_t n |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
747 | ) { |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
748 | size_t ins = 0; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
749 | if (!iter->valid(iter)) return 0; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
750 | if (tree->root == NULL) { |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
751 | // use the first element from the iter to create the root node |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
752 | void **eptr = iter->current(iter); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
753 | void *node = tree->node_create(*eptr, tree); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
754 | if (node == NULL) return 0; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
755 | cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
756 | tree->root = node; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
757 | ins = 1; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
758 | iter->next(iter); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
759 | } |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
760 | void *failed; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
761 | ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create, |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
762 | tree, &failed, tree->root, cx_tree_node_layout(tree)); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
763 | tree->size += ins; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
764 | if (ins < n) { |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
765 | cxFree(tree->allocator, failed); |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
766 | } |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
767 | return ins; |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
768 | } |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
769 | |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
770 | static void *cx_tree_default_find( |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
771 | CxTree *tree, |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
772 | const void *subtree, |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
773 | const void *data, |
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
774 | size_t depth |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
775 | ) { |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
776 | if (tree->root == NULL) return NULL; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
777 | |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
778 | void *found; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
779 | if (0 == cx_tree_search_data( |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
780 | subtree, |
930
6540096c17b7
add max depth for tree search - closes #459
Mike Becker <universe@uap-core.de>
parents:
921
diff
changeset
|
781 | depth, |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
782 | data, |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
783 | tree->search_data, |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
784 | &found, |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
785 | tree->loc_children, |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
786 | tree->loc_next |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
787 | )) { |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
788 | return found; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
789 | } else { |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
790 | return NULL; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
791 | } |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
792 | } |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
793 | |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
794 | static cx_tree_class cx_tree_default_class = { |
904
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
795 | cx_tree_default_insert_element, |
cdc49211d87f
implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents:
903
diff
changeset
|
796 | cx_tree_default_insert_many, |
914 | 797 | cx_tree_default_find |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
798 | }; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
799 | |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
800 | CxTree *cxTreeCreate( |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
801 | const CxAllocator *allocator, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
802 | cx_tree_node_create_func create_func, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
803 | cx_tree_search_func search_func, |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
804 | cx_tree_search_data_func search_data_func, |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
805 | ptrdiff_t loc_parent, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
806 | ptrdiff_t loc_children, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
807 | ptrdiff_t loc_last_child, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
808 | ptrdiff_t loc_prev, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
809 | ptrdiff_t loc_next |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
810 | ) { |
989
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
811 | if (allocator == NULL) { |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
812 | allocator = cxDefaultAllocator; |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
813 | } |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
814 | assert(create_func != NULL); |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
815 | assert(search_func != NULL); |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
816 | assert(search_data_func != NULL); |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
817 | |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
818 | CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
819 | if (tree == NULL) return NULL; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
820 | |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
821 | tree->cl = &cx_tree_default_class; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
822 | tree->allocator = allocator; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
823 | tree->node_create = create_func; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
824 | tree->search = search_func; |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
825 | tree->search_data = search_data_func; |
910
5c2af036103f
fix uninitialized simple_destructor - fixes #443
Mike Becker <universe@uap-core.de>
parents:
909
diff
changeset
|
826 | tree->simple_destructor = NULL; |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
827 | tree->advanced_destructor = (cx_destructor_func2) cxFree; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
828 | tree->destructor_data = (void *) allocator; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
829 | tree->loc_parent = loc_parent; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
830 | tree->loc_children = loc_children; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
831 | tree->loc_last_child = loc_last_child; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
832 | tree->loc_prev = loc_prev; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
833 | tree->loc_next = loc_next; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
834 | tree->root = NULL; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
835 | tree->size = 0; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
836 | |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
837 | return tree; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
838 | } |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
839 | |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
840 | CxTree *cxTreeCreateWrapped( |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
841 | const CxAllocator *allocator, |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
842 | void *root, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
843 | ptrdiff_t loc_parent, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
844 | ptrdiff_t loc_children, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
845 | ptrdiff_t loc_last_child, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
846 | ptrdiff_t loc_prev, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
847 | ptrdiff_t loc_next |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
848 | ) { |
989
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
849 | if (allocator == NULL) { |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
850 | allocator = cxDefaultAllocator; |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
851 | } |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
852 | assert(root != NULL); |
8aa57a7fecc4
improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents:
988
diff
changeset
|
853 | |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
854 | CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
855 | if (tree == NULL) return NULL; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
856 | |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
857 | tree->cl = &cx_tree_default_class; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
858 | // set the allocator anyway, just in case... |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
859 | tree->allocator = allocator; |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
860 | tree->node_create = NULL; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
861 | tree->search = NULL; |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
862 | tree->search_data = NULL; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
863 | tree->simple_destructor = NULL; |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
864 | tree->advanced_destructor = NULL; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
865 | tree->destructor_data = NULL; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
866 | tree->loc_parent = loc_parent; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
867 | tree->loc_children = loc_children; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
868 | tree->loc_last_child = loc_last_child; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
869 | tree->loc_prev = loc_prev; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
870 | tree->loc_next = loc_next; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
871 | tree->root = root; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
872 | tree->size = cxTreeSubtreeSize(tree, root); |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
873 | return tree; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
874 | } |
901
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
875 | |
918 | 876 | void cxTreeSetParent( |
877 | CxTree *tree, | |
878 | void *parent, | |
879 | void *child | |
880 | ) { | |
881 | size_t loc_parent = tree->loc_parent; | |
882 | if (tree_parent(child) == NULL) { | |
883 | tree->size++; | |
884 | } | |
885 | cx_tree_link(parent, child, cx_tree_node_layout(tree)); | |
886 | } | |
887 | ||
888 | void cxTreeAddChildNode( | |
889 | CxTree *tree, | |
890 | void *parent, | |
891 | void *child | |
892 | ) { | |
893 | cx_tree_link(parent, child, cx_tree_node_layout(tree)); | |
894 | tree->size++; | |
895 | } | |
896 | ||
901
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
897 | int cxTreeAddChild( |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
898 | CxTree *tree, |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
899 | void *parent, |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
900 | const void *data) { |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
901 | void *node = tree->node_create(data, tree); |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
902 | if (node == NULL) return 1; |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
903 | cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
904 | cx_tree_link(parent, node, cx_tree_node_layout(tree)); |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
905 | tree->size++; |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
906 | return 0; |
109567325fe7
add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents:
893
diff
changeset
|
907 | } |
902
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
908 | |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
909 | size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) { |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
910 | CxTreeVisitor visitor = cx_tree_visitor( |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
911 | subtree_root, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
912 | tree->loc_children, |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
913 | tree->loc_next |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
914 | ); |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
915 | while (cxIteratorValid(visitor)) { |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
916 | cxIteratorNext(visitor); |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
917 | } |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
918 | return visitor.counter; |
5ed7f634f046
implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents:
901
diff
changeset
|
919 | } |
903
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
920 | |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
921 | size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) { |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
922 | CxTreeVisitor visitor = cx_tree_visitor( |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
923 | subtree_root, |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
924 | tree->loc_children, |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
925 | tree->loc_next |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
926 | ); |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
927 | while (cxIteratorValid(visitor)) { |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
928 | cxIteratorNext(visitor); |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
929 | } |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
930 | return visitor.depth; |
a018f5916d3b
add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents:
902
diff
changeset
|
931 | } |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
932 | |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
933 | size_t cxTreeDepth(CxTree *tree) { |
914 | 934 | CxTreeVisitor visitor = cx_tree_visitor( |
935 | tree->root, tree->loc_children, tree->loc_next | |
936 | ); | |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
937 | while (cxIteratorValid(visitor)) { |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
938 | cxIteratorNext(visitor); |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
939 | } |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
940 | return visitor.depth; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
941 | } |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
942 | |
913
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
943 | int cxTreeRemoveNode( |
909
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
944 | CxTree *tree, |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
945 | void *node, |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
946 | cx_tree_relink_func relink_func |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
947 | ) { |
908
f49f8a7060aa
rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents:
907
diff
changeset
|
948 | if (node == tree->root) return 1; |
f49f8a7060aa
rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents:
907
diff
changeset
|
949 | |
909
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
950 | // determine the new parent |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
951 | ptrdiff_t loc_parent = tree->loc_parent; |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
952 | void *new_parent = tree_parent(node); |
908
f49f8a7060aa
rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents:
907
diff
changeset
|
953 | |
909
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
954 | // first, unlink from the parent |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
955 | cx_tree_unlink(node, cx_tree_node_layout(tree)); |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
956 | |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
957 | // then relink each child |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
958 | ptrdiff_t loc_children = tree->loc_children; |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
959 | ptrdiff_t loc_next = tree->loc_next; |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
960 | void *child = tree_children(node); |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
961 | while (child != NULL) { |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
962 | // forcibly set the parent to NULL - we do not use the unlink function |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
963 | // because that would unnecessarily modify the children linked list |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
964 | tree_parent(child) = NULL; |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
965 | |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
966 | // update contents, if required |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
967 | if (relink_func != NULL) { |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
968 | relink_func(child, node, new_parent); |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
969 | } |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
970 | |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
971 | // link to new parent |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
972 | cx_tree_link(new_parent, child, cx_tree_node_layout(tree)); |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
973 | |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
974 | // proceed to next child |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
975 | child = tree_next(child); |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
976 | } |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
977 | |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
978 | // clear the linked list of the removed node |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
979 | tree_children(node) = NULL; |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
980 | ptrdiff_t loc_last_child = tree->loc_last_child; |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
981 | if (loc_last_child >= 0) tree_last_child(node) = NULL; |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
982 | |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
983 | // the tree now has one member less |
f4e00bb3f3b2
implement cxTreeRemove() with re-link function
Mike Becker <universe@uap-core.de>
parents:
908
diff
changeset
|
984 | tree->size--; |
908
f49f8a7060aa
rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents:
907
diff
changeset
|
985 | |
f49f8a7060aa
rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents:
907
diff
changeset
|
986 | return 0; |
f49f8a7060aa
rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents:
907
diff
changeset
|
987 | } |
f49f8a7060aa
rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents:
907
diff
changeset
|
988 | |
f49f8a7060aa
rename cxTreeRemove() to cxTreeRemoveSubtree()
Mike Becker <universe@uap-core.de>
parents:
907
diff
changeset
|
989 | void cxTreeRemoveSubtree(CxTree *tree, void *node) { |
907
1f72fb9af87e
fix bug when removing the root node of a tree
Mike Becker <universe@uap-core.de>
parents:
905
diff
changeset
|
990 | if (node == tree->root) { |
1f72fb9af87e
fix bug when removing the root node of a tree
Mike Becker <universe@uap-core.de>
parents:
905
diff
changeset
|
991 | tree->root = NULL; |
1f72fb9af87e
fix bug when removing the root node of a tree
Mike Becker <universe@uap-core.de>
parents:
905
diff
changeset
|
992 | tree->size = 0; |
1f72fb9af87e
fix bug when removing the root node of a tree
Mike Becker <universe@uap-core.de>
parents:
905
diff
changeset
|
993 | return; |
1f72fb9af87e
fix bug when removing the root node of a tree
Mike Becker <universe@uap-core.de>
parents:
905
diff
changeset
|
994 | } |
905
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
995 | size_t subtree_size = cxTreeSubtreeSize(tree, node); |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
996 | cx_tree_unlink(node, cx_tree_node_layout(tree)); |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
997 | tree->size -= subtree_size; |
39aa4f106a71
complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents:
904
diff
changeset
|
998 | } |
913
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
999 | |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1000 | int cxTreeDestroyNode( |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1001 | CxTree *tree, |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1002 | void *node, |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1003 | cx_tree_relink_func relink_func |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1004 | ) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1005 | int result = cxTreeRemoveNode(tree, node, relink_func); |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1006 | if (result == 0) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1007 | if (tree->simple_destructor) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1008 | tree->simple_destructor(node); |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1009 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1010 | if (tree->advanced_destructor) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1011 | tree->advanced_destructor(tree->destructor_data, node); |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1012 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1013 | return 0; |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1014 | } else { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1015 | return result; |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1016 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1017 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1018 | |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1019 | void cxTreeDestroySubtree(CxTree *tree, void *node) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1020 | cx_tree_unlink(node, cx_tree_node_layout(tree)); |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1021 | CxTreeIterator iter = cx_tree_iterator( |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1022 | node, true, |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1023 | tree->loc_children, tree->loc_next |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1024 | ); |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1025 | cx_foreach(void *, child, iter) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1026 | if (iter.exiting) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1027 | if (tree->simple_destructor) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1028 | tree->simple_destructor(child); |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1029 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1030 | if (tree->advanced_destructor) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1031 | tree->advanced_destructor(tree->destructor_data, child); |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1032 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1033 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1034 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1035 | tree->size -= iter.counter; |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1036 | if (node == tree->root) { |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1037 | tree->root = NULL; |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1038 | } |
72db8e42b95e
implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438
Mike Becker <universe@uap-core.de>
parents:
910
diff
changeset
|
1039 | } |