BTreeReadersTest.cpp

Go to the documentation of this file.
00001 /*
00002 // $Id: //open/dev/fennel/test/BTreeReadersTest.cpp#5 $
00003 // Fennel is a library of data storage and processing components.
00004 // Copyright (C) 2005-2009 The Eigenbase Project
00005 // Copyright (C) 2005-2009 SQLstream, Inc.
00006 // Copyright (C) 2005-2009 LucidEra, Inc.
00007 // Portions Copyright (C) 1999-2009 John V. Sichi
00008 //
00009 // This program is free software; you can redistribute it and/or modify it
00010 // under the terms of the GNU General Public License as published by the Free
00011 // Software Foundation; either version 2 of the License, or (at your option)
00012 // any later version approved by The Eigenbase Project.
00013 //
00014 // This program is distributed in the hope that it will be useful,
00015 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00016 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00017 // GNU General Public License for more details.
00018 //
00019 // You should have received a copy of the GNU General Public License
00020 // along with this program; if not, write to the Free Software
00021 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
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 <functional>
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<FixedBuffer> nonLeafRecordBuf;
00066     boost::scoped_array<FixedBuffer> 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<PBuffer>(&leafRecord.key);
00142     leafTupleData[1].pData = reinterpret_cast<PBuffer>(&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     // Load the btree with random values
00160 
00161     treeDescriptor.rootPageId = NULL_PAGE_ID;
00162     BTreeBuilder builder(treeDescriptor, pRandomSegment);
00163 
00164     keyData.compute(builder.getKeyDescriptor());
00165     keyData[0].pData = reinterpret_cast<PConstBuffer>(&leafRecord.key);
00166 
00167     builder.createEmptyRoot();
00168     treeDescriptor.rootPageId = builder.getRootPageId();
00169 
00170     // Generate random key/value data
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         // +2 to guarantee holes
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     // Load the data into the tree
00195     builder.build(*pInputStream,nRecords,1.0);
00196     treeDescriptor.rootPageId = builder.getRootPageId();
00197 
00198     // Make sure we can search for each key individually
00199     pInputStream->seekSegPos(startPos);
00200     testSearch(pInputStream,nRecords);
00201 
00202     // Make sure we can scan all tuples
00203     pInputStream->seekSegPos(startPos);
00204     testScan(pInputStream,nRecords);
00205 
00206     // Deallocate the test data storage
00207     pInputStream->seekSegPos(startPos);
00208     pInputStream->setDeallocate(true);
00209     pInputStream.reset();
00210 
00211     // And deallocate the tree's storage
00212     builder.truncate(true);
00213 }
00214 
00215 void BTreeReadersTest::testSearch(
00216     SharedByteInputStream pInputStream,
00217     uint nRecords)
00218 {
00219     // Search for each key in the btree using both leaf and non-leaf readers
00220 
00221     BTreeNonLeafReader nonLeafReader(treeDescriptor);
00222     BTreeLeafReader leafReader(treeDescriptor);
00223     for (uint i = 0; i < nRecords; ++i) {
00224         // First search for the leaf pageId containing the desired key value
00225         // using the nonLeafReader, provided this is a multi-level tree.
00226         // If not, then directly search the leaf.
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         // Use the leafReader to locate the key in the leaf page
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     // Read records from both leaf and non-leaf pages starting from left
00263     // to right.
00264 
00265     BTreeNonLeafReader nonLeafReader(treeDescriptor);
00266     BTreeLeafReader leafReader(treeDescriptor);
00267 
00268     // Position to the first record in the non-leaf page, just above the leaf
00269     // level.
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             // Read the non-leaf record to locate the leaf pageId.
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         // Position to the start of that leaf page.
00300         found = leafReader.searchFirst();
00301         if (!found) {
00302             BOOST_FAIL("searchFirst on leaf found nothing");
00303         }
00304 
00305         // Iterate over each record in the leaf page until we hit the
00306         // end of the page.
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         // Check that the last key on the leaf matches the last one read
00324         // in the loop above.
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             // Position to the next record in the non-leaf page, then loop back
00339             // and repeat.
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 // End BTreeReadersTest.cpp

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