ft/serialize/rbtree_mhs.cc

/*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
#ident "$Id$"
/*======
This file is part of PerconaFT.


Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.

    PerconaFT is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License, version 2,
    as published by the Free Software Foundation.

    PerconaFT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILIT or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with PerconaFT.  If not, see <http://www.gnu.org/licenses/>.

----------------------------------------

    PerconaFT is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License, version 3,
    as published by the Free Software Foundation.

    PerconaFT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with PerconaFT.  If not, see <http://www.gnu.org/licenses/>.
======= */

#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."

#include "ft/serialize/rbtree_mhs.h"
#include "portability/toku_assert.h"
#include "portability/toku_portability.h"
#include <algorithm>

namespace MhsRbTree {

    Tree::Tree() : _root(NULL), _align(1) {}

    Tree::Tree(uint64_t align) : _root(NULL), _align(align) {}

    Tree::~Tree() { Destroy(); }

    void Tree::PreOrder(Node *tree) const {
        if (tree != NULL) {
            fprintf(stderr, "%" PRIu64 " ", rbn_offset(tree).ToInt());
            PreOrder(tree->_left);
            PreOrder(tree->_right);
        }
    }

    void Tree::PreOrder() { PreOrder(_root); }

    void Tree::InOrder(Node *tree) const {
        if (tree != NULL) {
            InOrder(tree->_left);
            fprintf(stderr, "%" PRIu64 " ", rbn_offset(tree).ToInt());
            InOrder(tree->_right);
        }
    }

    // yeah, i only care about in order visitor. -Jun
    void Tree::InOrderVisitor(Node *tree,
                              void (*f)(void *, Node *, uint64_t),
                              void *extra,
                              uint64_t depth) {
        if (tree != NULL) {
            InOrderVisitor(tree->_left, f, extra, depth + 1);
            f(extra, tree, depth);
            InOrderVisitor(tree->_right, f, extra, depth + 1);
        }
    }

    void Tree::InOrderVisitor(void (*f)(void *, Node *, uint64_t),
                              void *extra) {
        InOrderVisitor(_root, f, extra, 0);
    }

    void Tree::InOrder() { InOrder(_root); }

    void Tree::PostOrder(Node *tree) const {
        if (tree != NULL) {
            PostOrder(tree->_left);
            PostOrder(tree->_right);
            fprintf(stderr, "%" PRIu64 " ", rbn_offset(tree).ToInt());
        }
    }

    void Tree::PostOrder() { PostOrder(_root); }

    Node *Tree::SearchByOffset(uint64_t offset) {
        Node *x = _root;
        while ((x != NULL) && (rbn_offset(x).ToInt() != offset)) {
            if (offset < rbn_offset(x).ToInt())
                x = x->_left;
            else
                x = x->_right;
        }

        return x;
    }

    // mostly for testing
    Node *Tree::SearchFirstFitBySize(uint64_t size) {
        if (EffectiveSize(_root) < size && rbn_left_mhs(_root) < size &&
            rbn_right_mhs(_root) < size) {
            return nullptr;
        } else {
            return SearchFirstFitBySizeHelper(_root, size);
        }
    }

    Node *Tree::SearchFirstFitBySizeHelper(Node *x, uint64_t size) {
        if (EffectiveSize(x) >= size) {
            // only possible to go left
            if (rbn_left_mhs(x) >= size)
                return SearchFirstFitBySizeHelper(x->_left, size);
            else
                return x;
        }
        if (rbn_left_mhs(x) >= size)
            return SearchFirstFitBySizeHelper(x->_left, size);

        if (rbn_right_mhs(x) >= size)
            return SearchFirstFitBySizeHelper(x->_right, size);

        // this is an invalid state
        Dump();
        ValidateBalance();
        ValidateMhs();
        invariant(0);
        return NULL;
    }

    Node *Tree::MinNode(Node *tree) {
        if (tree == NULL)
            return NULL;

        while (tree->_left != NULL)
            tree = tree->_left;
        return tree;
    }

    Node *Tree::MinNode() { return MinNode(_root); }

