dbtuxtree.cpp

MySQL数据库开发源码 值得一看哦

/* Copyright (C) 2003 MySQL AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program 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 General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

#define DBTUX_TREE_CPP
#include "Dbtux.hpp"

/*
 * Add entry.  Handle the case when there is room for one more.  This
 * is the common case given slack in nodes.
 */
void
Dbtux::treeAdd(Frag& frag, TreePos treePos, TreeEnt ent)
{
  TreeHead& tree = frag.m_tree;
  NodeHandle node(frag);
  if (treePos.m_loc != NullTupLoc) {
    // non-empty tree
    jam();
    selectNode(node, treePos.m_loc);
    unsigned pos = treePos.m_pos;
    if (node.getOccup() < tree.m_maxOccup) {
      // node has room
      jam();
      nodePushUp(node, pos, ent, RNIL);
      return;
    }
    treeAddFull(frag, node, pos, ent);
    return;
  }
  jam();
  insertNode(node);
  nodePushUp(node, 0, ent, RNIL);
  node.setSide(2);
  tree.m_root = node.m_loc;
}

/*
 * Add entry when node is full.  Handle the case when there is g.l.b
 * node in left subtree with room for one more.  It will receive the min
 * entry of this node.  The min entry could be the entry to add.
 */
void
Dbtux::treeAddFull(Frag& frag, NodeHandle lubNode, unsigned pos, TreeEnt ent)
{
  TreeHead& tree = frag.m_tree;
  TupLoc loc = lubNode.getLink(0);
  if (loc != NullTupLoc) {
    // find g.l.b node
    NodeHandle glbNode(frag);
    do {
      jam();
      selectNode(glbNode, loc);
      loc = glbNode.getLink(1);
    } while (loc != NullTupLoc);
    if (glbNode.getOccup() < tree.m_maxOccup) {
      // g.l.b node has room
      jam();
      Uint32 scanList = RNIL;
      if (pos != 0) {
        jam();
        // add the new entry and return min entry
        nodePushDown(lubNode, pos - 1, ent, scanList);
      }
      // g.l.b node receives min entry from l.u.b node
      nodePushUp(glbNode, glbNode.getOccup(), ent, scanList);
      return;
    }
    treeAddNode(frag, lubNode, pos, ent, glbNode, 1);
    return;
  }
  treeAddNode(frag, lubNode, pos, ent, lubNode, 0);
}

/*
 * Add entry when there is no g.l.b node in left subtree or the g.l.b
 * node is full.  We must add a new left or right child node which
 * becomes the new g.l.b node.
 */
void
Dbtux::treeAddNode(Frag& frag, NodeHandle lubNode, unsigned pos, TreeEnt ent, NodeHandle parentNode, unsigned i)
{
  NodeHandle glbNode(frag);
  insertNode(glbNode);
  // connect parent and child
  parentNode.setLink(i, glbNode.m_loc);
  glbNode.setLink(2, parentNode.m_loc);
  glbNode.setSide(i);
  Uint32 scanList = RNIL;
  if (pos != 0) {
    jam();
    // add the new entry and return min entry
    nodePushDown(lubNode, pos - 1, ent, scanList);
  }
  // g.l.b node receives min entry from l.u.b node
  nodePushUp(glbNode, 0, ent, scanList);
  // re-balance the tree
  treeAddRebalance(frag, parentNode, i);
}

/*
 * Re-balance tree after adding a node.  The process starts with the
 * parent of the added node.
 */
void
Dbtux::treeAddRebalance(Frag& frag, NodeHandle node, unsigned i)
{
  while (true) {
    // height of subtree i has increased by 1
    int j = (i == 0 ? -1 : +1);
    int b = node.getBalance();
    if (b == 0) {
      // perfectly balanced
      jam();
      node.setBalance(j);
      // height change propagates up
    } else if (b == -j) {
      // height of shorter subtree increased
      jam();
      node.setBalance(0);
      // height of tree did not change - done
      break;
    } else if (b == j) {
      // height of longer subtree increased
      jam();
      NodeHandle childNode(frag);
      selectNode(childNode, node.getLink(i));
      int b2 = childNode.getBalance();
      if (b2 == b) {
        jam();
        treeRotateSingle(frag, node, i);
      } else if (b2 == -b) {
        jam();
        treeRotateDouble(frag, node, i);
      } else {
        // height of subtree increased so it cannot be perfectly balanced
        ndbrequire(false);
      }
      // height of tree did not increase - done
      break;
    } else {
      ndbrequire(false);
    }
    TupLoc parentLoc = node.getLink(2);
    if (parentLoc == NullTupLoc) {
      jam();
      // root node - done
      break;
    }
    i = node.getSide();
    selectNode(node, parentLoc);
  }
}

/*
 * Remove entry.  Optimize for nodes with slack.  Handle the case when
 * there is no underflow i.e. occupancy remains at least minOccup.  For
 * interior nodes this is a requirement.  For others it means that we do
 * not need to consider merge of semi-leaf and leaf.
 */
void
Dbtux::treeRemove(Frag& frag, TreePos treePos)
{
  TreeHead& tree = frag.m_tree;
  unsigned pos = treePos.m_pos;
  NodeHandle node(frag);
  selectNode(node, treePos.m_loc);
  TreeEnt ent;
  if (node.getOccup() > tree.m_minOccup) {
    // no underflow in any node type
    jam();
    nodePopDown(node, pos, ent, 0);
    return;
  }
  if (node.getChilds() == 2) {
    // underflow in interior node
    jam();
    treeRemoveInner(frag, node, pos);
    return;
  }
  // remove entry in semi/leaf
  nodePopDown(node, pos, ent, 0);
  if (node.getLink(0) != NullTupLoc) {
    jam();
    treeRemoveSemi(frag, node, 0);
    return;
  }
  if (node.getLink(1) != NullTupLoc) {
    jam();
    treeRemoveSemi(frag, node, 1);
    return;
  }
  treeRemoveLeaf(frag, node);
}

