BTreeWriter Class Reference

BTreeWriter extends BTreeReader to provide read-write access to the contents of a BTree. More...

#include <BTreeWriter.h>

Inheritance diagram for BTreeWriter:


Public Member Functions
	BTreeWriter (BTreeDescriptor const &descriptor, SegmentAccessor const &scratchAccessor, bool monotonic=false)
	Creates a new BTreeWriter.
virtual	~BTreeWriter ()
void	insertTupleData (TupleData const &tupleData, Distinctness distinctness)
	Inserts a tuple from unmarshalled TupleData form; requires this writer to already be positioned to the correct location (the caller is trusted, with no verification).
uint	insertTupleFromBuffer (PConstBuffer pTupleBuffer, Distinctness distinctness)
	Inserts a tuple from a marshalled tuple buffer.
void	deleteCurrent ()
	Deletes the current tuple.
bool	updateCurrent (TupleData const &tupleData)
	Attempts to update the current tuple's value without changing its key and without splitting the page.
void	releaseScratchBuffers ()
	Releases any allocated scratch buffers.
virtual LogicalTxnClassId	getParticipantClassId () const
	Returns: the LogicalTxnClassId for this participant; this will be used during recovery to find the correct LogicalTxnParticipantFactory
virtual void	describeParticipant (ByteOutputStream &logStream)
	Called by LogicalTxn the first time an action is logged for this participant.
virtual void	undoLogicalAction (LogicalActionType actionType, ByteInputStream &logStream)
	Performs undo for one logical action during rollback or recovery.
virtual void	redoLogicalAction (LogicalActionType actionType, ByteInputStream &logStream)
	Performs redo for one logical action during recovery.
TupleAccessor const &	getTupleAccessorForRead () const
	Gets a read-only accessor for leaf tuples.
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 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.
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
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.
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()
virtual bool	searchExtreme (bool first)
	Searches for the first or last tuple in the tree.
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	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.
LogicalTxn *	getLogicalTxn ()
	Returns: LogicalTxn being participated in, or null if no txn in progress; null is also returned during recovery
bool	isLoggingEnabled () const
	Returns: true if actions should be logged; this is false during recovery
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
void	optimizeRootLockMode ()
void	compactNode (BTreePageLock &targetPageLock)
	Performs compaction on a node to free up space for inserting a tuple.
void	splitCurrentNode (PConstBuffer pTupleBuffer, uint cbTuple, uint iNewTuple)
	Splits the current node locked by pageLock to free up space for inserting a tuple, and then performs the actual insertion.
void	grow (BTreeNode const &rightNode, PageId rightPageId)
	Grows the tree by one level, preserving the root PageId.
uint	lockParentPage (uint height, bool rightMostNode)
	Finds the parent page by using the page stack (plus searches if root splits are encountered).
bool	attemptInsertWithoutSplit (BTreePageLock &targetPageLock, PConstBuffer pTupleBuffer, uint cbTuple, uint iNewTuple)
	Attempts to perform an insertion without splitting, performing compaction automatically if it will allow the insertion to succeed.
void	insertLogged (ByteInputStream &logStream)
	Inserts a tuple read from a log stream.
void	deleteLogged (ByteInputStream &logStream)
	Deletes a tuple read from a log stream.
bool	positionSearchKey (BTreeNodeAccessor &nodeAccessor)
	Positions search key for insert, also detecting duplicate key values.
bool	checkMonotonicity (BTreeNodeAccessor &nodeAccessor, PConstBuffer pTupleBuffer)
	Checks to ensure that when monotonic insert mode is used, the keys really are increasing.
Private Attributes
SegmentAccessor	scratchAccessor
	Accessor for scratch segment.
BTreePageLock	scratchPageLock
	Lock on scratch page used during splits.
std::vector< PageId >	pageStack
	Stack of rightmost non-leaf pages seen while searching in preparation for an insertion; this is used in reverse while splitting.
boost::scoped_array< FixedBuffer >	splitTupleBuffer
	Buffer used for storing entry to be inserted into parent node during split.
boost::scoped_array< FixedBuffer >	leafTupleBuffer
	Buffer used for marshalling in insertTupleData.
bool	monotonic
	If true, caller promises inserts will be strictly increasing.
Static Private Attributes
static const LogicalActionType	ACTION_INSERT = 1
	LogicalActionType for inserting an entry into a BTree.
static const LogicalActionType	ACTION_DELETE = 2
	LogicalActionType for deleting an entry from a BTree.

Detailed Description

BTreeWriter extends BTreeReader to provide read-write access to the contents of a BTree.

Optionally, it can also be used as a transaction participant.

Definition at line 39 of file BTreeWriter.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

BTreeWriter::BTreeWriter	(	BTreeDescriptor const &	descriptor,
		SegmentAccessor const &	scratchAccessor,
		bool	monotonic = `false`
	)			`[explicit]`

Creates a new BTreeWriter.

Parameters:

	descriptor	descriptor for tree to be accessed
	scratchAccessor	accessor for scratch segment used in splits
	monotonic	if true, inserts are always increasing

Definition at line 38 of file BTreeWriter.cpp.

References SegPageLock::accessSegment(), FixedBuffer, BTreeReader::leafLockMode, leafTupleBuffer, LOCKMODE_X, monotonic, BTreeAccessBase::pLeafNodeAccessor, BTreeAccessBase::pNonLeafNodeAccessor, scratchAccessor, scratchPageLock, and splitTupleBuffer.

00042     : BTreeReader(descriptor),
00043       scratchAccessor(scratchAccessorInit)
00044 {
00045     // we need exclusive locks on leaves for update operations
00046     leafLockMode = LOCKMODE_X;
00047     scratchPageLock.accessSegment(scratchAccessor);
00048     splitTupleBuffer.reset(
00049         new FixedBuffer[pNonLeafNodeAccessor->tupleAccessor.getMaxByteCount()]);
00050     leafTupleBuffer.reset(
00051         new FixedBuffer[pLeafNodeAccessor->tupleAccessor.getMaxByteCount()]);
00052     monotonic = monotonicInit;
00053 }

BTreeWriter::~BTreeWriter ( ) [virtual]

Definition at line 55 of file BTreeWriter.cpp.

00056 {
00057 }

Member Function Documentation

void BTreeWriter::optimizeRootLockMode ( ) [inline, private]

Definition at line 518 of file BTreeWriter.cpp.

References BTreeAccessBase::getRootPageId(), LOCKMODE_S, BTreeReader::pageId, and BTreeReader::rootLockMode.

Referenced by deleteCurrent(), and updateCurrent().

00519 {
00520     if (pageId != getRootPageId()) {
00521         // In case the tree has grown, counteract the effect of
00522         // adjustRootLockMode for subsequent searches.
00523         rootLockMode = LOCKMODE_S;
00524     }
00525 }

void BTreeWriter::compactNode ( BTreePageLock & targetPageLock ) [private]

Performs compaction on a node to free up space for inserting a tuple.