    Node *Tree::MaxNode(Node *tree) {
        if (tree == NULL)
            return NULL;

        while (tree->_right != NULL)
            tree = tree->_right;
        return tree;
    }

    Node *Tree::MaxNode() { return MaxNode(_root); }

    Node *Tree::SuccessorHelper(Node *y, Node *x) {
        while ((y != NULL) && (x == y->_right)) {
            x = y;
            y = y->_parent;
        }
        return y;
    }
    Node *Tree::Successor(Node *x) {
        if (x->_right != NULL)
            return MinNode(x->_right);

        Node *y = x->_parent;
        return SuccessorHelper(y, x);
    }

    Node *Tree::PredecessorHelper(Node *y, Node *x) {
        while ((y != NULL) && (x == y->_left)) {
            x = y;
            y = y->_parent;
        }

        return y;
    }
    Node *Tree::Predecessor(Node *x) {
        if (x->_left != NULL)
            return MaxNode(x->_left);

        Node *y = x->_parent;
        return SuccessorHelper(y, x);
    }

    /*
    *      px                              px
    *     /                               /
    *    x                               y
    *   /  \      --(left rotation)-->  / \               #
    *  lx   y                          x  ry
    *     /   \                       /  \
    *    ly   ry                      lx  ly
    *  max_hole_size updates are pretty local
    */

    void Tree::LeftRotate(Node *&root, Node *x) {
        Node *y = x->_right;

        x->_right = y->_left;
        rbn_right_mhs(x) = rbn_left_mhs(y);

        if (y->_left != NULL)
            y->_left->_parent = x;

        y->_parent = x->_parent;

        if (x->_parent == NULL) {
            root = y;
        } else {
            if (x->_parent->_left == x) {
                x->_parent->_left = y;
            } else {
                x->_parent->_right = y;
            }
        }
        y->_left = x;
        rbn_left_mhs(y) = mhs_of_subtree(x);

        x->_parent = y;
    }

    /*            py                               py
     *           /                                /
     *          y                                x
     *         /  \      --(right rotate)-->    /  \                     #
     *        x   ry                           lx   y
     *       / \                                   / \                   #
     *      lx  rx                                rx  ry
     *
     */

    void Tree::RightRotate(Node *&root, Node *y) {
        Node *x = y->_left;

        y->_left = x->_right;
        rbn_left_mhs(y) = rbn_right_mhs(x);

        if (x->_right != NULL)
            x->_right->_parent = y;

        x->_parent = y->_parent;

        if (y->_parent == NULL) {
            root = x;
        } else {
            if (y == y->_parent->_right)
                y->_parent->_right = x;
            else
                y->_parent->_left = x;
        }

        x->_right = y;
        rbn_right_mhs(x) = mhs_of_subtree(y);
        y->_parent = x;
    }

    // walking from this node up to update the mhs info
    // whenver there is change on left/right mhs or size we should recalculate.
    // prerequisit: the children of the node are mhs up-to-date.
    void Tree::RecalculateMhs(Node *node) {
        uint64_t *p_node_mhs = 0;
        Node *parent = node->_parent;

        if (!parent)
            return;

        uint64_t max_mhs = mhs_of_subtree(node);
        if (node == parent->_left) {
            p_node_mhs = &rbn_left_mhs(parent);
        } else if (node == parent->_right) {
            p_node_mhs = &rbn_right_mhs(parent);
        } else {
            return;
        }
        if (*p_node_mhs != max_mhs) {
            *p_node_mhs = max_mhs;
            RecalculateMhs(parent);
        }
    }

    void Tree::IsNewNodeMergable(Node *pred,
                                 Node *succ,
                                 Node::BlockPair pair,
                                 bool *left_merge,
                                 bool *right_merge) {
        if (pred) {
            OUUInt64 end_of_pred = rbn_size(pred) + rbn_offset(pred);
            if (end_of_pred < pair._offset)
                *left_merge = false;
            else {
                invariant(end_of_pred == pair._offset);
                *left_merge = true;
            }
        }
        if (succ) {
            OUUInt64 begin_of_succ = rbn_offset(succ);
            OUUInt64 end_of_node = pair._offset + pair._size;
            if (end_of_node < begin_of_succ) {
                *right_merge = false;
            } else {
                invariant(end_of_node == begin_of_succ);
                *right_merge = true;
            }
        }
    }

