Fennel: BTreeCompactNodeAccessor Class Reference (original) (raw)

BTreeCompactNodeAccessor maintains the data on a BTreeNode as a compact array of fixed-length entries, with all free space contiguous at the end of the page. More...

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

Inheritance diagram for BTreeCompactNodeAccessor:

List of all members.

Public Types
enum Capacity { CAN_FIT, CAN_FIT_WITH_COMPACTION, CAN_NOT_FIT }
Enumeration used to classify the storage state of a node which is targeted for insertion. More...
Public Member Functions
BTreeCompactNodeAccessor ()
PConstBuffer getEntryForReadInline (BTreeNode const &node, uint iEntry)
virtual void onInit ()
Receives notification from BTreeAccessBase after tupleDescriptor has been set up.
virtual PBuffer allocateEntry (BTreeNode &node, uint iEntry, uint cbEntry)
Allocates space for a new tuple.
virtual void deallocateEntry (BTreeNode &node, uint iEntry)
Deallocates the space for an existing tuple.
virtual bool hasFixedWidthEntries () const
**Returns:**true iff this NodeAccessor always stores tuples in fixed-width slots (even if the tuples themselves are variable-length)
virtual Capacity calculateCapacity (BTreeNode const &node, uint cbEntry)
Determines whether a tuple can be inserted into a node.
virtual uint getEntryByteCount (uint cbTuple)
Determines the storage required for a tuple, including any overhead.
virtual void compactNode (BTreeNode &node, BTreeNode &scratchNode)
Performs compaction on a node.
uint getKeyCount (BTreeNode const &node) const
Gets the number of keys stored on a node.
virtual void clearNode (BTreeNode &node, uint cbPage)
Clears the contents of a node, converting it to an empty root.
virtual PConstBuffer getEntryForRead (BTreeNode const &node, uint iEntry)=0
Gets the location of a stored tuple.
void dumpNode (std::ostream &os, BTreeNode const &node, PageId pageId)
Dumps the contents of a node.
virtual void accessTuple (BTreeNode const &node, uint iEntry)=0
Binds tupleAccessor to a stored tuple.
virtual uint binarySearch (BTreeNode const &node, TupleDescriptor const &keyDescriptor, TupleData const &searchKey, DuplicateSeek dupSeek, bool leastUpper, TupleData &scratchKey, bool &found)=0
Searches for a tuple based on a key.
virtual int compareFirstKey (BTreeNode const &node, TupleDescriptor const &keyDescriptor, TupleData const &searchKey, TupleData &scratchKey)=0
Compare first key on a node to provided search key.
virtual void accessTupleInline (BTreeNode const &node, uint iEntry)=0
Sets tuple accessor to provided node entry.
virtual void unmarshalKey (TupleData &keyData)=0
Unmarshals the key for the current tuple after a call to accessTuple.
virtual void splitNode (BTreeNode &node, BTreeNode &newNode, uint cbNewTuple, bool monotonic)
Splits a node.
Public Attributes
TupleDescriptor tupleDescriptor
Descriptor for tuples stored on nodes accessed by this.
TupleAccessor tupleAccessor
Accessor for tuples stored on nodes accessed by this.
TupleData tupleData
TupleData for tuples stored on nodes accessed by this.
Private Attributes
uint cbEntry
Number of bytes per entry.

Detailed Description

BTreeCompactNodeAccessor maintains the data on a BTreeNode as a compact array of fixed-length entries, with all free space contiguous at the end of the page.

TODO: a high-performance template for builtin datatypes

Definition at line 40 of file BTreeCompactNodeAccessor.h.

Member Enumeration Documentation

Enumeration used to classify the storage state of a node which is targeted for insertion.

Enumerator:

CAN_FIT The tuple can fit without compaction.
CAN_FIT_WITH_COMPACTION The tuple can fit, but only after compaction.
CAN_NOT_FIT The tuple can't fit. Compaction wouldn't help.

Definition at line 238 of file BTreeNodeAccessor.h.

Constructor & Destructor Documentation