This method uses swapBuffers for efficiency; as a side-effect, pointers to BTreeNodes may be invalidated, so use with caution. (That's also why the parameter is a page lock rather than a node reference).

Parameters:

targetPageLock

lock on node to be compacted

Definition at line 174 of file BTreeWriter.cpp.

References SegNodeLock< Node >::allocatePage(), BTreeNodeAccessor::clearNode(), BTreeNodeAccessor::compactNode(), BTreeAccessBase::getNodeAccessor(), SegNodeLock< Node >::getNodeForWrite(), BTreeAccessBase::getSegment(), SegPageLock::isLocked(), BTreeReader::pageLock, scratchPageLock, and SegPageLock::swapBuffers().

Referenced by attemptInsertWithoutSplit(), and updateCurrent().

00175 {
00176     BTreeNode &node = targetPageLock.getNodeForWrite();
00177     if (!scratchPageLock.isLocked()) {
00178         scratchPageLock.allocatePage();
00179     }
00180     BTreeNode &scratchNode = scratchPageLock.getNodeForWrite();
00181     BTreeNodeAccessor &nodeAccessor = getNodeAccessor(node);
00182     nodeAccessor.clearNode(scratchNode,getSegment()->getUsablePageSize());
00183     nodeAccessor.compactNode(node,scratchNode);
00184     pageLock.swapBuffers(scratchPageLock);
00185 }

void BTreeWriter::splitCurrentNode	(	PConstBuffer	pTupleBuffer,
		uint	cbTuple,
		uint	iNewTuple
	)			`[private]`

Splits the current node locked by pageLock to free up space for inserting a tuple, and then performs the actual insertion.

Parameters:

	pTupleBuffer	buffer containing the tuple being inserted
	cbTuple	number of bytes in pTupleBuffer
	iNewTuple	desired 0-based position for new tuple

Definition at line 187 of file BTreeWriter.cpp.

Referenced by insertTupleFromBuffer().

00189 {
00190     // Current node will be on left after split.
00191     PageId leftPageId = pageId;
00192     BTreeNode &node = pageLock.getNodeForWrite();
00193     BTreeNodeAccessor &nodeAccessor = getNodeAccessor(node);
00194 
00195     // New node will be on right after split.
00196     BTreePageLock newPageLock(treeDescriptor.segmentAccessor);
00197     PageId newPageId = newPageLock.allocatePage(getPageOwnerId());
00198     BTreeNode &newNode = newPageLock.getNodeForWrite();
00199     nodeAccessor.clearNode(newNode,getSegment()->getUsablePageSize());
00200 
00201 #if 0
00202     std::cerr << "BEFORE SPLIT:" << std::endl;
00203     nodeAccessor.dumpNode(std::cerr,node,pageId);
00204 #endif
00205 
00206     setRightSibling(newNode,newPageId,node.rightSibling);
00207     setRightSibling(node,pageId,newPageId);
00208 
00209     nodeAccessor.splitNode(node,newNode,cbTuple,monotonic);
00210 
00211 #if 0
00212     std::cerr << "LEFT AFTER SPLIT:" << std::endl;
00213     nodeAccessor.dumpNode(std::cerr,node,pageId);
00214     std::cerr << "RIGHT AFTER SPLIT:" << std::endl;
00215     nodeAccessor.dumpNode(std::cerr,newNode,newPageId);
00216 #endif
00217 
00218     // Figure out where new tuple goes
00219     BTreePageLock *pLockForNewTuple = NULL;
00220     if (iNewTuple < node.nEntries) {
00221         // definitely on left
00222         pLockForNewTuple = &pageLock;
00223     } else if (iNewTuple > node.nEntries) {
00224         // definitely on right
00225         pLockForNewTuple = &newPageLock;
00226     } else {
00227         // could go either way depending on how the balancing worked out
00228         if (nodeAccessor.calculateCapacity(newNode,cbTuple) !=
00229             BTreeNodeAccessor::CAN_NOT_FIT)
00230         {
00231             pLockForNewTuple = &newPageLock;
00232         } else {
00233             pLockForNewTuple = &pageLock;
00234         }
00235     }
00236     if (pLockForNewTuple == &newPageLock) {
00237         iNewTuple -= node.nEntries;
00238     }
00239 
00240     // NOTE:  After this,  either the node or newNode reference may be
00241     // invalid, so don't use them.
00242     bool inserted = attemptInsertWithoutSplit(
00243         *pLockForNewTuple,pTupleBuffer,cbTuple,iNewTuple);
00244     permAssert(inserted);
00245 
00246     // We cannot safely access node or newNode any more, so from here
00247     // on use these instead:
00248     // leftNode == node
00249     // rightNode == newNode
00250 
00251     BTreeNode const &leftNode = pageLock.getNodeForRead();
00252     BTreeNode const &rightNode = newPageLock.getNodeForRead();
00253 
00254     if (pageStack.empty()) {
00255         // We're splitting the root:  time to grow the tree.
00256         grow(rightNode, newPageId);
00257 
00258         // NOTE:  newPageLock will unlock automatically on return,
00259         // and pageLock will be unlocked by the endSearch() call
00260         // in insertTupleFromBuffer, so there's no need to
00261         // explicitly unlock either one here.
00262         return;
00263     }
00264 
00265     // We're done splitting current node; now update parent node with new keys
00266     // from split.  In the case of monotonic inserts, flush the left node.
00267     assert(leftNode.nEntries);
00268     if (monotonic) {
00269         pageLock.flushPage(true);
00270     }
00271 
00272     // This will be the same as nodeAccessor if we're splitting a non-leaf.
00273     BTreeNodeAccessor &upperNodeAccessor = *pNonLeafNodeAccessor;
00274 
00275     // Prepare the parent entry to associate with the left node,
00276     // and marshal it into splitTupleBuffer.
00277     nodeAccessor.accessTuple(leftNode,leftNode.nEntries - 1);
00278     nodeAccessor.unmarshalKey(upperNodeAccessor.tupleData);
00279     upperNodeAccessor.tupleData.back().pData =
00280         reinterpret_cast<PConstBuffer>(&leftPageId);
00281     upperNodeAccessor.tupleAccessor.marshal(
00282         upperNodeAccessor.tupleData,
00283         splitTupleBuffer.get());
00284 
00285     // Save a copy of the right page's high key in searchKeyData; we'll need it
00286     // later inside of lockParentPage.  Note that this means rightNode needs to
00287     // remain locked for the duration, because searchKeyData will point into
00288     // it.
00289     uint nRightKeys = nodeAccessor.getKeyCount(rightNode);
00290     nodeAccessor.accessTuple(rightNode,nRightKeys - 1);
00291     nodeAccessor.unmarshalKey(searchKeyData);
00292 
00293     // Now, lock parent page and find the position of the entry pointing
00294     // to the original node (pre-split).  If that node is the rightmost node,
00295     // then the position in the parent node corresponds to the infinity
00296     // key, i.e., the last entry in the node.
00297     bool rightMostNode = (rightNode.rightSibling == NULL_PAGE_ID);
00298     assert(!monotonic || (monotonic && rightMostNode));
00299     uint iPosition = lockParentPage(leftNode.height, rightMostNode);
00300 
00301     // TODO jvs 12-Feb-2006: The code below uses getEntryForRead, even though
00302     // we're actually going to write; should either rename that method or add a
00303     // new getEntryForWrite which returns a non-const pointer.
00304 
00305     // Update the original entry in the parent, changing its child pointer
00306     // to reference newPageId instead of leftPageId.
00307     BTreeNode &upperNode = pageLock.getNodeForWrite();
00308     upperNodeAccessor.tupleAccessor.setCurrentTupleBuf(
00309         const_cast<PBuffer>(
00310             upperNodeAccessor.getEntryForRead(upperNode,iPosition)));
00311     TupleDatum &childDatum = upperNodeAccessor.tupleData.back();
00312     pChildAccessor->unmarshalValue(
00313         upperNodeAccessor.tupleAccessor,
00314         childDatum);
00315     PageId &childPageId =
00316         *(reinterpret_cast<PageId *>(const_cast<PBuffer>(childDatum.pData)));
00317     assert(childPageId == leftPageId);
00318     childPageId = newPageId;
00319 
00320     // Finally, insert the splitter entry; this may entail recursively
00321     // splitting again.
00322     upperNodeAccessor.tupleAccessor.setCurrentTupleBuf(splitTupleBuffer.get());
00323     cbTuple = upperNodeAccessor.tupleAccessor.getCurrentByteCount();
00324     inserted = attemptInsertWithoutSplit(
00325         pageLock,splitTupleBuffer.get(),cbTuple,iPosition);
00326     if (inserted) {
00327         // The entry fit; no need for recursion.
00328         return;
00329     }
00330 
00331     // Oops, couldn't fit:  go recursive.
00332 
00333     // REVIEW jvs 12-Feb-2006:  split locking in general.
00334     newPageLock.unlock();
00335 
00336     splitCurrentNode(splitTupleBuffer.get(),cbTuple,iPosition);
00337 }

void BTreeWriter::grow	(	BTreeNode const &	rightNode,
		PageId	rightPageId
	)			`[private]`

Grows the tree by one level, preserving the root PageId.

On entry, the original root (identified by pageId) should be held by pageLock. On return, the new root node will have two entries: the first entry will point to a copy of the old root on a new page, and the second entry will point to rightNode.

Parameters:

	rightNode	the right-hand split of the old root
	rightPageId	PageId corresponding to rightNode

Definition at line 442 of file BTreeWriter.cpp.

References BTreeNodeAccessor::accessTuple(), BTreeNodeAccessor::allocateEntry(), SegNodeLock< Node >::allocatePage(), BTreeNodeAccessor::clearNode(), BTreeNodeAccessor::dumpNode(), SegPageLock::flushPage(), TupleAccessor::getByteCount(), BTreeNode::getDataForRead(), BTreeNode::getDataForWrite(), BTreeAccessBase::getNodeAccessor(), SegNodeLock< Node >::getNodeForWrite(), BTreeAccessBase::getNonLeafNodeAccessor(), BTreeAccessBase::getPageOwnerId(), BTreeAccessBase::getSegment(), BTreeNode::height, TupleAccessor::marshal(), monotonic, BTreeNode::nEntries, NULL_PAGE_ID, BTreeReader::pageId, BTreeReader::pageLock, BTreeDescriptor::segmentAccessor, BTreeAccessBase::treeDescriptor, BTreeNodeAccessor::tupleAccessor, BTreeNodeAccessor::tupleData, SegPageLock::unlock(), and BTreeNodeAccessor::unmarshalKey().

Referenced by splitCurrentNode().

00444 {
00445     BTreeNode &node = pageLock.getNodeForWrite();
00446     BTreeNodeAccessor &nodeAccessor = getNodeAccessor(node);
00447     // GROW BTREE
00448     // the btree needs to grow. The root should have
00449     // two entries: one to the left page and one the right page.
00450     // and the btree needs to keep the old root page id.
00451 #if  0
00452     std::cerr << "before grow root:" << std::endl;
00453     nodeAccessor.dumpNode(std::cerr,node,pageId);
00454     std::cerr << "before grow right:" << std::endl;
00455     nodeAccessor.dumpNode(std::cerr,rightNode,rightPageId);
00456 #endif
00457 
00458     BTreePageLock newLeftPageLock(treeDescriptor.segmentAccessor);
00459     PageId newLeftPageId = newLeftPageLock.allocatePage(getPageOwnerId());
00460     BTreeNode &newLeftNode = newLeftPageLock.getNodeForWrite();
00461     nodeAccessor.clearNode(newLeftNode,getSegment()->getUsablePageSize());
00462     // 1. copy the content of old root page to the new page2. (left).
00463     newLeftNode = node;
00464     memcpy(
00465         newLeftNode.getDataForWrite(),
00466         node.getDataForRead(),
00467         getSegment()->getUsablePageSize() - sizeof(BTreeNode));
00468 
00469     // 1a. fix the prefetch links to match the games we're playing
00470     // with the root
00471     getSegment()->setPageSuccessor(newLeftPageId, rightPageId);
00472     getSegment()->setPageSuccessor(pageId, NULL_PAGE_ID);
00473 
00474     // 2. clear the root page and set the right height.
00475     // we use the old nodeAccessor to clear the node.
00476 
00477     nodeAccessor.clearNode(node,getSegment()->getUsablePageSize());
00478     node.height = newLeftNode.height + 1;
00479     BTreeNodeAccessor &rootNodeAccessor = getNonLeafNodeAccessor(node);
00480 
00481     // 3. add two entries to the root page.
00482 
00483     nodeAccessor.accessTuple(newLeftNode, newLeftNode.nEntries - 1);
00484     nodeAccessor.unmarshalKey(rootNodeAccessor.tupleData);
00485     rootNodeAccessor.tupleData.back().pData =
00486         reinterpret_cast<PConstBuffer>(&newLeftPageId);
00487     uint cb = rootNodeAccessor.tupleAccessor.getByteCount(
00488                         rootNodeAccessor.tupleData);
00489     PBuffer pBuffer1 = rootNodeAccessor.allocateEntry(node,0,cb);
00490     rootNodeAccessor.tupleAccessor.marshal(
00491                 rootNodeAccessor.tupleData, pBuffer1);
00492 
00493     nodeAccessor.accessTuple(rightNode, rightNode.nEntries - 1);
00494     nodeAccessor.unmarshalKey(rootNodeAccessor.tupleData);
00495     rootNodeAccessor.tupleData.back().pData =
00496             reinterpret_cast<PConstBuffer>(&rightPageId);
00497     cb = rootNodeAccessor.tupleAccessor.getByteCount(
00498                 rootNodeAccessor.tupleData);
00499 
00500     PBuffer pBuffer2 = rootNodeAccessor.allocateEntry(node,1,cb);
00501     rootNodeAccessor.tupleAccessor.marshal(
00502                         rootNodeAccessor.tupleData, pBuffer2);
00503 #if 0
00504     std::cerr << "after grow root:" << std::endl;
00505     rootNodeAccessor.dumpNode(std::cerr,node,pageId);
00506     std::cerr << "after grow left:" << std::endl;
00507     nodeAccessor.dumpNode(std::cerr,newLeftNode,newLeftPageId);
00508     std::cerr << "after grow right:" << std::endl;
00509     nodeAccessor.dumpNode(std::cerr,rightNode,rightPageId);
00510 #endif
00511     if (monotonic) {
00512         newLeftPageLock.flushPage(true);
00513     }
00514     newLeftPageLock.unlock();
00515     return;
00516 }

uint BTreeWriter::lockParentPage	(	uint	height,
		bool	rightMostNode
	)			`[private]`

Finds the parent page by using the page stack (plus searches if root splits are encountered).

On return, the result is in pageId, and the parent page has been accquired by pageLock.

Parameters:

	height	is the current height of the btree.
	rightMostNode	true if the node being split is the rightmost node at that level in the btree; thus, the entry in the parent page corresponding to that node is the infinity key

Returns:: 0-based entry position on parent page corresponding to searchKeyData

Definition at line 339 of file BTreeWriter.cpp.

References BTreeNodeAccessor::accessTuple(), BTreeNodeAccessor::binarySearch(), DUP_SEEK_ANY, BTreeNodeAccessor::getKeyCount(), BTreeAccessBase::getNodeAccessor(), SegNodeLock< Node >::getNodeForRead(), BTreeAccessBase::getRootPageId(), BTreeNode::height, BTreeAccessBase::keyDescriptor, LOCKMODE_S, LOCKMODE_X, SegPageLock::lockPageWithCoupling(), NULL_PAGE_ID, BTreeReader::pageId, BTreeReader::pageLock, pageStack, BTreeNode::rightSibling, BTreeReader::searchKeyData, BTreeDescriptor::segmentAccessor, BTreeAccessBase::treeDescriptor, BTreeNodeAccessor::tupleData, SegPageLock::unlock(), and BTreeNodeAccessor::unmarshalKey().

Referenced by splitCurrentNode().

00340 {
00341     assert(!pageStack.empty());
00342     pageId = pageStack.back();
00343     pageStack.pop_back();
00344 
00345     uint iPosition;
00346     for (;;) {
00347         pageLock.lockPageWithCoupling(pageId,LOCKMODE_X);
00348 
00349         bool found;
00350         BTreeNode const &parentNode = pageLock.getNodeForRead();
00351         if (pageId == getRootPageId() && parentNode.height != height+1) {
00352             // REVIEW jvs 12-Feb-2006:  I promised Xiaoyang I would
00353             // review this code, but I still haven't gotten to it.
00354             // Should only get here in page-level concurrency scenarios.
00355             // Also need to devise some tests which force this situation.
00356 
00357             // the tree has grown during the time.
00358             // the new root is not the parent any more.
00359             //
00360             pageLock.unlock();
00361             BTreePageLock stackPageLock(treeDescriptor.segmentAccessor);
00362             uint iPosition;
00363             for (;;) {
00364                 stackPageLock.lockPageWithCoupling(pageId,LOCKMODE_S);
00365                 bool found;
00366                 BTreeNode const &node = stackPageLock.getNodeForRead();
00367                 if (node.height == height) {
00368                     // it is the same level now. get out of the loop.
00369                     stackPageLock.unlock();
00370                     break;
00371                 }
00372                 BTreeNodeAccessor &nodeAccessor = getNodeAccessor(node);
00373 
00374                 iPosition = nodeAccessor.binarySearch(
00375                     node,
00376                     keyDescriptor,
00377                     searchKeyData,
00378                     DUP_SEEK_ANY,
00379                     true,
00380                     nodeAccessor.tupleData,
00381                     found);
00382                 nodeAccessor.accessTuple(node, iPosition);
00383                 nodeAccessor.unmarshalKey(nodeAccessor.tupleData);
00384                 if (iPosition == nodeAccessor.getKeyCount(node)) {
00385                     assert(!found);
00386                     // What we're searching for is bigger than everything on
00387                     // this node.  Have to search right.
00388                     if (node.rightSibling != NULL_PAGE_ID) {
00389                         pageId = node.rightSibling;
00390                         continue;
00391                     }
00392                 }
00393                 pageStack.push_back(pageId);
00394                 pageId = *(PageId *)(nodeAccessor.tupleData.back().pData);
00395                 stackPageLock.unlock();
00396             }
00397             pageId = pageStack.back();
00398             pageStack.pop_back();
00399             // now lock the real parent.
00400             pageLock.lockPageWithCoupling(pageId,LOCKMODE_X);
00401         }
00402 
00403         // we can not use parentNode because it might be changed.
00404         BTreeNode const &node = pageLock.getNodeForRead();
00405 
00406         BTreeNodeAccessor &nodeAccessor = getNodeAccessor(node);
00407         if (rightMostNode) {
00408             // If the split node is the rightmost node, return the position of
00409             // the rightmost entry in the parent node.
00410             iPosition = nodeAccessor.getKeyCount(node);
00411             break;
00412         }
00413 
00414         // TODO:  deal with duplicates here and above
00415 
00416         iPosition = nodeAccessor.binarySearch(
00417             node,
00418             keyDescriptor,
00419             searchKeyData,
00420             DUP_SEEK_ANY,
00421             true,
00422             nodeAccessor.tupleData,
00423             found);
00424 
00425         if (iPosition == nodeAccessor.getKeyCount(node)) {
00426             assert(!found);
00427             // What we're searching for is bigger than everything on
00428             // this node.  Have to search right.
00429             if (node.rightSibling != NULL_PAGE_ID) {
00430                 pageId = node.rightSibling;
00431                 continue;
00432             } else {
00433                 break;
00434             }
00435         }
00436         // it could be before the first entry, so not found is OK!
00437         break;
00438     }
00439     return iPosition;
00440 }

bool BTreeWriter::attemptInsertWithoutSplit	(	BTreePageLock &	targetPageLock,
		PConstBuffer	pTupleBuffer,
		uint	cbTuple,
		uint	iNewTuple
	)			`[private]`

Attempts to perform an insertion without splitting, performing compaction automatically if it will allow the insertion to succeed.

See warnings on compactNode.

Parameters:

	targetPageLock	lock on node into which tuple is to be inserted
	pTupleBuffer	buffer containing the tuple being inserted
	cbTuple	number of bytes in pTupleBuffer
	iNewTuple	desired 0-based position for new tuple

Returns:: true if insertion succeeded; false if a split is required

Definition at line 143 of file BTreeWriter.cpp.

Referenced by insertTupleFromBuffer(), and splitCurrentNode().

00146 {
00147     BTreeNode *pNode = &(targetPageLock.getNodeForWrite());
00148     BTreeNodeAccessor &nodeAccessor = getNodeAccessor(*pNode);
00149     switch (nodeAccessor.calculateCapacity(*pNode,cbTuple)) {
00150     case BTreeNodeAccessor::CAN_FIT:
00151         break;
00152     case BTreeNodeAccessor::CAN_FIT_WITH_COMPACTION:
00153         compactNode(pageLock);
00154         // compactNode uses swapBuffers, which is why we have to use a pointer
00155         // rather than a reference for pNode
00156         pNode = &(targetPageLock.getNodeForWrite());
00157         assert(nodeAccessor.calculateCapacity(*pNode,cbTuple)
00158                == BTreeNodeAccessor::CAN_FIT);
00159 
00160 #if 0
00161         std::cerr << "AFTER COMPACTION:" << std::endl;
00162         nodeAccessor.dumpNode(std::cerr,*pNode,pageId);
00163 #endif
00164 
00165         break;
00166     case BTreeNodeAccessor::CAN_NOT_FIT:
00167         return false;
00168     }
00169     PBuffer pBuffer = nodeAccessor.allocateEntry(*pNode,iPosition,cbTuple);
00170     memcpy(pBuffer,pTupleBuffer,cbTuple);
00171     return true;
00172 }

void BTreeWriter::insertLogged ( ByteInputStream & logStream ) [private]

Inserts a tuple read from a log stream.

Parameters:

logStream

stream containing tuple image

Definition at line 661 of file BTreeWriter.cpp.

References ByteInputStream::consumeReadPointer(), DUP_ALLOW, ByteInputStream::getReadPointer(), and insertTupleFromBuffer().

Referenced by redoLogicalAction(), and undoLogicalAction().

00662 {
00663     // REVIEW:  do we ever need to use a different Distinctness?
00664     uint cbTuple = insertTupleFromBuffer(
00665         logStream.getReadPointer(1),DUP_ALLOW);
00666     logStream.consumeReadPointer(cbTuple);
00667 }

void BTreeWriter::deleteLogged ( ByteInputStream & logStream ) [private]

Deletes a tuple read from a log stream.

Parameters:

logStream

stream containing tuple image

Definition at line 669 of file BTreeWriter.cpp.

References ByteInputStream::consumeReadPointer(), deleteCurrent(), DUP_SEEK_ANY, BTreeReader::endSearch(), ByteInputStream::getReadPointer(), BTreeAccessBase::pLeafNodeAccessor, BTreeReader::searchForKey(), and BTreeReader::searchKeyData.

Referenced by redoLogicalAction(), and undoLogicalAction().

00670 {
00671     pLeafNodeAccessor->tupleAccessor.setCurrentTupleBuf(
00672         logStream.getReadPointer(1));
00673     uint cbTuple = pLeafNodeAccessor->tupleAccessor.getCurrentByteCount();
00674     pLeafNodeAccessor->unmarshalKey(searchKeyData);
00675     if (searchForKey(searchKeyData,DUP_SEEK_ANY)) {
00676         deleteCurrent();
00677     } else {
00678         // TODO:  assert?
00679     }
00680     endSearch();
00681     logStream.consumeReadPointer(cbTuple);
00682 }

bool BTreeWriter::positionSearchKey ( BTreeNodeAccessor & nodeAccessor ) [private]

Positions search key for insert, also detecting duplicate key values.

Parameters:

nodeAccessor

node accessor for leaf node

Returns:: true if duplicate key found

Definition at line 689 of file BTreeWriter.cpp.

References DUP_SEEK_ANY, DUP_SEEK_END, BTreeAccessBase::getRootPageId(), monotonic, pageStack, BTreeReader::READ_ALL, BTreeReader::rootLockMode, BTreeReader::searchKeyData, and BTreeNodeAccessor::unmarshalKey().

Referenced by insertTupleFromBuffer().

00690 {
00691     nodeAccessor.unmarshalKey(searchKeyData);
00692     pageStack.clear();
00693     DuplicateSeek seekMode = (monotonic) ? DUP_SEEK_END : DUP_SEEK_ANY;
00694     bool duplicate = searchForKeyTemplate< true, std::vector<PageId> >(
00695         searchKeyData,seekMode,true,pageStack,getRootPageId(),rootLockMode,
00696         READ_ALL);
00697     return duplicate;
00698 }

bool BTreeWriter::checkMonotonicity	(	BTreeNodeAccessor &	nodeAccessor,
		PConstBuffer	pTupleBuffer
	)			`[private]`

Checks to ensure that when monotonic insert mode is used, the keys really are increasing.

Note though that the check is only done for the 2nd and subsequent keys on a leaf page. I.e., the check is not done across page boundaries.

Parameters:

	nodeAccessor	node accessor for leaf node
	pTupleBuffer	tuple buffer for new key to be inserted

Returns:: true if new key is > previous key and it will be inserted in the last position in the node

Definition at line 700 of file BTreeWriter.cpp.

References BTreeReader::accessTupleInline(), TupleDescriptor::compareTuples(), BTreeReader::comparisonKeyData, SegNodeLock< Node >::getNodeForRead(), BTreeReader::iTupleOnLowestLevel, BTreeAccessBase::keyDescriptor, BTreeNode::nEntries, BTreeReader::pageLock, BTreeReader::searchKeyData, TupleAccessor::setCurrentTupleBuf(), BTreeNodeAccessor::tupleAccessor, and BTreeNodeAccessor::unmarshalKey().

Referenced by insertTupleFromBuffer().

00702 {
00703     // unmarshal previous key, if accessible
00704     if (iTupleOnLowestLevel == 0) {
00705         return true;
00706     }
00707     BTreeNode const &node = pageLock.getNodeForRead();
00708     accessTupleInline(node, iTupleOnLowestLevel - 1);
00709     nodeAccessor.unmarshalKey(comparisonKeyData);
00710 
00711     nodeAccessor.tupleAccessor.setCurrentTupleBuf(pTupleBuffer);
00712     nodeAccessor.unmarshalKey(searchKeyData);
00713     int keyComp = keyDescriptor.compareTuples(comparisonKeyData, searchKeyData);
00714 
00715     return (keyComp <= 0 && node.nEntries == iTupleOnLowestLevel);
00716 }

void BTreeWriter::insertTupleData	(	TupleData const &	tupleData,
		Distinctness	distinctness
	)

Inserts a tuple from unmarshalled TupleData form; requires this writer to already be positioned to the correct location (the caller is trusted, with no verification).

See insertTupleFromBuffer for duplicate handling.

Parameters:

	tupleData	tuple to be inserted
	distinctness	how to handle duplicates

Definition at line 59 of file BTreeWriter.cpp.

References insertTupleFromBuffer(), leafTupleBuffer, and BTreeAccessBase::pLeafNodeAccessor.

00061 {
00062     // TODO:  a small optimization is to use unmarshalled key data directly
00063     pLeafNodeAccessor->tupleAccessor.marshal(tupleData,leafTupleBuffer.get());
00064     insertTupleFromBuffer(leafTupleBuffer.get(),distinctness);
00065 }

uint BTreeWriter::insertTupleFromBuffer	(	PConstBuffer	pTupleBuffer,
		Distinctness	distinctness
	)

Inserts a tuple from a marshalled tuple buffer.

If the key already exists, and distinctness is set to DUP_FAIL, a BTreeDuplicateKeyExcn will be thrown (or an assertion failure if monotonic mode is enabled). If distinctness is set to DUP_DISCARD, the new tuple is not inserted. Otherwise (DUP_ALLOW), the tuple is inserted with a duplicate key. In monotonic mode, only DUP_FAIL is allowed.

Parameters:

	pTupleBuffer	buffer containing tuple to be inserted
	distinctness	how to handle duplicates

Definition at line 67 of file BTreeWriter.cpp.

References ACTION_INSERT, attemptInsertWithoutSplit(), LogicalTxn::beginLogicalAction(), checkMonotonicity(), ByteOutputStream::consumeWritePointer(), TupleData::containsNull(), DUP_ALLOW, DUP_DISCARD, LogicalTxn::endLogicalAction(), BTreeReader::endSearch(), TupleAccessor::getCurrentByteCount(), LogicalTxnParticipant::getLogicalTxn(), ByteOutputStream::getWritePointer(), LogicalTxnParticipant::isLoggingEnabled(), BTreeReader::isPositioned(), BTreeReader::iTupleOnLowestLevel, BTreeAccessBase::keyDescriptor, monotonic, BTreeReader::pageLock, BTreeAccessBase::pLeafNodeAccessor, positionSearchKey(), TuplePrinter::print(), BTreeReader::searchKeyData, TupleAccessor::setCurrentTupleBuf(), splitCurrentNode(), BTreeNodeAccessor::tupleAccessor, and BTreeAccessBase::validateTupleSize().

Referenced by insertLogged(), insertTupleData(), BTreeTxnTest::insertTxn(), BTreeTest::testInserts(), and BTreeTest::testMultiKeySearches().

00069 {
00070     BTreeNodeAccessor &nodeAccessor = *pLeafNodeAccessor;
00071     nodeAccessor.tupleAccessor.setCurrentTupleBuf(pTupleBuffer);
00072 
00073     validateTupleSize(nodeAccessor.tupleAccessor);
00074 
00075     uint cbTuple = nodeAccessor.tupleAccessor.getCurrentByteCount();
00076 
00077 #if 0
00078     TuplePrinter tuplePrinter;
00079     tuplePrinter.print(std::cout, keyDescriptor, searchKeyData);
00080     std::cout << std::endl;
00081 #endif
00082 
00083     // monotonic inserts do not need to search for key; we will always
00084     // be inserting after where we are positioned except the first time
00085     // through or after a split, where we will need to do an initial search
00086     // to setup the appropriate position
00087     if (monotonic) {
00088         if (isPositioned()) {
00089             ++iTupleOnLowestLevel;
00090             assert(checkMonotonicity(nodeAccessor, pTupleBuffer));
00091         } else {
00092             positionSearchKey(nodeAccessor);
00093         }
00094     } else {
00095         bool duplicate = positionSearchKey(nodeAccessor);
00096 
00097         // REVIEW:  This implements the SQL semantics whereby keys with null
00098         // values are considered duplicates for DISTINCT but not for UNIQUE.
00099         // Should probably introduce new DUP_ options to make it explicit.
00100         if (duplicate) {
00101             switch (distinctness) {
00102             case DUP_ALLOW:
00103                 break;
00104             case DUP_DISCARD:
00105                 endSearch();
00106                 return cbTuple;
00107             default:
00108                 if (!searchKeyData.containsNull()) {
00109                     endSearch();
00110                     throw BTreeDuplicateKeyExcn(keyDescriptor,searchKeyData);
00111                 }
00112             }
00113         }
00114     }
00115 
00116     if (isLoggingEnabled()) {
00117         ByteOutputStream &logStream = getLogicalTxn()->beginLogicalAction(
00118             *this,
00119             ACTION_INSERT);
00120         memcpy(
00121             logStream.getWritePointer(cbTuple),
00122             pTupleBuffer,
00123             cbTuple);
00124         logStream.consumeWritePointer(cbTuple);
00125         getLogicalTxn()->endLogicalAction();
00126     }
00127 
00128     bool split = !attemptInsertWithoutSplit(
00129         pageLock,pTupleBuffer,cbTuple,iTupleOnLowestLevel);
00130     if (split) {
00131         splitCurrentNode(pTupleBuffer,cbTuple,iTupleOnLowestLevel);
00132     }
00133 
00134     // restart the search after a split even if monotonic insert to
00135     // ensure correct path to newnode
00136     if (!monotonic || split) {
00137         endSearch();
00138     }
00139 
00140     return cbTuple;
00141 }

void BTreeWriter::deleteCurrent ( )

Deletes the current tuple.

Can be called after one of the BTreeReader search methods. Deletion invalidates the current tuple, but the next tuple can still be accessed by calling searchNext().

Definition at line 527 of file BTreeWriter.cpp.

References ACTION_DELETE, LogicalTxn::beginLogicalAction(), ByteOutputStream::consumeWritePointer(), BTreeNodeAccessor::deallocateEntry(), LogicalTxn::endLogicalAction(), TupleAccessor::getCurrentByteCount(), TupleAccessor::getCurrentTupleBuf(), BTreeAccessBase::getLeafNodeAccessor(), LogicalTxnParticipant::getLogicalTxn(), SegNodeLock< Node >::getNodeForWrite(), ByteOutputStream::getWritePointer(), SegPageLock::isLocked(), LogicalTxnParticipant::isLoggingEnabled(), BTreeReader::iTupleOnLowestLevel, optimizeRootLockMode(), BTreeReader::pageLock, and BTreeNodeAccessor::tupleAccessor.

Referenced by deleteLogged(), BTreeTxnTest::deleteTxn(), BTreeTest::testMultiKeySearches(), and BTreeTest::testScan().

00528 {
00529     // TODO:  Balancing, all that jazz?  Maybe.
00530 
00531     assert(pageLock.isLocked());
00532 
00533     optimizeRootLockMode();
00534 
00535     BTreeNode &node = pageLock.getNodeForWrite();
00536     BTreeNodeAccessor &nodeAccessor = getLeafNodeAccessor(node);
00537 
00538     if (isLoggingEnabled()) {
00539         uint cbTuple = nodeAccessor.tupleAccessor.getCurrentByteCount();
00540         ByteOutputStream &logStream = getLogicalTxn()->beginLogicalAction(
00541             *this,
00542             ACTION_DELETE);
00543         memcpy(
00544             logStream.getWritePointer(cbTuple),
00545             nodeAccessor.tupleAccessor.getCurrentTupleBuf(),
00546             cbTuple);
00547         logStream.consumeWritePointer(cbTuple);
00548         getLogicalTxn()->endLogicalAction();
00549     }
00550 
00551     nodeAccessor.deallocateEntry(node,iTupleOnLowestLevel);
00552 
00553     // precompensate for subsequent calls to searchNext()
00554     --iTupleOnLowestLevel;
00555 }

bool BTreeWriter::updateCurrent ( TupleData const & tupleData )

Attempts to update the current tuple's value without changing its key and without splitting the page.

Can be called after one of the BTreeReader search methods. It is the caller's responsibility to ensure that the key is preserved (otherwise index corruption results). This action is NOT logged; an assertion failure will result if logging is enabled.

Parameters:

tupleData

new tuple data

Returns:: true if successful; false if request failed because a split would have been required

Definition at line 557 of file BTreeWriter.cpp.

00558 {
00559     // TODO:  assert that key has not changed
00560 
00561     PBuffer pTupleBuf;
00562 
00563     assert(pageLock.isLocked());
00564 
00565     optimizeRootLockMode();
00566 
00567     BTreeNode *pNode = &(pageLock.getNodeForWrite());
00568     BTreeNodeAccessor &nodeAccessor = getLeafNodeAccessor(*pNode);
00569 
00570     assert(!isLoggingEnabled());
00571 
00572     if (nodeAccessor.hasFixedWidthEntries()) {
00573         // we can use a direct overwrite
00574         pTupleBuf = const_cast<PBuffer>(
00575             nodeAccessor.getEntryForRead(*pNode,iTupleOnLowestLevel));
00576         nodeAccessor.tupleAccessor.marshal(tupleData,pTupleBuf);
00577         return true;
00578     }
00579 
00580     // calculate whether updated tuple can fit
00581     uint cbTuple =
00582         nodeAccessor.tupleAccessor.getByteCount(tupleData);
00583     int cbDelta =
00584         cbTuple - nodeAccessor.tupleAccessor.getCurrentByteCount();
00585     if (cbDelta < 0) {
00586         cbDelta = 0;
00587     }
00588 
00589     // NOTE:  there's a tiny discrepancy here due to entry overhead, but it
00590     // errs on the safe side, so ignore it
00591     switch (nodeAccessor.calculateCapacity(*pNode,cbDelta)) {
00592     case BTreeNodeAccessor::CAN_FIT:
00593         nodeAccessor.deallocateEntry(*pNode,iTupleOnLowestLevel);
00594         break;
00595     case BTreeNodeAccessor::CAN_FIT_WITH_COMPACTION:
00596         nodeAccessor.deallocateEntry(*pNode,iTupleOnLowestLevel);
00597         compactNode(pageLock);
00598         // compactNode uses swapBuffers, which is why we have to use a pointer
00599         // rather than a reference for pNode
00600         pNode = &(pageLock.getNodeForWrite());
00601         assert(nodeAccessor.calculateCapacity(*pNode,cbTuple)
00602                == BTreeNodeAccessor::CAN_FIT);
00603         break;
00604     case BTreeNodeAccessor::CAN_NOT_FIT:
00605         return false;
00606     default:
00607         permAssert(false);
00608     }
00609 
00610     pTupleBuf = nodeAccessor.allocateEntry(*pNode,iTupleOnLowestLevel,cbTuple);
00611     nodeAccessor.tupleAccessor.marshal(tupleData,pTupleBuf);
00612     return true;
00613 }

void BTreeWriter::releaseScratchBuffers ( )

Releases any allocated scratch buffers.

Definition at line 684 of file BTreeWriter.cpp.

References scratchPageLock, and SegPageLock::unlock().

00685 {
00686     scratchPageLock.unlock();
00687 }

LogicalTxnClassId BTreeWriter::getParticipantClassId ( ) const [virtual]

Returns:: the LogicalTxnClassId for this participant; this will be used during recovery to find the correct LogicalTxnParticipantFactory

Implements LogicalTxnParticipant.

Definition at line 615 of file BTreeWriter.cpp.

References BTreeRecoveryFactory::getParticipantClassId().

00616 {
00617     return BTreeRecoveryFactory::getParticipantClassId();
00618 }

void BTreeWriter::describeParticipant ( ByteOutputStream & logStream ) [virtual]

Called by LogicalTxn the first time an action is logged for this participant.

The participant must implement this by writing a description of itself to the given output stream. This information must be sufficient for reconstructing the participant during recovery.

Parameters:

logStream

stream to which the participant description should be written

Implements LogicalTxnParticipant.

Definition at line 620 of file BTreeWriter.cpp.

References BTreeAccessBase::getKeyProjection(), BTreeAccessBase::getRootPageId(), BTreeAccessBase::getTupleDescriptor(), TupleProjection::writePersistent(), TupleDescriptor::writePersistent(), and ByteOutputStream::writeValue().

00622 {
00623     PageId rootPageId = getRootPageId();
00624     logStream.writeValue(rootPageId);
00625     getTupleDescriptor().writePersistent(logStream);
00626     getKeyProjection().writePersistent(logStream);
00627 }

void BTreeWriter::undoLogicalAction	(	LogicalActionType	actionType,
		ByteInputStream &	logStream
	)			`[virtual]`

Performs undo for one logical action during rollback or recovery.

The implementation must consume ALL log data for this action, even if some of it turns out to be unneeded.

Parameters:

	actionType	the type of action to undo; the rest of the action parameters should be read from the LogicalTxn's input stream
	logStream	stream from which to read action data

Implements LogicalTxnParticipant.

Definition at line 629 of file BTreeWriter.cpp.

References ACTION_DELETE, ACTION_INSERT, deleteLogged(), and insertLogged().

00632 {
00633     switch (actionType) {
00634     case ACTION_INSERT:
00635         deleteLogged(logStream);
00636         break;
00637     case ACTION_DELETE:
00638         insertLogged(logStream);
00639         break;
00640     default:
00641         permAssert(false);
00642     }
00643 }

void BTreeWriter::redoLogicalAction	(	LogicalActionType	actionType,
		ByteInputStream &	logStream
	)			`[virtual]`

Performs redo for one logical action during recovery.

The implementation must consume ALL log data for this action, even if some of it turns out to be unneeded.

Parameters:

	actionType	the type of action to redo; the rest of the action parameters should be read from the LogicalTxn's input stream
	logStream	stream from which to read action data

Implements LogicalTxnParticipant.

Definition at line 645 of file BTreeWriter.cpp.

References ACTION_DELETE, ACTION_INSERT, deleteLogged(), and insertLogged().

00648 {
00649     switch (actionType) {
00650     case ACTION_INSERT:
00651         insertLogged(logStream);
00652         break;
00653     case ACTION_DELETE:
00654         deleteLogged(logStream);
00655         break;
00656     default:
00657         permAssert(false);
00658     }
00659 }

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 }