    void Tree::AbsorbNewNode(Node *pred,
                             Node *succ,
                             Node::BlockPair pair,
                             bool left_merge,
                             bool right_merge,
                             bool is_right_child) {
        invariant(left_merge || right_merge);
        if (left_merge && right_merge) {
            // merge to the succ
            if (!is_right_child) {
                rbn_size(succ) += pair._size;
                rbn_offset(succ) = pair._offset;
                // merge to the pred
                rbn_size(pred) += rbn_size(succ);
                // to keep the invariant of the tree -no overlapping holes
                rbn_offset(succ) += rbn_size(succ);
                rbn_size(succ) = 0;
                RecalculateMhs(succ);
                RecalculateMhs(pred);
                // pred dominates succ. this is going to
                // update the pred labels separately.
                // remove succ
                RawRemove(_root, succ);
            } else {
                rbn_size(pred) += pair._size;
                rbn_offset(succ) = rbn_offset(pred);
                rbn_size(succ) += rbn_size(pred);
                rbn_offset(pred) += rbn_size(pred);
                rbn_size(pred) = 0;
                RecalculateMhs(pred);
                RecalculateMhs(succ);
                // now remove pred
                RawRemove(_root, pred);
            }
        } else if (left_merge) {
            rbn_size(pred) += pair._size;
            RecalculateMhs(pred);
        } else if (right_merge) {
            rbn_offset(succ) -= pair._size;
            rbn_size(succ) += pair._size;
            RecalculateMhs(succ);
        }
    }
    // this is the most tedious part, but not complicated:
    // 1.find where to insert the pair
    // 2.if the pred and succ can merge with the pair. merge with them. either
    // pred
    // or succ can be removed.
    // 3. if only left-mergable or right-mergeable, just merge
    // 4. non-mergable case. insert the node and run the fixup.

    int Tree::Insert(Node *&root, Node::BlockPair pair) {
        Node *x = _root;
        Node *y = NULL;
        bool left_merge = false;
        bool right_merge = false;
        Node *node = NULL;

        while (x != NULL) {
            y = x;
            if (pair._offset < rbn_key(x))
                x = x->_left;
            else
                x = x->_right;
        }

        // we found where to insert, lets find out the pred and succ for
        // possible
        // merges.
        //  node->parent = y;
        Node *pred, *succ;
        if (y != NULL) {
            if (pair._offset < rbn_key(y)) {
                // as the left child
                pred = PredecessorHelper(y->_parent, y);
                succ = y;
                IsNewNodeMergable(pred, succ, pair, &left_merge, &right_merge);
                if (left_merge || right_merge) {
                    AbsorbNewNode(
                        pred, succ, pair, left_merge, right_merge, false);
                } else {
                    // construct the node
                    Node::Pair mhsp {0, 0};
                    node =
                        new Node(EColor::BLACK, pair, mhsp, nullptr, nullptr, nullptr);
                    if (!node)
                        return -1;
                    y->_left = node;
                    node->_parent = y;
                    RecalculateMhs(node);
                }

            } else {
                // as the right child
                pred = y;
                succ = SuccessorHelper(y->_parent, y);
                IsNewNodeMergable(pred, succ, pair, &left_merge, &right_merge);
                if (left_merge || right_merge) {
                    AbsorbNewNode(
                        pred, succ, pair, left_merge, right_merge, true);
                } else {
                    // construct the node
                    Node::Pair mhsp {0, 0};
                    node =
                        new Node(EColor::BLACK, pair, mhsp, nullptr, nullptr, nullptr);
                    if (!node)
                        return -1;
                    y->_right = node;
                    node->_parent = y;
                    RecalculateMhs(node);
                }
            }
        } else {
            Node::Pair mhsp {0, 0};
            node = new Node(EColor::BLACK, pair, mhsp, nullptr, nullptr, nullptr);
            if (!node)
                return -1;
            root = node;
        }
        if (!left_merge && !right_merge) {
            invariant_notnull(node);
            node->_color = EColor::RED;
            return InsertFixup(root, node);
        }
        return 0;
    }

