ucx/tree.c

Sun, 06 Oct 2024 12:00:31 +0200

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Sun, 06 Oct 2024 12:00:31 +0200
branch
newapi
changeset 324
ce13a778654a
parent 253
087cc9216f28
permissions
-rw-r--r--

update ucx

253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1 /*
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
3 *
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
5 *
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
8 *
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
11 *
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
15 *
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
27 */
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
28
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
29 #include "cx/tree.h"
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
30
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
31 #include "cx/array_list.h"
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
32
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33 #include <assert.h>
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
34
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
35 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
36 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
37 #define tree_children(node) CX_TREE_PTR(node, loc_children)
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
38 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child)
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
39 #define tree_prev(node) CX_TREE_PTR(node, loc_prev)
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
40 #define tree_next(node) CX_TREE_PTR(node, loc_next)
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
41
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
42 #define cx_tree_ptr_locations \
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
43 loc_parent, loc_children, loc_last_child, loc_prev, loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
44
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
45 static void cx_tree_zero_pointers(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
46 void *node,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
47 ptrdiff_t loc_parent,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
48 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
49 ptrdiff_t loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
50 ptrdiff_t loc_prev,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
51 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
52 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
53 tree_parent(node) = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
54 tree_prev(node) = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
55 tree_next(node) = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
56 tree_children(node) = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
57 if (loc_last_child >= 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
58 tree_last_child(node) = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
59 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
60 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
61
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 void cx_tree_link(
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 void *restrict parent,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64 void *restrict node,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
65 ptrdiff_t loc_parent,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 ptrdiff_t loc_children,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
67 ptrdiff_t loc_last_child,
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
68 ptrdiff_t loc_prev,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 ptrdiff_t loc_next
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
70 ) {
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
71 void *current_parent = tree_parent(node);
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
72 if (current_parent == parent) return;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73 if (current_parent != NULL) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
74 cx_tree_unlink(node, cx_tree_ptr_locations);
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
75 }
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 if (tree_children(parent) == NULL) {
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
78 tree_children(parent) = node;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
79 if (loc_last_child >= 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
80 tree_last_child(parent) = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
81 }
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
82 } else {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
83 if (loc_last_child >= 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
84 void *child = tree_last_child(parent);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
85 tree_prev(node) = child;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
86 tree_next(child) = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
87 tree_last_child(parent) = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
88 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
89 void *child = tree_children(parent);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
90 void *next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
91 while ((next = tree_next(child)) != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
92 child = next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
93 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
94 tree_prev(node) = child;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
95 tree_next(child) = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
96 }
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
97 }
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
98 tree_parent(node) = parent;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
99 }
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
100
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101 void cx_tree_unlink(
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102 void *node,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
103 ptrdiff_t loc_parent,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
104 ptrdiff_t loc_children,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
105 ptrdiff_t loc_last_child,
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
106 ptrdiff_t loc_prev,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
107 ptrdiff_t loc_next
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 ) {
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109 if (tree_parent(node) == NULL) return;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 void *left = tree_prev(node);
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
112 void *right = tree_next(node);
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
113 void *parent = tree_parent(node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
114 assert(left == NULL || tree_children(parent) != node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
115 assert(right == NULL || loc_last_child < 0 ||
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
116 tree_last_child(parent) != node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
117
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
118 if (left == NULL) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
119 tree_children(parent) = right;
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
120 } else {
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
121 tree_next(left) = right;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
122 }
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
123 if (right == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
124 if (loc_last_child >= 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
125 tree_last_child(parent) = left;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
126 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
127 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
128 tree_prev(right) = left;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
129 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
130
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 tree_parent(node) = NULL;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132 tree_prev(node) = NULL;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 tree_next(node) = NULL;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 }
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
135
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
136 int cx_tree_search(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
137 const void *root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
138 const void *node,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
139 cx_tree_search_func sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
140 void **result,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
141 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
142 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
143 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
144 int ret;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
145 *result = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
146
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
147 // shortcut: compare root before doing anything else
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
148 ret = sfunc(root, node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
149 if (ret < 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
150 return ret;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
151 } else if (ret == 0 || tree_children(root) == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
152 *result = (void*)root;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
153 return ret;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
154 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
155
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
156 // create a working stack
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
157 CX_ARRAY_DECLARE(const void *, work);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
158 cx_array_initialize(work, 32);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
159
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
160 // add the children of root to the working stack
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
161 {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
162 void *c = tree_children(root);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
163 while (c != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
164 cx_array_simple_add(work, c);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
165 c = tree_next(c);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
166 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
167 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
168
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
169 // remember a candidate for adding the data
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
170 // also remember the exact return code from sfunc
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
171 void *candidate = (void *) root;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
172 int ret_candidate = ret;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
173
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
174 // process the working stack
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
175 while (work_size > 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
176 // pop element
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
177 const void *elem = work[--work_size];
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
178
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
179 // apply the search function
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
180 ret = sfunc(elem, node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
181
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
182 if (ret == 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
183 // if found, exit the search
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
184 *result = (void *) elem;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
185 work_size = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
186 break;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
187 } else if (ret > 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
188 // if children might contain the data, add them to the stack
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
189 void *c = tree_children(elem);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
190 while (c != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
191 cx_array_simple_add(work, c);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
192 c = tree_next(c);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
193 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
194
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
195 // remember this node in case no child is suitable
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
196 if (ret < ret_candidate) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
197 candidate = (void *) elem;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
198 ret_candidate = ret;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
199 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
200 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
201 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
202
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
203 // not found, but was there a candidate?
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
204 if (ret != 0 && candidate != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
205 ret = ret_candidate;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
206 *result = candidate;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
207 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
208
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
209 // free the working queue and return
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
210 free(work);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
211 return ret;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
212 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
213
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
214 int cx_tree_search_data(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
215 const void *root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
216 const void *data,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
217 cx_tree_search_data_func sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
218 void **result,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
219 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
220 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
221 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
222 // it is basically the same implementation
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
223 return cx_tree_search(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
224 root, data,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
225 (cx_tree_search_func) sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
226 result,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
227 loc_children, loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
228 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
229
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
230 static bool cx_tree_iter_valid(const void *it) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
231 const struct cx_tree_iterator_s *iter = it;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
232 return iter->node != NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
233 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
234
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
235 static void *cx_tree_iter_current(const void *it) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
236 const struct cx_tree_iterator_s *iter = it;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
237 return iter->node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
238 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
239
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
240 static void cx_tree_iter_next(void *it) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
241 struct cx_tree_iterator_s *iter = it;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
242 ptrdiff_t const loc_next = iter->loc_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
243 ptrdiff_t const loc_children = iter->loc_children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
244 // protect us from misuse
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
245 if (!iter->base.valid(iter)) return;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
246
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
247 void *children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
248
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
249 // check if we are currently exiting or entering nodes
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
250 if (iter->exiting) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
251 children = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
252 // skipping on exit is pointless, just clear the flag
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
253 iter->skip = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
254 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
255 if (iter->skip) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
256 // skip flag is set, pretend that there are no children
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
257 iter->skip = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
258 children = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
259 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
260 // try to enter the children (if any)
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
261 children = tree_children(iter->node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
262 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
263 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
264
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
265 if (children == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
266 // search for the next node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
267 void *next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
268 cx_tree_iter_search_next:
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
269 // check if there is a sibling
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
270 if (iter->exiting) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
271 next = iter->node_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
272 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
273 next = tree_next(iter->node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
274 iter->node_next = next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
275 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
276 if (next == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
277 // no sibling, we are done with this node and exit
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
278 if (iter->visit_on_exit && !iter->exiting) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
279 // iter is supposed to visit the node again
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
280 iter->exiting = true;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
281 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
282 iter->exiting = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
283 if (iter->depth == 1) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
284 // there is no parent - we have iterated the entire tree
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
285 // invalidate the iterator and free the node stack
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
286 iter->node = iter->node_next = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
287 iter->stack_capacity = iter->depth = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
288 free(iter->stack);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
289 iter->stack = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
290 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
291 // the parent node can be obtained from the top of stack
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
292 // this way we can avoid the loc_parent in the iterator
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
293 iter->depth--;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
294 iter->node = iter->stack[iter->depth - 1];
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
295 // retry with the parent node to find a sibling
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
296 goto cx_tree_iter_search_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
297 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
298 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
299 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
300 if (iter->visit_on_exit && !iter->exiting) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
301 // iter is supposed to visit the node again
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
302 iter->exiting = true;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
303 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
304 iter->exiting = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
305 // move to the sibling
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
306 iter->counter++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
307 iter->node = next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
308 // new top of stack is the sibling
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
309 iter->stack[iter->depth - 1] = next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
310 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
311 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
312 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
313 // node has children, push the first child onto the stack and enter it
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
314 cx_array_simple_add(iter->stack, children);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
315 iter->node = children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
316 iter->counter++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
317 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
318 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
319
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
320 CxTreeIterator cx_tree_iterator(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
321 void *root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
322 bool visit_on_exit,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
323 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
324 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
325 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
326 CxTreeIterator iter;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
327 iter.loc_children = loc_children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
328 iter.loc_next = loc_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
329 iter.visit_on_exit = visit_on_exit;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
330
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
331 // initialize members
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
332 iter.node_next = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
333 iter.exiting = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
334 iter.skip = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
335
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
336 // assign base iterator functions
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
337 iter.base.mutating = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
338 iter.base.remove = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
339 iter.base.current_impl = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
340 iter.base.valid = cx_tree_iter_valid;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
341 iter.base.next = cx_tree_iter_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
342 iter.base.current = cx_tree_iter_current;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
343
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
344 // visit the root node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
345 iter.node = root;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
346 if (root != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
347 iter.stack_capacity = 16;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
348 iter.stack = malloc(sizeof(void *) * 16);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
349 iter.stack[0] = root;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
350 iter.counter = 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
351 iter.depth = 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
352 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
353 iter.stack_capacity = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
354 iter.stack = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
355 iter.counter = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
356 iter.depth = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
357 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
358
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
359 return iter;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
360 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
361
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
362 static bool cx_tree_visitor_valid(const void *it) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
363 const struct cx_tree_visitor_s *iter = it;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
364 return iter->node != NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
365 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
366
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
367 static void *cx_tree_visitor_current(const void *it) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
368 const struct cx_tree_visitor_s *iter = it;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
369 return iter->node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
370 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
371
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
372 __attribute__((__nonnull__))
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
373 static void cx_tree_visitor_enqueue_siblings(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
374 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
375 node = tree_next(node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
376 while (node != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
377 struct cx_tree_visitor_queue_s *q;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
378 q = malloc(sizeof(struct cx_tree_visitor_queue_s));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
379 q->depth = iter->queue_last->depth;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
380 q->node = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
381 iter->queue_last->next = q;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
382 iter->queue_last = q;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
383 node = tree_next(node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
384 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
385 iter->queue_last->next = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
386 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
387
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
388 static void cx_tree_visitor_next(void *it) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
389 struct cx_tree_visitor_s *iter = it;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
390 // protect us from misuse
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
391 if (!iter->base.valid(iter)) return;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
392
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
393 ptrdiff_t const loc_next = iter->loc_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
394 ptrdiff_t const loc_children = iter->loc_children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
395
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
396 // add the children of the current node to the queue
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
397 // unless the skip flag is set
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
398 void *children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
399 if (iter->skip) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
400 iter->skip = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
401 children = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
402 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
403 children = tree_children(iter->node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
404 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
405 if (children != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
406 struct cx_tree_visitor_queue_s *q;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
407 q = malloc(sizeof(struct cx_tree_visitor_queue_s));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
408 q->depth = iter->depth + 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
409 q->node = children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
410 if (iter->queue_last == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
411 assert(iter->queue_next == NULL);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
412 iter->queue_next = q;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
413 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
414 iter->queue_last->next = q;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
415 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
416 iter->queue_last = q;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
417 cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
418 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
419
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
420 // check if there is a next node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
421 if (iter->queue_next == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
422 iter->node = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
423 return;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
424 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
425
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
426 // dequeue the next node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
427 iter->node = iter->queue_next->node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
428 iter->depth = iter->queue_next->depth;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
429 {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
430 struct cx_tree_visitor_queue_s *q = iter->queue_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
431 iter->queue_next = q->next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
432 if (iter->queue_next == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
433 assert(iter->queue_last == q);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
434 iter->queue_last = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
435 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
436 free(q);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
437 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
438
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
439 // increment the node counter
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
440 iter->counter++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
441 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
442
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
443 CxTreeVisitor cx_tree_visitor(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
444 void *root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
445 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
446 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
447 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
448 CxTreeVisitor iter;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
449 iter.loc_children = loc_children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
450 iter.loc_next = loc_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
451
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
452 // initialize members
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
453 iter.skip = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
454 iter.queue_next = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
455 iter.queue_last = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
456
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
457 // assign base iterator functions
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
458 iter.base.mutating = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
459 iter.base.remove = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
460 iter.base.current_impl = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
461 iter.base.valid = cx_tree_visitor_valid;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
462 iter.base.next = cx_tree_visitor_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
463 iter.base.current = cx_tree_visitor_current;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
464
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
465 // visit the root node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
466 iter.node = root;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
467 if (root != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
468 iter.counter = 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
469 iter.depth = 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
470 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
471 iter.counter = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
472 iter.depth = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
473 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
474
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
475 return iter;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
476 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
477
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
478 static void cx_tree_add_link_duplicate(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
479 void *original, void *duplicate,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
480 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
481 ptrdiff_t loc_prev, ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
482 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
483 void *shared_parent = tree_parent(original);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
484 if (shared_parent == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
485 cx_tree_link(original, duplicate, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
486 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
487 cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
488 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
489 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
490
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
491 static void cx_tree_add_link_new(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
492 void *parent, void *node, cx_tree_search_func sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
493 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
494 ptrdiff_t loc_prev, ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
495 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
496 // check the current children one by one,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
497 // if they could be children of the new node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
498 void *child = tree_children(parent);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
499 while (child != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
500 void *next = tree_next(child);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
501
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
502 if (sfunc(node, child) > 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
503 // the sibling could be a child -> re-link
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
504 cx_tree_link(node, child, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
505 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
506
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
507 child = next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
508 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
509
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
510 // add new node as new child
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
511 cx_tree_link(parent, node, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
512 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
513
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
514 int cx_tree_add(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
515 const void *src,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
516 cx_tree_search_func sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
517 cx_tree_node_create_func cfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
518 void *cdata,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
519 void **cnode,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
520 void *root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
521 ptrdiff_t loc_parent,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
522 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
523 ptrdiff_t loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
524 ptrdiff_t loc_prev,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
525 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
526 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
527 *cnode = cfunc(src, cdata);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
528 if (*cnode == NULL) return 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
529 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
530
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
531 void *match = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
532 int result = cx_tree_search(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
533 root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
534 *cnode,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
535 sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
536 &match,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
537 loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
538 loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
539 );
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
540
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
541 if (result < 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
542 // node does not fit into the tree - return non-zero value
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
543 return 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
544 } else if (result == 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
545 // data already found in the tree, link duplicate
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
546 cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
547 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
548 // closest match found, add new node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
549 cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
550 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
551
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
552 return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
553 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
554
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
555 unsigned int cx_tree_add_look_around_depth = 3;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
556
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
557 size_t cx_tree_add_iter(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
558 struct cx_iterator_base_s *iter,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
559 size_t num,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
560 cx_tree_search_func sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
561 cx_tree_node_create_func cfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
562 void *cdata,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
563 void **failed,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
564 void *root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
565 ptrdiff_t loc_parent,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
566 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
567 ptrdiff_t loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
568 ptrdiff_t loc_prev,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
569 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
570 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
571 // erase the failed pointer
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
572 *failed = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
573
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
574 // iter not valid? cancel...
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
575 if (!iter->valid(iter)) return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
576
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
577 size_t processed = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
578 void *current_node = root;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
579 const void *elem;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
580
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
581 for (void **eptr; processed < num &&
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
582 iter->valid(iter) && (eptr = iter->current(iter)) != NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
583 iter->next(iter)) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
584 elem = *eptr;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
585
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
586 // create the new node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
587 void *new_node = cfunc(elem, cdata);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
588 if (new_node == NULL) return processed;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
589 cx_tree_zero_pointers(new_node, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
590
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
591 // start searching from current node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
592 void *match;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
593 int result;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
594 unsigned int look_around_retries = cx_tree_add_look_around_depth;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
595 cx_tree_add_look_around_retry:
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
596 result = cx_tree_search(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
597 current_node,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
598 new_node,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
599 sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
600 &match,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
601 loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
602 loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
603 );
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
604
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
605 if (result < 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
606 // traverse upwards and try to find better parents
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
607 void *parent = tree_parent(current_node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
608 if (parent != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
609 if (look_around_retries > 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
610 look_around_retries--;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
611 current_node = parent;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
612 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
613 // look around retries exhausted, start from the root
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
614 current_node = root;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
615 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
616 goto cx_tree_add_look_around_retry;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
617 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
618 // no parents. so we failed
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
619 *failed = new_node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
620 return processed;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
621 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
622 } else if (result == 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
623 // data already found in the tree, link duplicate
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
624 cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
625 // but stick with the original match, in case we needed a new root
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
626 current_node = match;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
627 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
628 // closest match found, add new node as child
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
629 cx_tree_add_link_new(match, new_node, sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
630 cx_tree_ptr_locations);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
631 current_node = match;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
632 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
633
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
634 processed++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
635 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
636 return processed;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
637 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
638
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
639 size_t cx_tree_add_array(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
640 const void *src,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
641 size_t num,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
642 size_t elem_size,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
643 cx_tree_search_func sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
644 cx_tree_node_create_func cfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
645 void *cdata,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
646 void **failed,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
647 void *root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
648 ptrdiff_t loc_parent,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
649 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
650 ptrdiff_t loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
651 ptrdiff_t loc_prev,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
652 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
653 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
654 // erase failed pointer
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
655 *failed = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
656
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
657 // super special case: zero elements
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
658 if (num == 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
659 return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
660 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
661
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
662 // special case: one element does not need an iterator
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
663 if (num == 1) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
664 void *node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
665 if (0 == cx_tree_add(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
666 src, sfunc, cfunc, cdata, &node, root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
667 loc_parent, loc_children, loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
668 loc_prev, loc_next)) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
669 return 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
670 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
671 *failed = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
672 return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
673 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
674 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
675
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
676 // otherwise, create iterator and hand over to other function
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
677 CxIterator iter = cxIterator(src, elem_size, num);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
678 return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
679 cfunc, cdata, failed, root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
680 loc_parent, loc_children, loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
681 loc_prev, loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
682 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
683
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
684 static void cx_tree_default_destructor(CxTree *tree) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
685 if (tree->simple_destructor != NULL || tree->advanced_destructor != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
686 CxTreeIterator iter = tree->cl->iterator(tree, true);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
687 cx_foreach(void *, node, iter) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
688 if (iter.exiting) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
689 if (tree->simple_destructor) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
690 tree->simple_destructor(node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
691 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
692 if (tree->advanced_destructor) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
693 tree->advanced_destructor(tree->destructor_data, node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
694 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
695 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
696 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
697 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
698 cxFree(tree->allocator, tree);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
699 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
700
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
701 static CxTreeIterator cx_tree_default_iterator(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
702 CxTree *tree,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
703 bool visit_on_exit
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
704 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
705 return cx_tree_iterator(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
706 tree->root, visit_on_exit,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
707 tree->loc_children, tree->loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
708 );
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
709 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
710
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
711 static CxTreeVisitor cx_tree_default_visitor(CxTree *tree) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
712 return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
713 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
714
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
715 static int cx_tree_default_insert_element(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
716 CxTree *tree,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
717 const void *data
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
718 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
719 void *node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
720 if (tree->root == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
721 node = tree->node_create(data, tree);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
722 if (node == NULL) return 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
723 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
724 tree->root = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
725 tree->size = 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
726 return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
727 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
728 int result = cx_tree_add(data, tree->search, tree->node_create,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
729 tree, &node, tree->root, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
730 if (0 == result) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
731 tree->size++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
732 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
733 cxFree(tree->allocator, node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
734 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
735 return result;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
736 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
737
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
738 static size_t cx_tree_default_insert_many(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
739 CxTree *tree,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
740 struct cx_iterator_base_s *iter,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
741 size_t n
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
742 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
743 size_t ins = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
744 if (!iter->valid(iter)) return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
745 if (tree->root == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
746 // use the first element from the iter to create the root node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
747 void **eptr = iter->current(iter);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
748 void *node = tree->node_create(*eptr, tree);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
749 if (node == NULL) return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
750 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
751 tree->root = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
752 ins = 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
753 iter->next(iter);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
754 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
755 void *failed;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
756 ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
757 tree, &failed, tree->root, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
758 tree->size += ins;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
759 if (ins < n) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
760 cxFree(tree->allocator, failed);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
761 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
762 return ins;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
763 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
764
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
765 static void *cx_tree_default_find(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
766 CxTree *tree,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
767 const void *subtree,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
768 const void *data
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
769 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
770 if (tree->root == NULL) return NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
771
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
772 void *found;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
773 if (0 == cx_tree_search_data(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
774 subtree,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
775 data,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
776 tree->search_data,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
777 &found,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
778 tree->loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
779 tree->loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
780 )) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
781 return found;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
782 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
783 return NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
784 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
785 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
786
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
787 static cx_tree_class cx_tree_default_class = {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
788 cx_tree_default_destructor,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
789 cx_tree_default_insert_element,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
790 cx_tree_default_insert_many,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
791 cx_tree_default_find,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
792 cx_tree_default_iterator,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
793 cx_tree_default_visitor
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
794 };
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
795
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
796 CxTree *cxTreeCreate(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
797 const CxAllocator *allocator,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
798 cx_tree_node_create_func create_func,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
799 cx_tree_search_func search_func,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
800 cx_tree_search_data_func search_data_func,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
801 ptrdiff_t loc_parent,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
802 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
803 ptrdiff_t loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
804 ptrdiff_t loc_prev,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
805 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
806 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
807 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
808 if (tree == NULL) return NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
809
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
810 tree->cl = &cx_tree_default_class;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
811 tree->allocator = allocator;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
812 tree->node_create = create_func;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
813 tree->search = search_func;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
814 tree->search_data = search_data_func;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
815 tree->advanced_destructor = (cx_destructor_func2) cxFree;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
816 tree->destructor_data = (void *) allocator;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
817 tree->loc_parent = loc_parent;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
818 tree->loc_children = loc_children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
819 tree->loc_last_child = loc_last_child;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
820 tree->loc_prev = loc_prev;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
821 tree->loc_next = loc_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
822 tree->root = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
823 tree->size = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
824
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
825 return tree;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
826 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
827
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
828 CxTree *cxTreeCreateWrapped(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
829 const CxAllocator *allocator,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
830 void *root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
831 ptrdiff_t loc_parent,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
832 ptrdiff_t loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
833 ptrdiff_t loc_last_child,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
834 ptrdiff_t loc_prev,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
835 ptrdiff_t loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
836 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
837 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
838 if (tree == NULL) return NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
839
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
840 tree->cl = &cx_tree_default_class;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
841 // set the allocator anyway, just in case...
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
842 tree->allocator = allocator;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
843 tree->node_create = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
844 tree->search = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
845 tree->search_data = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
846 tree->simple_destructor = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
847 tree->advanced_destructor = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
848 tree->destructor_data = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
849 tree->loc_parent = loc_parent;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
850 tree->loc_children = loc_children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
851 tree->loc_last_child = loc_last_child;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
852 tree->loc_prev = loc_prev;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
853 tree->loc_next = loc_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
854 tree->root = root;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
855 tree->size = cxTreeSubtreeSize(tree, root);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
856 return tree;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
857 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
858
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
859 int cxTreeAddChild(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
860 CxTree *tree,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
861 void *parent,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
862 const void *data) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
863 void *node = tree->node_create(data, tree);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
864 if (node == NULL) return 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
865 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
866 cx_tree_link(parent, node, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
867 tree->size++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
868 return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
869 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
870
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
871 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
872 CxTreeVisitor visitor = cx_tree_visitor(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
873 subtree_root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
874 tree->loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
875 tree->loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
876 );
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
877 while (cxIteratorValid(visitor)) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
878 cxIteratorNext(visitor);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
879 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
880 return visitor.counter;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
881 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
882
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
883 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
884 CxTreeVisitor visitor = cx_tree_visitor(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
885 subtree_root,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
886 tree->loc_children,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
887 tree->loc_next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
888 );
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
889 while (cxIteratorValid(visitor)) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
890 cxIteratorNext(visitor);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
891 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
892 return visitor.depth;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
893 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
894
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
895 size_t cxTreeDepth(CxTree *tree) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
896 CxTreeVisitor visitor = tree->cl->visitor(tree);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
897 while (cxIteratorValid(visitor)) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
898 cxIteratorNext(visitor);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
899 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
900 return visitor.depth;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
901 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
902
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
903 int cxTreeRemove(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
904 CxTree *tree,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
905 void *node,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
906 cx_tree_relink_func relink_func
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
907 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
908 if (node == tree->root) return 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
909
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
910 // determine the new parent
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
911 ptrdiff_t loc_parent = tree->loc_parent;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
912 void *new_parent = tree_parent(node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
913
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
914 // first, unlink from the parent
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
915 cx_tree_unlink(node, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
916
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
917 // then relink each child
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
918 ptrdiff_t loc_children = tree->loc_children;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
919 ptrdiff_t loc_next = tree->loc_next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
920 void *child = tree_children(node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
921 while (child != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
922 // forcibly set the parent to NULL - we do not use the unlink function
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
923 // because that would unnecessarily modify the children linked list
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
924 tree_parent(child) = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
925
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
926 // update contents, if required
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
927 if (relink_func != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
928 relink_func(child, node, new_parent);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
929 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
930
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
931 // link to new parent
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
932 cx_tree_link(new_parent, child, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
933
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
934 // proceed to next child
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
935 child = tree_next(child);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
936 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
937
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
938 // clear the linked list of the removed node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
939 tree_children(node) = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
940 ptrdiff_t loc_last_child = tree->loc_last_child;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
941 if (loc_last_child >= 0) tree_last_child(node) = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
942
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
943 // the tree now has one member less
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
944 tree->size--;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
945
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
946 return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
947 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
948
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
949 void cxTreeRemoveSubtree(CxTree *tree, void *node) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
950 if (node == tree->root) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
951 tree->root = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
952 tree->size = 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
953 return;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
954 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
955 size_t subtree_size = cxTreeSubtreeSize(tree, node);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
956 cx_tree_unlink(node, cx_tree_node_layout(tree));
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
957 tree->size -= subtree_size;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
958 }

mercurial