bool BTreeReader::adjustRootLockMode ( LockMode & lockMode ) [inline, protected, inherited]

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

When that happens, and rootLockMode != leafLockMode, we have to compensate.

Parameters:

lockMode

the lock mode used to lock a root+leaf; receives the adjusted lock mode on return

Returns:: false if the adjustment requires the original operation to be restarted

Reimplemented in BTreeLeafReader, and BTreeNonLeafReader.

Definition at line 53 of file BTreeReaderImpl.h.

References BTreeReader::leafLockMode, BTreeReader::pageLock, BTreeReader::rootLockMode, SegPageLock::tryUpgrade(), and SegPageLock::unlock().

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

00054 {
00055     if (lockMode == leafLockMode) {
00056         // We already got the correct lock mode.
00057         return true;
00058     }
00059 
00060     // Oops, we got the wrong lock mode.  Next time we'll get it right.
00061     rootLockMode = leafLockMode;
00062     lockMode = leafLockMode;
00063 
00064     // We can try an upgrade.  If it succeeds, great.  Otherwise, it will fail
00065     // immediately so we can do it the hard way.
00066     if (pageLock.tryUpgrade()) {
00067         return true;
00068     }
00069 
00070     // Shucks, have to unlock and retry original operation.
00071     pageLock.unlock();
00072     return false;
00073 }

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 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(), BTreeNonLeafReader::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::searchExtreme ( bool first ) [protected, virtual, inherited]

