BadVPN – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | /** |
2 | * @file BAVL.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 | * @section DESCRIPTION |
||
30 | * |
||
31 | * AVL tree. |
||
32 | */ |
||
33 | |||
34 | #ifndef BADVPN_STRUCTURE_BAVL_H |
||
35 | #define BADVPN_STRUCTURE_BAVL_H |
||
36 | |||
37 | //#define BAVL_DEBUG |
||
38 | |||
39 | #include <stdint.h> |
||
40 | #include <stddef.h> |
||
41 | |||
42 | #include <misc/debug.h> |
||
43 | |||
44 | /** |
||
45 | * Handler function called by tree algorithms to compare two values. |
||
46 | * For any two values, the comparator must always return the same result. |
||
47 | * The <= relation defined by the comparator must be a total order. |
||
48 | * Values are obtained like that: |
||
49 | * - The value of a node in the tree, or a node that is being inserted is: |
||
50 | * (uint8_t *)node + offset. |
||
51 | * - The value being looked up is the same as given to the lookup function. |
||
52 | * |
||
53 | * @param user as in {@link BAVL_Init} |
||
54 | * @param val1 first value |
||
55 | * @param val2 second value |
||
56 | * @return -1 if val1 < val2, 0 if val1 = val2, 1 if val1 > val2 |
||
57 | */ |
||
58 | typedef int (*BAVL_comparator) (void *user, void *val1, void *val2); |
||
59 | |||
60 | struct BAVLNode; |
||
61 | |||
62 | /** |
||
63 | * AVL tree. |
||
64 | */ |
||
65 | typedef struct { |
||
66 | int offset; |
||
67 | BAVL_comparator comparator; |
||
68 | void *user; |
||
69 | struct BAVLNode *root; |
||
70 | } BAVL; |
||
71 | |||
72 | /** |
||
73 | * AVL tree node. |
||
74 | */ |
||
75 | typedef struct BAVLNode { |
||
76 | struct BAVLNode *parent; |
||
77 | struct BAVLNode *link[2]; |
||
78 | int8_t balance; |
||
79 | #ifdef BAVL_COUNT |
||
80 | uint64_t count; |
||
81 | #endif |
||
82 | } BAVLNode; |
||
83 | |||
84 | /** |
||
85 | * Initializes the tree. |
||
86 | * |
||
87 | * @param o tree to initialize |
||
88 | * @param offset offset of a value from its node |
||
89 | * @param comparator value comparator handler function |
||
90 | * @param user value to pass to comparator |
||
91 | */ |
||
92 | static void BAVL_Init (BAVL *o, int offset, BAVL_comparator comparator, void *user); |
||
93 | |||
94 | /** |
||
95 | * Inserts a node into the tree. |
||
96 | * Must not be called from comparator. |
||
97 | * |
||
98 | * @param o the tree |
||
99 | * @param node uninitialized node to insert. Must have a valid value (its value |
||
100 | * may be passed to the comparator during insertion). |
||
101 | * @param ref if not NULL, will return (regardless if insertion succeeded): |
||
102 | * - the greatest node lesser than the inserted value, or (not in order) |
||
103 | * - the smallest node greater than the inserted value, or |
||
104 | * - NULL meaning there were no nodes in the tree. |
||
105 | * @param 1 on success, 0 if an element with an equal value is already in the tree |
||
106 | */ |
||
107 | static int BAVL_Insert (BAVL *o, BAVLNode *node, BAVLNode **ref); |
||
108 | |||
109 | /** |
||
110 | * Removes a node from the tree. |
||
111 | * Must not be called from comparator. |
||
112 | * |
||
113 | * @param o the tree |
||
114 | * @param node node to remove |
||
115 | */ |
||
116 | static void BAVL_Remove (BAVL *o, BAVLNode *node); |
||
117 | |||
118 | /** |
||
119 | * Checks if the tree is empty. |
||
120 | * Must not be called from comparator. |
||
121 | * |
||
122 | * @param o the tree |
||
123 | * @return 1 if empty, 0 if not |
||
124 | */ |
||
125 | static int BAVL_IsEmpty (const BAVL *o); |
||
126 | |||
127 | /** |
||
128 | * Looks for a value in the tree. |
||
129 | * Must not be called from comparator. |
||
130 | * |
||
131 | * @param o the tree |
||
132 | * @param val value to look for |
||
133 | * @return If a node is in the thee with an equal value, that node. |
||
134 | * Else if the tree is not empty: |
||
135 | * - the greatest node lesser than the given value, or (not in order) |
||
136 | * - the smallest node greater than the given value. |
||
137 | * NULL if the tree is empty. |
||
138 | */ |
||
139 | static BAVLNode * BAVL_Lookup (const BAVL *o, void *val); |
||
140 | |||
141 | /** |
||
142 | * Looks for a value in the tree. |
||
143 | * Must not be called from comparator. |
||
144 | * |
||
145 | * @param o the tree |
||
146 | * @param val value to look for |
||
147 | * @return If a node is in the thee with an equal value, that node. |
||
148 | * Else NULL. |
||
149 | */ |
||
150 | static BAVLNode * BAVL_LookupExact (const BAVL *o, void *val); |
||
151 | |||
152 | /** |
||
153 | * Returns the smallest node in the tree, or NULL if the tree is empty. |
||
154 | * |
||
155 | * @param o the tree |
||
156 | * @return smallest node or NULL |
||
157 | */ |
||
158 | static BAVLNode * BAVL_GetFirst (const BAVL *o); |
||
159 | |||
160 | /** |
||
161 | * Returns the greatest node in the tree, or NULL if the tree is empty. |
||
162 | * |
||
163 | * @param o the tree |
||
164 | * @return greatest node or NULL |
||
165 | */ |
||
166 | static BAVLNode * BAVL_GetLast (const BAVL *o); |
||
167 | |||
168 | /** |
||
169 | * Returns the node that follows the given node, or NULL if it's the |
||
170 | * last node. |
||
171 | * |
||
172 | * @param o the tree |
||
173 | * @param n node |
||
174 | * @return next node, or NULL |
||
175 | */ |
||
176 | static BAVLNode * BAVL_GetNext (const BAVL *o, BAVLNode *n); |
||
177 | |||
178 | /** |
||
179 | * Returns the node that precedes the given node, or NULL if it's the |
||
180 | * first node. |
||
181 | * |
||
182 | * @param o the tree |
||
183 | * @param n node |
||
184 | * @return previous node, or NULL |
||
185 | */ |
||
186 | static BAVLNode * BAVL_GetPrev (const BAVL *o, BAVLNode *n); |
||
187 | |||
188 | #ifdef BAVL_COUNT |
||
189 | static uint64_t BAVL_Count (const BAVL *o); |
||
190 | static uint64_t BAVL_IndexOf (const BAVL *o, BAVLNode *n); |
||
191 | static BAVLNode * BAVL_GetAt (const BAVL *o, uint64_t index); |
||
192 | #endif |
||
193 | |||
194 | static void BAVL_Verify (BAVL *o); |
||
195 | |||
196 | #define BAVL_MAX(_a, _b) ((_a) > (_b) ? (_a) : (_b)) |
||
197 | #define BAVL_OPTNEG(_a, _neg) ((_neg) ? -(_a) : (_a)) |
||
198 | |||
199 | static void * _BAVL_node_value (const BAVL *o, BAVLNode *n) |
||
200 | { |
||
201 | return ((uint8_t *)n + o->offset); |
||
202 | } |
||
203 | |||
204 | static int _BAVL_compare_values (const BAVL *o, void *v1, void *v2) |
||
205 | { |
||
206 | int res = o->comparator(o->user, v1, v2); |
||
207 | |||
208 | ASSERT(res == -1 || res == 0 || res == 1) |
||
209 | |||
210 | return res; |
||
211 | } |
||
212 | |||
213 | static int _BAVL_compare_nodes (BAVL *o, BAVLNode *n1, BAVLNode *n2) |
||
214 | { |
||
215 | return _BAVL_compare_values(o, _BAVL_node_value(o, n1), _BAVL_node_value(o, n2)); |
||
216 | } |
||
217 | |||
218 | #ifdef BAVL_AUTO_VERIFY |
||
219 | #define BAVL_ASSERT(_h) BAVL_Verify((_h)); |
||
220 | #else |
||
221 | #define BAVL_ASSERT(_h) |
||
222 | #endif |
||
223 | |||
224 | static int _BAVL_assert_recurser (BAVL *o, BAVLNode *n) |
||
225 | { |
||
226 | ASSERT_FORCE(n->balance >= -1) |
||
227 | ASSERT_FORCE(n->balance <= 1) |
||
228 | |||
229 | int height_left = 0; |
||
230 | int height_right = 0; |
||
231 | #ifdef BAVL_COUNT |
||
232 | uint64_t count_left = 0; |
||
233 | uint64_t count_right = 0; |
||
234 | #endif |
||
235 | |||
236 | // check left subtree |
||
237 | if (n->link[0]) { |
||
238 | // check parent link |
||
239 | ASSERT_FORCE(n->link[0]->parent == n) |
||
240 | // check binary search tree |
||
241 | ASSERT_FORCE(_BAVL_compare_nodes(o, n->link[0], n) == -1) |
||
242 | // recursively calculate height |
||
243 | height_left = _BAVL_assert_recurser(o, n->link[0]); |
||
244 | #ifdef BAVL_COUNT |
||
245 | count_left = n->link[0]->count; |
||
246 | #endif |
||
247 | } |
||
248 | |||
249 | // check right subtree |
||
250 | if (n->link[1]) { |
||
251 | // check parent link |
||
252 | ASSERT_FORCE(n->link[1]->parent == n) |
||
253 | // check binary search tree |
||
254 | ASSERT_FORCE(_BAVL_compare_nodes(o, n->link[1], n) == 1) |
||
255 | // recursively calculate height |
||
256 | height_right = _BAVL_assert_recurser(o, n->link[1]); |
||
257 | #ifdef BAVL_COUNT |
||
258 | count_right = n->link[1]->count; |
||
259 | #endif |
||
260 | } |
||
261 | |||
262 | // check balance factor |
||
263 | ASSERT_FORCE(n->balance == height_right - height_left) |
||
264 | |||
265 | #ifdef BAVL_COUNT |
||
266 | // check count |
||
267 | ASSERT_FORCE(n->count == 1 + count_left + count_right) |
||
268 | #endif |
||
269 | |||
270 | return (BAVL_MAX(height_left, height_right) + 1); |
||
271 | } |
||
272 | |||
273 | #ifdef BAVL_COUNT |
||
274 | static void _BAVL_update_count_from_children (BAVLNode *n) |
||
275 | { |
||
276 | n->count = 1 + (n->link[0] ? n->link[0]->count : 0) + (n->link[1] ? n->link[1]->count : 0); |
||
277 | } |
||
278 | #endif |
||
279 | |||
280 | static void _BAVL_rotate (BAVL *tree, BAVLNode *r, uint8_t dir) |
||
281 | { |
||
282 | BAVLNode *nr = r->link[!dir]; |
||
283 | |||
284 | r->link[!dir] = nr->link[dir]; |
||
285 | if (r->link[!dir]) { |
||
286 | r->link[!dir]->parent = r; |
||
287 | } |
||
288 | nr->link[dir] = r; |
||
289 | nr->parent = r->parent; |
||
290 | if (nr->parent) { |
||
291 | nr->parent->link[r == r->parent->link[1]] = nr; |
||
292 | } else { |
||
293 | tree->root = nr; |
||
294 | } |
||
295 | r->parent = nr; |
||
296 | |||
297 | #ifdef BAVL_COUNT |
||
298 | // update counts |
||
299 | _BAVL_update_count_from_children(r); // first r! |
||
300 | _BAVL_update_count_from_children(nr); |
||
301 | #endif |
||
302 | } |
||
303 | |||
304 | static BAVLNode * _BAVL_subtree_max (BAVLNode *n) |
||
305 | { |
||
306 | ASSERT(n) |
||
307 | while (n->link[1]) { |
||
308 | n = n->link[1]; |
||
309 | } |
||
310 | return n; |
||
311 | } |
||
312 | |||
313 | static void _BAVL_replace_subtree (BAVL *tree, BAVLNode *dest, BAVLNode *n) |
||
314 | { |
||
315 | ASSERT(dest) |
||
316 | |||
317 | if (dest->parent) { |
||
318 | dest->parent->link[dest == dest->parent->link[1]] = n; |
||
319 | } else { |
||
320 | tree->root = n; |
||
321 | } |
||
322 | if (n) { |
||
323 | n->parent = dest->parent; |
||
324 | } |
||
325 | |||
326 | #ifdef BAVL_COUNT |
||
327 | // update counts |
||
328 | for (BAVLNode *c = dest->parent; c; c = c->parent) { |
||
329 | ASSERT(c->count >= dest->count) |
||
330 | c->count -= dest->count; |
||
331 | if (n) { |
||
332 | ASSERT(n->count <= UINT64_MAX - c->count) |
||
333 | c->count += n->count; |
||
334 | } |
||
335 | } |
||
336 | #endif |
||
337 | } |
||
338 | |||
339 | static void _BAVL_swap_nodes (BAVL *tree, BAVLNode *n1, BAVLNode *n2) |
||
340 | { |
||
341 | if (n2->parent == n1 || n1->parent == n2) { |
||
342 | // when the nodes are directly connected we need special handling |
||
343 | // make sure n1 is above n2 |
||
344 | if (n1->parent == n2) { |
||
345 | BAVLNode *t = n1; |
||
346 | n1 = n2; |
||
347 | n2 = t; |
||
348 | } |
||
349 | |||
350 | uint8_t side = (n2 == n1->link[1]); |
||
351 | BAVLNode *c = n1->link[!side]; |
||
352 | |||
353 | if (n1->link[0] = n2->link[0]) { |
||
354 | n1->link[0]->parent = n1; |
||
355 | } |
||
356 | if (n1->link[1] = n2->link[1]) { |
||
357 | n1->link[1]->parent = n1; |
||
358 | } |
||
359 | |||
360 | if (n2->parent = n1->parent) { |
||
361 | n2->parent->link[n1 == n1->parent->link[1]] = n2; |
||
362 | } else { |
||
363 | tree->root = n2; |
||
364 | } |
||
365 | |||
366 | n2->link[side] = n1; |
||
367 | n1->parent = n2; |
||
368 | if (n2->link[!side] = c) { |
||
369 | c->parent = n2; |
||
370 | } |
||
371 | } else { |
||
372 | BAVLNode *temp; |
||
373 | |||
374 | // swap parents |
||
375 | temp = n1->parent; |
||
376 | if (n1->parent = n2->parent) { |
||
377 | n1->parent->link[n2 == n2->parent->link[1]] = n1; |
||
378 | } else { |
||
379 | tree->root = n1; |
||
380 | } |
||
381 | if (n2->parent = temp) { |
||
382 | n2->parent->link[n1 == temp->link[1]] = n2; |
||
383 | } else { |
||
384 | tree->root = n2; |
||
385 | } |
||
386 | |||
387 | // swap left children |
||
388 | temp = n1->link[0]; |
||
389 | if (n1->link[0] = n2->link[0]) { |
||
390 | n1->link[0]->parent = n1; |
||
391 | } |
||
392 | if (n2->link[0] = temp) { |
||
393 | n2->link[0]->parent = n2; |
||
394 | } |
||
395 | |||
396 | // swap right children |
||
397 | temp = n1->link[1]; |
||
398 | if (n1->link[1] = n2->link[1]) { |
||
399 | n1->link[1]->parent = n1; |
||
400 | } |
||
401 | if (n2->link[1] = temp) { |
||
402 | n2->link[1]->parent = n2; |
||
403 | } |
||
404 | } |
||
405 | |||
406 | // swap balance factors |
||
407 | int8_t b = n1->balance; |
||
408 | n1->balance = n2->balance; |
||
409 | n2->balance = b; |
||
410 | |||
411 | #ifdef BAVL_COUNT |
||
412 | // swap counts |
||
413 | uint64_t c = n1->count; |
||
414 | n1->count = n2->count; |
||
415 | n2->count = c; |
||
416 | #endif |
||
417 | } |
||
418 | |||
419 | static void _BAVL_rebalance (BAVL *o, BAVLNode *node, uint8_t side, int8_t deltac) |
||
420 | { |
||
421 | ASSERT(side == 0 || side == 1) |
||
422 | ASSERT(deltac >= -1 && deltac <= 1) |
||
423 | ASSERT(node->balance >= -1 && node->balance <= 1) |
||
424 | |||
425 | // if no subtree changed its height, no more rebalancing is needed |
||
426 | if (deltac == 0) { |
||
427 | return; |
||
428 | } |
||
429 | |||
430 | // calculate how much our height changed |
||
431 | int8_t delta = BAVL_MAX(deltac, BAVL_OPTNEG(node->balance, side)) - BAVL_MAX(0, BAVL_OPTNEG(node->balance, side)); |
||
432 | ASSERT(delta >= -1 && delta <= 1) |
||
433 | |||
434 | // update our balance factor |
||
435 | node->balance -= BAVL_OPTNEG(deltac, side); |
||
436 | |||
437 | BAVLNode *child; |
||
438 | BAVLNode *gchild; |
||
439 | |||
440 | // perform transformations if the balance factor is wrong |
||
441 | if (node->balance == 2 || node->balance == -2) { |
||
442 | uint8_t bside; |
||
443 | int8_t bsidef; |
||
444 | if (node->balance == 2) { |
||
445 | bside = 1; |
||
446 | bsidef = 1; |
||
447 | } else { |
||
448 | bside = 0; |
||
449 | bsidef = -1; |
||
450 | } |
||
451 | |||
452 | ASSERT(node->link[bside]) |
||
453 | child = node->link[bside]; |
||
454 | switch (child->balance * bsidef) { |
||
455 | case 1: |
||
456 | _BAVL_rotate(o, node, !bside); |
||
457 | node->balance = 0; |
||
458 | child->balance = 0; |
||
459 | node = child; |
||
460 | delta -= 1; |
||
461 | break; |
||
462 | case 0: |
||
463 | _BAVL_rotate(o, node, !bside); |
||
464 | node->balance = 1 * bsidef; |
||
465 | child->balance = -1 * bsidef; |
||
466 | node = child; |
||
467 | break; |
||
468 | case -1: |
||
469 | ASSERT(child->link[!bside]) |
||
470 | gchild = child->link[!bside]; |
||
471 | _BAVL_rotate(o, child, bside); |
||
472 | _BAVL_rotate(o, node, !bside); |
||
473 | node->balance = -BAVL_MAX(0, gchild->balance * bsidef) * bsidef; |
||
474 | child->balance = BAVL_MAX(0, -gchild->balance * bsidef) * bsidef; |
||
475 | gchild->balance = 0; |
||
476 | node = gchild; |
||
477 | delta -= 1; |
||
478 | break; |
||
479 | default: |
||
480 | ASSERT(0); |
||
481 | } |
||
482 | } |
||
483 | |||
484 | ASSERT(delta >= -1 && delta <= 1) |
||
485 | // Transformations above preserve this. Proof: |
||
486 | // - if a child subtree gained 1 height and rebalancing was needed, |
||
487 | // it was the heavier subtree. Then delta was was originally 1, because |
||
488 | // the heaviest subtree gained one height. If the transformation reduces |
||
489 | // delta by one, it becomes 0. |
||
490 | // - if a child subtree lost 1 height and rebalancing was needed, it |
||
491 | // was the lighter subtree. Then delta was originally 0, because |
||
492 | // the height of the heaviest subtree was unchanged. If the transformation |
||
493 | // reduces delta by one, it becomes -1. |
||
494 | |||
495 | if (node->parent) { |
||
496 | _BAVL_rebalance(o, node->parent, node == node->parent->link[1], delta); |
||
497 | } |
||
498 | } |
||
499 | |||
500 | void BAVL_Init (BAVL *o, int offset, BAVL_comparator comparator, void *user) |
||
501 | { |
||
502 | o->offset = offset; |
||
503 | o->comparator = comparator; |
||
504 | o->user = user; |
||
505 | o->root = NULL; |
||
506 | |||
507 | BAVL_ASSERT(o) |
||
508 | } |
||
509 | |||
510 | int BAVL_Insert (BAVL *o, BAVLNode *node, BAVLNode **ref) |
||
511 | { |
||
512 | // insert to root? |
||
513 | if (!o->root) { |
||
514 | o->root = node; |
||
515 | node->parent = NULL; |
||
516 | node->link[0] = NULL; |
||
517 | node->link[1] = NULL; |
||
518 | node->balance = 0; |
||
519 | #ifdef BAVL_COUNT |
||
520 | node->count = 1; |
||
521 | #endif |
||
522 | |||
523 | BAVL_ASSERT(o) |
||
524 | |||
525 | if (ref) { |
||
526 | *ref = NULL; |
||
527 | } |
||
528 | return 1; |
||
529 | } |
||
530 | |||
531 | // find node to insert to |
||
532 | BAVLNode *c = o->root; |
||
533 | int side; |
||
534 | while (1) { |
||
535 | // compare |
||
536 | int comp = _BAVL_compare_nodes(o, node, c); |
||
537 | |||
538 | // have we found a node that compares equal? |
||
539 | if (comp == 0) { |
||
540 | if (ref) { |
||
541 | *ref = c; |
||
542 | } |
||
543 | return 0; |
||
544 | } |
||
545 | |||
546 | side = (comp == 1); |
||
547 | |||
548 | // have we reached a leaf? |
||
549 | if (!c->link[side]) { |
||
550 | break; |
||
551 | } |
||
552 | |||
553 | c = c->link[side]; |
||
554 | } |
||
555 | |||
556 | // insert |
||
557 | c->link[side] = node; |
||
558 | node->parent = c; |
||
559 | node->link[0] = NULL; |
||
560 | node->link[1] = NULL; |
||
561 | node->balance = 0; |
||
562 | #ifdef BAVL_COUNT |
||
563 | node->count = 1; |
||
564 | #endif |
||
565 | |||
566 | #ifdef BAVL_COUNT |
||
567 | // update counts |
||
568 | for (BAVLNode *p = c; p; p = p->parent) { |
||
569 | ASSERT(p->count < UINT64_MAX) |
||
570 | p->count++; |
||
571 | } |
||
572 | #endif |
||
573 | |||
574 | // rebalance |
||
575 | _BAVL_rebalance(o, c, side, 1); |
||
576 | |||
577 | BAVL_ASSERT(o) |
||
578 | |||
579 | if (ref) { |
||
580 | *ref = c; |
||
581 | } |
||
582 | return 1; |
||
583 | } |
||
584 | |||
585 | void BAVL_Remove (BAVL *o, BAVLNode *node) |
||
586 | { |
||
587 | // if we have both subtrees, swap the node and the largest node |
||
588 | // in the left subtree, so we have at most one subtree |
||
589 | if (node->link[0] && node->link[1]) { |
||
590 | // find the largest node in the left subtree |
||
591 | BAVLNode *max = _BAVL_subtree_max(node->link[0]); |
||
592 | // swap the nodes |
||
593 | _BAVL_swap_nodes(o, node, max); |
||
594 | } |
||
595 | |||
596 | // have at most one child now |
||
597 | ASSERT(!(node->link[0] && node->link[1])) |
||
598 | |||
599 | BAVLNode *parent = node->parent; |
||
600 | BAVLNode *child = (node->link[0] ? node->link[0] : node->link[1]); |
||
601 | |||
602 | if (parent) { |
||
603 | // remember on which side node is |
||
604 | int side = (node == parent->link[1]); |
||
605 | // replace node with child |
||
606 | _BAVL_replace_subtree(o, node, child); |
||
607 | // rebalance |
||
608 | _BAVL_rebalance(o, parent, side, -1); |
||
609 | } else { |
||
610 | // replace node with child |
||
611 | _BAVL_replace_subtree(o, node, child); |
||
612 | } |
||
613 | |||
614 | BAVL_ASSERT(o) |
||
615 | } |
||
616 | |||
617 | int BAVL_IsEmpty (const BAVL *o) |
||
618 | { |
||
619 | return (!o->root); |
||
620 | } |
||
621 | |||
622 | BAVLNode * BAVL_Lookup (const BAVL *o, void *val) |
||
623 | { |
||
624 | if (!o->root) { |
||
625 | return NULL; |
||
626 | } |
||
627 | |||
628 | BAVLNode *c = o->root; |
||
629 | while (1) { |
||
630 | // compare |
||
631 | int comp = _BAVL_compare_values(o, val, _BAVL_node_value(o, c)); |
||
632 | |||
633 | // have we found a node that compares equal? |
||
634 | if (comp == 0) { |
||
635 | return c; |
||
636 | } |
||
637 | |||
638 | int side = (comp == 1); |
||
639 | |||
640 | // have we reached a leaf? |
||
641 | if (!c->link[side]) { |
||
642 | return c; |
||
643 | } |
||
644 | |||
645 | c = c->link[side]; |
||
646 | } |
||
647 | } |
||
648 | |||
649 | BAVLNode * BAVL_LookupExact (const BAVL *o, void *val) |
||
650 | { |
||
651 | if (!o->root) { |
||
652 | return NULL; |
||
653 | } |
||
654 | |||
655 | BAVLNode *c = o->root; |
||
656 | while (1) { |
||
657 | // compare |
||
658 | int comp = _BAVL_compare_values(o, val, _BAVL_node_value(o, c)); |
||
659 | |||
660 | // have we found a node that compares equal? |
||
661 | if (comp == 0) { |
||
662 | return c; |
||
663 | } |
||
664 | |||
665 | int side = (comp == 1); |
||
666 | |||
667 | // have we reached a leaf? |
||
668 | if (!c->link[side]) { |
||
669 | return NULL; |
||
670 | } |
||
671 | |||
672 | c = c->link[side]; |
||
673 | } |
||
674 | } |
||
675 | |||
676 | BAVLNode * BAVL_GetFirst (const BAVL *o) |
||
677 | { |
||
678 | if (!o->root) { |
||
679 | return NULL; |
||
680 | } |
||
681 | |||
682 | BAVLNode *n = o->root; |
||
683 | while (n->link[0]) { |
||
684 | n = n->link[0]; |
||
685 | } |
||
686 | |||
687 | return n; |
||
688 | } |
||
689 | |||
690 | BAVLNode * BAVL_GetLast (const BAVL *o) |
||
691 | { |
||
692 | if (!o->root) { |
||
693 | return NULL; |
||
694 | } |
||
695 | |||
696 | BAVLNode *n = o->root; |
||
697 | while (n->link[1]) { |
||
698 | n = n->link[1]; |
||
699 | } |
||
700 | |||
701 | return n; |
||
702 | } |
||
703 | |||
704 | BAVLNode * BAVL_GetNext (const BAVL *o, BAVLNode *n) |
||
705 | { |
||
706 | if (n->link[1]) { |
||
707 | n = n->link[1]; |
||
708 | while (n->link[0]) { |
||
709 | n = n->link[0]; |
||
710 | } |
||
711 | } else { |
||
712 | while (n->parent && n == n->parent->link[1]) { |
||
713 | n = n->parent; |
||
714 | } |
||
715 | n = n->parent; |
||
716 | } |
||
717 | |||
718 | return n; |
||
719 | } |
||
720 | |||
721 | BAVLNode * BAVL_GetPrev (const BAVL *o, BAVLNode *n) |
||
722 | { |
||
723 | if (n->link[0]) { |
||
724 | n = n->link[0]; |
||
725 | while (n->link[1]) { |
||
726 | n = n->link[1]; |
||
727 | } |
||
728 | } else { |
||
729 | while (n->parent && n == n->parent->link[0]) { |
||
730 | n = n->parent; |
||
731 | } |
||
732 | n = n->parent; |
||
733 | } |
||
734 | |||
735 | return n; |
||
736 | } |
||
737 | |||
738 | #ifdef BAVL_COUNT |
||
739 | |||
740 | static uint64_t BAVL_Count (const BAVL *o) |
||
741 | { |
||
742 | return (o->root ? o->root->count : 0); |
||
743 | } |
||
744 | |||
745 | static uint64_t BAVL_IndexOf (const BAVL *o, BAVLNode *n) |
||
746 | { |
||
747 | uint64_t index = (n->link[0] ? n->link[0]->count : 0); |
||
748 | |||
749 | for (BAVLNode *c = n; c->parent; c = c->parent) { |
||
750 | if (c == c->parent->link[1]) { |
||
751 | ASSERT(c->parent->count > c->count) |
||
752 | ASSERT(c->parent->count - c->count <= UINT64_MAX - index) |
||
753 | index += c->parent->count - c->count; |
||
754 | } |
||
755 | } |
||
756 | |||
757 | return index; |
||
758 | } |
||
759 | |||
760 | static BAVLNode * BAVL_GetAt (const BAVL *o, uint64_t index) |
||
761 | { |
||
762 | if (index >= BAVL_Count(o)) { |
||
763 | return NULL; |
||
764 | } |
||
765 | |||
766 | BAVLNode *c = o->root; |
||
767 | |||
768 | while (1) { |
||
769 | ASSERT(c) |
||
770 | ASSERT(index < c->count) |
||
771 | |||
772 | uint64_t left_count = (c->link[0] ? c->link[0]->count : 0); |
||
773 | |||
774 | if (index == left_count) { |
||
775 | return c; |
||
776 | } |
||
777 | |||
778 | if (index < left_count) { |
||
779 | c = c->link[0]; |
||
780 | } else { |
||
781 | c = c->link[1]; |
||
782 | index -= left_count + 1; |
||
783 | } |
||
784 | } |
||
785 | } |
||
786 | |||
787 | #endif |
||
788 | |||
789 | static void BAVL_Verify (BAVL *o) |
||
790 | { |
||
791 | if (o->root) { |
||
792 | ASSERT(!o->root->parent) |
||
793 | _BAVL_assert_recurser(o, o->root); |
||
794 | } |
||
795 | } |
||
796 | |||
797 | #endif |