1/*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3#ident "$Id$"
4/*======
5This file is part of PerconaFT.
6
7
8Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILIT or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35======= */
36
37#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#include "ft/serialize/rbtree_mhs.h"
40#include "portability/toku_assert.h"
41#include "portability/toku_portability.h"
42#include <algorithm>
43
44namespace MhsRbTree {
45
46 Tree::Tree() : _root(NULL), _align(1) {}
47
48 Tree::Tree(uint64_t align) : _root(NULL), _align(align) {}
49
50 Tree::~Tree() { Destroy(); }
51
52 void Tree::PreOrder(Node *tree) const {
53 if (tree != NULL) {
54 fprintf(stderr, "%" PRIu64 " ", rbn_offset(tree).ToInt());
55 PreOrder(tree->_left);
56 PreOrder(tree->_right);
57 }
58 }
59
60 void Tree::PreOrder() { PreOrder(_root); }
61
62 void Tree::InOrder(Node *tree) const {
63 if (tree != NULL) {
64 InOrder(tree->_left);
65 fprintf(stderr, "%" PRIu64 " ", rbn_offset(tree).ToInt());
66 InOrder(tree->_right);
67 }
68 }
69
70 // yeah, i only care about in order visitor. -Jun
71 void Tree::InOrderVisitor(Node *tree,
72 void (*f)(void *, Node *, uint64_t),
73 void *extra,
74 uint64_t depth) {
75 if (tree != NULL) {
76 InOrderVisitor(tree->_left, f, extra, depth + 1);
77 f(extra, tree, depth);
78 InOrderVisitor(tree->_right, f, extra, depth + 1);
79 }
80 }
81
82 void Tree::InOrderVisitor(void (*f)(void *, Node *, uint64_t),
83 void *extra) {
84 InOrderVisitor(_root, f, extra, 0);
85 }
86
87 void Tree::InOrder() { InOrder(_root); }
88
89 void Tree::PostOrder(Node *tree) const {
90 if (tree != NULL) {
91 PostOrder(tree->_left);
92 PostOrder(tree->_right);
93 fprintf(stderr, "%" PRIu64 " ", rbn_offset(tree).ToInt());
94 }
95 }
96
97 void Tree::PostOrder() { PostOrder(_root); }
98
99 Node *Tree::SearchByOffset(uint64_t offset) {
100 Node *x = _root;
101 while ((x != NULL) && (rbn_offset(x).ToInt() != offset)) {
102 if (offset < rbn_offset(x).ToInt())
103 x = x->_left;
104 else
105 x = x->_right;
106 }
107
108 return x;
109 }
110
111 // mostly for testing
112 Node *Tree::SearchFirstFitBySize(uint64_t size) {
113 if (EffectiveSize(_root) < size && rbn_left_mhs(_root) < size &&
114 rbn_right_mhs(_root) < size) {
115 return nullptr;
116 } else {
117 return SearchFirstFitBySizeHelper(_root, size);
118 }
119 }
120
121 Node *Tree::SearchFirstFitBySizeHelper(Node *x, uint64_t size) {
122 if (EffectiveSize(x) >= size) {
123 // only possible to go left
124 if (rbn_left_mhs(x) >= size)
125 return SearchFirstFitBySizeHelper(x->_left, size);
126 else
127 return x;
128 }
129 if (rbn_left_mhs(x) >= size)
130 return SearchFirstFitBySizeHelper(x->_left, size);
131
132 if (rbn_right_mhs(x) >= size)
133 return SearchFirstFitBySizeHelper(x->_right, size);
134
135 // this is an invalid state
136 Dump();
137 ValidateBalance();
138 ValidateMhs();
139 invariant(0);
140 return NULL;
141 }
142
143 Node *Tree::MinNode(Node *tree) {
144 if (tree == NULL)
145 return NULL;
146
147 while (tree->_left != NULL)
148 tree = tree->_left;
149 return tree;
150 }
151
152 Node *Tree::MinNode() { return MinNode(_root); }
153
154 Node *Tree::MaxNode(Node *tree) {
155 if (tree == NULL)
156 return NULL;
157
158 while (tree->_right != NULL)
159 tree = tree->_right;
160 return tree;
161 }
162
163 Node *Tree::MaxNode() { return MaxNode(_root); }
164
165 Node *Tree::SuccessorHelper(Node *y, Node *x) {
166 while ((y != NULL) && (x == y->_right)) {
167 x = y;
168 y = y->_parent;
169 }
170 return y;
171 }
172 Node *Tree::Successor(Node *x) {
173 if (x->_right != NULL)
174 return MinNode(x->_right);
175
176 Node *y = x->_parent;
177 return SuccessorHelper(y, x);
178 }
179
180 Node *Tree::PredecessorHelper(Node *y, Node *x) {
181 while ((y != NULL) && (x == y->_left)) {
182 x = y;
183 y = y->_parent;
184 }
185
186 return y;
187 }
188 Node *Tree::Predecessor(Node *x) {
189 if (x->_left != NULL)
190 return MaxNode(x->_left);
191
192 Node *y = x->_parent;
193 return SuccessorHelper(y, x);
194 }
195
196 /*
197 * px px
198 * / /
199 * x y
200 * / \ --(left rotation)--> / \ #
201 * lx y x ry
202 * / \ / \
203 * ly ry lx ly
204 * max_hole_size updates are pretty local
205 */
206
207 void Tree::LeftRotate(Node *&root, Node *x) {
208 Node *y = x->_right;
209
210 x->_right = y->_left;
211 rbn_right_mhs(x) = rbn_left_mhs(y);
212
213 if (y->_left != NULL)
214 y->_left->_parent = x;
215
216 y->_parent = x->_parent;
217
218 if (x->_parent == NULL) {
219 root = y;
220 } else {
221 if (x->_parent->_left == x) {
222 x->_parent->_left = y;
223 } else {
224 x->_parent->_right = y;
225 }
226 }
227 y->_left = x;
228 rbn_left_mhs(y) = mhs_of_subtree(x);
229
230 x->_parent = y;
231 }
232
233 /* py py
234 * / /
235 * y x
236 * / \ --(right rotate)--> / \ #
237 * x ry lx y
238 * / \ / \ #
239 * lx rx rx ry
240 *
241 */
242
243 void Tree::RightRotate(Node *&root, Node *y) {
244 Node *x = y->_left;
245
246 y->_left = x->_right;
247 rbn_left_mhs(y) = rbn_right_mhs(x);
248
249 if (x->_right != NULL)
250 x->_right->_parent = y;
251
252 x->_parent = y->_parent;
253
254 if (y->_parent == NULL) {
255 root = x;
256 } else {
257 if (y == y->_parent->_right)
258 y->_parent->_right = x;
259 else
260 y->_parent->_left = x;
261 }
262
263 x->_right = y;
264 rbn_right_mhs(x) = mhs_of_subtree(y);
265 y->_parent = x;
266 }
267
268 // walking from this node up to update the mhs info
269 // whenver there is change on left/right mhs or size we should recalculate.
270 // prerequisit: the children of the node are mhs up-to-date.
271 void Tree::RecalculateMhs(Node *node) {
272 uint64_t *p_node_mhs = 0;
273 Node *parent = node->_parent;
274
275 if (!parent)
276 return;
277
278 uint64_t max_mhs = mhs_of_subtree(node);
279 if (node == parent->_left) {
280 p_node_mhs = &rbn_left_mhs(parent);
281 } else if (node == parent->_right) {
282 p_node_mhs = &rbn_right_mhs(parent);
283 } else {
284 return;
285 }
286 if (*p_node_mhs != max_mhs) {
287 *p_node_mhs = max_mhs;
288 RecalculateMhs(parent);
289 }
290 }
291
292 void Tree::IsNewNodeMergable(Node *pred,
293 Node *succ,
294 Node::BlockPair pair,
295 bool *left_merge,
296 bool *right_merge) {
297 if (pred) {
298 OUUInt64 end_of_pred = rbn_size(pred) + rbn_offset(pred);
299 if (end_of_pred < pair._offset)
300 *left_merge = false;
301 else {
302 invariant(end_of_pred == pair._offset);
303 *left_merge = true;
304 }
305 }
306 if (succ) {
307 OUUInt64 begin_of_succ = rbn_offset(succ);
308 OUUInt64 end_of_node = pair._offset + pair._size;
309 if (end_of_node < begin_of_succ) {
310 *right_merge = false;
311 } else {
312 invariant(end_of_node == begin_of_succ);
313 *right_merge = true;
314 }
315 }
316 }
317
318 void Tree::AbsorbNewNode(Node *pred,
319 Node *succ,
320 Node::BlockPair pair,
321 bool left_merge,
322 bool right_merge,
323 bool is_right_child) {
324 invariant(left_merge || right_merge);
325 if (left_merge && right_merge) {
326 // merge to the succ
327 if (!is_right_child) {
328 rbn_size(succ) += pair._size;
329 rbn_offset(succ) = pair._offset;
330 // merge to the pred
331 rbn_size(pred) += rbn_size(succ);
332 // to keep the invariant of the tree -no overlapping holes
333 rbn_offset(succ) += rbn_size(succ);
334 rbn_size(succ) = 0;
335 RecalculateMhs(succ);
336 RecalculateMhs(pred);
337 // pred dominates succ. this is going to
338 // update the pred labels separately.
339 // remove succ
340 RawRemove(_root, succ);
341 } else {
342 rbn_size(pred) += pair._size;
343 rbn_offset(succ) = rbn_offset(pred);
344 rbn_size(succ) += rbn_size(pred);
345 rbn_offset(pred) += rbn_size(pred);
346 rbn_size(pred) = 0;
347 RecalculateMhs(pred);
348 RecalculateMhs(succ);
349 // now remove pred
350 RawRemove(_root, pred);
351 }
352 } else if (left_merge) {
353 rbn_size(pred) += pair._size;
354 RecalculateMhs(pred);
355 } else if (right_merge) {
356 rbn_offset(succ) -= pair._size;
357 rbn_size(succ) += pair._size;
358 RecalculateMhs(succ);
359 }
360 }
361 // this is the most tedious part, but not complicated:
362 // 1.find where to insert the pair
363 // 2.if the pred and succ can merge with the pair. merge with them. either
364 // pred
365 // or succ can be removed.
366 // 3. if only left-mergable or right-mergeable, just merge
367 // 4. non-mergable case. insert the node and run the fixup.
368
369 int Tree::Insert(Node *&root, Node::BlockPair pair) {
370 Node *x = _root;
371 Node *y = NULL;
372 bool left_merge = false;
373 bool right_merge = false;
374 Node *node = NULL;
375
376 while (x != NULL) {
377 y = x;
378 if (pair._offset < rbn_key(x))
379 x = x->_left;
380 else
381 x = x->_right;
382 }
383
384 // we found where to insert, lets find out the pred and succ for
385 // possible
386 // merges.
387 // node->parent = y;
388 Node *pred, *succ;
389 if (y != NULL) {
390 if (pair._offset < rbn_key(y)) {
391 // as the left child
392 pred = PredecessorHelper(y->_parent, y);
393 succ = y;
394 IsNewNodeMergable(pred, succ, pair, &left_merge, &right_merge);
395 if (left_merge || right_merge) {
396 AbsorbNewNode(
397 pred, succ, pair, left_merge, right_merge, false);
398 } else {
399 // construct the node
400 Node::Pair mhsp {0, 0};
401 node =
402 new Node(EColor::BLACK, pair, mhsp, nullptr, nullptr, nullptr);
403 if (!node)
404 return -1;
405 y->_left = node;
406 node->_parent = y;
407 RecalculateMhs(node);
408 }
409
410 } else {
411 // as the right child
412 pred = y;
413 succ = SuccessorHelper(y->_parent, y);
414 IsNewNodeMergable(pred, succ, pair, &left_merge, &right_merge);
415 if (left_merge || right_merge) {
416 AbsorbNewNode(
417 pred, succ, pair, left_merge, right_merge, true);
418 } else {
419 // construct the node
420 Node::Pair mhsp {0, 0};
421 node =
422 new Node(EColor::BLACK, pair, mhsp, nullptr, nullptr, nullptr);
423 if (!node)
424 return -1;
425 y->_right = node;
426 node->_parent = y;
427 RecalculateMhs(node);
428 }
429 }
430 } else {
431 Node::Pair mhsp {0, 0};
432 node = new Node(EColor::BLACK, pair, mhsp, nullptr, nullptr, nullptr);
433 if (!node)
434 return -1;
435 root = node;
436 }
437 if (!left_merge && !right_merge) {
438 invariant_notnull(node);
439 node->_color = EColor::RED;
440 return InsertFixup(root, node);
441 }
442 return 0;
443 }
444
445 int Tree::InsertFixup(Node *&root, Node *node) {
446 Node *parent, *gparent;
447 while ((parent = rbn_parent(node)) && rbn_is_red(parent)) {
448 gparent = rbn_parent(parent);
449 if (parent == gparent->_left) {
450 {
451 Node *uncle = gparent->_right;
452 if (uncle && rbn_is_red(uncle)) {
453 rbn_set_black(uncle);
454 rbn_set_black(parent);
455 rbn_set_red(gparent);
456 node = gparent;
457 continue;
458 }
459 }
460
461 if (parent->_right == node) {
462 Node *tmp;
463 LeftRotate(root, parent);
464 tmp = parent;
465 parent = node;
466 node = tmp;
467 }
468
469 rbn_set_black(parent);
470 rbn_set_red(gparent);
471 RightRotate(root, gparent);
472 } else {
473 {
474 Node *uncle = gparent->_left;
475 if (uncle && rbn_is_red(uncle)) {
476 rbn_set_black(uncle);
477 rbn_set_black(parent);
478 rbn_set_red(gparent);
479 node = gparent;
480 continue;
481 }
482 }
483
484 if (parent->_left == node) {
485 Node *tmp;
486 RightRotate(root, parent);
487 tmp = parent;
488 parent = node;
489 node = tmp;
490 }
491 rbn_set_black(parent);
492 rbn_set_red(gparent);
493 LeftRotate(root, gparent);
494 }
495 }
496 rbn_set_black(root);
497 return 0;
498 }
499
500 int Tree::Insert(Node::BlockPair pair) { return Insert(_root, pair); }
501
502 uint64_t Tree::Remove(size_t size) {
503 Node *node = SearchFirstFitBySize(size);
504 return Remove(_root, node, size);
505 }
506
507 void Tree::RawRemove(Node *&root, Node *node) {
508 Node *child, *parent;
509 EColor color;
510
511 if ((node->_left != NULL) && (node->_right != NULL)) {
512 Node *replace = node;
513 replace = replace->_right;
514 while (replace->_left != NULL)
515 replace = replace->_left;
516
517 if (rbn_parent(node)) {
518 if (rbn_parent(node)->_left == node)
519 rbn_parent(node)->_left = replace;
520 else
521 rbn_parent(node)->_right = replace;
522 } else {
523 root = replace;
524 }
525 child = replace->_right;
526 parent = rbn_parent(replace);
527 color = rbn_color(replace);
528
529 if (parent == node) {
530 parent = replace;
531 } else {
532 if (child)
533 rbn_parent(child) = parent;
534
535 parent->_left = child;
536 rbn_left_mhs(parent) = rbn_right_mhs(replace);
537 RecalculateMhs(parent);
538 replace->_right = node->_right;
539 rbn_set_parent(node->_right, replace);
540 rbn_right_mhs(replace) = rbn_right_mhs(node);
541 }
542
543 replace->_parent = node->_parent;
544 replace->_color = node->_color;
545 replace->_left = node->_left;
546 rbn_left_mhs(replace) = rbn_left_mhs(node);
547 node->_left->_parent = replace;
548 RecalculateMhs(replace);
549 if (color == EColor::BLACK)
550 RawRemoveFixup(root, child, parent);
551 delete node;
552 return;
553 }
554
555 if (node->_left != NULL)
556 child = node->_left;
557 else
558 child = node->_right;
559
560 parent = node->_parent;
561 color = node->_color;
562
563 if (child)
564 child->_parent = parent;
565
566 if (parent) {
567 if (parent->_left == node) {
568 parent->_left = child;
569 rbn_left_mhs(parent) = child ? mhs_of_subtree(child) : 0;
570 } else {
571 parent->_right = child;
572 rbn_right_mhs(parent) = child ? mhs_of_subtree(child) : 0;
573 }
574 RecalculateMhs(parent);
575 } else
576 root = child;
577 if (color == EColor::BLACK)
578 RawRemoveFixup(root, child, parent);
579 delete node;
580 }
581
582 void Tree::RawRemove(uint64_t offset) {
583 Node *node = SearchByOffset(offset);
584 RawRemove(_root, node);
585 }
586 static inline uint64_t align(uint64_t value, uint64_t ba_alignment) {
587 return ((value + ba_alignment - 1) / ba_alignment) * ba_alignment;
588 }
589 uint64_t Tree::Remove(Node *&root, Node *node, size_t size) {
590 OUUInt64 n_offset = rbn_offset(node);
591 OUUInt64 n_size = rbn_size(node);
592 OUUInt64 answer_offset(align(rbn_offset(node).ToInt(), _align));
593
594 invariant((answer_offset + size) <= (n_offset + n_size));
595 if (answer_offset == n_offset) {
596 rbn_offset(node) += size;
597 rbn_size(node) -= size;
598 RecalculateMhs(node);
599 if (rbn_size(node) == 0) {
600 RawRemove(root, node);
601 }
602
603 } else {
604 if (answer_offset + size == n_offset + n_size) {
605 rbn_size(node) -= size;
606 RecalculateMhs(node);
607 } else {
608 // well, cut in the middle...
609 rbn_size(node) = answer_offset - n_offset;
610 RecalculateMhs(node);
611 Insert(_root,
612 {(answer_offset + size),
613 (n_offset + n_size) - (answer_offset + size)});
614 }
615 }
616 return answer_offset.ToInt();
617 }
618
619 void Tree::RawRemoveFixup(Node *&root, Node *node, Node *parent) {
620 Node *other;
621 while ((!node || rbn_is_black(node)) && node != root) {
622 if (parent->_left == node) {
623 other = parent->_right;
624 if (rbn_is_red(other)) {
625 // Case 1: the brother of X, w, is read
626 rbn_set_black(other);
627 rbn_set_red(parent);
628 LeftRotate(root, parent);
629 other = parent->_right;
630 }
631 if ((!other->_left || rbn_is_black(other->_left)) &&
632 (!other->_right || rbn_is_black(other->_right))) {
633 // Case 2: w is black and both of w's children are black
634 rbn_set_red(other);
635 node = parent;
636 parent = rbn_parent(node);
637 } else {
638 if (!other->_right || rbn_is_black(other->_right)) {
639 // Case 3: w is black and left child of w is red but
640 // right
641 // child is black
642 rbn_set_black(other->_left);
643 rbn_set_red(other);
644 RightRotate(root, other);
645 other = parent->_right;
646 }
647 // Case 4: w is black and right child of w is red,
648 // regardless of
649 // left child's color
650 rbn_set_color(other, rbn_color(parent));
651 rbn_set_black(parent);
652 rbn_set_black(other->_right);
653 LeftRotate(root, parent);
654 node = root;
655 break;
656 }
657 } else {
658 other = parent->_left;
659 if (rbn_is_red(other)) {
660 // Case 1: w is red
661 rbn_set_black(other);
662 rbn_set_red(parent);
663 RightRotate(root, parent);
664 other = parent->_left;
665 }
666 if ((!other->_left || rbn_is_black(other->_left)) &&
667 (!other->_right || rbn_is_black(other->_right))) {
668 // Case 2: w is black and both children are black
669 rbn_set_red(other);
670 node = parent;
671 parent = rbn_parent(node);
672 } else {
673 if (!other->_left || rbn_is_black(other->_left)) {
674 // Case 3: w is black and left child of w is red whereas
675 // right child is black
676 rbn_set_black(other->_right);
677 rbn_set_red(other);
678 LeftRotate(root, other);
679 other = parent->_left;
680 }
681 // Case 4:w is black and right child of w is red, regardless
682 // of
683 // the left child's color
684 rbn_set_color(other, rbn_color(parent));
685 rbn_set_black(parent);
686 rbn_set_black(other->_left);
687 RightRotate(root, parent);
688 node = root;
689 break;
690 }
691 }
692 }
693 if (node)
694 rbn_set_black(node);
695 }
696
697 void Tree::Destroy(Node *&tree) {
698 if (tree == NULL)
699 return;
700
701 if (tree->_left != NULL)
702 Destroy(tree->_left);
703 if (tree->_right != NULL)
704 Destroy(tree->_right);
705
706 delete tree;
707 tree = NULL;
708 }
709
710 void Tree::Destroy() { Destroy(_root); }
711
712 void Tree::Dump(Node *tree, Node::BlockPair pair, EDirection dir) {
713 if (tree != NULL) {
714 if (dir == EDirection::NONE)
715 fprintf(stderr,
716 "(%" PRIu64 ",%" PRIu64 ", mhs:(%" PRIu64 ",%" PRIu64
717 "))(B) is root\n",
718 rbn_offset(tree).ToInt(),
719 rbn_size(tree).ToInt(),
720 rbn_left_mhs(tree),
721 rbn_right_mhs(tree));
722 else
723 fprintf(stderr,
724 "(%" PRIu64 ",%" PRIu64 ",mhs:(%" PRIu64 ",%" PRIu64
725 "))(%c) is %" PRIu64 "'s %s\n",
726 rbn_offset(tree).ToInt(),
727 rbn_size(tree).ToInt(),
728 rbn_left_mhs(tree),
729 rbn_right_mhs(tree),
730 rbn_is_red(tree) ? 'R' : 'B',
731 pair._offset.ToInt(),
732 dir == EDirection::RIGHT ? "right child" : "left child");
733
734 Dump(tree->_left, tree->_hole, EDirection::LEFT);
735 Dump(tree->_right, tree->_hole, EDirection::RIGHT);
736 }
737 }
738
739 uint64_t Tree::EffectiveSize(Node *node) {
740 OUUInt64 offset = rbn_offset(node);
741 OUUInt64 size = rbn_size(node);
742 OUUInt64 end = offset + size;
743 OUUInt64 aligned_offset(align(offset.ToInt(), _align));
744 if (aligned_offset > end) {
745 return 0;
746 }
747 return (end - aligned_offset).ToInt();
748 }
749
750 void Tree::Dump() {
751 if (_root != NULL)
752 Dump(_root, _root->_hole, (EDirection)0);
753 }
754
755 static void vis_bal_f(void *extra, Node *node, uint64_t depth) {
756 uint64_t **p = (uint64_t **)extra;
757 uint64_t min = *p[0];
758 uint64_t max = *p[1];
759 if (node->_left) {
760 Node *left = node->_left;
761 invariant(node == left->_parent);
762 }
763
764 if (node->_right) {
765 Node *right = node->_right;
766 invariant(node == right->_parent);
767 }
768
769 if (!node->_left || !node->_right) {
770 if (min > depth) {
771 *p[0] = depth;
772 } else if (max < depth) {
773 *p[1] = depth;
774 }
775 }
776 }
777
778 void Tree::ValidateBalance() {
779 uint64_t min_depth = 0xffffffffffffffff;
780 uint64_t max_depth = 0;
781 if (!_root) {
782 return;
783 }
784 uint64_t *p[2] = {&min_depth, &max_depth};
785 InOrderVisitor(vis_bal_f, (void *)p);
786 invariant((min_depth + 1) * 2 >= max_depth + 1);
787 }
788
789 static void vis_cmp_f(void *extra, Node *node, uint64_t UU(depth)) {
790 Node::BlockPair **p = (Node::BlockPair **)extra;
791
792 invariant_notnull(*p);
793 invariant((*p)->_offset == node->_hole._offset);
794
795 *p = *p + 1;
796 }
797
798 // validate the input pairs matches with sorted pairs
799 void Tree::ValidateInOrder(Node::BlockPair *pairs) {
800 InOrderVisitor(vis_cmp_f, &pairs);
801 }
802
803 uint64_t Tree::ValidateMhs(Node *node) {
804 if (!node)
805 return 0;
806 else {
807 uint64_t mhs_left = ValidateMhs(node->_left);
808 uint64_t mhs_right = ValidateMhs(node->_right);
809 if (mhs_left != rbn_left_mhs(node)) {
810 printf("assert failure: mhs_left = %" PRIu64 "\n", mhs_left);
811 Dump(node, node->_hole, (EDirection)0);
812 }
813 invariant(mhs_left == rbn_left_mhs(node));
814
815 if (mhs_right != rbn_right_mhs(node)) {
816 printf("assert failure: mhs_right = %" PRIu64 "\n", mhs_right);
817 Dump(node, node->_hole, (EDirection)0);
818 }
819 invariant(mhs_right == rbn_right_mhs(node));
820 return std::max(EffectiveSize(node), std::max(mhs_left, mhs_right));
821 }
822 }
823
824 void Tree::ValidateMhs() {
825 if (!_root)
826 return;
827 uint64_t mhs_left = ValidateMhs(_root->_left);
828 uint64_t mhs_right = ValidateMhs(_root->_right);
829 invariant(mhs_left == rbn_left_mhs(_root));
830 invariant(mhs_right == rbn_right_mhs(_root));
831 }
832
833} // namespace MhsRbTree
834