    int Tree::InsertFixup(Node *&root, Node *node) {
        Node *parent, *gparent;
        while ((parent = rbn_parent(node)) && rbn_is_red(parent)) {
            gparent = rbn_parent(parent);
            if (parent == gparent->_left) {
                {
                    Node *uncle = gparent->_right;
                    if (uncle && rbn_is_red(uncle)) {
                        rbn_set_black(uncle);
                        rbn_set_black(parent);
                        rbn_set_red(gparent);
                        node = gparent;
                        continue;
                    }
                }

                if (parent->_right == node) {
                    Node *tmp;
                    LeftRotate(root, parent);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }

                rbn_set_black(parent);
                rbn_set_red(gparent);
                RightRotate(root, gparent);
            } else {
                {
                    Node *uncle = gparent->_left;
                    if (uncle && rbn_is_red(uncle)) {
                        rbn_set_black(uncle);
                        rbn_set_black(parent);
                        rbn_set_red(gparent);
                        node = gparent;
                        continue;
                    }
                }

                if (parent->_left == node) {
                    Node *tmp;
                    RightRotate(root, parent);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }
                rbn_set_black(parent);
                rbn_set_red(gparent);
                LeftRotate(root, gparent);
            }
        }
        rbn_set_black(root);
        return 0;
    }

    int Tree::Insert(Node::BlockPair pair) { return Insert(_root, pair); }

    uint64_t Tree::Remove(size_t size) {
        Node *node = SearchFirstFitBySize(size);
        return Remove(_root, node, size);
    }

    void Tree::RawRemove(Node *&root, Node *node) {
        Node *child, *parent;
        EColor color;

        if ((node->_left != NULL) && (node->_right != NULL)) {
            Node *replace = node;
            replace = replace->_right;
            while (replace->_left != NULL)
                replace = replace->_left;

            if (rbn_parent(node)) {
                if (rbn_parent(node)->_left == node)
                    rbn_parent(node)->_left = replace;
                else
                    rbn_parent(node)->_right = replace;
            } else {
                root = replace;
            }
            child = replace->_right;
            parent = rbn_parent(replace);
            color = rbn_color(replace);

            if (parent == node) {
                parent = replace;
            } else {
                if (child)
                    rbn_parent(child) = parent;

                parent->_left = child;
                rbn_left_mhs(parent) = rbn_right_mhs(replace);
                RecalculateMhs(parent);
                replace->_right = node->_right;
                rbn_set_parent(node->_right, replace);
                rbn_right_mhs(replace) = rbn_right_mhs(node);
            }

            replace->_parent = node->_parent;
            replace->_color = node->_color;
            replace->_left = node->_left;
            rbn_left_mhs(replace) = rbn_left_mhs(node);
            node->_left->_parent = replace;
            RecalculateMhs(replace);
            if (color == EColor::BLACK)
                RawRemoveFixup(root, child, parent);
            delete node;
            return;
        }

        if (node->_left != NULL)
            child = node->_left;
        else
            child = node->_right;

        parent = node->_parent;
        color = node->_color;

        if (child)
            child->_parent = parent;

        if (parent) {
            if (parent->_left == node) {
                parent->_left = child;
                rbn_left_mhs(parent) = child ? mhs_of_subtree(child) : 0;
            } else {
                parent->_right = child;
                rbn_right_mhs(parent) = child ? mhs_of_subtree(child) : 0;
            }
            RecalculateMhs(parent);
        } else
            root = child;
        if (color == EColor::BLACK)
            RawRemoveFixup(root, child, parent);
        delete node;
    }

