BadVPN – Blame information for rev 1

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