src/tree.c

Sun, 29 Sep 2024 13:10:52 +0200

author
Mike Becker <universe@uap-core.de>
date
Sun, 29 Sep 2024 13:10:52 +0200
changeset 892
6ebf6fdfbc2c
parent 890
54565fd74e74
child 893
0a2b328f5b91
permissions
-rw-r--r--

fix misleading documentation that could have indicated that an allocator is optional for lists

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

mercurial