    void Tree::RawRemove(uint64_t offset) {
        Node *node = SearchByOffset(offset);
        RawRemove(_root, node);
    }
    static inline uint64_t align(uint64_t value, uint64_t ba_alignment) {
        return ((value + ba_alignment - 1) / ba_alignment) * ba_alignment;
    }
    uint64_t Tree::Remove(Node *&root, Node *node, size_t size) {
        OUUInt64 n_offset = rbn_offset(node);
        OUUInt64 n_size = rbn_size(node);
        OUUInt64 answer_offset(align(rbn_offset(node).ToInt(), _align));

        invariant((answer_offset + size) <= (n_offset + n_size));
        if (answer_offset == n_offset) {
            rbn_offset(node) += size;
            rbn_size(node) -= size;
            RecalculateMhs(node);
            if (rbn_size(node) == 0) {
                RawRemove(root, node);
            }

        } else {
            if (answer_offset + size == n_offset + n_size) {
                rbn_size(node) -= size;
                RecalculateMhs(node);
            } else {
                // well, cut in the middle...
                rbn_size(node) = answer_offset - n_offset;
                RecalculateMhs(node);
                Insert(_root,
                       {(answer_offset + size),
                        (n_offset + n_size) - (answer_offset + size)});
            }
        }
        return answer_offset.ToInt();
    }

    void Tree::RawRemoveFixup(Node *&root, Node *node, Node *parent) {
        Node *other;
        while ((!node || rbn_is_black(node)) && node != root) {
            if (parent->_left == node) {
                other = parent->_right;
                if (rbn_is_red(other)) {
                    // Case 1: the brother of X, w, is read
                    rbn_set_black(other);
                    rbn_set_red(parent);
                    LeftRotate(root, parent);
                    other = parent->_right;
                }
                if ((!other->_left || rbn_is_black(other->_left)) &&
                    (!other->_right || rbn_is_black(other->_right))) {
                    // Case 2: w is black and both of w's children are black
                    rbn_set_red(other);
                    node = parent;
                    parent = rbn_parent(node);
                } else {
                    if (!other->_right || rbn_is_black(other->_right)) {
                        // Case 3: w is black and left child of w is red but
                        // right
                        // child is black
                        rbn_set_black(other->_left);
                        rbn_set_red(other);
                        RightRotate(root, other);
                        other = parent->_right;
                    }
                    // Case 4: w is black and right child of w is red,
                    // regardless of
                    // left child's color
                    rbn_set_color(other, rbn_color(parent));
                    rbn_set_black(parent);
                    rbn_set_black(other->_right);
                    LeftRotate(root, parent);
                    node = root;
                    break;
                }
            } else {
                other = parent->_left;
                if (rbn_is_red(other)) {
                    // Case 1: w is red
                    rbn_set_black(other);
                    rbn_set_red(parent);
                    RightRotate(root, parent);
                    other = parent->_left;
                }
                if ((!other->_left || rbn_is_black(other->_left)) &&
                    (!other->_right || rbn_is_black(other->_right))) {
                    // Case 2: w is black and both children are black
                    rbn_set_red(other);
                    node = parent;
                    parent = rbn_parent(node);
                } else {
                    if (!other->_left || rbn_is_black(other->_left)) {
                        // Case 3: w is black and left child of w is red whereas
                        // right child is black
                        rbn_set_black(other->_right);
                        rbn_set_red(other);
                        LeftRotate(root, other);
                        other = parent->_left;
                    }
                    // Case 4:w is black and right child of w is red, regardless
                    // of
                    // the left child's color
                    rbn_set_color(other, rbn_color(parent));
                    rbn_set_black(parent);
                    rbn_set_black(other->_left);
                    RightRotate(root, parent);
                    node = root;
                    break;
                }
            }
        }
        if (node)
            rbn_set_black(node);
    }

    void Tree::Destroy(Node *&tree) {
        if (tree == NULL)
            return;

        if (tree->_left != NULL)
            Destroy(tree->_left);
        if (tree->_right != NULL)
            Destroy(tree->_right);

        delete tree;
        tree = NULL;
    }

    void Tree::Destroy() { Destroy(_root); }

