src/tree.c

Sun, 22 Dec 2024 22:10:04 +0100

author
Mike Becker <universe@uap-core.de>
date
Sun, 22 Dec 2024 22:10:04 +0100
changeset 1047
40aad3f0bc9e
parent 1040
1ecf4dbbc60c
permissions
-rw-r--r--

don't trust that size_t always has word width

it should be the case on all platforms supported by UCX, but it's not strictly defined in POSIX that it must be the case

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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
276 ptrdiff_t const loc_next = iter->loc_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
398 return iter->node != NULL;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
399 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
403 return iter->node;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
404 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
407 static void cx_tree_visitor_enqueue_siblings(
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
408 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
409 node = tree_next(node);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
410 while (node != NULL) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
411 struct cx_tree_visitor_queue_s *q;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
412 q = malloc(sizeof(struct cx_tree_visitor_queue_s));
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
413 q->depth = iter->queue_last->depth;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
414 q->node = node;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
415 iter->queue_last->next = q;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
416 iter->queue_last = q;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
417 node = tree_next(node);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
418 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
419 iter->queue_last->next = NULL;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
420 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
421
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
422 static void cx_tree_visitor_next(void *it) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
427 ptrdiff_t const loc_next = iter->loc_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
428 ptrdiff_t const loc_children = iter->loc_children;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
454 // check if there is a next node
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
455 if (iter->queue_next == NULL) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
456 iter->node = NULL;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
457 return;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
458 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
459
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
460 // dequeue the next node
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
461 iter->node = iter->queue_next->node;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
462 iter->depth = iter->queue_next->depth;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
463 {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
464 struct cx_tree_visitor_queue_s *q = iter->queue_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
465 iter->queue_next = q->next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
466 if (iter->queue_next == NULL) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
467 assert(iter->queue_last == q);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
468 iter->queue_last = NULL;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
469 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
470 free(q);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
471 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
472
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
473 // increment the node counter
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
474 iter->counter++;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
475 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
476
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
477 CxTreeVisitor cx_tree_visitor(
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
478 void *root,
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
479 ptrdiff_t loc_children,
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
480 ptrdiff_t loc_next
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
481 ) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
482 CxTreeVisitor iter;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
483 iter.loc_children = loc_children;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
484 iter.loc_next = loc_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
490
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
509 return iter;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
510 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
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
7da30512efc4 simplify tree class
Mike Becker <universe@uap-core.de>
parents: 913
diff changeset
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
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
876 void cxTreeSetParent(
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
877 CxTree *tree,
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
878 void *parent,
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
879 void *child
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
880 ) {
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
881 size_t loc_parent = tree->loc_parent;
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
882 if (tree_parent(child) == NULL) {
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
883 tree->size++;
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
884 }
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
885 cx_tree_link(parent, child, cx_tree_node_layout(tree));
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
886 }
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
887
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
888 void cxTreeAddChildNode(
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
889 CxTree *tree,
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
890 void *parent,
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
891 void *child
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
892 ) {
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
893 cx_tree_link(parent, child, cx_tree_node_layout(tree));
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
894 tree->size++;
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
895 }
ec1f2015ec79 add cxTreeSetParent()
Mike Becker <universe@uap-core.de>
parents: 914
diff changeset
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
7da30512efc4 simplify tree class
Mike Becker <universe@uap-core.de>
parents: 913
diff changeset
934 CxTreeVisitor visitor = cx_tree_visitor(
7da30512efc4 simplify tree class
Mike Becker <universe@uap-core.de>
parents: 913
diff changeset
935 tree->root, tree->loc_children, tree->loc_next
7da30512efc4 simplify tree class
Mike Becker <universe@uap-core.de>
parents: 913
diff changeset
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 }

mercurial