/*
 * Remove entry when interior node underflows.  There is g.l.b node in
 * left subtree to borrow an entry from.  The max entry of the g.l.b
 * node becomes the min entry of this node.
 */
void
Dbtux::treeRemoveInner(Frag& frag, NodeHandle lubNode, unsigned pos)
{
  TreeHead& tree = frag.m_tree;
  TreeEnt ent;
  // find g.l.b node
  NodeHandle glbNode(frag);
  TupLoc loc = lubNode.getLink(0);
  do {
    jam();
    selectNode(glbNode, loc);
    loc = glbNode.getLink(1);
  } while (loc != NullTupLoc);
  // borrow max entry from semi/leaf
  Uint32 scanList = RNIL;
  nodePopDown(glbNode, glbNode.getOccup() - 1, ent, &scanList);
  // g.l.b may be empty now
  // a descending scan may try to enter the empty g.l.b
  // we prevent this in scanNext
  nodePopUp(lubNode, pos, ent, scanList);
  if (glbNode.getLink(0) != NullTupLoc) {
    jam();
    treeRemoveSemi(frag, glbNode, 0);
    return;
  }
  treeRemoveLeaf(frag, glbNode);
}

/*
 * Handle semi-leaf after removing an entry.  Move entries from leaf to
 * semi-leaf to bring semi-leaf occupancy above minOccup, if possible.
 * The leaf may become empty.
 */
void
Dbtux::treeRemoveSemi(Frag& frag, NodeHandle semiNode, unsigned i)
{
  TreeHead& tree = frag.m_tree;
  ndbrequire(semiNode.getChilds() < 2);
  TupLoc leafLoc = semiNode.getLink(i);
  NodeHandle leafNode(frag);
  selectNode(leafNode, leafLoc);
  if (semiNode.getOccup() < tree.m_minOccup) {
    jam();
    unsigned cnt = min(leafNode.getOccup(), tree.m_minOccup - semiNode.getOccup());
    nodeSlide(semiNode, leafNode, cnt, i);
    if (leafNode.getOccup() == 0) {
      // remove empty leaf
      jam();
      treeRemoveNode(frag, leafNode);
    }
  }
}

/*
 * Handle leaf after removing an entry.  If parent is semi-leaf, move
 * entries to it as in the semi-leaf case.  If parent is interior node,
 * do nothing.
 */
void
Dbtux::treeRemoveLeaf(Frag& frag, NodeHandle leafNode)
{
  TreeHead& tree = frag.m_tree;
  TupLoc parentLoc = leafNode.getLink(2);
  if (parentLoc != NullTupLoc) {
    jam();
    NodeHandle parentNode(frag);
    selectNode(parentNode, parentLoc);
    unsigned i = leafNode.getSide();
    if (parentNode.getLink(1 - i) == NullTupLoc) {
      // parent is semi-leaf
      jam();
      if (parentNode.getOccup() < tree.m_minOccup) {
        jam();
        unsigned cnt = min(leafNode.getOccup(), tree.m_minOccup - parentNode.getOccup());
        nodeSlide(parentNode, leafNode, cnt, i);
      }
    }
  }
  if (leafNode.getOccup() == 0) {
    jam();
    // remove empty leaf
    treeRemoveNode(frag, leafNode);
  }
}

/*
 * Remove empty leaf.
 */
void
Dbtux::treeRemoveNode(Frag& frag, NodeHandle leafNode)
{
  TreeHead& tree = frag.m_tree;
  ndbrequire(leafNode.getChilds() == 0);
  TupLoc parentLoc = leafNode.getLink(2);
  unsigned i = leafNode.getSide();
  deleteNode(leafNode);
  if (parentLoc != NullTupLoc) {
    jam();
    NodeHandle parentNode(frag);
    selectNode(parentNode, parentLoc);
    parentNode.setLink(i, NullTupLoc);
    // re-balance the tree
    treeRemoveRebalance(frag, parentNode, i);
    return;
  }
  // tree is now empty
  tree.m_root = NullTupLoc;
}

/*
 * Re-balance tree after removing a node.  The process starts with the
 * parent of the removed node.
 */
void
Dbtux::treeRemoveRebalance(Frag& frag, NodeHandle node, unsigned i)
{
  while (true) {
    // height of subtree i has decreased by 1
    int j = (i == 0 ? -1 : +1);
    int b = node.getBalance();
    if (b == 0) {
      // perfectly balanced
      jam();
      node.setBalance(-j);
      // height of tree did not change - done
      return;
    } else if (b == j) {
      // height of longer subtree has decreased
      jam();
      node.setBalance(0);
      // height change propagates up
    } else if (b == -j) {
      // height of shorter subtree has decreased
      jam();
      // child on the other side
      NodeHandle childNode(frag);
      selectNode(childNode, node.getLink(1 - i));
      int b2 = childNode.getBalance();
      if (b2 == b) {
        jam();
        treeRotateSingle(frag, node, 1 - i);
        // height of tree decreased and propagates up
      } else if (b2 == -b) {