List:Commits« Previous MessageNext Message »
From:Pekka Nousiainen Date:April 25 2011 2:52pm
Subject:bzr push into mysql-5.1-telco-7.0-wl4163 branch (pekka:4337 to 4340) WL#4163
View as plain text  
 4340 Pekka Nousiainen	2011-04-25
      wl#4163 c04_ops.diff
      search-within-node in search-to-update

    modified:
      storage/ndb/src/kernel/blocks/dbtux/Dbtux.hpp
      storage/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp
 4339 Pekka Nousiainen	2011-04-25
      wl#4163 c03_ops.diff
      search-down-tree for seach-to-update

    modified:
      storage/ndb/src/kernel/blocks/dbtux/Dbtux.hpp
      storage/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp
 4338 Pekka Nousiainen	2011-04-25
      wl#4163 c02_ops.diff
      add ctx arg to search-to-remove

    modified:
      storage/ndb/src/kernel/blocks/dbtux/Dbtux.hpp
      storage/ndb/src/kernel/blocks/dbtux/DbtuxMaint.cpp
      storage/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp
 4337 Pekka Nousiainen	2011-04-25
      wl#4163 c01_ops.diff
      remove use of bottom node in search-to-add

    modified:
      storage/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp
=== modified file 'storage/ndb/src/kernel/blocks/dbtux/Dbtux.hpp'
--- a/storage/ndb/src/kernel/blocks/dbtux/Dbtux.hpp	2011-04-24 16:20:23 +0000
+++ b/storage/ndb/src/kernel/blocks/dbtux/Dbtux.hpp	2011-04-25 14:50:33 +0000
@@ -657,8 +657,11 @@ private:
   /*
    * DbtuxSearch.cpp
    */
+  void findNodeToUpdate(TuxCtx&, Frag& frag, ConstData searchKey, TreeEnt searchEnt, NodeHandle& currNode);
+  bool findPosToAdd(TuxCtx&, Frag& frag, ConstData searchKey, TreeEnt searchEnt, NodeHandle& currNode, TreePos& treePos);
+  bool findPosToRemove(TuxCtx&, Frag& frag, ConstData searchKey, TreeEnt searchEnt, NodeHandle& currNode, TreePos& treePos);
   bool searchToAdd(TuxCtx&, Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos);
-  bool searchToRemove(Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos);
+  bool searchToRemove(TuxCtx&, Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos);
   void searchToScan(Frag& frag, ConstData boundInfo, unsigned boundCount, bool descending, TreePos& treePos);
   void searchToScanAscending(Frag& frag, ConstData boundInfo, unsigned boundCount, TreePos& treePos);
   void searchToScanDescending(Frag& frag, ConstData boundInfo, unsigned boundCount, TreePos& treePos);

=== modified file 'storage/ndb/src/kernel/blocks/dbtux/DbtuxMaint.cpp'
--- a/storage/ndb/src/kernel/blocks/dbtux/DbtuxMaint.cpp	2011-04-24 13:10:50 +0000
+++ b/storage/ndb/src/kernel/blocks/dbtux/DbtuxMaint.cpp	2011-04-25 14:42:38 +0000
@@ -144,7 +144,7 @@ Dbtux::execTUX_MAINT_REQ(Signal* signal)
     break;
   case TuxMaintReq::OpRemove:
     jam();
-    ok = searchToRemove(frag, c_ctx.c_searchKey, ent, treePos);
+    ok = searchToRemove(c_ctx, frag, c_ctx.c_searchKey, ent, treePos);
 #ifdef VM_TRACE
     if (debugFlags & DebugMaint) {
       debugOut << treePos << (! ok ? " - error" : "") << endl;

=== modified file 'storage/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp'
--- a/storage/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp	2011-04-25 14:15:19 +0000
+++ b/storage/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp	2011-04-25 14:50:33 +0000
@@ -20,22 +20,22 @@
 #include "Dbtux.hpp"
 
 /*
- * Search for entry to add.
+ * Search down non-empty tree for node to update.  Compare search key to
+ * each node minimum.  If greater, move to right subtree.  This can
+ * overshoot target node.  The last such node is saved.  The search ends
+ * at a final node which is a semi-leaf or leaf.  If search key is less
+ * than final node minimum then the saved node (if any) is the g.l.b of
+ * the final node and we move back to it.
  *
- * Similar to searchToRemove (see below).
+ * Search within the found node is done by caller.  On add, search key
+ * may be before minimum or after maximum entry.  On remove, search key
+ * is within the node.
  */
-bool
-Dbtux::searchToAdd(TuxCtx& ctx, Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos)
+void
+Dbtux::findNodeToUpdate(TuxCtx& ctx, Frag& frag, ConstData searchKey, TreeEnt searchEnt, NodeHandle& currNode)
 {
   const TreeHead& tree = frag.m_tree;
-  const unsigned numAttrs = frag.m_numAttrs;
-  NodeHandle currNode(frag);
-  currNode.m_loc = tree.m_root;
-  if (currNode.m_loc == NullTupLoc) {
-    // empty tree
-    thrjam(ctx.jamBuffer);
-    return true;
-  }
+  const Uint32 numAttrs = frag.m_numAttrs;
   NodeHandle glbNode(frag);     // potential g.l.b of final node
   while (true) {
     thrjam(ctx.jamBuffer);
@@ -71,7 +71,9 @@ Dbtux::searchToAdd(TuxCtx& ctx, Frag& fr
         // move up to the g.l.b
         currNode = glbNode;
       }
-    } else if (ret > 0) {
+      break;
+    }
+    if (ret > 0) {
       thrjam(ctx.jamBuffer);
       const TupLoc loc = currNode.getLink(1);
       if (loc != NullTupLoc) {
@@ -82,26 +84,28 @@ Dbtux::searchToAdd(TuxCtx& ctx, Frag& fr
         currNode.m_loc = loc;
         continue;
       }
-    } else {
-      thrjam(ctx.jamBuffer);
-      treePos.m_loc = currNode.m_loc;
-      treePos.m_pos = 0;
-      // entry found - error
-      return false;
+      break;
     }
+    // ret == 0
+    thrjam(ctx.jamBuffer);
     break;
   }
-  // anticipate
-  treePos.m_loc = currNode.m_loc;
-  // binary search
+}
+
+/*
+ * Find position within the final node to add entry to.  Use binary
+ * search.  Return true if ok i.e. entry to add is not a duplicate.
+ */
+bool
+Dbtux::findPosToAdd(TuxCtx& ctx, Frag& frag, ConstData searchKey, TreeEnt searchEnt, NodeHandle& currNode, TreePos& treePos)
+{
   int lo = -1;
-  int hi = currNode.getOccup();
+  int hi = (int)currNode.getOccup();
   int ret;
-  while (1) {
+  while (hi - lo > 1) {
     thrjam(ctx.jamBuffer);
     // hi - lo > 1 implies lo < j < hi
     int j = (hi + lo) / 2;
-
     // read and compare attributes
     unsigned start = 0;
     readKeyAttrs(ctx, frag, currNode.getEnt(j), start, ctx.c_entryKey);
@@ -112,112 +116,90 @@ Dbtux::searchToAdd(TuxCtx& ctx, Frag& fr
       // keys are equal, compare entry values
       ret = searchEnt.cmp(currNode.getEnt(j));
     }
-    if (ret < 0)
+    if (ret < 0) {
+      thrjam(ctx.jamBuffer);
       hi = j;
-    else if (ret > 0)
+    } else if (ret > 0) {
+      thrjam(ctx.jamBuffer);
       lo = j;
-    else {
+    } else {
       treePos.m_pos = j;
       // entry found - error
       return false;
     }
-    if (hi - lo == 1)
-      break;
   }
+  ndbrequire(hi - lo == 1);
+  // return hi pos, see treeAdd() for next step
   treePos.m_pos = hi;
   return true;
 }
 
 /*
+ * Find position within the final node to remove entry from.  Use linear
+ * search.  Return true if ok i.e. the entry was found.
+ */
+bool
+Dbtux::findPosToRemove(TuxCtx& ctx, Frag& frag, ConstData searchKey, TreeEnt searchEnt, NodeHandle& currNode, TreePos& treePos)
+{
+  const unsigned occup = currNode.getOccup();
+  for (unsigned j = 0; j < occup; j++) {
+    thrjam(ctx.jamBuffer);
+    // compare only the entry
+    if (searchEnt.eq(currNode.getEnt(j))) {
+      thrjam(ctx.jamBuffer);
+      treePos.m_pos = j;
+      return true;
+    }
+  }
+  treePos.m_pos = occup;
+  // not found - failed
+  return false;
+}
+
+/*
+ * Search for entry to add.
+ */
+bool
+Dbtux::searchToAdd(TuxCtx& ctx, Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos)
+{
+  const TreeHead& tree = frag.m_tree;
+  NodeHandle currNode(frag);
+  currNode.m_loc = tree.m_root;
+  if (unlikely(currNode.m_loc == NullTupLoc)) {
+    // empty tree
+    thrjam(ctx.jamBuffer);
+    return true;
+  }
+  findNodeToUpdate(ctx, frag, searchKey, searchEnt, currNode);
+  treePos.m_loc = currNode.m_loc;
+  if (! findPosToAdd(ctx, frag, searchKey, searchEnt, currNode, treePos)) {
+    thrjam(ctx.jamBuffer);
+    return false;
+  }
+  return true;
+}
+
+/*
  * Search for entry to remove.
- *
- * Compares search key to each node min.  A move to right subtree can
- * overshoot target node.  The last such node is saved.  The final node
- * is a semi-leaf or leaf.  If search key is less than final node min
- * then the saved node is the g.l.b of the final node and we move back
- * to it.
  */
 bool
-Dbtux::searchToRemove(Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos)
+Dbtux::searchToRemove(TuxCtx& ctx, Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos)
 {
   const TreeHead& tree = frag.m_tree;
-  const unsigned numAttrs = frag.m_numAttrs;
   NodeHandle currNode(frag);
   currNode.m_loc = tree.m_root;
-  if (currNode.m_loc == NullTupLoc) {
+  if (unlikely(currNode.m_loc == NullTupLoc)) {
     // empty tree - failed
-    jam();
+    thrjam(ctx.jamBuffer);
     return false;
   }
-  NodeHandle glbNode(frag);     // potential g.l.b of final node
-  while (true) {
-    jam();
-    selectNode(currNode, currNode.m_loc);
-    int ret;
-    // compare prefix
-    unsigned start = 0;
-    ret = cmpSearchKey(c_ctx, frag, start, searchKey, currNode.getPref(), tree.m_prefSize);
-    if (ret == NdbSqlUtil::CmpUnknown) {
-      jam();
-      // read and compare remaining attributes
-      ndbrequire(start < numAttrs);
-      readKeyAttrs(c_ctx, frag, currNode.getEnt(0), start, c_ctx.c_entryKey);
-      ret = cmpSearchKey(c_ctx, frag, start, searchKey, c_ctx.c_entryKey);
-      ndbrequire(ret != NdbSqlUtil::CmpUnknown);
-    }
-    if (ret == 0) {
-      jam();
-      // keys are equal, compare entry values
-      ret = searchEnt.cmp(currNode.getEnt(0));
-    }
-    if (ret < 0) {
-      jam();
-      const TupLoc loc = currNode.getLink(0);
-      if (loc != NullTupLoc) {
-        jam();
-        // continue to left subtree
-        currNode.m_loc = loc;
-        continue;
-      }
-      if (! glbNode.isNull()) {
-        jam();
-        // move up to the g.l.b
-        currNode = glbNode;
-      }
-    } else if (ret > 0) {
-      jam();
-      const TupLoc loc = currNode.getLink(1);
-      if (loc != NullTupLoc) {
-        jam();
-        // save potential g.l.b
-        glbNode = currNode;
-        // continue to right subtree
-        currNode.m_loc = loc;
-        continue;
-      }
-    } else {
-      jam();
-      treePos.m_loc = currNode.m_loc;
-      treePos.m_pos = 0;
-      return true;
-    }
-    break;
-  }
-  // anticipate
+  findNodeToUpdate(ctx, frag, searchKey, searchEnt, currNode);
   treePos.m_loc = currNode.m_loc;
-  // pos 0 was handled above
-  for (unsigned j = 1, occup = currNode.getOccup(); j < occup; j++) {
-    jam();
-    // compare only the entry
-    if (searchEnt.eq(currNode.getEnt(j))) {
-      jam();
-      treePos.m_pos = j;
-      return true;
-    }
+  if (! findPosToRemove(ctx, frag, searchKey, searchEnt, currNode, treePos)) {
+    thrjam(ctx.jamBuffer);
+    return false;
   }
-  treePos.m_pos = currNode.getOccup();
-  // not found - failed
-  return false;
+  return true;
 }
 
 /*

No bundle (reason: useless for push emails).
Thread
bzr push into mysql-5.1-telco-7.0-wl4163 branch (pekka:4337 to 4340) WL#4163Pekka Nousiainen25 Apr