Searches for the first or last tuple in the tree.

Parameters:

first

true for first; false for last

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

Reimplemented in BTreeLeafReader, and BTreeNonLeafReader.

Definition at line 49 of file BTreeReader.cpp.

References BTreeReader::READ_ALL, and BTreeReader::searchExtremeInternal().

Referenced by BTreeReader::searchFirst(), and BTreeReader::searchLast().

00050 {
00051     return searchExtremeInternal(first, READ_ALL);
00052 }

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 BTreeNonLeafReader::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 BTreeNonLeafReader::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 }

TupleAccessor const & BTreeReader::getTupleAccessorForRead ( ) const [inherited]

Gets a read-only accessor for leaf tuples.

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

Returns:: the leaf tuple accessor

Reimplemented in BTreeNonLeafReader.

Definition at line 173 of file BTreeReader.cpp.

References BTreeAccessBase::pLeafNodeAccessor.

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

00174 {
00175     return pLeafNodeAccessor->tupleAccessor;
00176 }

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 }

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

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

NOTE jvs 27-May-2007: This method's interface has some problems; resolving http://issues.eigenbase.org/browse/FNL-65 will involve coming up with a more rational interface. In particular, note that the return value is unreliable in the case of DUP_SEEK_END, and should be ignored by callers.

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 in BTreeLeafReader, and BTreeNonLeafReader.