| BTreeCompactNodeAccessor::BTreeCompactNodeAccessor | ( | | ) | [explicit] | | -------------------------------------------------- | - | | - | ------------ |

Member Function Documentation

| void BTreeCompactNodeAccessor::onInit | ( | | ) | [virtual] | | ------------------------------------- | - | | - | ----------- |

void BTreeCompactNodeAccessor::deallocateEntry ( BTreeNode & node,
uint iEntry
) [virtual]

| bool BTreeCompactNodeAccessor::hasFixedWidthEntries | ( | | ) | const [virtual] | | --------------------------------------------------- | - | | - | ----------------- |

Returns:

true iff this NodeAccessor always stores tuples in fixed-width slots (even if the tuples themselves are variable-length)

Implements BTreeNodeAccessor.

Definition at line 82 of file BTreeCompactNodeAccessor.cpp.

00083 { 00084 return true; 00085 }

uint BTreeCompactNodeAccessor::getEntryByteCount ( uint cbTuple ) [virtual]

Determines the storage required for a tuple, including any overhead.

Parameters:

cbTuple number of bytes without overhead

Returns:

number of bytes with overhead

Implements BTreeNodeAccessor.

Definition at line 97 of file BTreeCompactNodeAccessor.cpp.

00098 { 00099 return cb; 00100 }

void BTreeCompactNodeAccessor::compactNode ( BTreeNode & node,
BTreeNode & scratchNode
) [virtual]

Performs compaction on a node.

Parameters:

node the fragmented node to be compacted
scratchNode receives a compacted copy of node

Reimplemented from BTreeNodeAccessor.

Definition at line 102 of file BTreeCompactNodeAccessor.cpp.

00103 { 00104
00105
00106 permAssert(false); 00107 }

uint BTreeNodeAccessor::getKeyCount ( BTreeNode const & node ) const [inline, inherited]
void BTreeNodeAccessor::clearNode ( BTreeNode & node,
uint cbPage
) [virtual, inherited]

Clears the contents of a node, converting it to an empty root.

Parameters:

node the node to clear
cbPage number of usable bytes per page in segment storing BTree

Reimplemented in BTreeHeapNodeAccessor.

Definition at line 34 of file BTreeNodeAccessor.cpp.

References BTreeNode::cbCompactFree, BTreeNode::cbTotalFree, BTreeNode::height, MAXU, BTreeNode::nEntries, NULL_PAGE_ID, and BTreeNode::rightSibling.

Referenced by BTreeBuildLevel::allocatePage(), BTreeBuilder::buildBalanced(), BTreeHeapNodeAccessor::clearNode(), BTreeWriter::compactNode(), BTreeWriter::grow(), and BTreeWriter::splitCurrentNode().

void BTreeNodeAccessor::dumpNode ( std::ostream & os,
BTreeNode const & node,
PageId pageId
) [inherited]

Dumps the contents of a node.

Parameters:

os output stream receiving the dump
node the node to dump
pageId PageId of the node being dumped

Definition at line 49 of file BTreeNodeAccessor.cpp.

References BTreeNode::cbCompactFree, BTreeNode::cbTotalFree, BTreeNodeAccessor::getEntryForRead(), BTreeNode::height, isMAXU(), BTreeNode::nEntries, NULL_PAGE_ID, TuplePrinter::print(), BTreeNode::rightSibling, TupleAccessor::setCurrentTupleBuf(), BTreeNodeAccessor::tupleAccessor, BTreeNodeAccessor::tupleData, BTreeNodeAccessor::tupleDescriptor, and TupleAccessor::unmarshal().

Referenced by BTreeWriter::attemptInsertWithoutSplit(), BTreeWriter::grow(), BTreeWriter::splitCurrentNode(), and BTreeVerifier::verifyNode().