    void Tree::Dump(Node *tree, Node::BlockPair pair, EDirection dir) {
        if (tree != NULL) {
            if (dir == EDirection::NONE)
                fprintf(stderr,
                        "(%" PRIu64 ",%" PRIu64 ", mhs:(%" PRIu64 ",%" PRIu64
                        "))(B) is root\n",
                        rbn_offset(tree).ToInt(),
                        rbn_size(tree).ToInt(),
                        rbn_left_mhs(tree),
                        rbn_right_mhs(tree));
            else
                fprintf(stderr,
                        "(%" PRIu64 ",%" PRIu64 ",mhs:(%" PRIu64 ",%" PRIu64
                        "))(%c) is %" PRIu64 "'s %s\n",
                        rbn_offset(tree).ToInt(),
                        rbn_size(tree).ToInt(),
                        rbn_left_mhs(tree),
                        rbn_right_mhs(tree),
                        rbn_is_red(tree) ? 'R' : 'B',
                        pair._offset.ToInt(),
                        dir == EDirection::RIGHT ? "right child" : "left child");

            Dump(tree->_left, tree->_hole, EDirection::LEFT);
            Dump(tree->_right, tree->_hole, EDirection::RIGHT);
        }
    }

    uint64_t Tree::EffectiveSize(Node *node) {
        OUUInt64 offset = rbn_offset(node);
        OUUInt64 size = rbn_size(node);
        OUUInt64 end = offset + size;
        OUUInt64 aligned_offset(align(offset.ToInt(), _align));
        if (aligned_offset > end) {
            return 0;
        }
        return (end - aligned_offset).ToInt();
    }

    void Tree::Dump() {
        if (_root != NULL)
            Dump(_root, _root->_hole, (EDirection)0);
    }

    static void vis_bal_f(void *extra, Node *node, uint64_t depth) {
        uint64_t **p = (uint64_t **)extra;
        uint64_t min = *p[0];
        uint64_t max = *p[1];
        if (node->_left) {
            Node *left = node->_left;
            invariant(node == left->_parent);
        }

        if (node->_right) {
            Node *right = node->_right;
            invariant(node == right->_parent);
        }

        if (!node->_left || !node->_right) {
            if (min > depth) {
                *p[0] = depth;
            } else if (max < depth) {
                *p[1] = depth;
            }
        }
    }

    void Tree::ValidateBalance() {
        uint64_t min_depth = 0xffffffffffffffff;
        uint64_t max_depth = 0;
        if (!_root) {
            return;
        }
        uint64_t *p[2] = {&min_depth, &max_depth};
        InOrderVisitor(vis_bal_f, (void *)p);
        invariant((min_depth + 1) * 2 >= max_depth + 1);
    }

    static void vis_cmp_f(void *extra, Node *node, uint64_t UU(depth)) {
        Node::BlockPair **p = (Node::BlockPair **)extra;

        invariant_notnull(*p);
        invariant((*p)->_offset == node->_hole._offset);

        *p = *p + 1;
    }

    // validate the input pairs matches with sorted pairs
    void Tree::ValidateInOrder(Node::BlockPair *pairs) {
        InOrderVisitor(vis_cmp_f, &pairs);
    }

    uint64_t Tree::ValidateMhs(Node *node) {
        if (!node)
            return 0;
        else {
            uint64_t mhs_left = ValidateMhs(node->_left);
            uint64_t mhs_right = ValidateMhs(node->_right);
            if (mhs_left != rbn_left_mhs(node)) {
                printf("assert failure: mhs_left = %" PRIu64 "\n", mhs_left);
                Dump(node, node->_hole, (EDirection)0);
            }
            invariant(mhs_left == rbn_left_mhs(node));

            if (mhs_right != rbn_right_mhs(node)) {
                printf("assert failure: mhs_right = %" PRIu64 "\n", mhs_right);
                Dump(node, node->_hole, (EDirection)0);
            }
            invariant(mhs_right == rbn_right_mhs(node));
            return std::max(EffectiveSize(node), std::max(mhs_left, mhs_right));
        }
    }

    void Tree::ValidateMhs() {
        if (!_root)
            return;
        uint64_t mhs_left = ValidateMhs(_root->_left);
        uint64_t mhs_right = ValidateMhs(_root->_right);
        invariant(mhs_left == rbn_left_mhs(_root));
        invariant(mhs_right == rbn_right_mhs(_root));
    }

}  // namespace MhsRbTree