#include <BTreeBuildLevel.h>
Inheritance diagram for VariableBuildLevel:
Public Member Functions | |
virtual | ~VariableBuildLevel () |
void | indexLastChild () |
Protected Member Functions | |
bool | isFinished () const |
void | processInput (ByteInputStream &sortedInputStream) |
void | unmarshalLastKey () |
BTreeNode * | allocateAndLinkNewNode () |
BTreeNode & | allocatePage () |
virtual bool | isNodeFull (BTreeNode const &node, uint cbTuple) |
Protected Attributes | |
BTreeBuilder & | builder |
Owning BTreeBuilder. | |
BTreeNodeAccessor & | nodeAccessor |
BTreeNodeAccessor to use for accessing nodes in this level. | |
uint | iLevel |
0-based height of this level in tree. | |
RecordNum | iNode |
0-based sequence number of node being built on this level. | |
RecordNum | nEntriesTotal |
Total number of entries expected at this level. | |
BTreePageLock | pageLock |
Lock on current node. | |
PageId | pageId |
PageId of current node. | |
uint | nEntriesPerNode |
Number of entries to store on each node. | |
RecordNum | nEntriesProcessed |
Number of entries appended on this level so far (across all nodes). | |
uint | cbReserved |
Number of bytes of free space to reserve on each page (determined by fill factor). | |
Private Member Functions | |
VariableBuildLevel (BTreeBuilder &builderInit, BTreeNodeAccessor &nodeAccessorInit) | |
SharedSegInputStream | getParentKeyStream () |
virtual void | indexLastKey (bool finalize) |
Private Attributes | |
SharedSegOutputStream | pParentKeyStream |
Friends | |
class | BTreeBuilder |
Definition at line 138 of file BTreeBuildLevel.h.
VariableBuildLevel::VariableBuildLevel | ( | BTreeBuilder & | builderInit, | |
BTreeNodeAccessor & | nodeAccessorInit | |||
) | [explicit, private] |
Definition at line 214 of file BTreeBuildLevel.cpp.
References BTreeBuildLevel::builder, BTreeAccessBase::getCacheAccessor(), SegOutputStream::newSegOutputStream(), pParentKeyStream, and BTreeBuilder::pTempSegment.
00217 : BTreeBuildLevel(builderInit,nodeAccessorInit) 00218 { 00219 assert(builder.pTempSegment); 00220 SegmentAccessor tempSegmentAccessor( 00221 builder.pTempSegment,builder.getCacheAccessor()); 00222 pParentKeyStream = SegOutputStream::newSegOutputStream(tempSegmentAccessor); 00223 }
VariableBuildLevel::~VariableBuildLevel | ( | ) | [virtual] |
Definition at line 225 of file BTreeBuildLevel.cpp.
References getParentKeyStream(), and pParentKeyStream.
00226 { 00227 if (!pParentKeyStream->isClosed()) { 00228 // no one ever used the buffered keys, so we need to deallocate them 00229 // now 00230 getParentKeyStream(); 00231 } 00232 }
SharedSegInputStream VariableBuildLevel::getParentKeyStream | ( | ) | [private] |
Definition at line 234 of file BTreeBuildLevel.cpp.
References BTreeBuildLevel::builder, BTreeAccessBase::getCacheAccessor(), SegInputStream::newSegInputStream(), pParentKeyStream, and BTreeBuilder::pTempSegment.
Referenced by ~VariableBuildLevel().
00235 { 00236 PageId tempPageId = pParentKeyStream->getFirstPageId(); 00237 pParentKeyStream->close(); 00238 SegmentAccessor tempSegmentAccessor( 00239 builder.pTempSegment,builder.getCacheAccessor()); 00240 SharedSegInputStream pParentInputStream = 00241 SegInputStream::newSegInputStream( 00242 tempSegmentAccessor, 00243 tempPageId); 00244 // deallocate temp pages automatically 00245 pParentInputStream->setDeallocate(true); 00246 return pParentInputStream; 00247 }
void VariableBuildLevel::indexLastKey | ( | bool | finalize | ) | [private, virtual] |
Implements BTreeBuildLevel.
Definition at line 249 of file BTreeBuildLevel.cpp.
References BTreeBuildLevel::builder, TupleAccessor::getByteCount(), TupleAccessor::marshal(), BTreeBuildLevel::pageId, BTreeAccessBase::pNonLeafNodeAccessor, pParentKeyStream, BTreeNodeAccessor::tupleAccessor, BTreeNodeAccessor::tupleData, and BTreeBuildLevel::unmarshalLastKey().
00250 { 00251 unmarshalLastKey(); 00252 BTreeNodeAccessor &nonLeafNodeAccessor = *builder.pNonLeafNodeAccessor; 00253 // REVIEW: use parent level info instead? 00254 nonLeafNodeAccessor.tupleData.back().pData = 00255 reinterpret_cast<PConstBuffer>(&pageId); 00256 uint cbTuple = nonLeafNodeAccessor.tupleAccessor.getByteCount( 00257 nonLeafNodeAccessor.tupleData); 00258 PBuffer pStreamBuf = pParentKeyStream->getWritePointer(cbTuple); 00259 nonLeafNodeAccessor.tupleAccessor.marshal( 00260 nonLeafNodeAccessor.tupleData, 00261 pStreamBuf); 00262 pParentKeyStream->consumeWritePointer(cbTuple); 00263 }
bool BTreeBuildLevel::isFinished | ( | ) | const [protected, inherited] |
Definition at line 51 of file BTreeBuildLevel.cpp.
References SegNodeLock< Node >::getNodeForRead(), BTreeBuildLevel::nEntriesPerNode, BTreeBuildLevel::nEntriesProcessed, BTreeBuildLevel::nEntriesTotal, and BTreeBuildLevel::pageLock.
00052 { 00053 return (pageLock.getNodeForRead().nEntries == nEntriesPerNode) 00054 && (nEntriesProcessed == nEntriesTotal); 00055 }
void BTreeBuildLevel::processInput | ( | ByteInputStream & | sortedInputStream | ) | [protected, inherited] |
Definition at line 57 of file BTreeBuildLevel.cpp.
References BTreeBuildLevel::allocateAndLinkNewNode(), BTreeNodeAccessor::allocateEntry(), BTreeBuildLevel::builder, ByteInputStream::consumeReadPointer(), TupleAccessor::getCurrentByteCount(), SegNodeLock< Node >::getNodeForWrite(), ByteInputStream::getReadPointer(), BTreeBuildLevel::indexLastKey(), BTreeBuildLevel::isNodeFull(), BTreeNode::nEntries, BTreeBuildLevel::nEntriesProcessed, BTreeBuildLevel::nEntriesTotal, BTreeBuildLevel::nodeAccessor, BTreeBuildLevel::pageLock, TupleAccessor::setCurrentTupleBuf(), BTreeNodeAccessor::tupleAccessor, and BTreeAccessBase::validateTupleSize().
Referenced by BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), and BTreeBuilder::buildUnbalanced().
00058 { 00059 BTreeNode *pNode = &(pageLock.getNodeForWrite()); 00060 00061 for (;;) { 00062 // Read one tuple. 00063 uint cbActual; 00064 PConstBuffer pCurrentTupleBuf = 00065 sortedInputStream.getReadPointer(1,&cbActual); 00066 if (!pCurrentTupleBuf) { 00067 break; 00068 } 00069 if (nEntriesTotal) { 00070 assert(nEntriesProcessed < nEntriesTotal); 00071 } 00072 nodeAccessor.tupleAccessor.setCurrentTupleBuf(pCurrentTupleBuf); 00073 uint cbTuple = nodeAccessor.tupleAccessor.getCurrentByteCount(); 00074 assert(cbActual >= cbTuple); 00075 00076 builder.validateTupleSize(nodeAccessor.tupleAccessor); 00077 00078 // Make sure we have enough room. 00079 if (isNodeFull(*pNode,cbTuple)) { 00080 indexLastKey(false); 00081 pNode = allocateAndLinkNewNode(); 00082 assert(!isNodeFull(*pNode,cbTuple)); 00083 // indexLastKey used tupleAccessor, so have to rebind it 00084 nodeAccessor.tupleAccessor.setCurrentTupleBuf(pCurrentTupleBuf); 00085 } 00086 00087 // Append the current tuple. 00088 PBuffer pEntry = nodeAccessor.allocateEntry( 00089 *pNode, 00090 pNode->nEntries, 00091 cbTuple); 00092 memcpy( 00093 pEntry, 00094 pCurrentTupleBuf, 00095 cbTuple); 00096 ++nEntriesProcessed; 00097 00098 // Advance to the next input tuple. 00099 sortedInputStream.consumeReadPointer(cbTuple); 00100 } 00101 }
void BTreeBuildLevel::unmarshalLastKey | ( | ) | [protected, inherited] |
Definition at line 135 of file BTreeBuildLevel.cpp.
References BTreeNodeAccessor::accessTuple(), BTreeBuildLevel::builder, SegNodeLock< Node >::getNodeForRead(), BTreeNode::nEntries, BTreeBuildLevel::nodeAccessor, BTreeBuildLevel::pageLock, BTreeAccessBase::pNonLeafNodeAccessor, and BTreeNodeAccessor::unmarshalKey().
Referenced by BTreeBuildLevel::indexLastChild(), DynamicBuildLevel::indexLastKey(), indexLastKey(), and FixedBuildLevel::indexLastKey().
00136 { 00137 BTreeNode const &node = pageLock.getNodeForRead(); 00138 nodeAccessor.accessTuple(node,node.nEntries - 1); 00139 nodeAccessor.unmarshalKey(builder.pNonLeafNodeAccessor->tupleData); 00140 }
BTreeNode * BTreeBuildLevel::allocateAndLinkNewNode | ( | ) | [protected, inherited] |
Definition at line 142 of file BTreeBuildLevel.cpp.
References SegPageLock::accessSegment(), BTreeBuildLevel::allocatePage(), BTreeBuildLevel::builder, BTreeBuilder::calculateChildEntriesPerNode(), BTreeAccessBase::getCacheAccessor(), BTreeBuilder::getLevel(), SegNodeLock< Node >::getNodeForWrite(), SegPageLock::getPage(), BTreeBuildLevel::iLevel, BTreeBuildLevel::iNode, SegPageLock::lockExclusive(), BTreeBuildLevel::nEntriesPerNode, BTreeBuildLevel::nEntriesTotal, BTreeBuildLevel::pageId, BTreeDescriptor::segmentAccessor, BTreeAccessBase::setRightSibling(), and BTreeAccessBase::treeDescriptor.
Referenced by BTreeBuildLevel::indexLastChild(), and BTreeBuildLevel::processInput().
00143 { 00144 PageId prevPageId = pageId; 00145 00146 BTreeNode &node = allocatePage(); 00147 00148 // Ugly: we have to go back and fix up the rightSibling link on the 00149 // previous page. There are better ways, but they require messing with 00150 // SegPageLock. 00151 BTreePageLock prevPageLock; 00152 prevPageLock.accessSegment(builder.treeDescriptor.segmentAccessor); 00153 prevPageLock.lockExclusive(prevPageId); 00154 BTreeNode &prevNode = prevPageLock.getNodeForWrite(); 00155 builder.setRightSibling( 00156 prevNode, 00157 prevPageId, 00158 pageId); 00159 00160 // Let the cache know we're not planning to revisit the page we just 00161 // finished. 00162 builder.getCacheAccessor()->nicePage(prevPageLock.getPage()); 00163 00164 ++iNode; 00165 if (nEntriesPerNode) { 00166 // Recalculate balancing. 00167 nEntriesPerNode = builder.calculateChildEntriesPerNode( 00168 builder.getLevel(iLevel + 1).nEntriesTotal, 00169 nEntriesTotal, 00170 iNode); 00171 } 00172 return &node; 00173 }
BTreeNode & BTreeBuildLevel::allocatePage | ( | ) | [protected, inherited] |
Definition at line 181 of file BTreeBuildLevel.cpp.
References SegNodeLock< Node >::allocatePage(), BTreeBuildLevel::builder, BTreeNodeAccessor::clearNode(), SegNodeLock< Node >::getNodeForWrite(), BTreeAccessBase::getPageOwnerId(), BTreeAccessBase::getSegment(), BTreeNode::height, BTreeBuildLevel::iLevel, BTreeBuildLevel::nodeAccessor, BTreeBuildLevel::pageId, and BTreeBuildLevel::pageLock.
Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), and BTreeBuilder::growTree().
00182 { 00183 pageId = pageLock.allocatePage(builder.getPageOwnerId()); 00184 BTreeNode &node = pageLock.getNodeForWrite(); 00185 nodeAccessor.clearNode( 00186 node,builder.getSegment()->getUsablePageSize()); 00187 node.height = iLevel; 00188 return node; 00189 }
bool BTreeBuildLevel::isNodeFull | ( | BTreeNode const & | node, | |
uint | cbTuple | |||
) | [protected, virtual, inherited] |
Reimplemented in FixedBuildLevel.
Definition at line 175 of file BTreeBuildLevel.cpp.
References BTreeNodeAccessor::calculateCapacity(), BTreeNodeAccessor::CAN_FIT, BTreeBuildLevel::cbReserved, and BTreeBuildLevel::nodeAccessor.
Referenced by BTreeBuildLevel::indexLastChild(), and BTreeBuildLevel::processInput().
00176 { 00177 return nodeAccessor.calculateCapacity(node,cbReserved + cbTuple) 00178 != BTreeNodeAccessor::CAN_FIT; 00179 }
void BTreeBuildLevel::indexLastChild | ( | ) | [inherited] |
Definition at line 103 of file BTreeBuildLevel.cpp.
References BTreeBuildLevel::allocateAndLinkNewNode(), BTreeNodeAccessor::allocateEntry(), BTreeBuildLevel::builder, TupleAccessor::getByteCount(), BTreeBuilder::getLevel(), SegNodeLock< Node >::getNodeForWrite(), BTreeBuildLevel::iLevel, BTreeBuildLevel::indexLastKey(), BTreeBuildLevel::isNodeFull(), TupleAccessor::marshal(), BTreeNode::nEntries, BTreeBuildLevel::nEntriesProcessed, BTreeBuildLevel::nEntriesTotal, BTreeBuildLevel::nodeAccessor, BTreeBuildLevel::pageId, BTreeBuildLevel::pageLock, BTreeNodeAccessor::tupleAccessor, BTreeNodeAccessor::tupleData, and BTreeBuildLevel::unmarshalLastKey().
Referenced by DynamicBuildLevel::indexLastKey(), and FixedBuildLevel::indexLastKey().
00104 { 00105 assert(iLevel > 0); 00106 if (nEntriesTotal) { 00107 assert(nEntriesProcessed < nEntriesTotal); 00108 } 00109 00110 uint cbTuple = nodeAccessor.tupleAccessor.getByteCount( 00111 nodeAccessor.tupleData); 00112 00113 BTreeNode *pNode = &(pageLock.getNodeForWrite()); 00114 if (isNodeFull(*pNode,cbTuple)) { 00115 indexLastKey(false); 00116 pNode = allocateAndLinkNewNode(); 00117 00118 // FIXME: should override fillfactor here, or provide a proper error 00119 // msg; same thing somewhere else 00120 assert(!isNodeFull(*pNode,cbTuple)); 00121 00122 // indexLastKey used tupleData, so have to rebind it 00123 builder.getLevel(iLevel - 1).unmarshalLastKey(); 00124 } 00125 00126 // Now append the child entry. 00127 nodeAccessor.tupleData.back().pData = 00128 reinterpret_cast<PConstBuffer>(&(builder.getLevel(iLevel-1).pageId)); 00129 PBuffer pEntry = nodeAccessor.allocateEntry( 00130 *pNode,pNode->nEntries,cbTuple); 00131 nodeAccessor.tupleAccessor.marshal(nodeAccessor.tupleData,pEntry); 00132 ++nEntriesProcessed; 00133 }
friend class BTreeBuilder [friend] |
Definition at line 143 of file BTreeBuildLevel.h.
Referenced by getParentKeyStream(), indexLastKey(), VariableBuildLevel(), and ~VariableBuildLevel().
BTreeBuilder& BTreeBuildLevel::builder [protected, inherited] |
Owning BTreeBuilder.
Definition at line 48 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeBuildLevel::allocatePage(), BTreeBuildLevel::BTreeBuildLevel(), getParentKeyStream(), BTreeBuildLevel::indexLastChild(), DynamicBuildLevel::indexLastKey(), indexLastKey(), FixedBuildLevel::indexLastKey(), BTreeBuildLevel::processInput(), BTreeBuildLevel::unmarshalLastKey(), and VariableBuildLevel().
BTreeNodeAccessor& BTreeBuildLevel::nodeAccessor [protected, inherited] |
BTreeNodeAccessor to use for accessing nodes in this level.
Definition at line 53 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::allocatePage(), BTreeBuilder::buildBalanced(), BTreeBuildLevel::indexLastChild(), BTreeBuildLevel::isNodeFull(), BTreeBuildLevel::processInput(), and BTreeBuildLevel::unmarshalLastKey().
uint BTreeBuildLevel::iLevel [protected, inherited] |
0-based height of this level in tree.
Definition at line 58 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeBuildLevel::allocatePage(), BTreeBuildLevel::BTreeBuildLevel(), BTreeBuilder::buildBalanced(), BTreeBuilder::growTree(), BTreeBuildLevel::indexLastChild(), DynamicBuildLevel::indexLastKey(), and FixedBuildLevel::indexLastKey().
RecordNum BTreeBuildLevel::iNode [protected, inherited] |
0-based sequence number of node being built on this level.
Definition at line 63 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeBuildLevel::BTreeBuildLevel(), and BTreeBuilder::buildTwoPass().
RecordNum BTreeBuildLevel::nEntriesTotal [protected, inherited] |
Total number of entries expected at this level.
If 0, total is unknown.
Definition at line 68 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeBuildLevel::BTreeBuildLevel(), BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), BTreeBuilder::buildUnbalanced(), BTreeBuildLevel::indexLastChild(), BTreeBuildLevel::isFinished(), and BTreeBuildLevel::processInput().
BTreePageLock BTreeBuildLevel::pageLock [protected, inherited] |
Lock on current node.
Definition at line 73 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::allocatePage(), BTreeBuildLevel::BTreeBuildLevel(), BTreeBuilder::buildBalanced(), BTreeBuildLevel::indexLastChild(), FixedBuildLevel::indexLastKey(), BTreeBuildLevel::isFinished(), BTreeBuildLevel::processInput(), BTreeBuilder::swapRoot(), and BTreeBuildLevel::unmarshalLastKey().
PageId BTreeBuildLevel::pageId [protected, inherited] |
PageId of current node.
Definition at line 78 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeBuildLevel::allocatePage(), BTreeBuilder::buildBalanced(), BTreeBuildLevel::indexLastChild(), indexLastKey(), and BTreeBuilder::swapRoot().
uint BTreeBuildLevel::nEntriesPerNode [protected, inherited] |
Number of entries to store on each node.
This varies over the level to achieve the desired balancing. If 0, no balancing is being performed.
Definition at line 85 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::allocateAndLinkNewNode(), BTreeBuildLevel::BTreeBuildLevel(), BTreeBuilder::buildBalanced(), FixedBuildLevel::indexLastKey(), BTreeBuildLevel::isFinished(), and FixedBuildLevel::isNodeFull().
RecordNum BTreeBuildLevel::nEntriesProcessed [protected, inherited] |
Number of entries appended on this level so far (across all nodes).
For non-leaf levels, this should stay in sync with the iNode of the child level.
Definition at line 92 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::BTreeBuildLevel(), BTreeBuildLevel::indexLastChild(), BTreeBuildLevel::isFinished(), and BTreeBuildLevel::processInput().
uint BTreeBuildLevel::cbReserved [protected, inherited] |
Number of bytes of free space to reserve on each page (determined by fill factor).
0 for fixed-width entries.
Definition at line 98 of file BTreeBuildLevel.h.
Referenced by BTreeBuildLevel::BTreeBuildLevel(), BTreeBuilder::buildTwoPass(), BTreeBuilder::buildUnbalanced(), BTreeBuilder::growTree(), and BTreeBuildLevel::isNodeFull().