BadVPN – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | /** |
2 | * @file CAvl_impl.h |
||
3 | * @author Ambroz Bizjak <ambrop7@gmail.com> |
||
4 | * |
||
5 | * @section LICENSE |
||
6 | * |
||
7 | * Redistribution and use in source and binary forms, with or without |
||
8 | * modification, are permitted provided that the following conditions are met: |
||
9 | * 1. Redistributions of source code must retain the above copyright |
||
10 | * notice, this list of conditions and the following disclaimer. |
||
11 | * 2. Redistributions in binary form must reproduce the above copyright |
||
12 | * notice, this list of conditions and the following disclaimer in the |
||
13 | * documentation and/or other materials provided with the distribution. |
||
14 | * 3. Neither the name of the author nor the |
||
15 | * names of its contributors may be used to endorse or promote products |
||
16 | * derived from this software without specific prior written permission. |
||
17 | * |
||
18 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND |
||
19 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
||
20 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
||
21 | * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
||
22 | * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
||
23 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
||
24 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
||
25 | * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
||
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
||
27 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
||
28 | */ |
||
29 | |||
30 | #include "CAvl_header.h" |
||
31 | |||
32 | static CAvlLink CAvl_nulllink (void) |
||
33 | { |
||
34 | return CAVL_PARAM_VALUE_NULL; |
||
35 | } |
||
36 | |||
37 | static CAvlRef CAvl_nullref (void) |
||
38 | { |
||
39 | CAvlRef n; |
||
40 | n.link = CAVL_PARAM_VALUE_NULL; |
||
41 | n.ptr = NULL; |
||
42 | return n; |
||
43 | } |
||
44 | |||
45 | #if !CAVL_PARAM_FEATURE_KEYS_ARE_INDICES |
||
46 | |||
47 | static int CAvl_compare_entries (CAvlArg arg, CAvlRef node1, CAvlRef node2) |
||
48 | { |
||
49 | int res = CAVL_PARAM_FUN_COMPARE_ENTRIES(arg, node1, node2); |
||
50 | ASSERT(res >= -1) |
||
51 | ASSERT(res <= 1) |
||
52 | |||
53 | return res; |
||
54 | } |
||
55 | |||
56 | #if !CAVL_PARAM_FEATURE_NOKEYS |
||
57 | |||
58 | static int CAvl_compare_key_entry (CAvlArg arg, CAvlKey key1, CAvlRef node2) |
||
59 | { |
||
60 | int res = CAVL_PARAM_FUN_COMPARE_KEY_ENTRY(arg, key1, node2); |
||
61 | ASSERT(res >= -1) |
||
62 | ASSERT(res <= 1) |
||
63 | |||
64 | return res; |
||
65 | } |
||
66 | |||
67 | #endif |
||
68 | |||
69 | #endif |
||
70 | |||
71 | #if CAVL_PARAM_FEATURE_ASSOC |
||
72 | |||
73 | static CAvlAssoc CAvl_compute_node_assoc (CAvlArg arg, CAvlRef node) |
||
74 | { |
||
75 | CAvlAssoc sum = CAVL_PARAM_FUN_ASSOC_VALUE(arg, node); |
||
76 | if (CAvl_link(node)[0] != CAvl_nulllink()) { |
||
77 | sum = CAVL_PARAM_FUN_ASSOC_OPER(arg, CAvl_assoc(CAvlDeref(arg, CAvl_link(node)[0])), sum); |
||
78 | } |
||
79 | if (CAvl_link(node)[1] != CAvl_nulllink()) { |
||
80 | sum = CAVL_PARAM_FUN_ASSOC_OPER(arg, sum, CAvl_assoc(CAvlDeref(arg, CAvl_link(node)[1]))); |
||
81 | } |
||
82 | return sum; |
||
83 | } |
||
84 | |||
85 | #endif |
||
86 | |||
87 | static int CAvl_check_parent (CAvlRef p, CAvlRef c) |
||
88 | { |
||
89 | return (p.link == CAvl_parent(c)) && (p.link == CAvl_nulllink() || c.link == CAvl_link(p)[0] || c.link == CAvl_link(p)[1]); |
||
90 | } |
||
91 | |||
92 | static int CAvl_verify_recurser (CAvlArg arg, CAvlRef n) |
||
93 | { |
||
94 | ASSERT_FORCE(CAvl_balance(n) >= -1) |
||
95 | ASSERT_FORCE(CAvl_balance(n) <= 1) |
||
96 | |||
97 | int height_left = 0; |
||
98 | int height_right = 0; |
||
99 | #if CAVL_PARAM_FEATURE_COUNTS |
||
100 | CAvlCount count_left = 0; |
||
101 | CAvlCount count_right = 0; |
||
102 | #endif |
||
103 | |||
104 | // check left subtree |
||
105 | if (CAvl_link(n)[0] != CAvl_nulllink()) { |
||
106 | // check parent link |
||
107 | ASSERT_FORCE(CAvl_parent(CAvlDeref(arg, CAvl_link(n)[0])) == n.link) |
||
108 | // check binary search tree |
||
109 | #if !CAVL_PARAM_FEATURE_KEYS_ARE_INDICES |
||
110 | ASSERT_FORCE(CAvl_compare_entries(arg, CAvlDeref(arg, CAvl_link(n)[0]), n) == -1) |
||
111 | #endif |
||
112 | // recursively calculate height |
||
113 | height_left = CAvl_verify_recurser(arg, CAvlDeref(arg, CAvl_link(n)[0])); |
||
114 | #if CAVL_PARAM_FEATURE_COUNTS |
||
115 | count_left = CAvl_count(CAvlDeref(arg, CAvl_link(n)[0])); |
||
116 | #endif |
||
117 | } |
||
118 | |||
119 | // check right subtree |
||
120 | if (CAvl_link(n)[1] != CAvl_nulllink()) { |
||
121 | // check parent link |
||
122 | ASSERT_FORCE(CAvl_parent(CAvlDeref(arg, CAvl_link(n)[1])) == n.link) |
||
123 | // check binary search tree |
||
124 | #if !CAVL_PARAM_FEATURE_KEYS_ARE_INDICES |
||
125 | ASSERT_FORCE(CAvl_compare_entries(arg, CAvlDeref(arg, CAvl_link(n)[1]), n) == 1) |
||
126 | #endif |
||
127 | // recursively calculate height |
||
128 | height_right = CAvl_verify_recurser(arg, CAvlDeref(arg, CAvl_link(n)[1])); |
||
129 | #if CAVL_PARAM_FEATURE_COUNTS |
||
130 | count_right = CAvl_count(CAvlDeref(arg, CAvl_link(n)[1])); |
||
131 | #endif |
||
132 | } |
||
133 | |||
134 | // check balance factor |
||
135 | ASSERT_FORCE(CAvl_balance(n) == height_right - height_left) |
||
136 | |||
137 | #if CAVL_PARAM_FEATURE_COUNTS |
||
138 | // check count |
||
139 | ASSERT_FORCE(CAvl_count(n) == 1 + count_left + count_right) |
||
140 | #endif |
||
141 | |||
142 | #if CAVL_PARAM_FEATURE_ASSOC |
||
143 | // check assoc |
||
144 | ASSERT_FORCE(CAvl_assoc(n) == CAvl_compute_node_assoc(arg, n)) |
||
145 | #endif |
||
146 | |||
147 | return CAvl_MAX(height_left, height_right) + 1; |
||
148 | } |
||
149 | |||
150 | static void CAvl_assert_tree (CAvl *o, CAvlArg arg) |
||
151 | { |
||
152 | #ifdef CAVL_AUTO_VERIFY |
||
153 | CAvl_Verify(o, arg); |
||
154 | #endif |
||
155 | } |
||
156 | |||
157 | #if CAVL_PARAM_FEATURE_COUNTS |
||
158 | static void CAvl_update_count_from_children (CAvlArg arg, CAvlRef n) |
||
159 | { |
||
160 | CAvlCount left_count = CAvl_link(n)[0] != CAvl_nulllink() ? CAvl_count(CAvlDeref(arg, CAvl_link(n)[0])) : 0; |
||
161 | CAvlCount right_count = CAvl_link(n)[1] != CAvl_nulllink() ? CAvl_count(CAvlDeref(arg, CAvl_link(n)[1])) : 0; |
||
162 | CAvl_count(n) = 1 + left_count + right_count; |
||
163 | } |
||
164 | #endif |
||
165 | |||
166 | static void CAvl_rotate (CAvl *o, CAvlArg arg, CAvlRef r, uint8_t dir, CAvlRef r_parent) |
||
167 | { |
||
168 | ASSERT(CAvl_check_parent(r_parent, r)) |
||
169 | CAvlRef nr = CAvlDeref(arg, CAvl_link(r)[!dir]); |
||
170 | |||
171 | CAvl_link(r)[!dir] = CAvl_link(nr)[dir]; |
||
172 | if (CAvl_link(r)[!dir] != CAvl_nulllink()) { |
||
173 | CAvl_parent(CAvlDeref(arg, CAvl_link(r)[!dir])) = r.link; |
||
174 | } |
||
175 | CAvl_link(nr)[dir] = r.link; |
||
176 | CAvl_parent(nr) = r_parent.link; |
||
177 | if (r_parent.link != CAvl_nulllink()) { |
||
178 | CAvl_link(r_parent)[r.link == CAvl_link(r_parent)[1]] = nr.link; |
||
179 | } else { |
||
180 | o->root = nr.link; |
||
181 | } |
||
182 | CAvl_parent(r) = nr.link; |
||
183 | |||
184 | #if CAVL_PARAM_FEATURE_COUNTS |
||
185 | CAvl_update_count_from_children(arg, r); |
||
186 | CAvl_update_count_from_children(arg, nr); |
||
187 | #endif |
||
188 | |||
189 | #if CAVL_PARAM_FEATURE_ASSOC |
||
190 | CAvl_assoc(r) = CAvl_compute_node_assoc(arg, r); |
||
191 | CAvl_assoc(nr) = CAvl_compute_node_assoc(arg, nr); |
||
192 | #endif |
||
193 | } |
||
194 | |||
195 | static CAvlRef CAvl_subtree_min (CAvlArg arg, CAvlRef n) |
||
196 | { |
||
197 | ASSERT(n.link != CAvl_nulllink()) |
||
198 | |||
199 | while (CAvl_link(n)[0] != CAvl_nulllink()) { |
||
200 | n = CAvlDeref(arg, CAvl_link(n)[0]); |
||
201 | } |
||
202 | |||
203 | return n; |
||
204 | } |
||
205 | |||
206 | static CAvlRef CAvl_subtree_max (CAvlArg arg, CAvlRef n) |
||
207 | { |
||
208 | ASSERT(n.link != CAvl_nulllink()) |
||
209 | |||
210 | while (CAvl_link(n)[1] != CAvl_nulllink()) { |
||
211 | n = CAvlDeref(arg, CAvl_link(n)[1]); |
||
212 | } |
||
213 | |||
214 | return n; |
||
215 | } |
||
216 | |||
217 | static void CAvl_replace_subtree_fix_assoc (CAvl *o, CAvlArg arg, CAvlRef dest, CAvlRef n, CAvlRef dest_parent) |
||
218 | { |
||
219 | ASSERT(dest.link != CAvl_nulllink()) |
||
220 | ASSERT(CAvl_check_parent(dest_parent, dest)) |
||
221 | |||
222 | if (dest_parent.link != CAvl_nulllink()) { |
||
223 | CAvl_link(dest_parent)[dest.link == CAvl_link(dest_parent)[1]] = n.link; |
||
224 | } else { |
||
225 | o->root = n.link; |
||
226 | } |
||
227 | if (n.link != CAvl_nulllink()) { |
||
228 | CAvl_parent(n) = CAvl_parent(dest); |
||
229 | } |
||
230 | |||
231 | #if CAVL_PARAM_FEATURE_COUNTS || CAVL_PARAM_FEATURE_ASSOC |
||
232 | for (CAvlRef c = dest_parent; c.link != CAvl_nulllink(); c = CAvlDeref(arg, CAvl_parent(c))) { |
||
233 | #if CAVL_PARAM_FEATURE_COUNTS |
||
234 | ASSERT(CAvl_count(c) >= CAvl_count(dest)) |
||
235 | CAvl_count(c) -= CAvl_count(dest); |
||
236 | if (n.link != CAvl_nulllink()) { |
||
237 | ASSERT(CAvl_count(n) <= CAVL_PARAM_VALUE_COUNT_MAX - CAvl_count(c)) |
||
238 | CAvl_count(c) += CAvl_count(n); |
||
239 | } |
||
240 | #endif |
||
241 | #if CAVL_PARAM_FEATURE_ASSOC |
||
242 | CAvl_assoc(c) = CAvl_compute_node_assoc(arg, c); |
||
243 | #endif |
||
244 | } |
||
245 | #endif |
||
246 | } |
||
247 | |||
248 | static void CAvl_swap_for_remove (CAvl *o, CAvlArg arg, CAvlRef node, CAvlRef enode, CAvlRef node_parent, CAvlRef enode_parent) |
||
249 | { |
||
250 | ASSERT(CAvl_check_parent(node_parent, node)) |
||
251 | ASSERT(CAvl_check_parent(enode_parent, enode)) |
||
252 | |||
253 | if (enode_parent.link == node.link) { |
||
254 | // when the nodes are directly connected we need special handling |
||
255 | |||
256 | uint8_t side = (enode.link == CAvl_link(node)[1]); |
||
257 | CAvlRef c = CAvlDeref(arg, CAvl_link(node)[!side]); |
||
258 | |||
259 | if ((CAvl_link(node)[0] = CAvl_link(enode)[0]) != CAvl_nulllink()) { |
||
260 | CAvl_parent(CAvlDeref(arg, CAvl_link(node)[0])) = node.link; |
||
261 | } |
||
262 | if ((CAvl_link(node)[1] = CAvl_link(enode)[1]) != CAvl_nulllink()) { |
||
263 | CAvl_parent(CAvlDeref(arg, CAvl_link(node)[1])) = node.link; |
||
264 | } |
||
265 | |||
266 | CAvl_parent(enode) = CAvl_parent(node); |
||
267 | if (node_parent.link != CAvl_nulllink()) { |
||
268 | CAvl_link(node_parent)[node.link == CAvl_link(node_parent)[1]] = enode.link; |
||
269 | } else { |
||
270 | o->root = enode.link; |
||
271 | } |
||
272 | |||
273 | CAvl_link(enode)[side] = node.link; |
||
274 | CAvl_parent(node) = enode.link; |
||
275 | if ((CAvl_link(enode)[!side] = c.link) != CAvl_nulllink()) { |
||
276 | CAvl_parent(c) = enode.link; |
||
277 | } |
||
278 | } else { |
||
279 | CAvlRef temp; |
||
280 | |||
281 | // swap parents |
||
282 | temp = node_parent; |
||
283 | CAvl_parent(node) = CAvl_parent(enode); |
||
284 | if (enode_parent.link != CAvl_nulllink()) { |
||
285 | CAvl_link(enode_parent)[enode.link == CAvl_link(enode_parent)[1]] = node.link; |
||
286 | } else { |
||
287 | o->root = node.link; |
||
288 | } |
||
289 | CAvl_parent(enode) = temp.link; |
||
290 | if (temp.link != CAvl_nulllink()) { |
||
291 | CAvl_link(temp)[node.link == CAvl_link(temp)[1]] = enode.link; |
||
292 | } else { |
||
293 | o->root = enode.link; |
||
294 | } |
||
295 | |||
296 | // swap left children |
||
297 | temp = CAvlDeref(arg, CAvl_link(node)[0]); |
||
298 | if ((CAvl_link(node)[0] = CAvl_link(enode)[0]) != CAvl_nulllink()) { |
||
299 | CAvl_parent(CAvlDeref(arg, CAvl_link(node)[0])) = node.link; |
||
300 | } |
||
301 | if ((CAvl_link(enode)[0] = temp.link) != CAvl_nulllink()) { |
||
302 | CAvl_parent(CAvlDeref(arg, CAvl_link(enode)[0])) = enode.link; |
||
303 | } |
||
304 | |||
305 | // swap right children |
||
306 | temp = CAvlDeref(arg, CAvl_link(node)[1]); |
||
307 | if ((CAvl_link(node)[1] = CAvl_link(enode)[1]) != CAvl_nulllink()) { |
||
308 | CAvl_parent(CAvlDeref(arg, CAvl_link(node)[1])) = node.link; |
||
309 | } |
||
310 | if ((CAvl_link(enode)[1] = temp.link) != CAvl_nulllink()) { |
||
311 | CAvl_parent(CAvlDeref(arg, CAvl_link(enode)[1])) = enode.link; |
||
312 | } |
||
313 | } |
||
314 | |||
315 | // swap balance factors |
||
316 | int8_t b = CAvl_balance(node); |
||
317 | CAvl_balance(node) = CAvl_balance(enode); |
||
318 | CAvl_balance(enode) = b; |
||
319 | |||
320 | #if CAVL_PARAM_FEATURE_COUNTS |
||
321 | // swap counts |
||
322 | CAvlCount c = CAvl_count(node); |
||
323 | CAvl_count(node) = CAvl_count(enode); |
||
324 | CAvl_count(enode) = c; |
||
325 | #endif |
||
326 | |||
327 | // not fixing assoc values here because CAvl_replace_subtree_fix_assoc() will do it |
||
328 | } |
||
329 | |||
330 | static void CAvl_rebalance (CAvl *o, CAvlArg arg, CAvlRef node, uint8_t side, int8_t deltac) |
||
331 | { |
||
332 | ASSERT(side == 0 || side == 1) |
||
333 | ASSERT(deltac >= -1 && deltac <= 1) |
||
334 | ASSERT(CAvl_balance(node) >= -1 && CAvl_balance(node) <= 1) |
||
335 | |||
336 | // if no subtree changed its height, no more rebalancing is needed |
||
337 | if (deltac == 0) { |
||
338 | return; |
||
339 | } |
||
340 | |||
341 | // calculate how much our height changed |
||
342 | int8_t delta = CAvl_MAX(deltac, CAvl_OPTNEG(CAvl_balance(node), side)) - CAvl_MAX(0, CAvl_OPTNEG(CAvl_balance(node), side)); |
||
343 | ASSERT(delta >= -1 && delta <= 1) |
||
344 | |||
345 | // update our balance factor |
||
346 | CAvl_balance(node) -= CAvl_OPTNEG(deltac, side); |
||
347 | |||
348 | CAvlRef child; |
||
349 | CAvlRef gchild; |
||
350 | |||
351 | // perform transformations if the balance factor is wrong |
||
352 | if (CAvl_balance(node) == 2 || CAvl_balance(node) == -2) { |
||
353 | uint8_t bside; |
||
354 | int8_t bsidef; |
||
355 | if (CAvl_balance(node) == 2) { |
||
356 | bside = 1; |
||
357 | bsidef = 1; |
||
358 | } else { |
||
359 | bside = 0; |
||
360 | bsidef = -1; |
||
361 | } |
||
362 | |||
363 | ASSERT(CAvl_link(node)[bside] != CAvl_nulllink()) |
||
364 | child = CAvlDeref(arg, CAvl_link(node)[bside]); |
||
365 | |||
366 | switch (CAvl_balance(child) * bsidef) { |
||
367 | case 1: |
||
368 | CAvl_rotate(o, arg, node, !bside, CAvlDeref(arg, CAvl_parent(node))); |
||
369 | CAvl_balance(node) = 0; |
||
370 | CAvl_balance(child) = 0; |
||
371 | node = child; |
||
372 | delta -= 1; |
||
373 | break; |
||
374 | case 0: |
||
375 | CAvl_rotate(o, arg, node, !bside, CAvlDeref(arg, CAvl_parent(node))); |
||
376 | CAvl_balance(node) = 1 * bsidef; |
||
377 | CAvl_balance(child) = -1 * bsidef; |
||
378 | node = child; |
||
379 | break; |
||
380 | case -1: |
||
381 | ASSERT(CAvl_link(child)[!bside] != CAvl_nulllink()) |
||
382 | gchild = CAvlDeref(arg, CAvl_link(child)[!bside]); |
||
383 | CAvl_rotate(o, arg, child, bside, node); |
||
384 | CAvl_rotate(o, arg, node, !bside, CAvlDeref(arg, CAvl_parent(node))); |
||
385 | CAvl_balance(node) = -CAvl_MAX(0, CAvl_balance(gchild) * bsidef) * bsidef; |
||
386 | CAvl_balance(child) = CAvl_MAX(0, -CAvl_balance(gchild) * bsidef) * bsidef; |
||
387 | CAvl_balance(gchild) = 0; |
||
388 | node = gchild; |
||
389 | delta -= 1; |
||
390 | break; |
||
391 | default: |
||
392 | ASSERT(0); |
||
393 | } |
||
394 | } |
||
395 | |||
396 | ASSERT(delta >= -1 && delta <= 1) |
||
397 | // Transformations above preserve this. Proof: |
||
398 | // - if a child subtree gained 1 height and rebalancing was needed, |
||
399 | // it was the heavier subtree. Then delta was was originally 1, because |
||
400 | // the heaviest subtree gained one height. If the transformation reduces |
||
401 | // delta by one, it becomes 0. |
||
402 | // - if a child subtree lost 1 height and rebalancing was needed, it |
||
403 | // was the lighter subtree. Then delta was originally 0, because |
||
404 | // the height of the heaviest subtree was unchanged. If the transformation |
||
405 | // reduces delta by one, it becomes -1. |
||
406 | |||
407 | if (CAvl_parent(node) != CAvl_nulllink()) { |
||
408 | CAvlRef node_parent = CAvlDeref(arg, CAvl_parent(node)); |
||
409 | CAvl_rebalance(o, arg, node_parent, node.link == CAvl_link(node_parent)[1], delta); |
||
410 | } |
||
411 | } |
||
412 | |||
413 | #if CAVL_PARAM_FEATURE_KEYS_ARE_INDICES |
||
414 | static CAvlCount CAvl_child_count (CAvlArg arg, CAvlRef n, int dir) |
||
415 | { |
||
416 | return (CAvl_link(n)[dir] != CAvl_nulllink() ? CAvl_count(CAvlDeref(arg, CAvl_link(n)[dir])) : 0); |
||
417 | } |
||
418 | #endif |
||
419 | |||
420 | static int CAvlIsNullRef (CAvlRef node) |
||
421 | { |
||
422 | return node.link == CAvl_nulllink(); |
||
423 | } |
||
424 | |||
425 | static int CAvlIsValidRef (CAvlRef node) |
||
426 | { |
||
427 | return node.link != CAvl_nulllink(); |
||
428 | } |
||
429 | |||
430 | static CAvlRef CAvlDeref (CAvlArg arg, CAvlLink link) |
||
431 | { |
||
432 | if (link == CAvl_nulllink()) { |
||
433 | return CAvl_nullref(); |
||
434 | } |
||
435 | |||
436 | CAvlRef n; |
||
437 | n.ptr = CAVL_PARAM_FUN_DEREF(arg, link); |
||
438 | n.link = link; |
||
439 | |||
440 | ASSERT(n.ptr) |
||
441 | |||
442 | return n; |
||
443 | } |
||
444 | |||
445 | static void CAvl_Init (CAvl *o) |
||
446 | { |
||
447 | o->root = CAvl_nulllink(); |
||
448 | } |
||
449 | |||
450 | #if !CAVL_PARAM_FEATURE_KEYS_ARE_INDICES |
||
451 | |||
452 | static int CAvl_Insert (CAvl *o, CAvlArg arg, CAvlRef node, CAvlRef *out_ref) |
||
453 | { |
||
454 | ASSERT(node.link != CAvl_nulllink()) |
||
455 | #if CAVL_PARAM_FEATURE_COUNTS |
||
456 | ASSERT(CAvl_Count(o, arg) < CAVL_PARAM_VALUE_COUNT_MAX) |
||
457 | #endif |
||
458 | |||
459 | // insert to root? |
||
460 | if (o->root == CAvl_nulllink()) { |
||
461 | o->root = node.link; |
||
462 | CAvl_parent(node) = CAvl_nulllink(); |
||
463 | CAvl_link(node)[0] = CAvl_nulllink(); |
||
464 | CAvl_link(node)[1] = CAvl_nulllink(); |
||
465 | CAvl_balance(node) = 0; |
||
466 | #if CAVL_PARAM_FEATURE_COUNTS |
||
467 | CAvl_count(node) = 1; |
||
468 | #endif |
||
469 | #if CAVL_PARAM_FEATURE_ASSOC |
||
470 | CAvl_assoc(node) = CAVL_PARAM_FUN_ASSOC_VALUE(arg, node); |
||
471 | #endif |
||
472 | |||
473 | CAvl_assert_tree(o, arg); |
||
474 | |||
475 | if (out_ref) { |
||
476 | *out_ref = CAvl_nullref(); |
||
477 | } |
||
478 | return 1; |
||
479 | } |
||
480 | |||
481 | CAvlRef c = CAvlDeref(arg, o->root); |
||
482 | int side; |
||
483 | while (1) { |
||
484 | int comp = CAvl_compare_entries(arg, node, c); |
||
485 | |||
486 | if (comp == 0) { |
||
487 | if (out_ref) { |
||
488 | *out_ref = c; |
||
489 | } |
||
490 | return 0; |
||
491 | } |
||
492 | |||
493 | side = (comp == 1); |
||
494 | |||
495 | if (CAvl_link(c)[side] == CAvl_nulllink()) { |
||
496 | break; |
||
497 | } |
||
498 | |||
499 | c = CAvlDeref(arg, CAvl_link(c)[side]); |
||
500 | } |
||
501 | |||
502 | CAvl_link(c)[side] = node.link; |
||
503 | CAvl_parent(node) = c.link; |
||
504 | CAvl_link(node)[0] = CAvl_nulllink(); |
||
505 | CAvl_link(node)[1] = CAvl_nulllink(); |
||
506 | CAvl_balance(node) = 0; |
||
507 | #if CAVL_PARAM_FEATURE_COUNTS |
||
508 | CAvl_count(node) = 1; |
||
509 | #endif |
||
510 | #if CAVL_PARAM_FEATURE_ASSOC |
||
511 | CAvl_assoc(node) = CAVL_PARAM_FUN_ASSOC_VALUE(arg, node); |
||
512 | #endif |
||
513 | |||
514 | #if CAVL_PARAM_FEATURE_COUNTS || CAVL_PARAM_FEATURE_ASSOC |
||
515 | for (CAvlRef p = c; p.link != CAvl_nulllink(); p = CAvlDeref(arg, CAvl_parent(p))) { |
||
516 | #if CAVL_PARAM_FEATURE_COUNTS |
||
517 | CAvl_count(p)++; |
||
518 | #endif |
||
519 | #if CAVL_PARAM_FEATURE_ASSOC |
||
520 | CAvl_assoc(p) = CAvl_compute_node_assoc(arg, p); |
||
521 | #endif |
||
522 | } |
||
523 | #endif |
||
524 | |||
525 | CAvl_rebalance(o, arg, c, side, 1); |
||
526 | |||
527 | CAvl_assert_tree(o, arg); |
||
528 | |||
529 | if (out_ref) { |
||
530 | *out_ref = c; |
||
531 | } |
||
532 | return 1; |
||
533 | } |
||
534 | |||
535 | #else |
||
536 | |||
537 | static void CAvl_InsertAt (CAvl *o, CAvlArg arg, CAvlRef node, CAvlCount index) |
||
538 | { |
||
539 | ASSERT(node.link != CAvl_nulllink()) |
||
540 | ASSERT(index <= CAvl_Count(o, arg)) |
||
541 | ASSERT(CAvl_Count(o, arg) < CAVL_PARAM_VALUE_COUNT_MAX) |
||
542 | |||
543 | // insert to root? |
||
544 | if (o->root == CAvl_nulllink()) { |
||
545 | o->root = node.link; |
||
546 | CAvl_parent(node) = CAvl_nulllink(); |
||
547 | CAvl_link(node)[0] = CAvl_nulllink(); |
||
548 | CAvl_link(node)[1] = CAvl_nulllink(); |
||
549 | CAvl_balance(node) = 0; |
||
550 | CAvl_count(node) = 1; |
||
551 | #if CAVL_PARAM_FEATURE_ASSOC |
||
552 | CAvl_assoc(node) = CAVL_PARAM_FUN_ASSOC_VALUE(arg, node); |
||
553 | #endif |
||
554 | |||
555 | CAvl_assert_tree(o, arg); |
||
556 | return; |
||
557 | } |
||
558 | |||
559 | CAvlRef c = CAvlDeref(arg, o->root); |
||
560 | CAvlCount c_idx = CAvl_child_count(arg, c, 0); |
||
561 | int side; |
||
562 | while (1) { |
||
563 | side = (index > c_idx); |
||
564 | |||
565 | if (CAvl_link(c)[side] == CAvl_nulllink()) { |
||
566 | break; |
||
567 | } |
||
568 | |||
569 | c = CAvlDeref(arg, CAvl_link(c)[side]); |
||
570 | |||
571 | if (side == 0) { |
||
572 | c_idx -= 1 + CAvl_child_count(arg, c, 1); |
||
573 | } else { |
||
574 | c_idx += 1 + CAvl_child_count(arg, c, 0); |
||
575 | } |
||
576 | } |
||
577 | |||
578 | CAvl_link(c)[side] = node.link; |
||
579 | CAvl_parent(node) = c.link; |
||
580 | CAvl_link(node)[0] = CAvl_nulllink(); |
||
581 | CAvl_link(node)[1] = CAvl_nulllink(); |
||
582 | CAvl_balance(node) = 0; |
||
583 | CAvl_count(node) = 1; |
||
584 | #if CAVL_PARAM_FEATURE_ASSOC |
||
585 | CAvl_assoc(node) = CAVL_PARAM_FUN_ASSOC_VALUE(arg, node); |
||
586 | #endif |
||
587 | |||
588 | for (CAvlRef p = c; p.link != CAvl_nulllink(); p = CAvlDeref(arg, CAvl_parent(p))) { |
||
589 | CAvl_count(p)++; |
||
590 | #if CAVL_PARAM_FEATURE_ASSOC |
||
591 | CAvl_assoc(p) = CAvl_compute_node_assoc(arg, p); |
||
592 | #endif |
||
593 | } |
||
594 | |||
595 | CAvl_rebalance(o, arg, c, side, 1); |
||
596 | |||
597 | CAvl_assert_tree(o, arg); |
||
598 | return; |
||
599 | } |
||
600 | |||
601 | #endif |
||
602 | |||
603 | static void CAvl_Remove (CAvl *o, CAvlArg arg, CAvlRef node) |
||
604 | { |
||
605 | ASSERT(node.link != CAvl_nulllink()) |
||
606 | ASSERT(o->root != CAvl_nulllink()) |
||
607 | |||
608 | if (CAvl_link(node)[0] != CAvl_nulllink() && CAvl_link(node)[1] != CAvl_nulllink()) { |
||
609 | CAvlRef max = CAvl_subtree_max(arg, CAvlDeref(arg, CAvl_link(node)[0])); |
||
610 | CAvl_swap_for_remove(o, arg, node, max, CAvlDeref(arg, CAvl_parent(node)), CAvlDeref(arg, CAvl_parent(max))); |
||
611 | } |
||
612 | |||
613 | ASSERT(CAvl_link(node)[0] == CAvl_nulllink() || CAvl_link(node)[1] == CAvl_nulllink()) |
||
614 | |||
615 | CAvlRef paren = CAvlDeref(arg, CAvl_parent(node)); |
||
616 | CAvlRef child = (CAvl_link(node)[0] != CAvl_nulllink() ? CAvlDeref(arg, CAvl_link(node)[0]) : CAvlDeref(arg, CAvl_link(node)[1])); |
||
617 | |||
618 | if (paren.link != CAvl_nulllink()) { |
||
619 | int side = (node.link == CAvl_link(paren)[1]); |
||
620 | CAvl_replace_subtree_fix_assoc(o, arg, node, child, paren); |
||
621 | CAvl_rebalance(o, arg, paren, side, -1); |
||
622 | } else { |
||
623 | CAvl_replace_subtree_fix_assoc(o, arg, node, child, paren); |
||
624 | } |
||
625 | |||
626 | CAvl_assert_tree(o, arg); |
||
627 | } |
||
628 | |||
629 | #if !CAVL_PARAM_FEATURE_KEYS_ARE_INDICES && !CAVL_PARAM_FEATURE_NOKEYS |
||
630 | |||
631 | static CAvlRef CAvl_Lookup (const CAvl *o, CAvlArg arg, CAvlKey key) |
||
632 | { |
||
633 | if (o->root == CAvl_nulllink()) { |
||
634 | return CAvl_nullref(); |
||
635 | } |
||
636 | |||
637 | CAvlRef c = CAvlDeref(arg, o->root); |
||
638 | while (1) { |
||
639 | // compare |
||
640 | int comp = CAvl_compare_key_entry(arg, key, c); |
||
641 | |||
642 | // have we found a node that compares equal? |
||
643 | if (comp == 0) { |
||
644 | return c; |
||
645 | } |
||
646 | |||
647 | int side = (comp == 1); |
||
648 | |||
649 | // have we reached a leaf? |
||
650 | if (CAvl_link(c)[side] == CAvl_nulllink()) { |
||
651 | return c; |
||
652 | } |
||
653 | |||
654 | c = CAvlDeref(arg, CAvl_link(c)[side]); |
||
655 | } |
||
656 | } |
||
657 | |||
658 | static CAvlRef CAvl_LookupExact (const CAvl *o, CAvlArg arg, CAvlKey key) |
||
659 | { |
||
660 | if (o->root == CAvl_nulllink()) { |
||
661 | return CAvl_nullref(); |
||
662 | } |
||
663 | |||
664 | CAvlRef c = CAvlDeref(arg, o->root); |
||
665 | while (1) { |
||
666 | // compare |
||
667 | int comp = CAvl_compare_key_entry(arg, key, c); |
||
668 | |||
669 | // have we found a node that compares equal? |
||
670 | if (comp == 0) { |
||
671 | return c; |
||
672 | } |
||
673 | |||
674 | int side = (comp == 1); |
||
675 | |||
676 | // have we reached a leaf? |
||
677 | if (CAvl_link(c)[side] == CAvl_nulllink()) { |
||
678 | return CAvl_nullref(); |
||
679 | } |
||
680 | |||
681 | c = CAvlDeref(arg, CAvl_link(c)[side]); |
||
682 | } |
||
683 | } |
||
684 | |||
685 | static CAvlRef CAvl_GetFirstGreater (const CAvl *o, CAvlArg arg, CAvlKey key) |
||
686 | { |
||
687 | CAvlRef c = CAvl_Lookup(o, arg, key); |
||
688 | if (CAvlIsNullRef(c)) { |
||
689 | return CAvl_nullref(); |
||
690 | } |
||
691 | |||
692 | if (CAvl_compare_key_entry(arg, key, c) >= 0) { |
||
693 | c = CAvl_GetNext(o, arg, c); |
||
694 | if (CAvlIsNullRef(c)) { |
||
695 | return CAvl_nullref(); |
||
696 | } |
||
697 | } |
||
698 | |||
699 | ASSERT(CAvl_compare_key_entry(arg, key, c) < 0); |
||
700 | |||
701 | return c; |
||
702 | } |
||
703 | |||
704 | static CAvlRef CAvl_GetLastLesser (const CAvl *o, CAvlArg arg, CAvlKey key) |
||
705 | { |
||
706 | CAvlRef c = CAvl_Lookup(o, arg, key); |
||
707 | if (CAvlIsNullRef(c)) { |
||
708 | return CAvl_nullref(); |
||
709 | } |
||
710 | |||
711 | if (CAvl_compare_key_entry(arg, key, c) <= 0) { |
||
712 | c = CAvl_GetPrev(o, arg, c); |
||
713 | if (CAvlIsNullRef(c)) { |
||
714 | return CAvl_nullref(); |
||
715 | } |
||
716 | } |
||
717 | |||
718 | ASSERT(CAvl_compare_key_entry(arg, key, c) > 0); |
||
719 | |||
720 | return c; |
||
721 | } |
||
722 | |||
723 | static CAvlRef CAvl_GetFirstGreaterEqual (const CAvl *o, CAvlArg arg, CAvlKey key) |
||
724 | { |
||
725 | CAvlRef c = CAvl_Lookup(o, arg, key); |
||
726 | if (CAvlIsNullRef(c)) { |
||
727 | return CAvl_nullref(); |
||
728 | } |
||
729 | |||
730 | if (CAvl_compare_key_entry(arg, key, c) > 0) { |
||
731 | c = CAvl_GetNext(o, arg, c); |
||
732 | if (CAvlIsNullRef(c)) { |
||
733 | return CAvl_nullref(); |
||
734 | } |
||
735 | } |
||
736 | |||
737 | ASSERT(CAvl_compare_key_entry(arg, key, c) <= 0); |
||
738 | |||
739 | return c; |
||
740 | } |
||
741 | |||
742 | static CAvlRef CAvl_GetLastLesserEqual (const CAvl *o, CAvlArg arg, CAvlKey key) |
||
743 | { |
||
744 | CAvlRef c = CAvl_Lookup(o, arg, key); |
||
745 | if (CAvlIsNullRef(c)) { |
||
746 | return CAvl_nullref(); |
||
747 | } |
||
748 | |||
749 | if (CAvl_compare_key_entry(arg, key, c) < 0) { |
||
750 | c = CAvl_GetPrev(o, arg, c); |
||
751 | if (CAvlIsNullRef(c)) { |
||
752 | return CAvl_nullref(); |
||
753 | } |
||
754 | } |
||
755 | |||
756 | ASSERT(CAvl_compare_key_entry(arg, key, c) >= 0); |
||
757 | |||
758 | return c; |
||
759 | } |
||
760 | |||
761 | #endif |
||
762 | |||
763 | static CAvlRef CAvl_GetFirst (const CAvl *o, CAvlArg arg) |
||
764 | { |
||
765 | if (o->root == CAvl_nulllink()) { |
||
766 | return CAvl_nullref(); |
||
767 | } |
||
768 | |||
769 | return CAvl_subtree_min(arg, CAvlDeref(arg, o->root)); |
||
770 | } |
||
771 | |||
772 | static CAvlRef CAvl_GetLast (const CAvl *o, CAvlArg arg) |
||
773 | { |
||
774 | if (o->root == CAvl_nulllink()) { |
||
775 | return CAvl_nullref(); |
||
776 | } |
||
777 | |||
778 | return CAvl_subtree_max(arg, CAvlDeref(arg, o->root)); |
||
779 | } |
||
780 | |||
781 | static CAvlRef CAvl_GetNext (const CAvl *o, CAvlArg arg, CAvlRef node) |
||
782 | { |
||
783 | ASSERT(node.link != CAvl_nulllink()) |
||
784 | ASSERT(o->root != CAvl_nulllink()) |
||
785 | |||
786 | if (CAvl_link(node)[1] != CAvl_nulllink()) { |
||
787 | node = CAvlDeref(arg, CAvl_link(node)[1]); |
||
788 | while (CAvl_link(node)[0] != CAvl_nulllink()) { |
||
789 | node = CAvlDeref(arg, CAvl_link(node)[0]); |
||
790 | } |
||
791 | } else { |
||
792 | while (CAvl_parent(node) != CAvl_nulllink() && node.link == CAvl_link(CAvlDeref(arg, CAvl_parent(node)))[1]) { |
||
793 | node = CAvlDeref(arg, CAvl_parent(node)); |
||
794 | } |
||
795 | node = CAvlDeref(arg, CAvl_parent(node)); |
||
796 | } |
||
797 | |||
798 | return node; |
||
799 | } |
||
800 | |||
801 | static CAvlRef CAvl_GetPrev (const CAvl *o, CAvlArg arg, CAvlRef node) |
||
802 | { |
||
803 | ASSERT(node.link != CAvl_nulllink()) |
||
804 | ASSERT(o->root != CAvl_nulllink()) |
||
805 | |||
806 | if (CAvl_link(node)[0] != CAvl_nulllink()) { |
||
807 | node = CAvlDeref(arg, CAvl_link(node)[0]); |
||
808 | while (CAvl_link(node)[1] != CAvl_nulllink()) { |
||
809 | node = CAvlDeref(arg, CAvl_link(node)[1]); |
||
810 | } |
||
811 | } else { |
||
812 | while (CAvl_parent(node) != CAvl_nulllink() && node.link == CAvl_link(CAvlDeref(arg, CAvl_parent(node)))[0]) { |
||
813 | node = CAvlDeref(arg, CAvl_parent(node)); |
||
814 | } |
||
815 | node = CAvlDeref(arg, CAvl_parent(node)); |
||
816 | } |
||
817 | |||
818 | return node; |
||
819 | } |
||
820 | |||
821 | static int CAvl_IsEmpty (const CAvl *o) |
||
822 | { |
||
823 | return o->root == CAvl_nulllink(); |
||
824 | } |
||
825 | |||
826 | static void CAvl_Verify (const CAvl *o, CAvlArg arg) |
||
827 | { |
||
828 | if (o->root != CAvl_nulllink()) { |
||
829 | CAvlRef root = CAvlDeref(arg, o->root); |
||
830 | ASSERT(CAvl_parent(root) == CAvl_nulllink()) |
||
831 | CAvl_verify_recurser(arg, root); |
||
832 | } |
||
833 | } |
||
834 | |||
835 | #if CAVL_PARAM_FEATURE_COUNTS |
||
836 | |||
837 | static CAvlCount CAvl_Count (const CAvl *o, CAvlArg arg) |
||
838 | { |
||
839 | return (o->root != CAvl_nulllink() ? CAvl_count(CAvlDeref(arg, o->root)) : 0); |
||
840 | } |
||
841 | |||
842 | static CAvlCount CAvl_IndexOf (const CAvl *o, CAvlArg arg, CAvlRef node) |
||
843 | { |
||
844 | ASSERT(node.link != CAvl_nulllink()) |
||
845 | ASSERT(o->root != CAvl_nulllink()) |
||
846 | |||
847 | CAvlCount index = (CAvl_link(node)[0] != CAvl_nulllink() ? CAvl_count(CAvlDeref(arg, CAvl_link(node)[0])) : 0); |
||
848 | |||
849 | CAvlRef paren = CAvlDeref(arg, CAvl_parent(node)); |
||
850 | |||
851 | for (CAvlRef c = node; paren.link != CAvl_nulllink(); c = paren, paren = CAvlDeref(arg, CAvl_parent(c))) { |
||
852 | if (c.link == CAvl_link(paren)[1]) { |
||
853 | ASSERT(CAvl_count(paren) > CAvl_count(c)) |
||
854 | ASSERT(CAvl_count(paren) - CAvl_count(c) <= CAVL_PARAM_VALUE_COUNT_MAX - index) |
||
855 | index += CAvl_count(paren) - CAvl_count(c); |
||
856 | } |
||
857 | } |
||
858 | |||
859 | return index; |
||
860 | } |
||
861 | |||
862 | static CAvlRef CAvl_GetAt (const CAvl *o, CAvlArg arg, CAvlCount index) |
||
863 | { |
||
864 | if (index >= CAvl_Count(o, arg)) { |
||
865 | return CAvl_nullref(); |
||
866 | } |
||
867 | |||
868 | CAvlRef c = CAvlDeref(arg, o->root); |
||
869 | |||
870 | while (1) { |
||
871 | ASSERT(c.link != CAvl_nulllink()) |
||
872 | ASSERT(index < CAvl_count(c)) |
||
873 | |||
874 | CAvlCount left_count = (CAvl_link(c)[0] != CAvl_nulllink() ? CAvl_count(CAvlDeref(arg, CAvl_link(c)[0])) : 0); |
||
875 | |||
876 | if (index == left_count) { |
||
877 | return c; |
||
878 | } |
||
879 | |||
880 | if (index < left_count) { |
||
881 | c = CAvlDeref(arg, CAvl_link(c)[0]); |
||
882 | } else { |
||
883 | c = CAvlDeref(arg, CAvl_link(c)[1]); |
||
884 | index -= left_count + 1; |
||
885 | } |
||
886 | } |
||
887 | } |
||
888 | |||
889 | #endif |
||
890 | |||
891 | #if CAVL_PARAM_FEATURE_ASSOC |
||
892 | |||
893 | static CAvlAssoc CAvl_AssocSum (const CAvl *o, CAvlArg arg) |
||
894 | { |
||
895 | if (o->root == CAvl_nulllink()) { |
||
896 | return CAVL_PARAM_VALUE_ASSOC_ZERO; |
||
897 | } |
||
898 | CAvlRef root = CAvlDeref(arg, o->root); |
||
899 | return CAvl_assoc(root); |
||
900 | } |
||
901 | |||
902 | static CAvlAssoc CAvl_ExclusiveAssocPrefixSum (const CAvl *o, CAvlArg arg, CAvlRef node) |
||
903 | { |
||
904 | ASSERT(node.link != CAvl_nulllink()) |
||
905 | ASSERT(o->root != CAvl_nulllink()) |
||
906 | |||
907 | CAvlAssoc sum = (CAvl_link(node)[0] != CAvl_nulllink() ? CAvl_assoc(CAvlDeref(arg, CAvl_link(node)[0])) : CAVL_PARAM_VALUE_ASSOC_ZERO); |
||
908 | |||
909 | CAvlRef paren = CAvlDeref(arg, CAvl_parent(node)); |
||
910 | |||
911 | for (CAvlRef c = node; paren.link != CAvl_nulllink(); c = paren, paren = CAvlDeref(arg, CAvl_parent(c))) { |
||
912 | if (c.link == CAvl_link(paren)[1]) { |
||
913 | CAvlAssoc c_val = CAVL_PARAM_FUN_ASSOC_VALUE(arg, paren); |
||
914 | sum = CAVL_PARAM_FUN_ASSOC_OPER(arg, c_val, sum); |
||
915 | if (CAvl_link(paren)[0] != CAvl_nulllink()) { |
||
916 | sum = CAVL_PARAM_FUN_ASSOC_OPER(arg, CAvl_assoc(CAvlDeref(arg, CAvl_link(paren)[0])), sum); |
||
917 | } |
||
918 | } |
||
919 | } |
||
920 | |||
921 | return sum; |
||
922 | } |
||
923 | |||
924 | static CAvlRef CAvl_FindLastExclusiveAssocPrefixSumLesserEqual (const CAvl *o, CAvlArg arg, CAvlAssoc sum, int (*sum_less) (void *, CAvlAssoc, CAvlAssoc), void *user) |
||
925 | { |
||
926 | CAvlRef result = CAvl_nullref(); |
||
927 | CAvlRef c = CAvlDeref(arg, o->root); |
||
928 | CAvlAssoc sum_offset = CAVL_PARAM_VALUE_ASSOC_ZERO; |
||
929 | |||
930 | while (c.link != CAvl_nulllink()) { |
||
931 | CAvlAssoc left_sum = (CAvl_link(c)[0] != CAvl_nulllink() ? CAvl_assoc(CAvlDeref(arg, CAvl_link(c)[0])) : CAVL_PARAM_VALUE_ASSOC_ZERO); |
||
932 | CAvlAssoc c_prefixsum = CAVL_PARAM_FUN_ASSOC_OPER(arg, sum_offset, left_sum); |
||
933 | |||
934 | if (sum_less(user, sum, c_prefixsum)) { |
||
935 | c = CAvlDeref(arg, CAvl_link(c)[0]); |
||
936 | } else { |
||
937 | result = c; |
||
938 | CAvlAssoc c_val = CAVL_PARAM_FUN_ASSOC_VALUE(arg, c); |
||
939 | sum_offset = CAVL_PARAM_FUN_ASSOC_OPER(arg, c_prefixsum, c_val); |
||
940 | c = CAvlDeref(arg, CAvl_link(c)[1]); |
||
941 | } |
||
942 | } |
||
943 | |||
944 | return result; |
||
945 | } |
||
946 | |||
947 | #endif |
||
948 | |||
949 | #include "CAvl_footer.h" |