BTreeAccessBase Class Reference

BTreeAccessBase is a base for classes which access BTree contents. More...

#include <BTreeAccessBase.h>

Inheritance diagram for BTreeAccessBase:


Public Member Functions
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.
	BTreeAccessBase (BTreeDescriptor const &descriptor)
virtual	~BTreeAccessBase ()
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.

Detailed Description

BTreeAccessBase is a base for classes which access BTree contents.

It declares some of the necessary tuple accessors, helper methods, etc.

Definition at line 44 of file BTreeAccessBase.h.

Constructor & Destructor Documentation

BTreeAccessBase::BTreeAccessBase ( BTreeDescriptor const & descriptor ) [explicit, protected]

Definition at line 35 of file BTreeAccessBase.cpp.

References TupleProjectionAccessor::bind(), cbTupleMax, TupleAccessor::compute(), getKeyProjection(), getSegment(), TupleAccessor::isFixedWidth(), keyDescriptor, BTreeDescriptor::keyProjection, leafKeyAccessor, StandardTypeDescriptorFactory::newDataType(), pChildAccessor, pLeafNodeAccessor, pNonLeafNodeAccessor, TupleDescriptor::projectFrom(), STANDARD_TYPE_UINT_64, treeDescriptor, and BTreeDescriptor::tupleDescriptor.

00036     : treeDescriptor(treeDescriptorInit)
00037 {
00038     keyDescriptor.projectFrom(
00039         treeDescriptor.tupleDescriptor,
00040         treeDescriptor.keyProjection);
00041 
00042     // TODO:  fine-tuning (in some cases fixed-width may be better for short
00043     // variable-width tuples, and indirection may be good for long fixed-width
00044     // tuples)
00045 
00046     // supported leaf accessor types
00047     typedef BTreeKeyedNodeAccessor<
00048         BTreeHeapNodeAccessor,TupleAccessor>
00049         VarNonLeafNodeAccessor;
00050     typedef BTreeKeyedNodeAccessor<
00051         BTreeCompactNodeAccessor,TupleAccessor>
00052         FixedNonLeafNodeAccessor;
00053 
00054     // supported non-leaf accessor types
00055     typedef BTreeKeyedNodeAccessor<
00056         BTreeHeapNodeAccessor,TupleProjectionAccessor>
00057         VarLeafNodeAccessor;
00058     typedef BTreeKeyedNodeAccessor<
00059         BTreeCompactNodeAccessor,TupleProjectionAccessor>
00060         FixedLeafNodeAccessor;
00061 
00062     // REVIEW:  These are just for deciding between fixed and var.  Add an
00063     // isFixedWidth() method to TupleDescriptor instead?
00064     TupleAccessor tmpLeafAccessor;
00065     tmpLeafAccessor.compute(treeDescriptor.tupleDescriptor);
00066     TupleAccessor tmpNonLeafAccessor;
00067     tmpNonLeafAccessor.compute(keyDescriptor);
00068 
00069     if (tmpLeafAccessor.isFixedWidth()) {
00070         FixedLeafNodeAccessor *pLeafNodeAccessorImpl =
00071             new FixedLeafNodeAccessor();
00072         pLeafNodeAccessor.reset(pLeafNodeAccessorImpl);
00073         pLeafNodeAccessorImpl->pKeyAccessor = &leafKeyAccessor;
00074     } else {
00075         VarLeafNodeAccessor *pLeafNodeAccessorImpl =
00076             new VarLeafNodeAccessor();
00077         pLeafNodeAccessor.reset(pLeafNodeAccessorImpl);
00078         pLeafNodeAccessorImpl->pKeyAccessor = &leafKeyAccessor;
00079     }
00080 
00081     if (tmpNonLeafAccessor.isFixedWidth()) {
00082         FixedNonLeafNodeAccessor *pNonLeafNodeAccessorImpl =
00083             new FixedNonLeafNodeAccessor();
00084         pNonLeafNodeAccessor.reset(pNonLeafNodeAccessorImpl);
00085         pNonLeafNodeAccessorImpl->pKeyAccessor =
00086             &(pNonLeafNodeAccessor->tupleAccessor);
00087     } else {
00088         VarNonLeafNodeAccessor *pNonLeafNodeAccessorImpl =
00089             new VarNonLeafNodeAccessor();
00090         pNonLeafNodeAccessor.reset(pNonLeafNodeAccessorImpl);
00091         pNonLeafNodeAccessorImpl->pKeyAccessor =
00092             &(pNonLeafNodeAccessor->tupleAccessor);
00093     }
00094 
00095     pLeafNodeAccessor->tupleDescriptor = treeDescriptor.tupleDescriptor;
00096 
00097     pNonLeafNodeAccessor->tupleDescriptor = keyDescriptor;
00098     StandardTypeDescriptorFactory stdTypeFactory;
00099 
00100     // TODO:  make PageId storage type selection automatic
00101     assert(sizeof(PageId) == sizeof(uint64_t));
00102     TupleAttributeDescriptor pageIdDesc(
00103         stdTypeFactory.newDataType(STANDARD_TYPE_UINT_64));
00104     pNonLeafNodeAccessor->tupleDescriptor.push_back(pageIdDesc);
00105 
00106     pLeafNodeAccessor->onInit();
00107     pNonLeafNodeAccessor->onInit();
00108 
00109     pChildAccessor = &(
00110         pNonLeafNodeAccessor->tupleAccessor.getAttributeAccessor(
00111             getKeyProjection().size()));
00112 
00113     leafKeyAccessor.bind(
00114         pLeafNodeAccessor->tupleAccessor,
00115         getKeyProjection());
00116 
00117     cbTupleMax =
00118         ((getSegment()->getUsablePageSize() - sizeof(BTreeNode)) / 2)
00119         - pLeafNodeAccessor->getEntryByteCount(0);
00120 }

