DbtuxNode.cpp
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:16k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2003 MySQL AB
  2.    This program is free software; you can redistribute it and/or modify
  3.    it under the terms of the GNU General Public License as published by
  4.    the Free Software Foundation; either version 2 of the License, or
  5.    (at your option) any later version.
  6.    This program is distributed in the hope that it will be useful,
  7.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  9.    GNU General Public License for more details.
  10.    You should have received a copy of the GNU General Public License
  11.    along with this program; if not, write to the Free Software
  12.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  13. #define DBTUX_NODE_CPP
  14. #include "Dbtux.hpp"
  15. /*
  16.  * Allocate index node in TUP.
  17.  */
  18. int
  19. Dbtux::allocNode(Signal* signal, NodeHandle& node)
  20. {
  21.   if (ERROR_INSERTED(12007)) {
  22.     jam();
  23.     CLEAR_ERROR_INSERT_VALUE;
  24.     return TuxMaintReq::NoMemError;
  25.   }
  26.   Frag& frag = node.m_frag;
  27.   Uint32 pageId = NullTupLoc.getPageId();
  28.   Uint32 pageOffset = NullTupLoc.getPageOffset();
  29.   Uint32* node32 = 0;
  30.   int errorCode = c_tup->tuxAllocNode(signal, frag.m_tupIndexFragPtrI, pageId, pageOffset, node32);
  31.   jamEntry();
  32.   if (errorCode == 0) {
  33.     jam();
  34.     node.m_loc = TupLoc(pageId, pageOffset);
  35.     node.m_node = reinterpret_cast<TreeNode*>(node32);
  36.     ndbrequire(node.m_loc != NullTupLoc && node.m_node != 0);
  37.   } else {
  38.     switch (errorCode) {
  39.     case 827:
  40.       errorCode = TuxMaintReq::NoMemError;
  41.       break;
  42.     }
  43.   }
  44.   return errorCode;
  45. }
  46. /*
  47.  * Set handle to point to existing node.
  48.  */
  49. void
  50. Dbtux::selectNode(NodeHandle& node, TupLoc loc)
  51. {
  52.   Frag& frag = node.m_frag;
  53.   ndbrequire(loc != NullTupLoc);
  54.   Uint32 pageId = loc.getPageId();
  55.   Uint32 pageOffset = loc.getPageOffset();
  56.   Uint32* node32 = 0;
  57.   c_tup->tuxGetNode(frag.m_tupIndexFragPtrI, pageId, pageOffset, node32);
  58.   jamEntry();
  59.   node.m_loc = loc;
  60.   node.m_node = reinterpret_cast<TreeNode*>(node32);
  61.   ndbrequire(node.m_loc != NullTupLoc && node.m_node != 0);
  62. }
  63. /*
  64.  * Set handle to point to new node.  Uses a pre-allocated node.
  65.  */
  66. void
  67. Dbtux::insertNode(NodeHandle& node)
  68. {
  69.   Frag& frag = node.m_frag;
  70.   // unlink from freelist
  71.   selectNode(node, frag.m_freeLoc);
  72.   frag.m_freeLoc = node.getLink(0);
  73.   new (node.m_node) TreeNode();
  74. #ifdef VM_TRACE
  75.   TreeHead& tree = frag.m_tree;
  76.   memset(node.getPref(), DataFillByte, tree.m_prefSize << 2);
  77.   TreeEnt* entList = tree.getEntList(node.m_node);
  78.   memset(entList, NodeFillByte, (tree.m_maxOccup + 1) * (TreeEntSize << 2));
  79. #endif
  80. }
  81. /*
  82.  * Delete existing node.  Simply put it on the freelist.
  83.  */
  84. void
  85. Dbtux::deleteNode(NodeHandle& node)
  86. {
  87.   Frag& frag = node.m_frag;
  88.   ndbrequire(node.getOccup() == 0);
  89.   // link to freelist
  90.   node.setLink(0, frag.m_freeLoc);
  91.   frag.m_freeLoc = node.m_loc;
  92.   // invalidate the handle
  93.   node.m_loc = NullTupLoc;
  94.   node.m_node = 0;
  95. }
  96. /*
  97.  * Set prefix.  Copies the number of words that fits.  Includes
  98.  * attribute headers for now.  XXX use null mask instead
  99.  */
  100. void
  101. Dbtux::setNodePref(NodeHandle& node)
  102. {
  103.   const Frag& frag = node.m_frag;
  104.   const TreeHead& tree = frag.m_tree;
  105.   readKeyAttrs(frag, node.getMinMax(0), 0, c_entryKey);
  106.   copyAttrs(frag, c_entryKey, node.getPref(), tree.m_prefSize);
  107. }
  108. // node operations
  109. /*
  110.  * Add entry at position.  Move entries greater than or equal to the old
  111.  * one (if any) to the right.
  112.  *
  113.  *            X
  114.  *            v
  115.  *      A B C D E _ _  =>  A B C X D E _
  116.  *      0 1 2 3 4 5 6      0 1 2 3 4 5 6
  117.  *
  118.  * Add list of scans at the new entry.
  119.  */
  120. void
  121. Dbtux::nodePushUp(NodeHandle& node, unsigned pos, const TreeEnt& ent, Uint32 scanList)
  122. {
  123.   Frag& frag = node.m_frag;
  124.   TreeHead& tree = frag.m_tree;
  125.   const unsigned occup = node.getOccup();
  126.   ndbrequire(occup < tree.m_maxOccup && pos <= occup);
  127.   // fix old scans
  128.   if (node.getNodeScan() != RNIL)
  129.     nodePushUpScans(node, pos);
  130.   // fix node
  131.   TreeEnt* const entList = tree.getEntList(node.m_node);
  132.   entList[occup] = entList[0];
  133.   TreeEnt* const tmpList = entList + 1;
  134.   for (unsigned i = occup; i > pos; i--) {
  135.     jam();
  136.     tmpList[i] = tmpList[i - 1];
  137.   }
  138.   tmpList[pos] = ent;
  139.   entList[0] = entList[occup + 1];
  140.   node.setOccup(occup + 1);
  141.   // add new scans
  142.   if (scanList != RNIL)
  143.     addScanList(node, pos, scanList);
  144.   // fix prefix
  145.   if (occup == 0 || pos == 0)
  146.     setNodePref(node);
  147. }
  148. void
  149. Dbtux::nodePushUpScans(NodeHandle& node, unsigned pos)
  150. {
  151.   const unsigned occup = node.getOccup();
  152.   ScanOpPtr scanPtr;
  153.   scanPtr.i = node.getNodeScan();
  154.   do {
  155.     jam();
  156.     c_scanOpPool.getPtr(scanPtr);
  157.     TreePos& scanPos = scanPtr.p->m_scanPos;
  158.     ndbrequire(scanPos.m_loc == node.m_loc && scanPos.m_pos < occup);
  159.     if (scanPos.m_pos >= pos) {
  160.       jam();
  161. #ifdef VM_TRACE
  162.       if (debugFlags & DebugScan) {
  163.         debugOut << "Fix scan " << scanPtr.i << " " << *scanPtr.p << endl;
  164.         debugOut << "At pushUp pos=" << pos << " " << node << endl;
  165.       }
  166. #endif
  167.       scanPos.m_pos++;
  168.     }
  169.     scanPtr.i = scanPtr.p->m_nodeScan;
  170.   } while (scanPtr.i != RNIL);
  171. }
  172. /*
  173.  * Remove and return entry at position.  Move entries greater than the
  174.  * removed one to the left.  This is the opposite of nodePushUp.
  175.  *
  176.  *                               D
  177.  *            ^                  ^
  178.  *      A B C D E F _  =>  A B C E F _ _
  179.  *      0 1 2 3 4 5 6      0 1 2 3 4 5 6
  180.  *
  181.  * Scans at removed entry are returned if non-zero location is passed or
  182.  * else moved forward.
  183.  */
  184. void
  185. Dbtux::nodePopDown(NodeHandle& node, unsigned pos, TreeEnt& ent, Uint32* scanList)
  186. {
  187.   Frag& frag = node.m_frag;
  188.   TreeHead& tree = frag.m_tree;
  189.   const unsigned occup = node.getOccup();
  190.   ndbrequire(occup <= tree.m_maxOccup && pos < occup);
  191.   if (node.getNodeScan() != RNIL) {
  192.     // remove or move scans at this position
  193.     if (scanList == 0)
  194.       moveScanList(node, pos);
  195.     else
  196.       removeScanList(node, pos, *scanList);
  197.     // fix other scans
  198.     if (node.getNodeScan() != RNIL)
  199.       nodePopDownScans(node, pos);
  200.   }
  201.   // fix node
  202.   TreeEnt* const entList = tree.getEntList(node.m_node);
  203.   entList[occup] = entList[0];
  204.   TreeEnt* const tmpList = entList + 1;
  205.   ent = tmpList[pos];
  206.   for (unsigned i = pos; i < occup - 1; i++) {
  207.     jam();
  208.     tmpList[i] = tmpList[i + 1];
  209.   }
  210.   entList[0] = entList[occup - 1];
  211.   node.setOccup(occup - 1);
  212.   // fix prefix
  213.   if (occup != 1 && pos == 0)
  214.     setNodePref(node);
  215. }
  216. void
  217. Dbtux::nodePopDownScans(NodeHandle& node, unsigned pos)
  218. {
  219.   const unsigned occup = node.getOccup();
  220.   ScanOpPtr scanPtr;
  221.   scanPtr.i = node.getNodeScan();
  222.   do {
  223.     jam();
  224.     c_scanOpPool.getPtr(scanPtr);
  225.     TreePos& scanPos = scanPtr.p->m_scanPos;
  226.     ndbrequire(scanPos.m_loc == node.m_loc && scanPos.m_pos < occup);
  227.     // handled before
  228.     ndbrequire(scanPos.m_pos != pos);
  229.     if (scanPos.m_pos > pos) {
  230.       jam();
  231. #ifdef VM_TRACE
  232.       if (debugFlags & DebugScan) {
  233.         debugOut << "Fix scan " << scanPtr.i << " " << *scanPtr.p << endl;
  234.         debugOut << "At popDown pos=" << pos << " " << node << endl;
  235.       }
  236. #endif
  237.       scanPos.m_pos--;
  238.     }
  239.     scanPtr.i = scanPtr.p->m_nodeScan;
  240.   } while (scanPtr.i != RNIL);
  241. }
  242. /*
  243.  * Add entry at existing position.  Move entries less than or equal to
  244.  * the old one to the left.  Remove and return old min entry.
  245.  *
  246.  *            X            A
  247.  *      ^     v            ^
  248.  *      A B C D E _ _  =>  B C D X E _ _
  249.  *      0 1 2 3 4 5 6      0 1 2 3 4 5 6
  250.  *
  251.  * Return list of scans at the removed position 0.
  252.  */
  253. void
  254. Dbtux::nodePushDown(NodeHandle& node, unsigned pos, TreeEnt& ent, Uint32& scanList)
  255. {
  256.   Frag& frag = node.m_frag;
  257.   TreeHead& tree = frag.m_tree;
  258.   const unsigned occup = node.getOccup();
  259.   ndbrequire(occup <= tree.m_maxOccup && pos < occup);
  260.   if (node.getNodeScan() != RNIL) {
  261.     // remove scans at 0
  262.     removeScanList(node, 0, scanList);
  263.     // fix other scans
  264.     if (node.getNodeScan() != RNIL)
  265.       nodePushDownScans(node, pos);
  266.   }
  267.   // fix node
  268.   TreeEnt* const entList = tree.getEntList(node.m_node);
  269.   entList[occup] = entList[0];
  270.   TreeEnt* const tmpList = entList + 1;
  271.   TreeEnt oldMin = tmpList[0];
  272.   for (unsigned i = 0; i < pos; i++) {
  273.     jam();
  274.     tmpList[i] = tmpList[i + 1];
  275.   }
  276.   tmpList[pos] = ent;
  277.   ent = oldMin;
  278.   entList[0] = entList[occup];
  279.   // fix prefix
  280.   if (true)
  281.     setNodePref(node);
  282. }
  283. void
  284. Dbtux::nodePushDownScans(NodeHandle& node, unsigned pos)
  285. {
  286.   const unsigned occup = node.getOccup();
  287.   ScanOpPtr scanPtr;
  288.   scanPtr.i = node.getNodeScan();
  289.   do {
  290.     jam();
  291.     c_scanOpPool.getPtr(scanPtr);
  292.     TreePos& scanPos = scanPtr.p->m_scanPos;
  293.     ndbrequire(scanPos.m_loc == node.m_loc && scanPos.m_pos < occup);
  294.     // handled before
  295.     ndbrequire(scanPos.m_pos != 0);
  296.     if (scanPos.m_pos <= pos) {
  297.       jam();
  298. #ifdef VM_TRACE
  299.       if (debugFlags & DebugScan) {
  300.         debugOut << "Fix scan " << scanPtr.i << " " << *scanPtr.p << endl;
  301.         debugOut << "At pushDown pos=" << pos << " " << node << endl;
  302.       }
  303. #endif
  304.       scanPos.m_pos--;
  305.     }
  306.     scanPtr.i = scanPtr.p->m_nodeScan;
  307.   } while (scanPtr.i != RNIL);
  308. }
  309. /*
  310.  * Remove and return entry at position.  Move entries less than the
  311.  * removed one to the right.  Replace min entry by the input entry.
  312.  * This is the opposite of nodePushDown.
  313.  *
  314.  *      X                        D
  315.  *      v     ^                  ^
  316.  *      A B C D E _ _  =>  X A B C E _ _
  317.  *      0 1 2 3 4 5 6      0 1 2 3 4 5 6
  318.  *
  319.  * Move scans at removed entry and add scans at the new entry.
  320.  */
  321. void
  322. Dbtux::nodePopUp(NodeHandle& node, unsigned pos, TreeEnt& ent, Uint32 scanList)
  323. {
  324.   Frag& frag = node.m_frag;
  325.   TreeHead& tree = frag.m_tree;
  326.   const unsigned occup = node.getOccup();
  327.   ndbrequire(occup <= tree.m_maxOccup && pos < occup);
  328.   if (node.getNodeScan() != RNIL) {
  329.     // move scans whose entry disappears
  330.     moveScanList(node, pos);
  331.     // fix other scans
  332.     if (node.getNodeScan() != RNIL)
  333.       nodePopUpScans(node, pos);
  334.   }
  335.   // fix node
  336.   TreeEnt* const entList = tree.getEntList(node.m_node);
  337.   entList[occup] = entList[0];
  338.   TreeEnt* const tmpList = entList + 1;
  339.   TreeEnt newMin = ent;
  340.   ent = tmpList[pos];
  341.   for (unsigned i = pos; i > 0; i--) {
  342.     jam();
  343.     tmpList[i] = tmpList[i - 1];
  344.   }
  345.   tmpList[0] = newMin;
  346.   entList[0] = entList[occup];
  347.   // add scans
  348.   if (scanList != RNIL)
  349.     addScanList(node, 0, scanList);
  350.   // fix prefix
  351.   if (true)
  352.     setNodePref(node);
  353. }
  354. void
  355. Dbtux::nodePopUpScans(NodeHandle& node, unsigned pos)
  356. {
  357.   const unsigned occup = node.getOccup();
  358.   ScanOpPtr scanPtr;
  359.   scanPtr.i = node.getNodeScan();
  360.   do {
  361.     jam();
  362.     c_scanOpPool.getPtr(scanPtr);
  363.     TreePos& scanPos = scanPtr.p->m_scanPos;
  364.     ndbrequire(scanPos.m_loc == node.m_loc && scanPos.m_pos < occup);
  365.     ndbrequire(scanPos.m_pos != pos);
  366.     if (scanPos.m_pos < pos) {
  367.       jam();
  368. #ifdef VM_TRACE
  369.       if (debugFlags & DebugScan) {
  370.         debugOut << "Fix scan " << scanPtr.i << " " << *scanPtr.p << endl;
  371.         debugOut << "At popUp pos=" << pos << " " << node << endl;
  372.       }
  373. #endif
  374.       scanPos.m_pos++;
  375.     }
  376.     scanPtr.i = scanPtr.p->m_nodeScan;
  377.   } while (scanPtr.i != RNIL);
  378. }
  379. /*
  380.  * Move number of entries from another node to this node before the min
  381.  * (i=0) or after the max (i=1).  Expensive but not often used.
  382.  */
  383. void
  384. Dbtux::nodeSlide(NodeHandle& dstNode, NodeHandle& srcNode, unsigned cnt, unsigned i)
  385. {
  386.   Frag& frag = dstNode.m_frag;
  387.   TreeHead& tree = frag.m_tree;
  388.   ndbrequire(i <= 1);
  389.   while (cnt != 0) {
  390.     TreeEnt ent;
  391.     Uint32 scanList = RNIL;
  392.     nodePopDown(srcNode, i == 0 ? srcNode.getOccup() - 1 : 0, ent, &scanList);
  393.     nodePushUp(dstNode, i == 0 ? 0 : dstNode.getOccup(), ent, scanList);
  394.     cnt--;
  395.   }
  396. }
  397. // scans linked to node
  398. /*
  399.  * Add list of scans to node at given position.
  400.  */
  401. void
  402. Dbtux::addScanList(NodeHandle& node, unsigned pos, Uint32 scanList)
  403. {
  404.   ScanOpPtr scanPtr;
  405.   scanPtr.i = scanList;
  406.   do {
  407.     jam();
  408.     c_scanOpPool.getPtr(scanPtr);
  409. #ifdef VM_TRACE
  410.       if (debugFlags & DebugScan) {
  411.         debugOut << "Add scan " << scanPtr.i << " " << *scanPtr.p << endl;
  412.         debugOut << "To pos=" << pos << " " << node << endl;
  413.       }
  414. #endif
  415.     const Uint32 nextPtrI = scanPtr.p->m_nodeScan;
  416.     scanPtr.p->m_nodeScan = RNIL;
  417.     linkScan(node, scanPtr);
  418.     TreePos& scanPos = scanPtr.p->m_scanPos;
  419.     // set position but leave direction alone
  420.     scanPos.m_loc = node.m_loc;
  421.     scanPos.m_pos = pos;
  422.     scanPtr.i = nextPtrI;
  423.   } while (scanPtr.i != RNIL);
  424. }
  425. /*
  426.  * Remove list of scans from node at given position.  The return
  427.  * location must point to existing list (in fact RNIL always).
  428.  */
  429. void
  430. Dbtux::removeScanList(NodeHandle& node, unsigned pos, Uint32& scanList)
  431. {
  432.   ScanOpPtr scanPtr;
  433.   scanPtr.i = node.getNodeScan();
  434.   do {
  435.     jam();
  436.     c_scanOpPool.getPtr(scanPtr);
  437.     const Uint32 nextPtrI = scanPtr.p->m_nodeScan;
  438.     TreePos& scanPos = scanPtr.p->m_scanPos;
  439.     ndbrequire(scanPos.m_loc == node.m_loc);
  440.     if (scanPos.m_pos == pos) {
  441.       jam();
  442. #ifdef VM_TRACE
  443.       if (debugFlags & DebugScan) {
  444.         debugOut << "Remove scan " << scanPtr.i << " " << *scanPtr.p << endl;
  445.         debugOut << "Fron pos=" << pos << " " << node << endl;
  446.       }
  447. #endif
  448.       unlinkScan(node, scanPtr);
  449.       scanPtr.p->m_nodeScan = scanList;
  450.       scanList = scanPtr.i;
  451.       // unset position but leave direction alone
  452.       scanPos.m_loc = NullTupLoc;
  453.       scanPos.m_pos = ZNIL;
  454.     }
  455.     scanPtr.i = nextPtrI;
  456.   } while (scanPtr.i != RNIL);
  457. }
  458. /*
  459.  * Move list of scans away from entry about to be removed.  Uses scan
  460.  * method scanNext().
  461.  */
  462. void
  463. Dbtux::moveScanList(NodeHandle& node, unsigned pos)
  464. {
  465.   ScanOpPtr scanPtr;
  466.   scanPtr.i = node.getNodeScan();
  467.   do {
  468.     jam();
  469.     c_scanOpPool.getPtr(scanPtr);
  470.     TreePos& scanPos = scanPtr.p->m_scanPos;
  471.     const Uint32 nextPtrI = scanPtr.p->m_nodeScan;
  472.     ndbrequire(scanPos.m_loc == node.m_loc);
  473.     if (scanPos.m_pos == pos) {
  474.       jam();
  475. #ifdef VM_TRACE
  476.       if (debugFlags & DebugScan) {
  477.         debugOut << "Move scan " << scanPtr.i << " " << *scanPtr.p << endl;
  478.         debugOut << "At pos=" << pos << " " << node << endl;
  479.       }
  480. #endif
  481.       scanNext(scanPtr);
  482.       ndbrequire(! (scanPos.m_loc == node.m_loc && scanPos.m_pos == pos));
  483.     }
  484.     scanPtr.i = nextPtrI;
  485.   } while (scanPtr.i != RNIL);
  486. }
  487. /*
  488.  * Link scan to the list under the node.  The list is single-linked and
  489.  * ordering does not matter.
  490.  */
  491. void
  492. Dbtux::linkScan(NodeHandle& node, ScanOpPtr scanPtr)
  493. {
  494. #ifdef VM_TRACE
  495.   if (debugFlags & DebugScan) {
  496.     debugOut << "Link scan " << scanPtr.i << " " << *scanPtr.p << endl;
  497.     debugOut << "To node " << node << endl;
  498.   }
  499. #endif
  500.   ndbrequire(! islinkScan(node, scanPtr) && scanPtr.p->m_nodeScan == RNIL);
  501.   scanPtr.p->m_nodeScan = node.getNodeScan();
  502.   node.setNodeScan(scanPtr.i);
  503. }
  504. /*
  505.  * Unlink a scan from the list under the node.
  506.  */
  507. void
  508. Dbtux::unlinkScan(NodeHandle& node, ScanOpPtr scanPtr)
  509. {
  510. #ifdef VM_TRACE
  511.   if (debugFlags & DebugScan) {
  512.     debugOut << "Unlink scan " << scanPtr.i << " " << *scanPtr.p << endl;
  513.     debugOut << "From node " << node << endl;
  514.   }
  515. #endif
  516.   ScanOpPtr currPtr;
  517.   currPtr.i = node.getNodeScan();
  518.   ScanOpPtr prevPtr;
  519.   prevPtr.i = RNIL;
  520.   while (true) {
  521.     jam();
  522.     c_scanOpPool.getPtr(currPtr);
  523.     Uint32 nextPtrI = currPtr.p->m_nodeScan;
  524.     if (currPtr.i == scanPtr.i) {
  525.       jam();
  526.       if (prevPtr.i == RNIL) {
  527.         node.setNodeScan(nextPtrI);
  528.       } else {
  529.         jam();
  530.         prevPtr.p->m_nodeScan = nextPtrI;
  531.       }
  532.       scanPtr.p->m_nodeScan = RNIL;
  533.       // check for duplicates
  534.       ndbrequire(! islinkScan(node, scanPtr));
  535.       return;
  536.     }
  537.     prevPtr = currPtr;
  538.     currPtr.i = nextPtrI;
  539.   }
  540. }
  541. /*
  542.  * Check if a scan is linked to this node.  Only for ndbrequire.
  543.  */
  544. bool
  545. Dbtux::islinkScan(NodeHandle& node, ScanOpPtr scanPtr)
  546. {
  547.   ScanOpPtr currPtr;
  548.   currPtr.i = node.getNodeScan();
  549.   while (currPtr.i != RNIL) {
  550.     jam();
  551.     c_scanOpPool.getPtr(currPtr);
  552.     if (currPtr.i == scanPtr.i) {
  553.       jam();
  554.       return true;
  555.     }
  556.     currPtr.i = currPtr.p->m_nodeScan;
  557.   }
  558.   return false;
  559. }
  560. void
  561. Dbtux::NodeHandle::progError(int line, int cause, const char* file)
  562. {
  563.   ErrorReporter::handleAssert("Dbtux::NodeHandle: assert failed", file, line);
  564. }