BTreeReadersTest.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/test/SegStorageTestBase.h" 00026 #include "fennel/btree/BTreeBuilder.h" 00027 #include "fennel/btree/BTreeNonLeafReader.h" 00028 #include "fennel/btree/BTreeLeafReader.h" 00029 #include "fennel/segment/SegInputStream.h" 00030 #include "fennel/segment/SegOutputStream.h" 00031 #include "fennel/tuple/StandardTypeDescriptor.h" 00032 #include "fennel/tuple/TupleAccessor.h" 00033 00034 #include <boost/scoped_array.hpp> 00035 #include <boost/test/test_tools.hpp> 00036 00037 using namespace fennel; 00038 00039 #include 00040 00044 class BTreeReadersTest : virtual public SegStorageTestBase 00045 { 00046 enum { 00047 nRandomSeed = 1000000, 00048 iValueMax = 1000000000 00049 }; 00050 00051 struct LeafRecord 00052 { 00053 int32_t key; 00054 int32_t value; 00055 }; 00056 00057 BTreeDescriptor treeDescriptor; 00058 TupleDescriptor nonLeafDescriptor; 00059 00060 TupleAccessor leafTupleAccessor; 00061 TupleData keyData; 00062 TupleData leafTupleData; 00063 TupleData nonLeafTupleData; 00064 LeafRecord leafRecord; 00065 boost::scoped_array nonLeafRecordBuf; 00066 boost::scoped_array leafRecordBuf; 00067 00068 int32_t readLeafKey(); 00069 int32_t readNonLeafKey(); 00070 PageId readPageId(); 00071 int32_t readLeafValue(); 00072 00073 void testOneLevel() 00074 { 00075 testReaders(200); 00076 } 00077 00078 void testTwoLevels() 00079 { 00080 testReaders(20000); 00081 } 00082 00083 void testThreeLevels() 00084 { 00085 testReaders(200000); 00086 } 00087 00088 void testReaders(uint nRecords); 00089 void testScan(SharedByteInputStream, uint nRecords); 00090 void testSearch(SharedByteInputStream, uint nRecords); 00091 00092 void marshalLeafRecord(); 00093 void unmarshalLeafRecord(SharedByteInputStream pInputStream); 00094 00095 public: 00096 explicit BTreeReadersTest() 00097 { 00098 FENNEL_UNIT_TEST_CASE(BTreeReadersTest,testOneLevel); 00099 FENNEL_UNIT_TEST_CASE(BTreeReadersTest,testTwoLevels); 00100 FENNEL_UNIT_TEST_CASE(BTreeReadersTest,testThreeLevels); 00101 00102 StandardTypeDescriptorFactory stdTypeFactory; 00103 TupleAttributeDescriptor attrDesc( 00104 stdTypeFactory.newDataType(STANDARD_TYPE_INT_32)); 00105 treeDescriptor.tupleDescriptor.push_back(attrDesc); 00106 treeDescriptor.tupleDescriptor.push_back(attrDesc); 00107 treeDescriptor.keyProjection.push_back(0); 00108 leafTupleAccessor.compute(treeDescriptor.tupleDescriptor); 00109 leafRecordBuf.reset( 00110 new FixedBuffer[leafTupleAccessor.getMaxByteCount()]); 00111 leafTupleData.compute(treeDescriptor.tupleDescriptor); 00112 00113 nonLeafDescriptor.push_back(attrDesc); 00114 TupleAttributeDescriptor pageIdDesc( 00115 stdTypeFactory.newDataType(STANDARD_TYPE_UINT_64)); 00116 nonLeafDescriptor.push_back(pageIdDesc); 00117 nonLeafTupleData.compute(nonLeafDescriptor); 00118 } 00119 00120 virtual void testCaseSetUp(); 00121 virtual void testCaseTearDown(); 00122 }; 00123 00124 void BTreeReadersTest::testCaseSetUp() 00125 { 00126 openStorage(DeviceMode::createNew); 00127 openRandomSegment(); 00128 00129 treeDescriptor.segmentAccessor.pSegment = pRandomSegment; 00130 treeDescriptor.segmentAccessor.pCacheAccessor = pCache; 00131 } 00132 00133 void BTreeReadersTest::testCaseTearDown() 00134 { 00135 treeDescriptor.segmentAccessor.reset(); 00136 SegStorageTestBase::testCaseTearDown(); 00137 } 00138 00139 void BTreeReadersTest::marshalLeafRecord() 00140 { 00141 leafTupleData[0].pData = reinterpret_cast(&leafRecord.key); 00142 leafTupleData[1].pData = reinterpret_cast(&leafRecord.value); 00143 leafTupleAccessor.marshal(leafTupleData, leafRecordBuf.get()); 00144 } 00145 00146 void BTreeReadersTest::unmarshalLeafRecord(SharedByteInputStream pInputStream) 00147 { 00148 PConstBuffer pBuf = pInputStream->getReadPointer(1); 00149 leafTupleAccessor.setCurrentTupleBuf(pBuf); 00150 uint cbTuple = leafTupleAccessor.getCurrentByteCount(); 00151 leafTupleAccessor.unmarshal(leafTupleData); 00152 leafRecord.key = readLeafKey(); 00153 leafRecord.value = readLeafValue(); 00154 pInputStream->consumeReadPointer(cbTuple); 00155 } 00156 00157 void BTreeReadersTest::testReaders(uint nRecords) 00158 { 00159
00160 00161 treeDescriptor.rootPageId = NULL_PAGE_ID; 00162 BTreeBuilder builder(treeDescriptor, pRandomSegment); 00163 00164 keyData.compute(builder.getKeyDescriptor()); 00165 keyData[0].pData = reinterpret_cast(&leafRecord.key); 00166 00167 builder.createEmptyRoot(); 00168 treeDescriptor.rootPageId = builder.getRootPageId(); 00169 00170
00171 SegmentAccessor segmentAccessor(pRandomSegment,pCache); 00172 SharedSegOutputStream pOutputStream = 00173 SegOutputStream::newSegOutputStream(segmentAccessor); 00174 std::subtractive_rng randomNumberGenerator(nRandomSeed); 00175 leafRecord.key = 0; 00176 for (uint i = 0; i < nRecords; i++) { 00177
00178 leafRecord.key += (randomNumberGenerator(10)) + 2; 00179 leafRecord.value = randomNumberGenerator(iValueMax); 00180 00181 marshalLeafRecord(); 00182 uint cbTuple = leafTupleAccessor.getCurrentByteCount(); 00183 PBuffer pBuffer = pOutputStream->getWritePointer(cbTuple); 00184 memcpy(pBuffer,leafRecordBuf.get(),cbTuple); 00185 pOutputStream->consumeWritePointer(cbTuple); 00186 } 00187 PageId pageId = pOutputStream->getFirstPageId(); 00188 pOutputStream.reset(); 00189 SharedSegInputStream pInputStream = 00190 SegInputStream::newSegInputStream(segmentAccessor,pageId); 00191 SegStreamPosition startPos; 00192 pInputStream->getSegPos(startPos); 00193 00194
00195 builder.build(*pInputStream,nRecords,1.0); 00196 treeDescriptor.rootPageId = builder.getRootPageId(); 00197 00198
00199 pInputStream->seekSegPos(startPos); 00200 testSearch(pInputStream,nRecords); 00201 00202
00203 pInputStream->seekSegPos(startPos); 00204 testScan(pInputStream,nRecords); 00205 00206
00207 pInputStream->seekSegPos(startPos); 00208 pInputStream->setDeallocate(true); 00209 pInputStream.reset(); 00210 00211
00212 builder.truncate(true); 00213 } 00214 00215 void BTreeReadersTest::testSearch( 00216 SharedByteInputStream pInputStream, 00217 uint nRecords) 00218 { 00219
00220 00221 BTreeNonLeafReader nonLeafReader(treeDescriptor); 00222 BTreeLeafReader leafReader(treeDescriptor); 00223 for (uint i = 0; i < nRecords; ++i) { 00224
00225
00226
00227 unmarshalLeafRecord(pInputStream); 00228 00229 PageId leafPageId; 00230 if (nonLeafReader.isRootOnly()) { 00231 leafPageId = nonLeafReader.getRootPageId(); 00232 } else { 00233 nonLeafReader.searchForKey(keyData, DUP_SEEK_ANY); 00234 BOOST_CHECK(!nonLeafReader.isSingular()); 00235 nonLeafReader.getTupleAccessorForRead().unmarshal(nonLeafTupleData); 00236 if (!nonLeafReader.isPositionedOnInfinityKey() && 00237 readNonLeafKey() < leafRecord.key) 00238 { 00239 BOOST_FAIL( 00240 "Non-leaf key is less than expected key. Expected key = " 00241 << leafRecord.key << ". Key read = " << readNonLeafKey()); 00242 } 00243 leafPageId = readPageId(); 00244 } 00245 00246
00247 leafReader.setCurrentPageId(leafPageId); 00248 if (!leafReader.searchForKey(keyData, DUP_SEEK_ANY)) { 00249 BOOST_FAIL( 00250 "Couldn't locate key " << leafRecord.key << " in leaf page"); 00251 } 00252 leafReader.getTupleAccessorForRead().unmarshal(leafTupleData); 00253 BOOST_CHECK_EQUAL(leafRecord.key, readLeafKey()); 00254 BOOST_CHECK_EQUAL(leafRecord.value, readLeafValue()); 00255 } 00256 } 00257 00258 void BTreeReadersTest::testScan( 00259 SharedByteInputStream pInputStream, 00260 uint nRecords) 00261 { 00262
00263
00264 00265 BTreeNonLeafReader nonLeafReader(treeDescriptor); 00266 BTreeLeafReader leafReader(treeDescriptor); 00267 00268
00269
00270 bool found; 00271 int32_t lastKey = -1; 00272 bool rootOnly = nonLeafReader.isRootOnly(); 00273 if (!rootOnly) { 00274 found = nonLeafReader.searchFirst(); 00275 if (!found) { 00276 BOOST_FAIL("searchFirst on non-leaf found nothing"); 00277 } 00278 } 00279 00280 for (uint i = 0; i < nRecords;) { 00281 unmarshalLeafRecord(pInputStream); 00282 PageId leafPageId; 00283 if (rootOnly) { 00284 leafPageId = nonLeafReader.getRootPageId(); 00285 } else { 00286
00287 nonLeafReader.getTupleAccessorForRead().unmarshal(nonLeafTupleData); 00288 if (!nonLeafReader.isPositionedOnInfinityKey() && 00289 readNonLeafKey() < leafRecord.key) 00290 { 00291 BOOST_FAIL( 00292 "Non-leaf key is less than expected key. Expected key = " 00293 << leafRecord.key << ". Key read = " << readNonLeafKey()); 00294 } 00295 leafPageId = readPageId(); 00296 } 00297 leafReader.setCurrentPageId(leafPageId); 00298 00299
00300 found = leafReader.searchFirst(); 00301 if (!found) { 00302 BOOST_FAIL("searchFirst on leaf found nothing"); 00303 } 00304 00305
00306
00307 while (true) { 00308 leafReader.getTupleAccessorForRead().unmarshal(leafTupleData); 00309 lastKey = readLeafKey(); 00310 BOOST_CHECK_EQUAL(leafRecord.key, lastKey); 00311 BOOST_CHECK_EQUAL(leafRecord.value, readLeafValue()); 00312 i++; 00313 if (i == nRecords) { 00314 break; 00315 } 00316 found = leafReader.searchNext(); 00317 if (!found) { 00318 break; 00319 } 00320 unmarshalLeafRecord(pInputStream); 00321 } 00322 00323
00324
00325 found = leafReader.searchLast(); 00326 if (!found) { 00327 BOOST_FAIL("seachLast on leaf found nothing"); 00328 } 00329 leafReader.getTupleAccessorForRead().unmarshal(leafTupleData); 00330 BOOST_CHECK_EQUAL(lastKey, readLeafKey()); 00331 leafReader.endSearch(); 00332 00333 if (i == nRecords) { 00334 break; 00335 } 00336 00337 if (!rootOnly) { 00338
00339
00340 found = nonLeafReader.searchNext(); 00341 if (!found) { 00342 BOOST_FAIL("searchNext on non-leaf found nothing"); 00343 } 00344 } 00345 } 00346 00347 nonLeafReader.endSearch(); 00348 } 00349 00350 int32_t BTreeReadersTest::readLeafKey() 00351 { 00352 return *reinterpret_cast<int32_t const *>( 00353 leafTupleData[0].pData); 00354 } 00355 00356 int32_t BTreeReadersTest::readLeafValue() 00357 { 00358 return *reinterpret_cast<int32_t const *>( 00359 leafTupleData[1].pData); 00360 } 00361 00362 int32_t BTreeReadersTest::readNonLeafKey() 00363 { 00364 return *reinterpret_cast<int32_t const *>( 00365 nonLeafTupleData[0].pData); 00366 } 00367 00368 PageId BTreeReadersTest::readPageId() 00369 { 00370 return *reinterpret_cast<PageId const *>( 00371 nonLeafTupleData[1].pData); 00372 } 00373 00374 FENNEL_UNIT_TEST_SUITE(BTreeReadersTest); 00375 00376