Definition at line 145 of file BTreeReader.cpp.

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

Referenced by deleteLogged(), BTreeTxnTest::deleteTxn(), BTreeTxnTest::scanTxn(), BTreeTest::testInserts(), BTreeTest::testMultiKeySearches(), and BTreeTest::testSearch().

00147 {
00148     return
00149         searchForKeyInternal(
00150             key, dupSeek, leastUpper, getRootPageId(), rootLockMode, READ_ALL);
00151 }

bool BTreeReader::searchNext ( ) [virtual, inherited]

Searches for the next tuple.

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 in BTreeLeafReader, and BTreeNonLeafReader.

Definition at line 115 of file BTreeReader.cpp.

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

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

00116 {
00117     assert(pageLock.isLocked());
00118     assert(!pageLock.getNodeForRead().height);
00119     return searchNextInternal();
00120 }

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 deleteLogged(), BTreeTxnTest::deleteTxn(), BTreeLeafReader::endSearch(), 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 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(), deleteCurrent(), and 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 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(), attemptInsertWithoutSplit(), BTreeReader::binarySearch(), compactNode(), BTreeReader::compareFirstKey(), grow(), lockParentPage(), 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, 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 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 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(), compactNode(), BTreeBuilder::createEmptyRoot(), BTreeAccessBase::getRightSibling(), grow(), BTreeAccessBase::setRightSibling(), 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(), describeParticipant(), LcsClusterReplaceExecStream::getTupleForLoad(), LbmSplicerExecStream::getValidatedTuple(), BTreeNonLeafReader::isRootOnly(), LcsClusterReplaceExecStreamTest::loadCluster(), LcsMultiClusterAppendTest::loadClusters(), LcsRowScanExecStreamTest::loadOneCluster(), LbmSearchTest::loadTableAndIndex(), lockParentPage(), optimizeRootLockMode(), 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 ) [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(), grow(), and 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 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 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 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 }

