BTreeNonLeafReader Class Reference

BTreeNonLeafReader extends BTreeReader by only doing reads of non-leaf pages in a btree. More...

#include <BTreeNonLeafReader.h>

Inheritance diagram for BTreeNonLeafReader:


Public Member Functions
	BTreeNonLeafReader (BTreeDescriptor const &descriptor)
TupleAccessor const &	getTupleAccessorForRead () const
	Gets a read-only accessor for non-leaf tuples.
virtual bool	searchForKey (TupleData const &key, DuplicateSeek dupSeek, bool leastUpper=true)
	Searches for a tuple in the tree based on the given key.
virtual bool	searchNext ()
	Searches for the next tuple at the level just above the leaf.
bool	isRootOnly ()
	Indicates whether the btree, at the time the method is called, consists of only a single root node page.
bool	isPositionedOnInfinityKey ()
	Returns: true if the reader is currently positioned on the rightmost key, i.e., the special infinity key
BTreeNodeAccessor &	getNonLeafNodeAccessor ()
	Returns: node accessor corresponding to this reader
PageId	getChildForCurrent ()
	Returns: child pageId in the current non-leaf record
TupleData &	getSearchKeyForWrite ()
	Gets writable TupleData which can be used to prepare a key to be used in searchForKey.
bool	searchFirst ()
	Searches for the first tuple in the tree.
bool	searchLast ()
	Searches for the last tuple in the tree.
virtual void	endSearch ()
	Forgets the current search, releasing any page lock.
bool	isPositioned () const
	Returns: true if a search method has been called without a subsequent endSearch yet
bool	isSingular () const
	Returns: true if reader is either unpositioned or past last entry in tree
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 Types
enum	ReadMode { READ_ALL, READ_NONLEAF_ONLY, READ_LEAF_ONLY }
	Enumeration of which node types the reader should be reading. More...
Protected Member Functions
void	accessLeafTuple ()
uint	binarySearch (BTreeNode const &node, DuplicateSeek dupSeek, bool leastUpper, bool &found)
	Searches a node for the current search key.
TupleData const &	getSearchKey ()
	Returns: the key being sought
int	compareFirstKey (BTreeNode const &node)
	Compares the first key on a node to the current search key.
void	accessTupleInline (BTreeNode const &node, uint iEntry)
	Sets tuple accessor to provided node entry.
template<bool leafLockCoupling, class PageStack>
bool	searchForKeyTemplate (TupleData const &key, DuplicateSeek dupSeek, bool leastUpper, PageStack &pageStack, PageId startPageId, LockMode initialLockMode, ReadMode readMode)
	Implements the workhorse algorithm for performing the actual search through the tree; templated to efficiently allow for certain variations needed when the search is used in preparation for an insertion by BTreeWriter.
bool	searchForKeyInternal (TupleData const &key, DuplicateSeek dupSeek, bool leastUpper, PageId startPageId, LockMode initialLockMode, ReadMode readMode)
	See also: searchForKeyTemplate()
bool	searchExtremeInternal (bool first, ReadMode readMode)
	Searches for the first or last tuple in the tree.
bool	searchNextInternal ()
	Searches for next tuple.
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	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
BTreePageLock	pageLock
	Lock on node being searched.
PageId	pageId
	PageId of node being searched.
uint	iTupleOnLowestLevel
	0-based position on lowest level searched by the reader.
bool	singular
	See also: isSingular()
LockMode	rootLockMode
	LockMode to use when acquiring lock on root node.
LockMode	nonLeafLockMode
	LockMode to use when acquiring lock on non-leaf nodes other than the root.
LockMode	leafLockMode
	LockMode to use when acquiring lock on leaf nodes.
TupleData	comparisonKeyData
	TupleData used as a temp variable for comparisons while searching.
TupleData const *	pSearchKey
	Key being sought.
TupleData	searchKeyData
	TupleData for key used in searches.
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
bool	adjustRootLockMode (LockMode &lockMode)
	Deals with the fact that when we lock the root, we don't know whether it happens to be a leaf as well.
virtual bool	searchExtreme (bool first)
	Searches for the first or last tuple in the non-leaf node that's one level above the leaf level in the tree.

Detailed Description

