/* 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. */voidDbtux::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. */voidDbtux::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. */voidDbtux::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. */voidDbtux::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. */voidDbtux::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. */voidDbtux::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. */voidDbtux::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. */voidDbtux::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. */voidDbtux::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. */voidDbtux::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) {