BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
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"