Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4595] branches/QUADS_QUERY_BRANCH/bigdata/src
|
From: <tho...@us...> - 2011-06-01 19:09:48
|
Revision: 4595
http://bigdata.svn.sourceforge.net/bigdata/?rev=4595&view=rev
Author: thompsonbry
Date: 2011-06-01 19:09:40 +0000 (Wed, 01 Jun 2011)
Log Message:
-----------
Modified IndexSegmentPlan, IndexSegmentBuilder, etc. to permit the build of an index with an empty root leaf. Previously, the root leaf was not written out at all for this case. However, this was causing problems with the IndexSegmentTupleCursor which does not do top-down navigation and did not automatically provide a false empty root.
https://sourceforge.net/apps/trac/bigdata/ticket/149
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/BTreeUtilizationReport.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentBuilder.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentCheckpoint.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentPlan.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/Leaf.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestAll_IndexSegment.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromByteArray.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilderWithBlobCapacity.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilderWithSmallTree.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentPlan.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilder_EmptyIndex.java
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/BTreeUtilizationReport.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/BTreeUtilizationReport.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/BTreeUtilizationReport.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -70,7 +70,8 @@
nodeUtilization = (int) (nnodes == 0 ? 100 : (100L * numNonRootNodes)
/ (nnodes * (long) branchingFactor));
- leafUtilization = (int) ((100L * nentries) / (nleaves * (long) branchingFactor));
+ leafUtilization = (int) (nleaves == 0 ? 0 : (100L * nentries)
+ / (nleaves * (long) branchingFactor));
totalUtilization = (nodeUtilization + leafUtilization) / 2;
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentBuilder.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentBuilder.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentBuilder.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -1718,6 +1718,20 @@
// // Flag used to flush the last leaf iff it is dirty.
// boolean needsFlush = false;
+
+ if (plan.nentries == 0) {
+
+ /*
+ * A single empty root leaf.
+ */
+
+ leaf.reset(plan.numInNode[leaf.level][0]);
+
+ flushNodeOrLeaf(leaf);
+
+ return;
+
+ }
// For each leaf in the plan while tuples remain.
for (int i = 0; i < plan.nleaves && entryIterator.hasNext(); i++) {
@@ -2486,9 +2500,10 @@
* immediately above.
*
* Note: We only invoke flush() if a leaf has data so we should
- * never be in a position of writing out an empty leaf.
+ * never be in a position of writing out an empty leaf (with the
+ * exception of a B+Tree which has no tuples).
*/
- assert lastLeafData.getKeyCount() > 0 : "Last leaf is empty?";
+ assert plan.nentries == 0 || lastLeafData.getKeyCount() > 0 : "Last leaf is empty?";
if (log.isDebugEnabled())
log.debug("updating last leaf"//
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentCheckpoint.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentCheckpoint.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentCheckpoint.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -663,51 +663,52 @@
if (nentries < 0)
throw new RootBlockException("nentries=" + nentries);
- if (nentries == 0) {
-
- /*
- * Empty index segment.
- */
-
- if (nleaves != 0)
- throw new RootBlockException("empty index but nleaves="
- + nleaves);
-
- if (nnodes != 0)
- throw new RootBlockException("empty index but nnodes="
- + nnodes);
+// if (nentries == 0) {
+//
+// /*
+// * Empty index segment.
+// */
+//
+// if (nleaves != 0)
+// throw new RootBlockException("empty index but nleaves="
+// + nleaves);
+//
+// if (nnodes != 0)
+// throw new RootBlockException("empty index but nnodes="
+// + nnodes);
+//
+// if (maxNodeOrLeafLength != 0)
+// throw new RootBlockException(
+// "empty index but maxNodeOrLeafLength="
+// + maxNodeOrLeafLength);
+//
+// if (extentLeaves != 0L)
+// throw new RootBlockException("empty index but extentLeaves="
+// + extentLeaves);
+//
+// if (offsetLeaves != 0L)
+// throw new RootBlockException("empty index but offsetLeaves="
+// + offsetLeaves);
+//
+// if (extentNodes != 0L)
+// throw new RootBlockException("empty index but extentNodes="
+// + extentNodes);
+//
+// if (offsetNodes != 0L)
+// throw new RootBlockException("empty index but offsetNodes="
+// + offsetNodes);
+//
+// if (addrFirstLeaf != 0L)
+// throw new RootBlockException("empty index but addrFirstLeaf="
+// + addrFirstLeaf);
+//
+// if (addrLastLeaf != 0L)
+// throw new RootBlockException("empty index but addrLastLeaf="
+// + addrLastLeaf);
+//
+// } else {
+ {
- if (maxNodeOrLeafLength != 0)
- throw new RootBlockException(
- "empty index but maxNodeOrLeafLength="
- + maxNodeOrLeafLength);
-
- if (extentLeaves != 0L)
- throw new RootBlockException("empty index but extentLeaves="
- + extentLeaves);
-
- if (offsetLeaves != 0L)
- throw new RootBlockException("empty index but offsetLeaves="
- + offsetLeaves);
-
- if (extentNodes != 0L)
- throw new RootBlockException("empty index but extentNodes="
- + extentNodes);
-
- if (offsetNodes != 0L)
- throw new RootBlockException("empty index but offsetNodes="
- + offsetNodes);
-
- if (addrFirstLeaf != 0L)
- throw new RootBlockException("empty index but addrFirstLeaf="
- + addrFirstLeaf);
-
- if (addrLastLeaf != 0L)
- throw new RootBlockException("empty index but addrLastLeaf="
- + addrLastLeaf);
-
- } else {
-
if (nleaves <= 0)
throw new RootBlockException("nleaves=" + nleaves);
@@ -1015,7 +1016,7 @@
sb.append(", nnodes=" + nnodes);
sb.append(", nentries=" + nentries);
sb.append(", maxNodeOrLeafLength=" + maxNodeOrLeafLength);
- sb.append(", leavesRegion={extent=" + extentLeaves+", offset="+offsetLeaves+"}, avgLeafSize="+(extentLeaves/nleaves));
+ sb.append(", leavesRegion={extent=" + extentLeaves+", offset="+offsetLeaves+"}, avgLeafSize="+(nleaves==0?0:(extentLeaves/nleaves)));
sb.append(", nodesRegion={extent=" + extentNodes+", offset="+offsetNodes+"}, avgNodeSize="+(nnodes==0?0:(extentNodes/nnodes)));
sb.append(", blobsRegion={extent=" + extentBlobs+", offset="+offsetBlobs+"}");
sb.append(", addrRoot=" + am.toString(addrRoot));
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentPlan.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentPlan.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/IndexSegmentPlan.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -156,11 +156,11 @@
if (log.isInfoEnabled())
log.info("Empty tree.");
- nleaves = 0;
+ nleaves = 1;
height = 0;
- numInLeaf = new int[]{};
- numInNode = new int[][]{};
- numInLevel = new long[]{};
+ numInLeaf = new int[]{0};
+ numInNode = new int[][]{new int[]{0}};
+ numInLevel = new long[]{1};
nnodes = 0;
return;
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/Leaf.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/Leaf.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/Leaf.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -1991,8 +1991,16 @@
final int nkeys = this.getKeyCount();
final int minKeys = this.minKeys();
final int maxKeys = this.maxKeys();
-
- if ((btree.root != this) && (nkeys < minKeys)) {
+
+ /*
+ * Since the index segment does not materialize the root when running a
+ * leaf cursor we can not rely on [btree.root != this].
+ */
+ final boolean isRoot = (btree.root == this)
+ || ((btree instanceof IndexSegment) && btree.getEntryCount() == 0);
+
+ if (!isRoot
+ && (nkeys < minKeys)) {
/*
* Min keys failure.
*
@@ -2000,7 +2008,7 @@
*/
out.println(indent(height) + "ERROR: too few keys: m="
+ branchingFactor + ", minKeys=" + minKeys + ", nkeys="
- + nkeys + ", isLeaf=" + isLeaf());
+ + nkeys + ", isLeaf=" + isLeaf() + ", isRoot=" + isRoot);
ok = false;
}
@@ -2008,7 +2016,7 @@
// max keys failure.
out.println(indent(height) + "ERROR: too many keys: m="
+ branchingFactor + ", maxKeys=" + maxKeys + ", nkeys="
- + nkeys + ", isLeaf=" + isLeaf());
+ + nkeys + ", isLeaf=" + isLeaf() + ", isRoot=" + isRoot);
ok = false;
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestAll_IndexSegment.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestAll_IndexSegment.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestAll_IndexSegment.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -72,6 +72,8 @@
suite.addTestSuite(TestIndexSegmentAddressManager.class);
// test write and read back of the index segment metadata record.
suite.addTestSuite(TestIndexSegmentCheckpoint.class);
+ // test with an empty B+Tree.
+ suite.addTestSuite(TestIndexSegmentBuilder_EmptyIndex.class);
// test with small known examples in detail.
suite.addTestSuite(TestIndexSegmentBuilderWithSmallTree.class);
// and add in a stress test suite for those small examples.
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromByteArray.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromByteArray.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromByteArray.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -384,8 +384,8 @@
final Random r = new Random();
- // #of
- final int limit = 1000;
+ // #of iterations
+ final long limit = 1000000;
// Note: length is guaranteed to be LT int32 bits so [int] index is Ok.
final int len = r.nextInt(Bytes.kilobyte32 * 8) + 1;
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilderWithBlobCapacity.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilderWithBlobCapacity.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilderWithBlobCapacity.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -81,6 +81,10 @@
}
}
+ protected boolean useRawRecords() {
+ return true;
+ }
+
protected IndexSegmentCheckpoint doBuildAndDiscardCache(final BTree btree,
final int m) throws IOException, Exception {
@@ -108,8 +112,4 @@
}
- protected boolean useRawRecords() {
- return true;
- }
-
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilderWithSmallTree.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilderWithSmallTree.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilderWithSmallTree.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -26,8 +26,6 @@
import java.io.File;
import java.io.IOException;
-import junit.framework.TestSuite;
-
import org.apache.log4j.Level;
import com.bigdata.LRUNexus;
@@ -43,12 +41,6 @@
public class TestIndexSegmentBuilderWithSmallTree extends
AbstractIndexSegmentTestCase {
- private File outFile;
-
- private File tmpDir;
-
- private boolean bufferNodes;
-
public TestIndexSegmentBuilderWithSmallTree() {
}
@@ -56,6 +48,12 @@
super(name);
}
+ private File outFile;
+
+ private File tmpDir;
+
+ private boolean bufferNodes;
+
public void setUp() throws Exception {
super.setUp();
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilder_EmptyIndex.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilder_EmptyIndex.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilder_EmptyIndex.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -0,0 +1,194 @@
+/**
+
+Copyright (C) SYSTAP, LLC 2006-2011. All rights reserved.
+
+Contact:
+ SYSTAP, LLC
+ 4501 Tower Road
+ Greensboro, NC 27410
+ lic...@bi...
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+/*
+ * Created on Jun 1, 2011
+ */
+
+package com.bigdata.btree;
+
+import java.io.File;
+import java.io.IOException;
+
+import com.bigdata.LRUNexus;
+
+/**
+ * Test suite for building an {@link IndexSegment} from an empty {@link BTree}.
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id$
+ */
+public class TestIndexSegmentBuilder_EmptyIndex extends
+ AbstractIndexSegmentTestCase {
+
+ /**
+ *
+ */
+ public TestIndexSegmentBuilder_EmptyIndex() {
+ }
+
+ /**
+ * @param name
+ */
+ public TestIndexSegmentBuilder_EmptyIndex(String name) {
+ super(name);
+ }
+
+ private File outFile;
+
+ private File tmpDir;
+
+ private boolean bufferNodes;
+
+ public void setUp() throws Exception {
+
+ super.setUp();
+
+ // random choice.
+ bufferNodes = r.nextBoolean();
+
+ outFile = new File(getName() + ".seg");
+
+ if (outFile.exists() && !outFile.delete()) {
+
+ throw new RuntimeException("Could not delete file: " + outFile);
+
+ }
+
+ tmpDir = outFile.getAbsoluteFile().getParentFile();
+
+ }
+
+ public void tearDown() throws Exception {
+
+ if (outFile != null && outFile.exists() && !outFile.delete()) {
+
+ log.warn("Could not delete file: " + outFile);
+
+ }
+
+ super.tearDown();
+
+ // clear references.
+ outFile = null;
+ tmpDir = null;
+
+ }
+
+ /**
+ * Test ability to build an index segment from an empty {@link BTree}.
+ */
+ public void test_buildOrder3_emptyIndex() throws Exception {
+
+ final BTree btree = getBTree(3);
+
+ final IndexSegmentCheckpoint checkpoint = doBuildAndDiscardCache(btree,
+ 3/* m */);
+
+ /*
+ * Verify can load the index file and that the metadata associated with
+ * the index file is correct (we are only checking those aspects that
+ * are easily defined by the test case and not, for example, those
+ * aspects that depend on the specifics of the length of serialized
+ * nodes or leaves).
+ */
+
+ final IndexSegmentStore segStore = new IndexSegmentStore(outFile);
+
+ assertEquals(checkpoint.commitTime, segStore.getCheckpoint().commitTime);
+ assertEquals(0, segStore.getCheckpoint().height);
+ assertEquals(1, segStore.getCheckpoint().nleaves);
+ assertEquals(0, segStore.getCheckpoint().nnodes);
+ assertEquals(0, segStore.getCheckpoint().nentries);
+
+ final IndexSegment seg = segStore.loadIndexSegment();
+
+ try {
+
+ assertEquals(3, seg.getBranchingFactor());
+ assertEquals(0, seg.getHeight());
+ assertEquals(1, seg.getLeafCount());
+ assertEquals(0, seg.getNodeCount());
+ assertEquals(0, seg.getEntryCount());
+
+ testForwardScan(seg);
+ testReverseScan(seg);
+
+ // test index segment structure.
+ dumpIndexSegment(seg);
+
+ /*
+ * Test the tree in detail.
+ */
+ {
+
+ final Leaf a = (Leaf) seg.getRoot();
+
+ assertKeys(new int[] {}, a);
+
+ // Note: values are verified by testing the total order.
+
+ }
+
+ /*
+ * Verify the total index order.
+ */
+ assertSameBTree(btree, seg);
+
+ } finally {
+
+ // close so we can delete the backing store.
+ seg.close();
+
+ }
+
+ }
+
+ protected IndexSegmentCheckpoint doBuildAndDiscardCache(final BTree btree,
+ final int m) throws IOException, Exception {
+
+ final long commitTime = System.currentTimeMillis();
+
+ final IndexSegmentCheckpoint checkpoint = IndexSegmentBuilder
+ .newInstance(outFile, tmpDir, btree.getEntryCount(),
+ btree.rangeIterator(), m, btree.getIndexMetadata(),
+ commitTime, true/* compactingMerge */, bufferNodes)
+ .call();
+
+ if (LRUNexus.INSTANCE != null) {
+
+ /*
+ * Clear the records for the index segment from the cache so we will
+ * read directly from the file. This is necessary to ensure that the
+ * data on the file is good rather than just the data in the cache.
+ */
+
+ LRUNexus.INSTANCE.deleteCache(checkpoint.segmentUUID);
+
+ }
+
+ return checkpoint;
+
+ }
+
+}
Property changes on: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentBuilder_EmptyIndex.java
___________________________________________________________________
Added: svn:keywords
+ Id Date Revision Author HeadURL
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentPlan.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentPlan.java 2011-06-01 17:55:48 UTC (rev 4594)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexSegmentPlan.java 2011-06-01 19:09:40 UTC (rev 4595)
@@ -27,52 +27,10 @@
package com.bigdata.btree;
-
/**
* Test suite for efficient post-order rebuild of an index in an external index
* segment.
*
- * @todo verify post-conditions for files (temp file is deleted, perhaps the
- * index segment is read only).
- *
- * @todo try building large indices, exporting them into index segments, and
- * then verifying that the index segments have the correct data. We can
- * run a variety of index stress tests to build the index, sweep in data
- * from the file system, etc., and then generate the corresponding index
- * segment and validate it against the in memory {@link BTree}.
- *
- * @todo The notion of merging multiple index segments requires a notion of
- * which index segments are more recent or alternatively which values are
- * more recent so that we can reconcile values for the same key. this is
- * linked to how we will handle transactional isolation.
- *
- * @todo Handle "delete" markers. For full transactional isolation we need to
- * keep delete markers around until there are no more live transactions
- * that could read the index entry. This suggests that we probably want to
- * use the transaction timestamp rather than a version counter. Consider
- * that a read by tx1 needs to check the index on the journal and then
- * each index segment in turn in reverse historical order until an entry
- * (potentially a delete marker) is found that is equal to or less than
- * the timestamp of the committed state from which tx1 was born. This
- * means that an index miss must test the journal and all live segments
- * for that index (hence the use of bloom filters to filter out index
- * misses). It also suggests that we should keep the timestamp as part of
- * the key, except in the ground state index on the journal where the
- * timestamp is the timestamp of the last commit of the journal. This
- * probably will also address VLR TX that would span a freeze of the
- * journal. We expunge the isolated index into a segment and do a merge
- * when the transaction finally commits. We wind up doing the same
- * validation and merge steps as when the isolation occurs within a more
- * limited buffer, but in more of a batch fashion. This might work nicely
- * if we buffer the isolatation index out to a certain size in memory and
- * then start to spill it onto the journal. If fact, the hard reference
- * queue already does this so we can just test to see if (a) anything has
- * been written out from the isolation index; and (b) whether or not the
- * journal was frozen since the isolation index was created.
- *
- * Should the merge down should impose the transaction commit timestamp on the
- * items in the index?
- *
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
*/
@@ -368,6 +326,48 @@
/**
* Tests {@link IndexSegmentPlan} for a tree with a branching factor of
+ * (m=10) and (n=10) entries (everything fits into the root leaf)
+ */
+ public void test_plan_m10_n10_everythingInTheRootLeaf() {
+
+ IndexSegmentPlan plan = new IndexSegmentPlan(10,10);
+
+ assertEquals("m",10,plan.m);
+ assertEquals("(m+1/2)",5,plan.m2);
+ assertEquals("nentries",10,plan.nentries);
+ assertEquals("nleaves",1,plan.nleaves);
+ assertEquals("nnodes",0,plan.nnodes);
+ assertEquals("height",0,plan.height);
+ assertEquals("numInLeaf[]",new int[]{10},plan.numInLeaf);
+ assertEquals("numInLevel[]",new long[]{1},plan.numInLevel);
+ assertEquals("numInNode[][]",plan.height+1,plan.numInNode.length);
+ assertEquals("numInNode[0][]",new int[]{10},plan.numInNode[0]);
+
+ }
+
+ /**
+ * Tests {@link IndexSegmentPlan} for a tree with a branching factor of
+ * (m=3) and (n=0) entries.
+ */
+ public void test_plan_m3_n0_emptyRootLeaf() {
+
+ final IndexSegmentPlan plan = new IndexSegmentPlan(3, 0);
+
+ assertEquals("m",3,plan.m);
+ assertEquals("(m+1/2)",2,plan.m2);
+ assertEquals("nentries",0,plan.nentries);
+ assertEquals("nleaves",1,plan.nleaves);
+ assertEquals("nnodes",0,plan.nnodes);
+ assertEquals("height",0,plan.height);
+ assertEquals("numInLeaf[]",new int[]{0},plan.numInLeaf);
+ assertEquals("numInLevel[]",new long[]{1},plan.numInLevel);
+ assertEquals("numInNode[][]",plan.height+1,plan.numInNode.length);
+ assertEquals("numInNode[0][]",new int[]{0},plan.numInNode[0]);
+
+ }
+
+ /**
+ * Tests {@link IndexSegmentPlan} for a tree with a branching factor of
* (m=3) and (n=20) entries.
*/
public void test_plan_m3_n20() {
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
