Fennel: /home/pub/open/dev/fennel/btree/BTreeBuildLevel.cpp Source File (original) (raw)
00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "fennel/common/CommonPreamble.h"
00025 #include "fennel/btree/BTreeBuildLevel.h"
00026 #include "fennel/btree/BTreeNodeAccessor.h"
00027 #include "fennel/btree/BTreeAccessBaseImpl.h"
00028 #include "fennel/segment/SegInputStream.h"
00029 #include "fennel/segment/SegOutputStream.h"
00030
00031 FENNEL_BEGIN_CPPFILE("$Id: //open/dev/fennel/btree/BTreeBuildLevel.cpp#10 $");
00032
00033 BTreeBuildLevel::BTreeBuildLevel(
00034 BTreeBuilder &builderInit,
00035 BTreeNodeAccessor &nodeAccessorInit)
00036 : builder(builderInit), nodeAccessor(nodeAccessorInit)
00037 {
00038 iLevel = 0;
00039 nEntriesTotal = 0;
00040 cbReserved = 0;
00041 iNode = 0;
00042 nEntriesProcessed = 0;
00043 nEntriesPerNode = 0;
00044 pageLock.accessSegment(builder.treeDescriptor.segmentAccessor);
00045 }
00046
00047 BTreeBuildLevel::~BTreeBuildLevel()
00048 {
00049 }
00050
00051 bool BTreeBuildLevel::isFinished() const
00052 {
00053 return (pageLock.getNodeForRead().nEntries == nEntriesPerNode)
00054 && (nEntriesProcessed == nEntriesTotal);
00055 }
00056
00057 void BTreeBuildLevel::processInput(ByteInputStream &sortedInputStream)
00058 {
00059 BTreeNode *pNode = &(pageLock.getNodeForWrite());
00060
00061 for (;;) {
00062
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
00079 if (isNodeFull(*pNode,cbTuple)) {
00080 indexLastKey(false);
00081 pNode = allocateAndLinkNewNode();
00082 assert((*pNode,cbTuple));
00083
00084 nodeAccessor.tupleAccessor.setCurrentTupleBuf(pCurrentTupleBuf);
00085 }
00086
00087
00088 PBuffer pEntry = nodeAccessor.allocateEntry(
00089 *pNode,
00090 pNode->nEntries,
00091 cbTuple);
00092 memcpy(
00093 pEntry,
00094 pCurrentTupleBuf,
00095 cbTuple);
00096 ++nEntriesProcessed;
00097
00098
00099 sortedInputStream.consumeReadPointer(cbTuple);
00100 }
00101 }
00102
00103 void BTreeBuildLevel::indexLastChild()
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
00119
00120 assert((*pNode,cbTuple));
00121
00122
00123 builder.getLevel(iLevel - 1).unmarshalLastKey();
00124 }
00125
00126
00127 nodeAccessor.tupleData.back().pData =
00128 reinterpret_cast(&(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 }
00134
00135 void BTreeBuildLevel::unmarshalLastKey()
00136 {
00137 BTreeNode const &node = pageLock.getNodeForRead();
00138 nodeAccessor.accessTuple(node,node.nEntries - 1);
00139 nodeAccessor.unmarshalKey(builder.pNonLeafNodeAccessor->tupleData);
00140 }
00141
00142 BTreeNode *BTreeBuildLevel::allocateAndLinkNewNode()
00143 {
00144 PageId prevPageId = pageId;
00145
00146 BTreeNode &node = allocatePage();
00147
00148
00149
00150
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
00161
00162 builder.getCacheAccessor()->nicePage(prevPageLock.getPage());
00163
00164 ++iNode;
00165 if (nEntriesPerNode) {
00166
00167 nEntriesPerNode = builder.calculateChildEntriesPerNode(
00168 builder.getLevel(iLevel + 1).nEntriesTotal,
00169 nEntriesTotal,
00170 iNode);
00171 }
00172 return &node;
00173 }
00174
00175 bool BTreeBuildLevel::isNodeFull(BTreeNode const &node,uint cbTuple)
00176 {
00177 return nodeAccessor.calculateCapacity(node,cbReserved + cbTuple)
00178 != BTreeNodeAccessor::CAN_FIT;
00179 }
00180
00181 BTreeNode &BTreeBuildLevel::allocatePage()
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 }
00190
00191 FixedBuildLevel::FixedBuildLevel(
00192 BTreeBuilder &builderInit,
00193 BTreeNodeAccessor &nodeAccessorInit)
00194 : BTreeBuildLevel(builderInit,nodeAccessorInit)
00195 {
00196 }
00197
00198 void FixedBuildLevel::indexLastKey(bool finalize)
00199 {
00200 assert(pageLock.getNodeForRead().nEntries == nEntriesPerNode);
00201 if (iLevel == builder.getRootHeight()) {
00202 assert(finalize);
00203 return;
00204 }
00205 unmarshalLastKey();
00206 builder.getLevel(iLevel + 1).indexLastChild();
00207 }
00208
00209 bool FixedBuildLevel::isNodeFull(BTreeNode const &node,uint)
00210 {
00211 return (node.nEntries >= nEntriesPerNode);
00212 }
00213
00214 VariableBuildLevel::VariableBuildLevel(
00215 BTreeBuilder &builderInit,
00216 BTreeNodeAccessor &nodeAccessorInit)
00217 : BTreeBuildLevel(builderInit,nodeAccessorInit)
00218 {
00219 assert(builder.pTempSegment);
00220 SegmentAccessor tempSegmentAccessor(
00221 builder.pTempSegment,builder.getCacheAccessor());
00222 pParentKeyStream = SegOutputStream::newSegOutputStream(tempSegmentAccessor);
00223 }
00224
00225 VariableBuildLevel::~VariableBuildLevel()
00226 {
00227 if (->isClosed()) {
00228
00229
00230 getParentKeyStream();
00231 }
00232 }
00233
00234 SharedSegInputStream VariableBuildLevel::getParentKeyStream()
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
00245 pParentInputStream->setDeallocate(true);
00246 return pParentInputStream;
00247 }
00248
00249 void VariableBuildLevel::indexLastKey(bool)
00250 {
00251 unmarshalLastKey();
00252 BTreeNodeAccessor &nonLeafNodeAccessor = *builder.pNonLeafNodeAccessor;
00253
00254 nonLeafNodeAccessor.tupleData.back().pData =
00255 reinterpret_cast(&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 }
00264
00265 DynamicBuildLevel::DynamicBuildLevel(
00266 BTreeBuilder &builderInit,
00267 BTreeNodeAccessor &nodeAccessorInit)
00268 : BTreeBuildLevel(builderInit,nodeAccessorInit)
00269 {
00270 }
00271
00272 void DynamicBuildLevel::indexLastKey(bool finalize)
00273 {
00274 if (iLevel == builder.getRootHeight()) {
00275 if (finalize) {
00276 return;
00277 } else {
00278 builder.growTree();
00279 }
00280 }
00281 unmarshalLastKey();
00282 builder.getLevel(iLevel + 1).indexLastChild();
00283 }
00284
00285 FENNEL_END_CPPFILE("$Id: //open/dev/fennel/btree/BTreeBuildLevel.cpp#10 $");
00286
00287