BTreeNonLeafReader extends BTreeReader by only doing reads of non-leaf pages in a btree.

Definition at line 35 of file BTreeNonLeafReader.h.

Member Enumeration Documentation

enum BTreeReader::ReadMode [protected, inherited]

Enumeration of which node types the reader should be reading.

Enumerator:

READ_ALL	Read both non-leaf and leaf nodes.
READ_NONLEAF_ONLY	Read only non-leaf nodes.
READ_LEAF_ONLY	Read only leaf nodes.

Definition at line 43 of file BTreeReader.h.

00043                   {
00047         READ_ALL,
00051         READ_NONLEAF_ONLY,
00055         READ_LEAF_ONLY
00056     };

Constructor & Destructor Documentation

BTreeNonLeafReader::BTreeNonLeafReader ( BTreeDescriptor const & descriptor ) [explicit]

Definition at line 31 of file BTreeNonLeafReader.cpp.

00032     : BTreeReader(descriptor)
00033 {
00034 }

Member Function Documentation

bool BTreeNonLeafReader::adjustRootLockMode ( LockMode & lockMode ) [private]

Deals with the fact that when we lock the root, we don't know whether it happens to be a leaf as well.

This method should never be called since this class does not read leaf pages.

Parameters:

lockMode

the lock mode used to lock the root

Returns:: always returns false

Reimplemented from BTreeReader.

Definition at line 36 of file BTreeNonLeafReader.cpp.

00037 {
00038     assert(false);
00039     return false;
00040 }

bool BTreeNonLeafReader::searchExtreme ( bool first ) [private, virtual]

Searches for the first or last tuple in the non-leaf node that's one level above the leaf level in the tree.

This method should never be called on a tree consisting of a single root node. So, therefore, it should never be called on an empty tree.

Parameters:

first

true for first; false for last

Returns:: always returns true since it is never called on an empty tree

Reimplemented from BTreeReader.

Definition at line 42 of file BTreeNonLeafReader.cpp.

References isRootOnly(), BTreeReader::READ_NONLEAF_ONLY, and BTreeReader::searchExtremeInternal().

00043 {
00044     assert(!isRootOnly());
00045     bool rc = searchExtremeInternal(first, READ_NONLEAF_ONLY);
00046     assert(rc);
00047     return rc;
00048 }

TupleAccessor const & BTreeNonLeafReader::getTupleAccessorForRead ( ) const

Gets a read-only accessor for non-leaf tuples.

Tuples found by a search are returned implicitly by binding this accessor.

Returns:: the non-leaf tuple accessor

Reimplemented from BTreeReader.

Definition at line 69 of file BTreeNonLeafReader.cpp.

References BTreeAccessBase::pNonLeafNodeAccessor.

Referenced by BTreeReadersTest::testScan(), and BTreeReadersTest::testSearch().

00070 {
00071     return pNonLeafNodeAccessor->tupleAccessor;
00072 }

bool BTreeNonLeafReader::searchForKey	(	TupleData const &	key,
		DuplicateSeek	dupSeek,
		bool	leastUpper = `true`
	)			`[virtual]`

Searches for a tuple in the tree based on the given key.

The search is stopped at the level just above the leaf. This method should not but called on a btree that consists of a single root node.

Parameters:

	key	the key to search for
	dupSeek	what to do if duplicates are found
	leastUpper	(default true) - if true, reader will position on the least upper bound of key; otherwise, it will position on tuple with greatest lower bound

Returns:: true if tuple found; false if not found, in which case reader is positioned on tuple depending on leastUpper parameter

Reimplemented from BTreeReader.

Definition at line 50 of file BTreeNonLeafReader.cpp.

References BTreeAccessBase::getRootPageId(), isRootOnly(), BTreeReader::READ_NONLEAF_ONLY, BTreeReader::rootLockMode, and BTreeReader::searchForKeyInternal().

Referenced by BTreeReadersTest::testSearch().

00054 {
00055     assert(!isRootOnly());
00056     return
00057         searchForKeyInternal(
00058             key, dupSeek, leastUpper, getRootPageId(), rootLockMode,
00059             READ_NONLEAF_ONLY);
00060 }