LogicalTxn * LogicalTxnParticipant::getLogicalTxn ( ) [inline, protected, inherited]

Returns:: LogicalTxn being participated in, or null if no txn in progress; null is also returned during recovery

Definition at line 111 of file LogicalTxnParticipant.h.

References LogicalTxnParticipant::pTxn.

Referenced by LogicalTxnTest::commit(), deleteCurrent(), FtrsTableWriter::execute(), DatabaseTest::executeIncrementAction(), insertTupleFromBuffer(), LogicalTxnTest::rollbackFull(), LogicalTxnTest::testActions(), LogicalTxnTest::testCheckpointCommitSavepoint(), LogicalTxnTest::testRollbackSavepoint(), LogicalTxnTest::testTxn(), and LogicalTxnTest::testTxnIdSequence().

00112 {
00113     return pTxn;
00114 }

bool LogicalTxnParticipant::isLoggingEnabled ( ) const [inline, protected, inherited]

Returns:: true if actions should be logged; this is false during recovery

Definition at line 116 of file LogicalTxnParticipant.h.

References LogicalTxnParticipant::loggingEnabled.

Referenced by deleteCurrent(), FtrsTableWriter::execute(), insertTupleFromBuffer(), and updateCurrent().

00117 {
00118     return loggingEnabled;
00119 }