BTreeAccessBase::~BTreeAccessBase ( ) [protected, virtual]

Definition at line 122 of file BTreeAccessBase.cpp.

00123 {
00124 }

Member Function Documentation

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

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 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]

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 pNonLeafNodeAccessor.

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

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

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

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, pLeafNodeAccessor, and pNonLeafNodeAccessor.

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

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

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

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 pChildAccessor, TupleDatum::pData, pNonLeafNodeAccessor, and AttributeAccessor::unmarshalValue().

Referenced by 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]`

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(), getChildForCurrent(), and getNonLeafNodeAccessor().

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

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

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

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

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

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

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

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 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]

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 getChild(), SegNodeLock< Node >::getNodeForRead(), BTreeNode::height, SegPageLock::lockShared(), BTreeNode::nEntries, NULL_PAGE_ID, BTreeNode::rightSibling, BTreeDescriptor::segmentAccessor, and treeDescriptor.

Referenced by BTreeReader::searchForKeyTemplate(), and BTreeVerifier::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]

Returns:: the segment storing the BTree being accessed

Definition at line 234 of file BTreeAccessBase.h.

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

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

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

SharedCacheAccessor BTreeAccessBase::getCacheAccessor ( ) const [inline]

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

Definition at line 239 of file BTreeAccessBase.h.

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

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

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

PageId BTreeAccessBase::getRootPageId ( ) const [inline]

Returns:: the BTree's root PageId

Definition at line 244 of file BTreeAccessBase.h.

References BTreeDescriptor::rootPageId, and treeDescriptor.

Referenced by BTreeVerifier::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(), BTreeVerifier::verify(), and CmdInterpreter::visit().

00245 {
00246     return treeDescriptor.rootPageId;
00247 }

void BTreeAccessBase::setRootPageId ( PageId rootPageId )

Updates the BTree's root PageId.

Definition at line 141 of file BTreeAccessBase.cpp.

References BTreeDescriptor::rootPageId, and treeDescriptor.

00142 {
00143     treeDescriptor.rootPageId = rootPageId;
00144 }

SegmentId BTreeAccessBase::getSegmentId ( ) const [inline]

Returns:: SegmentId of segment storing the BTree

Definition at line 249 of file BTreeAccessBase.h.

References BTreeDescriptor::segmentId, and treeDescriptor.

00250 {
00251     return treeDescriptor.segmentId;
00252 }

PageOwnerId BTreeAccessBase::getPageOwnerId ( ) const [inline]

Returns:: PageOwnerId used to mark pages of the BTree

Definition at line 254 of file BTreeAccessBase.h.

References BTreeDescriptor::pageOwnerId, and treeDescriptor.

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

00255 {
00256     return treeDescriptor.pageOwnerId;
00257 }

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

Returns:: TupleDescriptor for tuples stored by this BTree

Definition at line 259 of file BTreeAccessBase.h.

References treeDescriptor, and BTreeDescriptor::tupleDescriptor.

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

00260 {
00261     return treeDescriptor.tupleDescriptor;
00262 }

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

Returns:: TupleDescriptor for keys indexed by this BTree

Definition at line 264 of file BTreeAccessBase.h.

References keyDescriptor.

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

00265 {
00266     return keyDescriptor;
00267 }

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

Returns:: TupleProjection from getTupleDescriptor() to getKeyDescriptor()

Definition at line 269 of file BTreeAccessBase.h.

References BTreeDescriptor::keyProjection, and treeDescriptor.

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

00270 {
00271     return treeDescriptor.keyProjection;
00272 }

void BTreeAccessBase::validateTupleSize ( TupleAccessor const & tupleAccessor )

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 cbTupleMax, TupleAccessor::getCurrentByteCount(), 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 }