00051 { 00052 os << "PageId: " << pageId << std::endl; 00053 if (node.rightSibling == NULL_PAGE_ID) { 00054 os << "rightSibling: " << std::endl; 00055 } else { 00056 os << "rightSibling: " << node.rightSibling << std::endl; 00057 } 00058 os << "nEntries: " << node.nEntries << std::endl; 00059 os << "height: " << node.height << std::endl; 00060 os << "cbTotalFree: " << node.cbTotalFree << std::endl; 00061 if (isMAXU(node.cbCompactFree)) { 00062 os << "cbCompactFree: " << node.cbCompactFree << std::endl; 00063 } 00064 os << std::endl; 00065 TuplePrinter tuplePrinter; 00066
00067 for (uint i = 0; i < node.nEntries; ++i) { 00068 PConstBuffer pEntry = getEntryForRead(node,i); 00069 os << "offset = " 00070 << pEntry - reinterpret_cast(&node) << std::endl; 00071 tupleAccessor.setCurrentTupleBuf(pEntry); 00072 tupleAccessor.unmarshal(tupleData); 00073 tuplePrinter.print(os,tupleDescriptor,tupleData); 00074 os << std::endl; 00075 } 00076 os << std::endl; 00077 }

virtual void BTreeNodeAccessor::accessTuple ( BTreeNode const & node,
uint iEntry
) [pure virtual, inherited]

Searches for a tuple based on a key.

Parameters:

node the node to search
keyDescriptor key descriptor to be used for comparisons
searchKey key to search for
dupSeek what to do if duplicates are found
leastUpper whether to position on least upper bound or greatest lower bound
scratchKey key to be used as a temp variable in comparisons
found same semantics as BTreeReader::binarySearch

Returns:

result of search as 0-based index of tuple on node

Referenced by BTreeReader::binarySearch(), and BTreeWriter::lockParentPage().

Compare first key on a node to provided search key.

Parameters:

node the node to search
keyDescriptor key descriptor to be used for comparisons
searchKey key to search for
scratchKey key to be used as a temp variable in comparison

Returns:

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

Referenced by BTreeReader::compareFirstKey().

virtual void BTreeNodeAccessor::accessTupleInline ( BTreeNode const & node,
uint iEntry
) [pure virtual, 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

Referenced by BTreeReader::accessTupleInline().

virtual void BTreeNodeAccessor::unmarshalKey ( TupleData & keyData ) [pure virtual, inherited]
void BTreeNodeAccessor::splitNode ( BTreeNode & node,
BTreeNode & newNode,
uint cbNewTuple,
bool monotonic
) [virtual, inherited]

Splits a node.

Parameters:

node the node to be split
newNode an empty node which receives half of the tuple data.
cbNewTuple number of bytes which will be required to store the tuple which caused this split
monotonic if true, inserts are always increasing so optimize the split accordingly

Definition at line 104 of file BTreeNodeAccessor.cpp.

References BTreeNodeAccessor::accessTuple(), BTreeNodeAccessor::allocateEntry(), BTreeNode::cbTotalFree, TupleAccessor::getCurrentByteCount(), TupleAccessor::getCurrentTupleBuf(), BTreeNodeAccessor::getEntryByteCount(), BTreeNode::height, max(), BTreeNode::nEntries, and BTreeNodeAccessor::tupleAccessor.

Referenced by BTreeWriter::splitCurrentNode().

Member Data Documentation

Accessor for tuples stored on nodes accessed by this.

This is used as a scratch variable in a variety of contexts, so reference with caution.

Definition at line 66 of file BTreeNodeAccessor.h.

Referenced by BTreeWriter::checkMonotonicity(), BTreeNodeAccessor::compactNode(), BTreeHeapNodeAccessor::deallocateEntry(), BTreeWriter::deleteCurrent(), BTreeNodeAccessor::dumpNode(), BTreeWriter::grow(), BTreeHeapNodeAccessor::hasFixedWidthEntries(), BTreeBuildLevel::indexLastChild(), VariableBuildLevel::indexLastKey(), BTreeWriter::insertTupleFromBuffer(), BTreeNodeAccessor::onInit(), onInit(), BTreeBuildLevel::processInput(), BTreeWriter::splitCurrentNode(), BTreeNodeAccessor::splitNode(), and BTreeWriter::updateCurrent().

The documentation for this class was generated from the following files:

Generated on Mon Jun 22 04:00:25 2009 for Fennel by doxygen 1.5.1