Member Data Documentation

const LogicalActionType BTreeWriter::ACTION_INSERT = 1 [static, private]

LogicalActionType for inserting an entry into a BTree.

Definition at line 45 of file BTreeWriter.h.

Referenced by insertTupleFromBuffer(), redoLogicalAction(), and undoLogicalAction().

const LogicalActionType BTreeWriter::ACTION_DELETE = 2 [static, private]

LogicalActionType for deleting an entry from a BTree.

Definition at line 50 of file BTreeWriter.h.

Referenced by deleteCurrent(), redoLogicalAction(), and undoLogicalAction().

SegmentAccessor BTreeWriter::scratchAccessor [private]

Accessor for scratch segment.

Definition at line 55 of file BTreeWriter.h.

Referenced by BTreeWriter().

BTreePageLock BTreeWriter::scratchPageLock [private]

Lock on scratch page used during splits.

Definition at line 60 of file BTreeWriter.h.

Referenced by BTreeWriter(), compactNode(), and releaseScratchBuffers().

std::vector<PageId> BTreeWriter::pageStack [private]

Stack of rightmost non-leaf pages seen while searching in preparation for an insertion; this is used in reverse while splitting.

Definition at line 66 of file BTreeWriter.h.

Referenced by lockParentPage(), positionSearchKey(), and splitCurrentNode().

