BTreeVerifier Class Reference

BTreeVerifier checks BTree integrity. More...

#include <BTreeVerifier.h>

Inheritance diagram for BTreeVerifier:

BTreeAccessBase List of all members.

Public Member Functions

 BTreeVerifier (BTreeDescriptor const &)
virtual ~BTreeVerifier ()
void verify (bool strict=true, bool keys=true, bool leaf=true)
 Performs verification over the entire tree.
BTreeStatistics const & getStatistics ()
 Gets statistics collected during the previous verification.
SharedSegment getSegment () const
 
Returns:
the segment storing the BTree being accessed

SharedCacheAccessor getCacheAccessor () const
 
Returns:
the CacheAccessor used to access the BTree's pages

PageId getRootPageId () const
 
Returns:
the BTree's root PageId

void setRootPageId (PageId rootPageId)
 Updates the BTree's root PageId.
SegmentId getSegmentId () const
 
Returns:
SegmentId of segment storing the BTree

PageOwnerId getPageOwnerId () const
 
Returns:
PageOwnerId used to mark pages of the BTree

TupleDescriptor const & getTupleDescriptor () const
 
Returns:
TupleDescriptor for tuples stored by this BTree

TupleDescriptor const & getKeyDescriptor () const
 
Returns:
TupleDescriptor for keys indexed by this BTree

TupleProjection const & getKeyProjection () const
 
Returns:
TupleProjection from getTupleDescriptor() to getKeyDescriptor()

void validateTupleSize (TupleAccessor const &tupleAccessor)
 Validates that a particular tuple can fit in this BTree, throwing a TupleOverflowExcn if not.

Protected Member Functions

BTreeNodeAccessor & getLeafNodeAccessor (BTreeNode const &node)
 Gets the node accessor for a leaf node, asserting that the node really is a leaf.
BTreeNodeAccessor & getNonLeafNodeAccessor (BTreeNode const &node)
 Gets the node accessor for a non-leaf node, asserting that the node really is a non-leaf.
BTreeNodeAccessor & getNodeAccessor (BTreeNode const &node)
 Gets the node accessor for any node, using the node height to determine whether it's a leaf or not.
PageId getChildForCurrent ()
 Gets the child PageId corresponding to the current key in a non-leaf node.
PageId getChild (BTreeNode const &node, uint iChild)
 Accesses a non-leaf tuple and gets its child PageId.
PageId getRightSibling (PageId pageId)
 Gets the right sibling of a node by consulting the containing segment's successor information.
void setRightSibling (BTreeNode &leftNode, PageId leftPageId, PageId rightPageId)
 Sets the right sibling of a node.
PageId getFirstChild (PageId pageId)
 Gets the first child of a non-leaf node.

Protected Attributes

BTreeDescriptor treeDescriptor
 Descriptor for tree being accessed.
TupleDescriptor keyDescriptor
 Descriptor for pure keys (common across leaf and non-leaf tuples).
AttributeAccessor const * pChildAccessor
 Accessor for the attribute of non-leaf tuples which stores the child PageId.
TupleProjectionAccessor leafKeyAccessor
 Accessor for keys of tuples stored in leaves.
boost::scoped_ptr< BTreeNodeAccessor > pNonLeafNodeAccessor
 Accessor for non-leaf nodes.
boost::scoped_ptr< BTreeNodeAccessor > pLeafNodeAccessor
 Accessor for leaf nodes.
uint cbTupleMax
 Maximum size for a leaf-level tuple.

Private Member Functions

PageId verifyNode (PageId pageId)
 Verifies one node.
void verifyChildren (BTreeNode const &node)
 Verifies all of the children of a non-leaf node.

Private Attributes

TupleData lowerBoundKey
 Key data used for verifying that all keys in a node are greater than or equal to an expected lower bound.
TupleData upperBoundKey
 Key data used for verifying that all keys in a node are less than or equal to an expected upper bound.
uint expectedHeight
 Expected height for node about to be verified.
PageId expectedRightSibling
 Expected right sibling for node about to be verified.
BTreeStatistics stats
 Statistics being gather during verification.
bool strict
 Whether to be strict during verification.
bool keys
 Whether to perform key verification.
bool leaf
 Whether to traverse the leaf level.
TupleData keyData
 Key data used for comparing successive keys.
TupleData keyData2
 Key data used for comparing successive keys.

Detailed Description

BTreeVerifier checks BTree integrity.

Definition at line 67 of file BTreeVerifier.h.

Constructor & Destructor Documentation

BTreeVerifier::BTreeVerifier ( BTreeDescriptor const &   )  [explicit]

Definition at line 32 of file BTreeVerifier.cpp.

References TupleData::compute(), BTreeAccessBase::getRootPageId(), keyData, keyData2, BTreeAccessBase::keyDescriptor, and NULL_PAGE_ID.

00033     : BTreeAccessBase(descriptor)
00034 {
00035     permAssert(getRootPageId() != NULL_PAGE_ID);
00036     keyData.compute(keyDescriptor);
00037     keyData2 = keyData;
00038 }

BTreeVerifier::~BTreeVerifier (  )  [virtual]

Definition at line 40 of file BTreeVerifier.cpp.

00041 {
00042 }

Member Function Documentation

PageId BTreeVerifier::verifyNode ( PageId  pageId  )  [private]

Verifies one node.

Various expected values should already have been set up when this is called.

Parameters:
pageId PageId of node to verify
Returns:
PageId of additional nodes to check with same parameters (only for non-strict checks; for strict checks, will always be NULL_PAGE_ID)

Definition at line 70 of file BTreeVerifier.cpp.

References SegPageLock::accessSegment(), BTreeNodeAccessor::accessTuple(), TupleDescriptor::compareTuples(), BTreeNodeAccessor::dumpNode(), expectedHeight, expectedRightSibling, BTreeNodeAccessor::getKeyCount(), BTreeAccessBase::getNodeAccessor(), SegNodeLock< Node >::getNodeForRead(), BTreeAccessBase::getRightSibling(), BTreeNode::height, isMAXU(), keyData, keyData2, BTreeAccessBase::keyDescriptor, keys, SegPageLock::lockShared(), lowerBoundKey, BTreeNode::MAGIC_NUMBER, StoredNode::magicNumber, BTreeNode::nEntries, BTreeStatistics::nLeafNodes, BTreeStatistics::nLevels, BTreeStatistics::nNonLeafNodes, BTreeStatistics::nTuples, NULL_PAGE_ID, BTreeStatistics::nUniqueKeys, BTreeNode::rightSibling, BTreeDescriptor::segmentAccessor, stats, strict, BTreeAccessBase::treeDescriptor, BTreeNodeAccessor::unmarshalKey(), upperBoundKey, and verifyChildren().

Referenced by verify(), and verifyChildren().

00072 {
00073     BTreePageLock pageLock;
00074     pageLock.accessSegment(treeDescriptor.segmentAccessor);
00075     pageLock.lockShared(pageId);
00076     BTreeNode const &node = pageLock.getNodeForRead();
00077     PageId returnPageId = NULL_PAGE_ID;
00078 
00079     // for optimized build, we don't check node magic numbers implicitly,
00080     // so do it explicitly here
00081     permAssert(node.magicNumber == BTreeNode::MAGIC_NUMBER);
00082 
00083     if (isMAXU(expectedHeight)) {
00084         stats.nLevels = node.height + 1;
00085     } else {
00086         permAssert(node.height == expectedHeight);
00087     }
00088 
00089     if (strict) {
00090         permAssert(node.rightSibling == getRightSibling(pageId));
00091         permAssert(node.rightSibling == expectedRightSibling);
00092     } else {
00093         if (node.rightSibling != expectedRightSibling) {
00094             permAssert(node.rightSibling != NULL_PAGE_ID);
00095             returnPageId = node.rightSibling;
00096         }
00097     }
00098 
00099     BTreeNodeAccessor &nodeAccessor = getNodeAccessor(node);
00100 
00101     // TODO:  delegate to nodeAccessor for checking node integrity
00102 
00103     // verify key ordering, including lower bound
00104     if (keys) {
00105         bool countUniqueKeys = (node.height == 0);
00106         keyData = lowerBoundKey;
00107         uint nKeys = nodeAccessor.getKeyCount(node);
00108         for (uint i = 0; i < nKeys; ++i) {
00109             nodeAccessor.accessTuple(node,i);
00110             nodeAccessor.unmarshalKey(keyData2);
00111             if (keyData.size()) {
00112                 int c = keyDescriptor.compareTuples(keyData,keyData2);
00113 
00114                 // TODO:  move this somewhere else
00115                 if (c > 0) {
00116                     nodeAccessor.dumpNode(std::cerr,node,pageId);
00117                 }
00118                 permAssert(c <= 0);
00119                 // TODO:  for unique, assert(c == 0)
00120 
00121                 if (countUniqueKeys && c == -1) {
00122                     // Only count differences in the first column of the key.
00123                     stats.nUniqueKeys++;
00124                 }
00125             } else if (countUniqueKeys) {
00126                 stats.nUniqueKeys++;
00127             }
00128             keyData = keyData2;
00129         }
00130     }
00131 
00132     // verify upper bound (using last key left over from previous loop)
00133     if (keyData.size() && upperBoundKey.size()) {
00134         keyData2 = upperBoundKey;
00135         int c = keyDescriptor.compareTuples(keyData,keyData2);
00136         permAssert(c <= 0);
00137     }
00138     if (node.height) {
00139         stats.nNonLeafNodes++;
00140         verifyChildren(node);
00141     } else {
00142         stats.nLeafNodes++;
00143         stats.nTuples += node.nEntries;
00144     }
00145     return returnPageId;
00146 }

void BTreeVerifier::verifyChildren ( BTreeNode const &  node  )  [private]

Verifies all of the children of a non-leaf node.

Parameters:
node the non-leaf node to be verified

Definition at line 148 of file BTreeVerifier.cpp.

References BTreeNodeAccessor::accessTuple(), expectedHeight, expectedRightSibling, BTreeAccessBase::getChild(), BTreeAccessBase::getFirstChild(), BTreeAccessBase::getNodeAccessor(), BTreeNode::height, keyData, leaf, lowerBoundKey, BTreeNode::nEntries, BTreeStatistics::nLeafNodes, NULL_PAGE_ID, BTreeNode::rightSibling, stats, BTreeNodeAccessor::unmarshalKey(), upperBoundKey, and verifyNode().

Referenced by verifyNode().

00149 {
00150     // skip over leaf nodes if we are not traversing them
00151     if (node.height == 1 && !leaf) {
00152         stats.nLeafNodes += node.nEntries;
00153         return;
00154     }
00155 
00156     BTreeNodeAccessor &nodeAccessor = getNodeAccessor(node);
00157     for (uint i = 0; i < node.nEntries; ++i) {
00158         PageId nextChildPageId;
00159         if (i + 1 < node.nEntries) {
00160             nextChildPageId = getChild(node,i + 1);
00161         } else {
00162             nextChildPageId = getFirstChild(node.rightSibling);
00163         }
00164         PageId childPageId = getChild(node,i);
00165         do {
00166             expectedRightSibling = nextChildPageId;
00167             expectedHeight = node.height - 1;
00168             nodeAccessor.accessTuple(node,i);
00169             nodeAccessor.unmarshalKey(keyData);
00170             if (nextChildPageId == NULL_PAGE_ID) {
00171                 // pretend last key is +infinity
00172                 upperBoundKey.clear();
00173             } else {
00174                 upperBoundKey = keyData;
00175             }
00176             childPageId = verifyNode(childPageId);
00177         } while (childPageId != NULL_PAGE_ID);
00178         nodeAccessor.accessTuple(node,i);
00179         nodeAccessor.unmarshalKey(keyData);
00180         lowerBoundKey = keyData;
00181     }
00182 }

void BTreeVerifier::verify ( bool  strict = true,
bool  keys = true,
bool  leaf = true 
)

Performs verification over the entire tree.

Parameters:
strict if true, the tree is assumed to be in a quiescent state with all update operations completed; if false, violations which are possible with incomplete update operations are ignored
keys whether to verify key ordering (and count unique keys)
leaf whether to traverse the leaf level

Definition at line 44 of file BTreeVerifier.cpp.

References expectedHeight, expectedRightSibling, BTreeAccessBase::getRootPageId(), isMAXU(), keys, leaf, lowerBoundKey, MAXU, BTreeStatistics::nLeafNodes, BTreeStatistics::nLevels, BTreeStatistics::nNonLeafNodes, BTreeStatistics::nTuples, NULL_PAGE_ID, BTreeStatistics::nUniqueKeys, stats, strict, upperBoundKey, and verifyNode().

Referenced by BTreeTxnTest::verifyTree(), BTreeTest::verifyTree(), and CmdInterpreter::visit().

00045 {
00046     strict = strictInit;
00047     keys = keysInit;
00048     leaf = leafInit;
00049     lowerBoundKey.clear();
00050     upperBoundKey.clear();
00051     stats.nLevels = MAXU;
00052     stats.nNonLeafNodes = 0;
00053     stats.nLeafNodes = 0;
00054     stats.nTuples = 0;
00055     stats.nUniqueKeys = 0;
00056     PageId pageId = getRootPageId();
00057     do {
00058         expectedRightSibling = NULL_PAGE_ID;
00059         if (isMAXU(stats.nLevels)) {
00060             expectedHeight = MAXU;
00061         } else {
00062             expectedHeight = stats.nLevels - 1;
00063         }
00064         pageId = verifyNode(pageId);
00065     } while (pageId != NULL_PAGE_ID);
00066 }

BTreeStatistics const & BTreeVerifier::getStatistics (  ) 

Gets statistics collected during the previous verification.

This is only valid after verify is called, and is overwritten by each verify call, so copy as needed.

Returns:
collected statistics

Definition at line 184 of file BTreeVerifier.cpp.

References stats.

Referenced by BTreeTxnTest::verifyTree(), BTreeTest::verifyTree(), and CmdInterpreter::visit().

00185 {
00186     return stats;
00187 }

FENNEL_BEGIN_NAMESPACE BTreeNodeAccessor & BTreeAccessBase::getLeafNodeAccessor ( BTreeNode const &  node  )  [inline, protected, inherited]

Gets the node accessor for a leaf node, asserting that the node really is a leaf.

Parameters:
node leaf node to access
Returns:
node accessor

Definition at line 32 of file BTreeAccessBaseImpl.h.

References BTreeNode::height, and BTreeAccessBase::pLeafNodeAccessor.

Referenced by BTreeReader::accessLeafTuple(), BTreeWriter::deleteCurrent(), and BTreeWriter::updateCurrent().

00034 {
00035     assert(!node.height);
00036     return *pLeafNodeAccessor;
00037 }

BTreeNodeAccessor & BTreeAccessBase::getNonLeafNodeAccessor ( BTreeNode const &  node  )  [inline, protected, inherited]

Gets the node accessor for a non-leaf node, asserting that the node really is a non-leaf.

Parameters:
node non-leaf node to access
Returns:
node accessor

Definition at line 39 of file BTreeAccessBaseImpl.h.

References BTreeNode::height, and BTreeAccessBase::pNonLeafNodeAccessor.

Referenced by BTreeAccessBase::getChild(), and BTreeWriter::grow().

00041 {
00042     assert(node.height);
00043     return *pNonLeafNodeAccessor;
00044 }

BTreeNodeAccessor & BTreeAccessBase::getNodeAccessor ( BTreeNode const &  node  )  [inline, protected, inherited]

Gets the node accessor for any node, using the node height to determine whether it's a leaf or not.

If you already know this from the context, call getLeafNodeAccessor or getNonLeafNodeAccessor instead.

Parameters:
node node to access
Returns:
node accessor

Definition at line 46 of file BTreeAccessBaseImpl.h.

References BTreeNode::height, BTreeAccessBase::pLeafNodeAccessor, and BTreeAccessBase::pNonLeafNodeAccessor.

Referenced by BTreeReader::accessTupleInline(), BTreeWriter::attemptInsertWithoutSplit(), BTreeReader::binarySearch(), BTreeWriter::compactNode(), BTreeReader::compareFirstKey(), BTreeWriter::grow(), BTreeWriter::lockParentPage(), BTreeWriter::splitCurrentNode(), verifyChildren(), and verifyNode().

00048 {
00049     if (node.height) {
00050         return *pNonLeafNodeAccessor;
00051     } else {
00052         return *pLeafNodeAccessor;
00053     }
00054 }

PageId BTreeAccessBase::getChildForCurrent (  )  [inline, protected, inherited]

Gets the child PageId corresponding to the current key in a non-leaf node.

Assumes that accessTuple has already been called on pNonLeafNodeAccessor (but can't assert this), so use with caution.

Returns:
child PageId

Reimplemented in BTreeNonLeafReader.

Definition at line 56 of file BTreeAccessBaseImpl.h.

References BTreeAccessBase::pChildAccessor, TupleDatum::pData, BTreeAccessBase::pNonLeafNodeAccessor, and AttributeAccessor::unmarshalValue().

Referenced by BTreeAccessBase::getChild(), BTreeNonLeafReader::getChildForCurrent(), and BTreeReader::searchForKeyTemplate().

00057 {
00058     TupleDatum &childDatum = pNonLeafNodeAccessor->tupleData.back();
00059     pChildAccessor->unmarshalValue(
00060         pNonLeafNodeAccessor->tupleAccessor,childDatum);
00061     return *reinterpret_cast<PageId const *>(childDatum.pData);
00062 }

PageId BTreeAccessBase::getChild ( BTreeNode const &  node,
uint  iChild 
) [inline, protected, inherited]

Accesses a non-leaf tuple and gets its child PageId.

Parameters:
node non-leaf node to access
iChild 0-based index of tuple to access
Returns:
child PageId of accessed tuple

Definition at line 64 of file BTreeAccessBaseImpl.h.

References BTreeNodeAccessor::accessTuple(), BTreeAccessBase::getChildForCurrent(), and BTreeAccessBase::getNonLeafNodeAccessor().

Referenced by BTreeAccessBase::getFirstChild(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKeyTemplate(), BTreeBuilder::truncateChildren(), and verifyChildren().

00065 {
00066     getNonLeafNodeAccessor(node).accessTuple(node,iChild);
00067     return getChildForCurrent();
00068 }

PageId BTreeAccessBase::getRightSibling ( PageId  pageId  )  [inline, protected, inherited]

Gets the right sibling of a node by consulting the containing segment's successor information.

Should only be used when the node is not already locked (e.g. during prefetch). When the node is already locked, its rightSibling field should be accessed instead.

Parameters:
pageId PageId of node whose sibling is to be found
Returns:
PageId of right sibling

Definition at line 70 of file BTreeAccessBaseImpl.h.

References BTreeAccessBase::getSegment().

Referenced by BTreeBuilder::truncateChildren(), and verifyNode().

00071 {
00072     return getSegment()->getPageSuccessor(pageId);
00073 }

void BTreeAccessBase::setRightSibling ( BTreeNode &  leftNode,
PageId  leftPageId,
PageId  rightPageId 
) [inline, protected, inherited]

Sets the right sibling of a node.

Parameters:
leftNode node whose right sibling is to be set
leftPageId PageId corresponding to leftNode
rightPageId PageId of new right sibling

Definition at line 75 of file BTreeAccessBaseImpl.h.

References BTreeAccessBase::getSegment(), and BTreeNode::rightSibling.

Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), and BTreeWriter::splitCurrentNode().

00077 {
00078     getSegment()->setPageSuccessor(leftPageId,rightPageId);
00079     leftNode.rightSibling = rightPageId;
00080 }

PageId BTreeAccessBase::getFirstChild ( PageId  pageId  )  [protected, inherited]

Gets the first child of a non-leaf node.

Parameters:
pageId PageId of non-leaf node
Returns:
PageId of node's first child

Definition at line 126 of file BTreeAccessBase.cpp.

References BTreeAccessBase::getChild(), SegNodeLock< Node >::getNodeForRead(), BTreeNode::height, SegPageLock::lockShared(), BTreeNode::nEntries, NULL_PAGE_ID, BTreeNode::rightSibling, BTreeDescriptor::segmentAccessor, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeReader::searchForKeyTemplate(), and verifyChildren().

00127 {
00128     BTreePageLock pageLock(treeDescriptor.segmentAccessor);
00129     while (parentPageId != NULL_PAGE_ID) {
00130         pageLock.lockShared(parentPageId);
00131         BTreeNode const &node = pageLock.getNodeForRead();
00132         assert(node.height);
00133         if (node.nEntries) {
00134             return getChild(node,0);
00135         }
00136         parentPageId = node.rightSibling;
00137     }
00138     return NULL_PAGE_ID;
00139 }

SharedSegment BTreeAccessBase::getSegment (  )  const [inline, inherited]

Returns:
the segment storing the BTree being accessed

Definition at line 234 of file BTreeAccessBase.h.

References SegmentAccessor::pSegment, BTreeDescriptor::segmentAccessor, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeBuildLevel::allocatePage(), BTreeAccessBase::BTreeAccessBase(), BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), BTreeBuilder::buildUnbalanced(), BTreeWriter::compactNode(), BTreeBuilder::createEmptyRoot(), BTreeAccessBase::getRightSibling(), BTreeWriter::grow(), BTreeAccessBase::setRightSibling(), BTreeWriter::splitCurrentNode(), and BTreeBuilder::truncate().

00235 {
00236     return treeDescriptor.segmentAccessor.pSegment;
00237 }

SharedCacheAccessor BTreeAccessBase::getCacheAccessor (  )  const [inline, inherited]

Returns:
the CacheAccessor used to access the BTree's pages

Definition at line 239 of file BTreeAccessBase.h.

References SegmentAccessor::pCacheAccessor, BTreeDescriptor::segmentAccessor, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), VariableBuildLevel::getParentKeyStream(), and VariableBuildLevel::VariableBuildLevel().

00240 {
00241     return treeDescriptor.segmentAccessor.pCacheAccessor;
00242 }

PageId BTreeAccessBase::getRootPageId (  )  const [inline, inherited]

Returns:
the BTree's root PageId

Definition at line 244 of file BTreeAccessBase.h.

References BTreeDescriptor::rootPageId, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeVerifier(), BTreeBuilder::buildBalanced(), BTreeInsertExecStream::buildTree(), LbmSplicerExecStreamTest::createBTree(), BTreeBuilder::createEmptyRoot(), BTreeWriter::describeParticipant(), LcsClusterReplaceExecStream::getTupleForLoad(), LbmSplicerExecStream::getValidatedTuple(), BTreeNonLeafReader::isRootOnly(), LcsClusterReplaceExecStreamTest::loadCluster(), LcsMultiClusterAppendTest::loadClusters(), LcsRowScanExecStreamTest::loadOneCluster(), LbmSearchTest::loadTableAndIndex(), BTreeWriter::lockParentPage(), BTreeWriter::optimizeRootLockMode(), BTreeWriter::positionSearchKey(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKey(), BTreeNonLeafReader::searchForKey(), BTreeBuilder::swapRoot(), ExecStreamTestSuite::testBTreeInsertExecStream(), BTreeTest::testBulkLoad(), BTreeTest::testInserts(), LbmLoadBitmapTest::testLoad(), LcsClusterAppendExecStreamTest::testLoadMultiCol(), LcsClusterAppendExecStreamTest::testLoadSingleCol(), BTreeTest::testMultiKeySearches(), BTreeReadersTest::testReaders(), BTreeReadersTest::testScan(), LcsRowScanExecStreamTest::testScanOnEmptyCluster(), BTreeReadersTest::testSearch(), BTreeBuilder::truncate(), verify(), and CmdInterpreter::visit().

00245 {
00246     return treeDescriptor.rootPageId;
00247 }

void BTreeAccessBase::setRootPageId ( PageId  rootPageId  )  [inherited]

Updates the BTree's root PageId.

Definition at line 141 of file BTreeAccessBase.cpp.

References BTreeDescriptor::rootPageId, and BTreeAccessBase::treeDescriptor.

00142 {
00143     treeDescriptor.rootPageId = rootPageId;
00144 }

SegmentId BTreeAccessBase::getSegmentId (  )  const [inline, inherited]

Returns:
SegmentId of segment storing the BTree

Definition at line 249 of file BTreeAccessBase.h.

References BTreeDescriptor::segmentId, and BTreeAccessBase::treeDescriptor.

00250 {
00251     return treeDescriptor.segmentId;
00252 }

PageOwnerId BTreeAccessBase::getPageOwnerId (  )  const [inline, inherited]

Returns:
PageOwnerId used to mark pages of the BTree

Definition at line 254 of file BTreeAccessBase.h.

References BTreeDescriptor::pageOwnerId, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeBuildLevel::allocatePage(), BTreeBuilder::createEmptyRoot(), BTreeWriter::grow(), and BTreeWriter::splitCurrentNode().

00255 {
00256     return treeDescriptor.pageOwnerId;
00257 }

TupleDescriptor const & BTreeAccessBase::getTupleDescriptor (  )  const [inline, inherited]

Returns:
TupleDescriptor for tuples stored by this BTree

Definition at line 259 of file BTreeAccessBase.h.

References BTreeAccessBase::treeDescriptor, and BTreeDescriptor::tupleDescriptor.

Referenced by BTreeWriter::describeParticipant(), and BTreeAccessBase::validateTupleSize().

00260 {
00261     return treeDescriptor.tupleDescriptor;
00262 }

TupleDescriptor const & BTreeAccessBase::getKeyDescriptor (  )  const [inline, inherited]

Returns:
TupleDescriptor for keys indexed by this BTree

Definition at line 264 of file BTreeAccessBase.h.

References BTreeAccessBase::keyDescriptor.

Referenced by BTreeTest::testBulkLoad(), BTreeTest::testInserts(), BTreeTest::testMultiKeySearches(), and BTreeReadersTest::testReaders().

00265 {
00266     return keyDescriptor;
00267 }

TupleProjection const & BTreeAccessBase::getKeyProjection (  )  const [inline, inherited]

Returns:
TupleProjection from getTupleDescriptor() to getKeyDescriptor()

Definition at line 269 of file BTreeAccessBase.h.

References BTreeDescriptor::keyProjection, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeAccessBase::BTreeAccessBase(), and BTreeWriter::describeParticipant().

00270 {
00271     return treeDescriptor.keyProjection;
00272 }

void BTreeAccessBase::validateTupleSize ( TupleAccessor const &  tupleAccessor  )  [inherited]

Validates that a particular tuple can fit in this BTree, throwing a TupleOverflowExcn if not.

Parameters:
tupleAccessor TupleAccessor referencing tuple to be inserted

Definition at line 146 of file BTreeAccessBase.cpp.

References BTreeAccessBase::cbTupleMax, TupleAccessor::getCurrentByteCount(), BTreeAccessBase::getTupleDescriptor(), and TupleAccessor::unmarshal().

Referenced by BTreeWriter::insertTupleFromBuffer(), and BTreeBuildLevel::processInput().

00147 {
00148     uint cbTuple = tupleAccessor.getCurrentByteCount();
00149     if (cbTuple > cbTupleMax) {
00150         TupleData tupleData(getTupleDescriptor());
00151         tupleAccessor.unmarshal(tupleData);
00152         throw TupleOverflowExcn(
00153             getTupleDescriptor(),
00154             tupleData,
00155             cbTuple,
00156             cbTupleMax);
00157     }
00158 }

Member Data Documentation

TupleData BTreeVerifier::lowerBoundKey [private]

Key data used for verifying that all keys in a node are greater than or equal to an expected lower bound.

If size is 0, represents negative infinity.

Definition at line 75 of file BTreeVerifier.h.

Referenced by verify(), verifyChildren(), and verifyNode().

TupleData BTreeVerifier::upperBoundKey [private]

Key data used for verifying that all keys in a node are less than or equal to an expected upper bound.

If size is 0, represents positive infinity.

Definition at line 82 of file BTreeVerifier.h.

Referenced by verify(), verifyChildren(), and verifyNode().

uint BTreeVerifier::expectedHeight [private]

Expected height for node about to be verified.

When MAXU, indicates that we don't know the height of the tree because we haven't yet verified the root.

Definition at line 89 of file BTreeVerifier.h.

Referenced by verify(), verifyChildren(), and verifyNode().

PageId BTreeVerifier::expectedRightSibling [private]

Expected right sibling for node about to be verified.

For non-strict verification, this may not match (although it must be reachable by traversing right siblings).

Definition at line 96 of file BTreeVerifier.h.

Referenced by verify(), verifyChildren(), and verifyNode().

BTreeStatistics BTreeVerifier::stats [private]

Statistics being gather during verification.

Definition at line 101 of file BTreeVerifier.h.

Referenced by getStatistics(), verify(), verifyChildren(), and verifyNode().

bool BTreeVerifier::strict [private]

Whether to be strict during verification.

Definition at line 106 of file BTreeVerifier.h.

Referenced by verify(), and verifyNode().

bool BTreeVerifier::keys [private]

Whether to perform key verification.

Definition at line 111 of file BTreeVerifier.h.

Referenced by verify(), and verifyNode().

bool BTreeVerifier::leaf [private]

Whether to traverse the leaf level.

Definition at line 116 of file BTreeVerifier.h.

Referenced by verify(), and verifyChildren().

TupleData BTreeVerifier::keyData [private]

Key data used for comparing successive keys.

Definition at line 121 of file BTreeVerifier.h.

Referenced by BTreeVerifier(), verifyChildren(), and verifyNode().

TupleData BTreeVerifier::keyData2 [private]

Key data used for comparing successive keys.

Definition at line 126 of file BTreeVerifier.h.

Referenced by BTreeVerifier(), and verifyNode().

BTreeDescriptor BTreeAccessBase::treeDescriptor [protected, inherited]

Descriptor for tree being accessed.

Definition at line 51 of file BTreeAccessBase.h.

Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeAccessBase::BTreeAccessBase(), BTreeBuildLevel::BTreeBuildLevel(), BTreeReader::BTreeReader(), BTreeBuilder::buildBalanced(), BTreeBuilder::createEmptyRoot(), BTreeAccessBase::getCacheAccessor(), BTreeAccessBase::getFirstChild(), BTreeAccessBase::getKeyProjection(), BTreeAccessBase::getPageOwnerId(), BTreeAccessBase::getRootPageId(), BTreeAccessBase::getSegment(), BTreeAccessBase::getSegmentId(), BTreeAccessBase::getTupleDescriptor(), BTreeWriter::grow(), BTreeWriter::lockParentPage(), BTreeAccessBase::setRootPageId(), BTreeWriter::splitCurrentNode(), BTreeBuilder::swapRoot(), BTreeBuilder::truncate(), BTreeBuilder::truncateChildren(), BTreeBuilder::truncateExternal(), and verifyNode().

TupleDescriptor BTreeAccessBase::keyDescriptor [protected, inherited]

Descriptor for pure keys (common across leaf and non-leaf tuples).

Definition at line 56 of file BTreeAccessBase.h.

Referenced by BTreeReader::binarySearch(), BTreeAccessBase::BTreeAccessBase(), BTreeReader::BTreeReader(), BTreeVerifier(), BTreeWriter::checkMonotonicity(), BTreeReader::compareFirstKey(), BTreeAccessBase::getKeyDescriptor(), BTreeWriter::insertTupleFromBuffer(), BTreeWriter::lockParentPage(), BTreeReader::searchForKeyTemplate(), and verifyNode().

AttributeAccessor const* BTreeAccessBase::pChildAccessor [protected, inherited]

Accessor for the attribute of non-leaf tuples which stores the child PageId.

Definition at line 62 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase(), BTreeAccessBase::getChildForCurrent(), and BTreeWriter::splitCurrentNode().

TupleProjectionAccessor BTreeAccessBase::leafKeyAccessor [protected, inherited]

Accessor for keys of tuples stored in leaves.

Definition at line 67 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase().

boost::scoped_ptr<BTreeNodeAccessor> BTreeAccessBase::pNonLeafNodeAccessor [protected, inherited]

Accessor for non-leaf nodes.

Definition at line 72 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase(), BTreeWriter::BTreeWriter(), BTreeBuilder::build(), BTreeBuilder::buildBalanced(), BTreeAccessBase::getChildForCurrent(), BTreeAccessBase::getNodeAccessor(), BTreeNonLeafReader::getNonLeafNodeAccessor(), BTreeAccessBase::getNonLeafNodeAccessor(), BTreeNonLeafReader::getTupleAccessorForRead(), BTreeBuilder::growTree(), VariableBuildLevel::indexLastKey(), BTreeWriter::splitCurrentNode(), and BTreeBuildLevel::unmarshalLastKey().

boost::scoped_ptr<BTreeNodeAccessor> BTreeAccessBase::pLeafNodeAccessor [protected, inherited]

Accessor for leaf nodes.

Definition at line 77 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase(), BTreeWriter::BTreeWriter(), BTreeBuilder::build(), BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), BTreeBuilder::createEmptyRoot(), BTreeWriter::deleteLogged(), BTreeReader::endSearch(), BTreeAccessBase::getLeafNodeAccessor(), BTreeAccessBase::getNodeAccessor(), BTreeReader::getTupleAccessorForRead(), BTreeBuilder::growTree(), BTreeWriter::insertTupleData(), BTreeWriter::insertTupleFromBuffer(), and BTreeBuilder::truncate().

uint BTreeAccessBase::cbTupleMax [protected, inherited]

Maximum size for a leaf-level tuple.

Definition at line 82 of file BTreeAccessBase.h.

Referenced by BTreeAccessBase::BTreeAccessBase(), and BTreeAccessBase::validateTupleSize().

The documentation for this class was generated from the following files:
Generated on Mon Jun 22 04:00:26 2009 for Fennel by  doxygen 1.5.1