Fennel: BTreeVerifier Class Reference (original) (raw)

BTreeVerifier checks BTree integrity. More...

#include <[BTreeVerifier.h](BTreeVerifier%5F8h-source.html)>

Inheritance diagram for BTreeVerifier:

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 | ( | | ) | [virtual] | | ------------------------------ | - | | - | ----------- |

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().

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().

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().

FENNEL_BEGIN_NAMESPACE BTreeNodeAccessor & BTreeAccessBase::getLeafNodeAccessor	(	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:

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().

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

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

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]

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

| 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().

| 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().

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

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

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

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

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

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