boost::scoped_array<FixedBuffer> BTreeWriter::splitTupleBuffer [private]

Buffer used for storing entry to be inserted into parent node during split.

Definition at line 72 of file BTreeWriter.h.

Referenced by BTreeWriter(), and splitCurrentNode().

boost::scoped_array<FixedBuffer> BTreeWriter::leafTupleBuffer [private]

Buffer used for marshalling in insertTupleData.

Definition at line 77 of file BTreeWriter.h.

Referenced by BTreeWriter(), and insertTupleData().

bool BTreeWriter::monotonic [private]

If true, caller promises inserts will be strictly increasing.

Definition at line 82 of file BTreeWriter.h.

Referenced by BTreeWriter(), grow(), insertTupleFromBuffer(), positionSearchKey(), and splitCurrentNode().

BTreePageLock BTreeReader::pageLock [protected, inherited]

PageId BTreeReader::pageId [protected, inherited]

PageId of node being searched.

Definition at line 80 of file BTreeReader.h.

Referenced by attemptInsertWithoutSplit(), grow(), lockParentPage(), optimizeRootLockMode(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKeyTemplate(), BTreeReader::searchNextInternal(), and splitCurrentNode().

uint BTreeReader::iTupleOnLowestLevel [protected, inherited]

0-based position on lowest level searched by the reader.

Definition at line 85 of file BTreeReader.h.

Referenced by BTreeReader::accessLeafTuple(), checkMonotonicity(), deleteCurrent(), insertTupleFromBuffer(), BTreeNonLeafReader::isPositionedOnInfinityKey(), BTreeLeafReader::searchExtreme(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKeyTemplate(), BTreeLeafReader::searchNext(), BTreeReader::searchNextInternal(), and updateCurrent().

bool BTreeReader::singular [protected, inherited]

See also:: isSingular()

Definition at line 90 of file BTreeReader.h.

Referenced by BTreeReader::BTreeReader(), BTreeReader::endSearch(), BTreeReader::isSingular(), BTreeLeafReader::searchExtreme(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKeyInternal(), BTreeReader::searchForKeyTemplate(), BTreeLeafReader::searchNext(), and BTreeReader::searchNextInternal().

LockMode BTreeReader::rootLockMode [protected, inherited]

LockMode to use when acquiring lock on root node.

Definition at line 95 of file BTreeReader.h.

Referenced by BTreeReader::adjustRootLockMode(), BTreeReader::BTreeReader(), BTreeNonLeafReader::isRootOnly(), optimizeRootLockMode(), positionSearchKey(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKey(), and BTreeNonLeafReader::searchForKey().

LockMode BTreeReader::nonLeafLockMode [protected, inherited]

LockMode to use when acquiring lock on non-leaf nodes other than the root.

Definition at line 101 of file BTreeReader.h.

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

LockMode BTreeReader::leafLockMode [protected, inherited]

LockMode to use when acquiring lock on leaf nodes.

Definition at line 106 of file BTreeReader.h.

Referenced by BTreeReader::adjustRootLockMode(), BTreeLeafReader::adjustRootLockMode(), BTreeReader::BTreeReader(), BTreeWriter(), BTreeLeafReader::searchExtreme(), BTreeReader::searchExtremeInternal(), BTreeLeafReader::searchForKey(), BTreeReader::searchForKeyTemplate(), and BTreeReader::searchNextInternal().

TupleData BTreeReader::comparisonKeyData [protected, inherited]

TupleData used as a temp variable for comparisons while searching.

Definition at line 111 of file BTreeReader.h.

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

TupleData const* BTreeReader::pSearchKey [protected, inherited]

Key being sought.

NULL except while search in progress.

Definition at line 116 of file BTreeReader.h.

Referenced by BTreeReader::BTreeReader(), BTreeReader::getSearchKey(), BTreeReader::searchForKeyInternal(), and BTreeReader::searchForKeyTemplate().

TupleData BTreeReader::searchKeyData [protected, inherited]

TupleData for key used in searches.

Definition at line 121 of file BTreeReader.h.

Referenced by BTreeReader::BTreeReader(), checkMonotonicity(), deleteLogged(), BTreeReader::getSearchKeyForWrite(), insertTupleFromBuffer(), lockParentPage(), positionSearchKey(), and splitCurrentNode().

BTreeDescriptor BTreeAccessBase::treeDescriptor [protected, inherited]

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::BTreeVerifier(), checkMonotonicity(), BTreeReader::compareFirstKey(), BTreeAccessBase::getKeyDescriptor(), insertTupleFromBuffer(), lockParentPage(), BTreeReader::searchForKeyTemplate(), and BTreeVerifier::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 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(), BTreeBuilder::build(), BTreeBuilder::buildBalanced(), BTreeAccessBase::getChildForCurrent(), BTreeAccessBase::getNodeAccessor(), BTreeNonLeafReader::getNonLeafNodeAccessor(), BTreeAccessBase::getNonLeafNodeAccessor(), BTreeNonLeafReader::getTupleAccessorForRead(), BTreeBuilder::growTree(), VariableBuildLevel::indexLastKey(), 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(), BTreeBuilder::build(), BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), BTreeBuilder::createEmptyRoot(), deleteLogged(), BTreeReader::endSearch(), BTreeAccessBase::getLeafNodeAccessor(), BTreeAccessBase::getNodeAccessor(), BTreeReader::getTupleAccessorForRead(), BTreeBuilder::growTree(), insertTupleData(), 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:

/home/pub/open/dev/fennel/btree/BTreeWriter.h
/home/pub/open/dev/fennel/btree/BTreeWriter.cpp

Generated on Mon Jun 22 04:00:26 2009 for Fennel by

1.5.1

BTreeWriter Class Reference

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation