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#4163 | Pekka Nousiainen | 25 Apr |