bool BTreeNonLeafReader::searchNext ( ) [virtual]

Searches for the next tuple at the level just above the leaf.

Can be used after either searchFirst or searchForKey, but illegal when isSingular().

Returns:: true if next tuple found; false if end of tree reached

Reimplemented from BTreeReader.

Definition at line 62 of file BTreeNonLeafReader.cpp.

References SegNodeLock< Node >::getNodeForRead(), SegPageLock::isLocked(), BTreeReader::pageLock, and BTreeReader::searchNextInternal().

Referenced by BTreeReadersTest::testScan().

00063 {
00064     assert(pageLock.isLocked());
00065     assert(pageLock.getNodeForRead().height == 1);
00066     return searchNextInternal();
00067 }

bool BTreeNonLeafReader::isRootOnly ( )

Indicates whether the btree, at the time the method is called, consists of only a single root node page.

Returns:: true if the btree consists of only a single root node

Definition at line 74 of file BTreeNonLeafReader.cpp.

References SegNodeLock< Node >::getNodeForRead(), BTreeAccessBase::getRootPageId(), BTreeNode::height, SegPageLock::lockPage(), BTreeReader::pageLock, BTreeReader::rootLockMode, and SegPageLock::unlock().

Referenced by searchExtreme(), searchForKey(), BTreeReadersTest::testScan(), and BTreeReadersTest::testSearch().

00075 {
00076     pageLock.lockPage(getRootPageId(), rootLockMode);
00077     BTreeNode const &node = pageLock.getNodeForRead();
00078     bool rc = (node.height == 0);
00079     pageLock.unlock();
00080     return rc;
00081 }

bool BTreeNonLeafReader::isPositionedOnInfinityKey ( )

Returns:: true if the reader is currently positioned on the rightmost key, i.e., the special infinity key

Definition at line 83 of file BTreeNonLeafReader.cpp.

References SegNodeLock< Node >::getNodeForRead(), SegPageLock::isLocked(), BTreeReader::iTupleOnLowestLevel, NULL_PAGE_ID, and BTreeReader::pageLock.

Referenced by BTreeReadersTest::testScan(), and BTreeReadersTest::testSearch().

00084 {
00085     assert(pageLock.isLocked());
00086     BTreeNode const &node = pageLock.getNodeForRead();
00087     return
00088         (node.rightSibling == NULL_PAGE_ID &&
00089             iTupleOnLowestLevel == node.nEntries - 1);
00090 }

BTreeNodeAccessor & BTreeNonLeafReader::getNonLeafNodeAccessor ( )

Returns:: node accessor corresponding to this reader

Definition at line 92 of file BTreeNonLeafReader.cpp.

References BTreeAccessBase::pNonLeafNodeAccessor.

00093 {
00094     return *pNonLeafNodeAccessor;
00095 }

PageId BTreeNonLeafReader::getChildForCurrent ( )

Returns:: child pageId in the current non-leaf record

Reimplemented from BTreeAccessBase.

Definition at line 97 of file BTreeNonLeafReader.cpp.

References BTreeAccessBase::getChildForCurrent().

00098 {
00099     return BTreeReader::getChildForCurrent();
00100 }

void BTreeReader::accessLeafTuple ( ) [inline, protected, inherited]

Definition at line 89 of file BTreeReaderImpl.h.

References BTreeNodeAccessor::accessTuple(), BTreeAccessBase::getLeafNodeAccessor(), SegNodeLock< Node >::getNodeForRead(), BTreeReader::iTupleOnLowestLevel, and BTreeReader::pageLock.

Referenced by BTreeLeafReader::searchExtreme(), BTreeReader::searchExtremeInternal(), and BTreeLeafReader::searchNext().

00090 {
00091     BTreeNode const &node = pageLock.getNodeForRead();
00092     getLeafNodeAccessor(node).accessTuple(node,iTupleOnLowestLevel);
00093 }

uint BTreeReader::binarySearch	(	BTreeNode const &	node,
		DuplicateSeek	dupSeek,
		bool	leastUpper,
		bool &	found
	)			`[inline, protected, inherited]`

Searches a node for the current search key.

Parameters:

	node	the node to search
	dupSeek	what to do if duplicates are found
	leastUpper	whether to position on least upper bound or greatest lower bound
	found	receives whether the search key was found; if false, the position of the least upper bound is returned instead

Returns:: 0-based position of found key on node

Definition at line 37 of file BTreeReaderImpl.h.

References BTreeNodeAccessor::binarySearch(), BTreeReader::comparisonKeyData, BTreeAccessBase::getNodeAccessor(), BTreeReader::getSearchKey(), and BTreeAccessBase::keyDescriptor.

Referenced by BTreeReader::searchForKeyTemplate().

00042 {
00043     return getNodeAccessor(node).binarySearch(
00044         node,
00045         keyDescriptor,
00046         getSearchKey(),
00047         dupSeek,
00048         leastUpper,
00049         comparisonKeyData,
00050         found);
00051 }

FENNEL_BEGIN_NAMESPACE TupleData const & BTreeReader::getSearchKey ( ) [inline, protected, inherited]

Returns:: the key being sought

Definition at line 31 of file BTreeReaderImpl.h.

References BTreeReader::pSearchKey.

Referenced by BTreeReader::binarySearch(), and BTreeReader::compareFirstKey().

00032 {
00033     assert(pSearchKey);
00034     return *pSearchKey;
00035 }

int BTreeReader::compareFirstKey ( BTreeNode const & node ) [inline, protected, inherited]

Compares the first key on a node to the current search key.

Parameters:

node

the node to search

Returns:: result of comparing searchKey with the first key (0, -1, or 1)

Definition at line 75 of file BTreeReaderImpl.h.

References BTreeNodeAccessor::compareFirstKey(), BTreeReader::comparisonKeyData, BTreeAccessBase::getNodeAccessor(), BTreeReader::getSearchKey(), and BTreeAccessBase::keyDescriptor.

Referenced by BTreeReader::searchForKeyTemplate().

00076 {
00077     return getNodeAccessor(node).compareFirstKey(
00078         node,
00079         keyDescriptor,
00080         getSearchKey(),
00081         comparisonKeyData);
00082 }

void BTreeReader::accessTupleInline	(	BTreeNode const &	node,
		uint	iEntry
	)			`[inline, protected, inherited]`

Sets tuple accessor to provided node entry.

Parameters:

	node	the current node positioned on
	iEntry	the entry within the node to set the tuple accessor to

Definition at line 84 of file BTreeReaderImpl.h.

References BTreeNodeAccessor::accessTupleInline(), and BTreeAccessBase::getNodeAccessor().

Referenced by BTreeWriter::checkMonotonicity(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKeyTemplate(), and BTreeReader::searchNextInternal().

00085 {
00086     getNodeAccessor(node).accessTupleInline(node, iEntry);
00087 }

template<bool leafLockCoupling, class PageStack>

bool BTreeReader::searchForKeyTemplate	(	TupleData const &	key,
		DuplicateSeek	dupSeek,
		bool	leastUpper,
		PageStack &	pageStack,
		PageId	startPageId,
		LockMode	initialLockMode,
		ReadMode	readMode
	)			`[inline, protected, inherited]`

Implements the workhorse algorithm for performing the actual search through the tree; templated to efficiently allow for certain variations needed when the search is used in preparation for an insertion by BTreeWriter.

leafLockCoupling controls whether lock coupling is enforced while moving rightward at the leaf level.

Parameters:

	key	the key being searched for
	dupSeek	how to handle duplicates
	leastUpper	whether to position on least upper bound or greatest lower bound
	pageStack	receives a path of rightmost PageId's encountered from root to the level above the leaf (PageStack must support the push_back method)
	startPageId	the pageId at which the search should start
	initialLockMode	the initial lockmode to use when searching the tree
	readMode	which node types should be searched

Definition at line 96 of file BTreeReaderImpl.h.

References BTreeReader::accessTupleInline(), BTreeReader::adjustRootLockMode(), BTreeReader::binarySearch(), BTreeReader::compareFirstKey(), DUP_SEEK_END, BTreeAccessBase::getChild(), BTreeAccessBase::getChildForCurrent(), BTreeAccessBase::getFirstChild(), SegNodeLock< Node >::getNodeForRead(), BTreeNode::height, BTreeReader::iTupleOnLowestLevel, BTreeAccessBase::keyDescriptor, BTreeReader::leafLockMode, SegPageLock::lockPage(), SegPageLock::lockPageWithCoupling(), BTreeNode::nEntries, NULL_PAGE_ID, BTreeReader::pageId, BTreeReader::pageLock, BTreeReader::pSearchKey, BTreeReader::READ_LEAF_ONLY, BTreeReader::READ_NONLEAF_ONLY, BTreeNode::rightSibling, BTreeReader::singular, and SegPageLock::unlock().

00100 {
00101     pSearchKey = &key;
00102 
00103     // At each level, we may have to search right due to splits.  To bound
00104     // this search, we record the parent's notion of the PageId for the
00105     // right sibling of the child page.  Lehman-Yao uses keys instead, but
00106     // PageId should work as well?
00107     PageId rightSearchTerminator = NULL_PAGE_ID;
00108     pageId = startPageId;
00109     LockMode lockMode = initialLockMode;
00110     bool lockCoupling = false;
00111     bool foundKeyAndMovedRight = false;
00112     for (;;) {
00113         if (leafLockCoupling && lockCoupling) {
00114             pageLock.lockPageWithCoupling(pageId,lockMode);
00115         } else {
00116             pageLock.lockPage(pageId,lockMode);
00117         }
00118 
00119         BTreeNode const *pNode = &(pageLock.getNodeForRead());
00120 
00121         // TODO:  pull this out of loop
00122         if (!pNode->height && !adjustRootLockMode(lockMode)) {
00123             // Retry with correct lock mode
00124             continue;
00125         }
00126 
00127         bool found;
00128         uint iKeyBound = binarySearch(*pNode,dupSeek,leastUpper,found);
00129         if (foundKeyAndMovedRight && !found) {
00130             // if we previously located our desired key on the page to
00131             // the left of this one and had to search to the right because
00132             // we're doing a DUP_SEEK_END search, but the key doesn't
00133             // exist on the current page, then we should revert back to the
00134             // prior "found" status, since we did find the key
00135             assert(iKeyBound == 0);
00136             found = true;
00137         }
00138 
00139         // if we're searching for the greatest lower bound, we didn't
00140         // find an exact match, and we're positioned at the rightmost
00141         // key entry, need to search the first key in the right sibling
00142         // to be sure we have the correct glb
00143         if (!leastUpper && !found && iKeyBound == pNode->nEntries - 1 &&
00144             pNode->rightSibling != NULL_PAGE_ID)
00145         {
00146             // not currently handling leaf lock coupling for reads,
00147             // which is the only time we're searching for glb
00148             assert(leafLockCoupling == false);
00149 
00150             PageId siblingPageId = pNode->rightSibling;
00151             pageLock.unlock();
00152             pageLock.lockPage(siblingPageId, lockMode);
00153             BTreeNode const &rightNode = pageLock.getNodeForRead();
00154             int res = compareFirstKey(rightNode);
00155 
00156             pageLock.unlock();
00157             if (res < 0) {
00158                 // stick with the current node, so go back and relock it
00159                 // and reset the tuple accessor back to the prior key
00160                 //
00161                 // FIXME zfong 7-Dec-2005: Need to handle case where a
00162                 // node split has occurred since the current node was
00163                 // unlocked.  To do so, need to search starting at the
00164                 // current node and continue searching right until you
00165                 // find a node whose right sibling is equal to the
00166                 // original right sibling.  The key we want should then
00167                 // be the last entry on that node.
00168                 pageLock.lockPage(pageId, lockMode);
00169                 pNode = &(pageLock.getNodeForRead());
00170                 accessTupleInline(*pNode, iKeyBound);
00171             } else {
00172                 // switch over to the right sibling, unless we're only
00173                 // searching a single leaf page
00174                 if (readMode == READ_LEAF_ONLY) {
00175                     assert(rightNode.height == 0);
00176                     // need to relock the original page and position to the
00177                     // last key on the page
00178                     pageLock.lockPage(pageId, lockMode);
00179                     iTupleOnLowestLevel = iKeyBound;
00180                     return false;
00181                 }
00182                 pageId = siblingPageId;
00183                 foundKeyAndMovedRight = false;
00184                 continue;
00185             }
00186         }
00187 
00188         if (iKeyBound == pNode->nEntries) {
00189             assert(!found || (dupSeek == DUP_SEEK_END));
00190             // What we're searching for is bigger than everything on
00191             // this node.
00192             if (pNode->rightSibling == rightSearchTerminator) {
00193                 // No need to search rightward.  This should only
00194                 // happen at the leaf level (since we never delete keys from
00195                 // nodes, the upper bound should match at parent and child
00196                 // levels.)
00197                 assert(!pNode->height);
00198                 if (rightSearchTerminator == NULL_PAGE_ID) {
00199                     singular = true;
00200                 }
00201             } else {
00202                 // have to search right
00203                 foundKeyAndMovedRight = found;
00204                 pageId = pNode->rightSibling;
00205                 if (leafLockCoupling && !pNode->height) {
00206                     lockCoupling = true;
00207                 }
00208                 continue;
00209             }
00210         }
00211 
00212         switch (pNode->height) {
00213         case 0:
00214             // at leaf level
00215             iTupleOnLowestLevel = iKeyBound;
00216             return found;
00217 
00218         case 1:
00219             if (readMode == READ_NONLEAF_ONLY) {
00220                 iTupleOnLowestLevel = iKeyBound;
00221                 return found;
00222             }
00223             // prepare to hit rock bottom
00224             lockMode = leafLockMode;
00225             break;
00226         }
00227 
00228         // leave a trail of breadcrumbs
00229         pageStack.push_back(pageId);
00230 
00231         // we'll continue search on child
00232         pageId = getChildForCurrent();
00233         foundKeyAndMovedRight = false;
00234 
00235         // Record the successor child as a terminator for rightward
00236         // searches once we descend to the child level, unless we're doing
00237         // a partial key search or a DUP_SEEK_END search.  In those
00238         // exception cases, when the last key value in a parent does not
00239         // exist in the leaf, we have to continue reading to the right.
00240         // That condition occurs if the last key was deleted from the leaf.
00241         // Because we didn't make a corresponding update in the parent node,
00242         // we find a match in the parent, but not the leaf.
00243         if ((*pSearchKey).size() == keyDescriptor.size() &&
00244             dupSeek != DUP_SEEK_END)
00245         {
00246             if (iKeyBound < (pNode->nEntries - 1)) {
00247                 rightSearchTerminator = getChild(*pNode,iKeyBound + 1);
00248             } else {
00249                 // have to consult our own sibling to find the successor
00250                 // child
00251                 // need to get the pageId first, then unlock.
00252                 PageId rightSiblingPageId = pNode->rightSibling;
00253                 pageLock.unlock();
00254                 rightSearchTerminator = getFirstChild(rightSiblingPageId);
00255             }
00256         }
00257     }
00258 }

bool BTreeReader::searchForKeyInternal	(	TupleData const &	key,
		DuplicateSeek	dupSeek,
		bool	leastUpper,
		PageId	startPageId,
		LockMode	initialLockMode,
		ReadMode	readMode
	)			`[protected, inherited]`

See also:: searchForKeyTemplate()

Definition at line 153 of file BTreeReader.cpp.

References BTreeReader::pSearchKey, and BTreeReader::singular.

Referenced by BTreeReader::searchForKey(), searchForKey(), and BTreeLeafReader::searchForKey().

00156 {
00157     singular = false;
00158     NullPageStack nullPageStack;
00159     bool found = searchForKeyTemplate<false,NullPageStack>(
00160         key,dupSeek,leastUpper,nullPageStack,startPageId,initialLockMode,
00161         readMode);
00162     pSearchKey = NULL;
00163     return found;
00164 }

bool BTreeReader::searchExtremeInternal	(	bool	first,
		ReadMode	readMode
	)			`[protected, inherited]`

Searches for the first or last tuple in the tree.

Parameters:

	first	true for first; false for last
	readMode	which types of nodes should be searched

Returns:: true if tuple found; false if tree is empty

Definition at line 54 of file BTreeReader.cpp.

References BTreeReader::accessLeafTuple(), BTreeReader::accessTupleInline(), BTreeReader::adjustRootLockMode(), BTreeAccessBase::getChild(), SegNodeLock< Node >::getNodeForRead(), BTreeAccessBase::getRootPageId(), BTreeNode::height, BTreeReader::iTupleOnLowestLevel, BTreeReader::leafLockMode, SegPageLock::lockPage(), BTreeNode::nEntries, BTreeReader::nonLeafLockMode, NULL_PAGE_ID, BTreeReader::pageId, BTreeReader::pageLock, BTreeReader::READ_NONLEAF_ONLY, BTreeNode::rightSibling, BTreeReader::rootLockMode, and BTreeReader::singular.

Referenced by BTreeReader::searchExtreme(), and searchExtreme().

00055 {
00056     singular = false;
00057     pageId = getRootPageId();
00058     LockMode lockMode = rootLockMode;
00059     for (;;) {
00060         pageLock.lockPage(pageId,lockMode);
00061         BTreeNode const &node = pageLock.getNodeForRead();
00062         switch (node.height) {
00063         case 0:
00064             // at leaf level
00065             if (!adjustRootLockMode(lockMode)) {
00066                 // Retry with correct lock mode
00067                 continue;
00068             }
00069             if (!node.nEntries) {
00070                 pageId = node.rightSibling;
00071                 if (pageId == NULL_PAGE_ID) {
00072                     // FIXME jvs 11-Nov-2005:  see note in method documentation
00073                     // for searchLast.
00074                     singular = true;
00075                     return false;
00076                 }
00077                 continue;
00078             }
00079             if (first) {
00080                 iTupleOnLowestLevel = 0;
00081             } else {
00082                 iTupleOnLowestLevel = node.nEntries - 1;
00083             }
00084             accessLeafTuple();
00085             return true;
00086         case 1:
00087             if (readMode == READ_NONLEAF_ONLY) {
00088                 if (first) {
00089                     iTupleOnLowestLevel = 0;
00090                 } else {
00091                     iTupleOnLowestLevel = node.nEntries - 1;
00092                 }
00093                 accessTupleInline(node, iTupleOnLowestLevel);
00094                 return true;
00095             }
00096             // next level down is leaf, so take the correct lock
00097             lockMode = leafLockMode;
00098             break;
00099         default:
00100             lockMode = nonLeafLockMode;
00101             break;
00102         }
00103 
00104         assert(node.nEntries);
00105         if (first) {
00106             // continue searching on first child
00107             pageId = getChild(node,0);
00108         } else {
00109             // continue searching on last child
00110             pageId = getChild(node,node.nEntries - 1);
00111        }
00112     }
00113 }

bool BTreeReader::searchNextInternal ( ) [protected, inherited]

Searches for next tuple.

Returns:: true if next tuple found; false if end of tree reached

Definition at line 122 of file BTreeReader.cpp.

References BTreeReader::accessTupleInline(), SegNodeLock< Node >::getNodeForRead(), BTreeReader::iTupleOnLowestLevel, BTreeReader::leafLockMode, SegPageLock::lockPage(), NULL_PAGE_ID, BTreeReader::pageId, BTreeReader::pageLock, and BTreeReader::singular.

Referenced by BTreeReader::searchNext(), and searchNext().

00123 {
00124     assert(!singular);
00125     ++iTupleOnLowestLevel;
00126     for (;;) {
00127         BTreeNode const &node = pageLock.getNodeForRead();
00128         if (iTupleOnLowestLevel < node.nEntries) {
00129             accessTupleInline(node, iTupleOnLowestLevel);
00130             break;
00131         }
00132         pageId = node.rightSibling;
00133         if (pageId == NULL_PAGE_ID) {
00134             // might as well preserve position
00135             --iTupleOnLowestLevel;
00136             singular = true;
00137             return false;
00138         }
00139         pageLock.lockPage(pageId,leafLockMode);
00140         iTupleOnLowestLevel = 0;
00141     }
00142     return true;
00143 }

TupleData & BTreeReader::getSearchKeyForWrite ( ) [inline, inherited]

Gets writable TupleData which can be used to prepare a key to be used in searchForKey.

This is strictly an optional convenience; any key can be passed to searchForKey.

Returns:: writable TupleData for key

Definition at line 342 of file BTreeReader.h.

References BTreeReader::searchKeyData.

00343 {
00344     return searchKeyData;
00345 }

bool BTreeReader::searchFirst ( ) [inline, inherited]

Searches for the first tuple in the tree.

Returns:: true if tuple found; false if tree is empty

Definition at line 357 of file BTreeReader.h.

References BTreeReader::searchExtreme().

Referenced by LbmSplicerExecStreamTest::testLER5968(), LbmSplicerExecStreamTest::testLER6473(), BTreeTest::testScan(), BTreeReadersTest::testScan(), LbmSplicerExecStreamTest::testSpliceRids(), LbmSplicerExecStreamTest::testSpliceWithKeys(), and BTreeBuilder::truncateExternal().

00358 {
00359     return searchExtreme(true);
00360 }

bool BTreeReader::searchLast ( ) [inline, inherited]

Searches for the last tuple in the tree.

FIXME jvs 11-Nov-2005: This method isn't currently guaranteed to work after deletions on a tree. The problem is that deletions may leave the last page of the tree empty, so when we hit leaf level, we may not find anything, even though a predecessor page is non-empty. We only have right-sibling links, not left-siblings, so the fix requires keeping a breadcrumb trail on the way down and backtracking when we hit an empty leaf.

Returns:: true if tuple found; false if tree is empty

Definition at line 362 of file BTreeReader.h.

References BTreeReader::searchExtreme().

Referenced by BTreeTest::testScan(), BTreeReadersTest::testScan(), and BTreeTest::testSearchLast().

00363 {
00364     return searchExtreme(false);
00365 }

void BTreeReader::endSearch ( ) [virtual, inherited]

Forgets the current search, releasing any page lock.

Reimplemented in BTreeLeafReader.

Definition at line 166 of file BTreeReader.cpp.

References BTreeReader::pageLock, BTreeAccessBase::pLeafNodeAccessor, BTreeReader::singular, and SegPageLock::unlock().

Referenced by BTreeWriter::deleteLogged(), BTreeTxnTest::deleteTxn(), BTreeLeafReader::endSearch(), BTreeWriter::insertTupleFromBuffer(), BTreeTxnTest::scanTxn(), BTreeTest::testMultiKeySearches(), BTreeTest::testScan(), BTreeReadersTest::testScan(), and BTreeReader::~BTreeReader().

00167 {
00168     pLeafNodeAccessor->tupleAccessor.resetCurrentTupleBuf();
00169     pageLock.unlock();
00170     singular = true;
00171 }

bool BTreeReader::isPositioned ( ) const [inline, inherited]

Returns:: true if a search method has been called without a subsequent endSearch yet

Definition at line 352 of file BTreeReader.h.

References SegPageLock::isLocked(), and BTreeReader::pageLock.

Referenced by BTreeWriter::insertTupleFromBuffer().

00353 {
00354     return pageLock.isLocked();
00355 }

bool BTreeReader::isSingular ( ) const [inline, inherited]

Returns:: true if reader is either unpositioned or past last entry in tree

Definition at line 347 of file BTreeReader.h.

References BTreeReader::singular.

Referenced by BTreeReadersTest::testSearch().

00348 {
00349     return singular;
00350 }

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(), BTreeVerifier::verifyChildren(), and BTreeVerifier::verifyNode().

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

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 BTreeVerifier::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 BTreeVerifier::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 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, 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::BTreeVerifier(), BTreeBuilder::buildBalanced(), BTreeInsertExecStream::buildTree(), LbmSplicerExecStreamTest::createBTree(), BTreeBuilder::createEmptyRoot(), BTreeWriter::describeParticipant(), LcsClusterReplaceExecStream::getTupleForLoad(), LbmSplicerExecStream::getValidatedTuple(), isRootOnly(), LcsClusterReplaceExecStreamTest::loadCluster(), LcsMultiClusterAppendTest::loadClusters(), LcsRowScanExecStreamTest::loadOneCluster(), LbmSearchTest::loadTableAndIndex(), BTreeWriter::lockParentPage(), BTreeWriter::optimizeRootLockMode(), BTreeWriter::positionSearchKey(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKey(), 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 ) [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 }