Author: chirino
Date: Mon Aug 25 13:11:14 2008
New Revision: 688859
URL: http://svn.apache.org/viewvc?rev=688859&view=rev
Log:
- Implemented branch pruning in the BTree implementation. Before empty branch
nodes were not being freed up.
- The BTreeIndexBenchMark now runs fine without errors
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexBenchMark.java
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexBenchmark.java
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexTestSupport.java
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java?rev=688859&r1=688858&r2=688859&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java
(original)
+++
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java
Mon Aug 25 13:11:14 2008
@@ -17,6 +17,11 @@
package org.apache.kahadb.page;
import java.io.IOException;
+import java.io.OutputStream;
+import java.io.PrintStream;
+import java.io.PrintWriter;
+import java.io.StringWriter;
+import java.io.Writer;
import java.util.concurrent.atomic.AtomicBoolean;
import org.apache.commons.logging.Log;
@@ -141,7 +146,7 @@
this.rootPageId = rootPageId;
}
- public void load() throws IOException {
+ synchronized public void load() throws IOException {
if (loaded.compareAndSet(false, true)) {
LOG.debug("loading");
if( keyMarshaller == null ) {
@@ -168,7 +173,7 @@
}
}
- public void unload() {
+ synchronized public void unload() {
if (loaded.compareAndSet(true, false)) {
root=null;
}
@@ -198,14 +203,36 @@
return false;
}
- public void clear(Transaction tx) throws IOException {
+ synchronized public void clear(Transaction tx) throws IOException {
throw new RuntimeException("Not implemented...");
}
- public int size(Transaction tx) {
+ synchronized public int size(Transaction tx) {
throw new RuntimeException("Not implemented...");
}
+
+ synchronized public int getMinLeafDepth(Transaction tx) throws IOException
{
+ return root.getMinLeafDepth(tx, 0);
+ }
+
+ synchronized public int getMaxLeafDepth(Transaction tx) throws IOException
{
+ return root.getMaxLeafDepth(tx, 0);
+ }
+
+ synchronized public void printStructure(Transaction tx, PrintWriter out)
throws IOException {
+ root.printStructure(tx, out, "");
+ }
+
+ synchronized public void printStructure(Transaction tx, OutputStream out)
throws IOException {
+ PrintWriter pw = new PrintWriter(out,false);
+ root.printStructure(tx, pw, "");
+ pw.flush();
+ }
+
+ synchronized Value getFirst(Transaction tx) throws IOException {
+ return root.getFirst(tx);
+ }
///////////////////////////////////////////////////////////////////
// Internal implementation methods
@@ -251,7 +278,8 @@
void storeNode(Transaction tx, BTreeNode<Key,Value> node, boolean
overflow) throws IOException {
tx.store(node.getPage(), marshaller, overflow);
}
-
+
+
///////////////////////////////////////////////////////////////////
// Property Accessors
///////////////////////////////////////////////////////////////////
@@ -284,5 +312,4 @@
this.prefixer = prefixer;
}
-
}
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java?rev=688859&r1=688858&r2=688859&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java
(original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java
Mon Aug 25 13:11:14 2008
@@ -19,8 +19,11 @@
import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
+import java.io.PrintWriter;
import java.util.Arrays;
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
import org.apache.kahadb.page.BTreeIndex.Prefixer;
@@ -29,7 +32,8 @@
* one Page of a PageFile.
*/
public final class BTreeNode<Key,Value> {
-
+ private static final Log LOG = LogFactory.getLog(BTreeNode.class);
+
// The index that this node is part of.
private final BTreeIndex<Key,Value> index;
// The parent node or null if this is the root node of the BTree
@@ -101,7 +105,7 @@
if( is.readBoolean() ) {
node.children = new long[count+1];
- for (int i = 0; i < count; i++) {
+ for (int i = 0; i < count+1; i++) {
node.children[i] = is.readLong();
}
} else {
@@ -130,41 +134,86 @@
*/
private BTreeNode<Key,Value> getChild(Transaction tx, int idx) throws
IOException {
if (isBranch() && idx >= 0 && idx < children.length) {
- return this.index.loadNode(tx, children[idx], this);
+ BTreeNode<Key, Value> result = this.index.loadNode(tx,
children[idx], this);
+ return result;
} else {
return null;
}
}
- public synchronized Value remove(Transaction tx, Key key) throws
IOException {
- int idx = Arrays.binarySearch(keys, key);
+ public Value remove(Transaction tx, Key key) throws IOException {
if(isBranch()) {
+ int idx = Arrays.binarySearch(keys, key);
idx = idx < 0 ? -(idx + 1) : idx + 1;
- return getChild(tx, idx).remove(tx, key);
+ BTreeNode<Key, Value> node = getChild(tx, idx);
+ if( node.getPageId() == index.getRootPageId() ) {
+ throw new IOException("BTree corrupted: Cylce detected.");
+ }
+ Value rc = node.remove(tx, key);
+
+ // Leaf is empty.. remove it from the branch node.
+ if( node.keys.length == 0 ) {
+ // If the empty node is branch, promote
+ if( node.isBranch() ) {
+ children[idx] = node.children[0];
+ } else {
+ // If it's not the last child
+ if( idx < children.length-1 ) {
+ // Then delete it and key to the right.
+ setBranchData(arrayDelete(keys, idx),
arrayDelete(children, idx));
+ } else {
+ // Then delete it and key to the left
+ setBranchData(arrayDelete(keys, idx-1),
arrayDelete(children, idx));
+ }
+
+ // If we are the root node, and only have 1 child left.
Then
+ // make the root be the leaf node.
+ if( children.length == 1 && parent==null ) {
+ node = getChild(tx, 0);
+ keys = node.keys;
+ children = node.children;
+ values = node.values;
+ // free up the page..
+ tx.free(node.getPage());
+ }
+
+ }
+ index.storeNode(tx, this, true);
+ }
+
+ return rc;
} else {
+ int idx = Arrays.binarySearch(keys, key);
if (idx < 0) {
return null;
} else {
Value oldValue = values[idx];
setLeafData(arrayDelete(keys, idx), arrayDelete(values, idx));
- index.storeNode(tx, this, true);
+
+ if( keys.length!=0 ) {
+ index.storeNode(tx, this, true);
+ } else {
+ // If this leaf is empty and is not the root node..
+ if( parent!=null ) {
+ tx.free(getPage());
+ }
+ }
+
return oldValue;
}
}
}
- public synchronized Value put(Transaction tx, Key key, Value value) throws
IOException {
+ public Value put(Transaction tx, Key key, Value value) throws IOException {
if (key == null) {
throw new IllegalArgumentException("Key cannot be null");
}
- int idx = Arrays.binarySearch(keys, key);
-
if( isBranch() ) {
- idx = idx < 0 ? -(idx + 1) : idx + 1;
- return getChild(tx, idx).put(tx, key, value);
+ return getLeafNode(tx, this, key).put(tx, key, value);
} else {
+ int idx = Arrays.binarySearch(keys, key);
Value oldValue=null;
if (idx >= 0) {
@@ -189,7 +238,7 @@
}
}
- private synchronized void promoteValue(Transaction tx, Key key, long
nodeId) throws IOException {
+ private void promoteValue(Transaction tx, Key key, long nodeId) throws
IOException {
int idx = Arrays.binarySearch(keys, key);
idx = idx < 0 ? -(idx + 1) : idx + 1;
@@ -211,8 +260,8 @@
Key[] rightKeys;
Value[] leftValues=null;
Value[] rightValues=null;
- long[] leftNodeIds=null;
- long[] rightNodeIds=null;
+ long[] leftChildren=null;
+ long[] rightChildren=null;
Key separator;
int vc = keys.length;
@@ -222,14 +271,14 @@
if( isBranch() ) {
leftKeys = createKeyArray(pivot);
- leftNodeIds = new long[leftKeys.length + 1];
+ leftChildren = new long[leftKeys.length + 1];
rightKeys = createKeyArray(vc - (pivot + 1));
- rightNodeIds = new long[rightKeys.length + 1];
+ rightChildren = new long[rightKeys.length + 1];
System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
- System.arraycopy(children, 0, leftNodeIds, 0, leftNodeIds.length);
+ System.arraycopy(children, 0, leftChildren, 0,
leftChildren.length);
System.arraycopy(keys, leftKeys.length + 1, rightKeys, 0,
rightKeys.length);
- System.arraycopy(children, leftNodeIds.length, rightNodeIds, 0,
rightNodeIds.length);
+ System.arraycopy(children, leftChildren.length, rightChildren, 0,
rightChildren.length);
// Is it a Simple Prefix BTree??
Prefixer<Key> prefixer = index.getPrefixer();
@@ -266,8 +315,8 @@
BTreeNode<Key,Value> lNode = this.index.createNode(tx, this);
if( isBranch() ) {
- rNode.setBranchData(rightKeys, rightNodeIds);
- lNode.setBranchData(leftKeys, leftNodeIds);
+ rNode.setBranchData(rightKeys, rightChildren);
+ lNode.setBranchData(leftKeys, leftChildren);
} else {
rNode.setLeafData(rightKeys, rightValues);
lNode.setLeafData(leftKeys, leftValues);
@@ -285,8 +334,8 @@
BTreeNode<Key,Value> rNode = this.index.createNode(tx, parent);
if( isBranch() ) {
- setBranchData(leftKeys, leftNodeIds);
- rNode.setBranchData(rightKeys, rightNodeIds);
+ setBranchData(leftKeys, leftChildren);
+ rNode.setBranchData(rightKeys, rightChildren);
} else {
setLeafData(leftKeys, leftValues);
rNode.setLeafData(rightKeys, rightValues);
@@ -298,19 +347,62 @@
}
}
- // ///////////////////////////////////////////////////////////////
+ public void printStructure(Transaction tx, PrintWriter out, String prefix)
throws IOException {
+ if( prefix.length()>0 && parent == null ) {
+ throw new IllegalStateException("Cycle back to root node
detected.");
+ }
+
+ if( isBranch() ) {
+ for(int i=0 ; i < children.length; i++) {
+ BTreeNode<Key, Value> child = getChild(tx, i);
+ if( i == children.length-1) {
+ out.println(prefix+"\\-
"+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":""));
+ child.printStructure(tx, out, prefix+" ");
+ } else {
+ out.println(prefix+"|-
"+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":"")+" :
"+keys[i]);
+ child.printStructure(tx, out, prefix+" ");
+ }
+ }
+ }
+ }
+
+
+ public int getMinLeafDepth(Transaction tx, int depth) throws IOException {
+ depth++;
+ if( isBranch() ) {
+ int min = Integer.MAX_VALUE;
+ for(int i=0 ; i < children.length; i++) {
+ min = Math.min(min, getChild(tx, i).getMinLeafDepth(tx,
depth));
+ }
+ return min;
+ } else {
+// print(depth*2, "- "+page.getPageId());
+ return depth;
+ }
+ }
- public synchronized Value get(Transaction tx, Key key) throws IOException {
+ public int getMaxLeafDepth(Transaction tx, int depth) throws IOException {
+ depth++;
+ if( isBranch() ) {
+ int v = 0;
+ for(int i=0 ; i < children.length; i++) {
+ v = Math.max(v, getChild(tx, i).getMaxLeafDepth(tx, depth));
+ }
+ depth = v;
+ }
+ return depth;
+ }
+
+ public Value get(Transaction tx, Key key) throws IOException {
if (key == null) {
throw new IllegalArgumentException("Key cannot be null");
}
-
- int idx = Arrays.binarySearch(keys, key);
-
if( isBranch() ) {
- idx = idx < 0 ? -(idx + 1) : idx + 1;
- return getChild(tx, idx).get(tx, key);
+
+
+ return getLeafNode(tx, this, key).get(tx, key);
} else {
+ int idx = Arrays.binarySearch(keys, key);
if (idx < 0) {
return null;
} else {
@@ -318,17 +410,49 @@
}
}
}
+
+ public Value getFirst(Transaction tx) throws IOException {
+ BTreeNode<Key, Value> node = this;
+ while( node .isBranch() ) {
+ node = node.getChild(tx, 0);
+ }
+ if( node.values.length>0 ) {
+ return node.values[0];
+ } else {
+ return null;
+ }
+ }
+
+ private static <Key,Value> BTreeNode<Key, Value> getLeafNode(Transaction
tx, final BTreeNode<Key, Value> node, Key key) throws IOException {
+ BTreeNode<Key, Value> current = node;
+ while( true ) {
+ if( current.isBranch() ) {
+ int idx = Arrays.binarySearch(current.keys, key);
+ idx = idx < 0 ? -(idx + 1) : idx + 1;
+ BTreeNode<Key, Value> child = current.getChild(tx, idx);
+
+ // A little cycle detection for sanity's sake
+ if( child == node ) {
+ throw new IOException("BTree corrupted: Cylce detected.");
+ }
+
+ current = child;
+ } else {
+ break;
+ }
+ }
+ return current;
+ }
- public synchronized boolean contains(Transaction tx, Key key) throws
IOException {
+ public boolean contains(Transaction tx, Key key) throws IOException {
if (key == null) {
throw new IllegalArgumentException("Key cannot be null");
}
- int idx = Arrays.binarySearch(keys, key);
if( isBranch() ) {
- idx = idx < 0 ? -(idx + 1) : idx + 1;
- return getChild(tx, idx).contains(tx, key);
+ return getLeafNode(tx, this, key).contains(tx, key);
} else {
+ int idx = Arrays.binarySearch(keys, key);
if (idx < 0) {
return false;
} else {
@@ -352,7 +476,8 @@
///////////////////////////////////////////////////////////////////
// Implementation methods
///////////////////////////////////////////////////////////////////
-
+
+
private boolean allowOverflow() {
// Only allow page overflow if there are <= 3 keys in the node.
Otherwise a split will occur on overflow
return this.keys.length<=3;
@@ -393,16 +518,16 @@
return newVals;
}
-// static private long[] arrayDelete(long[] vals, int idx) {
-// long[] newVals = new long[vals.length - 1];
-// if (idx > 0) {
-// System.arraycopy(vals, 0, newVals, 0, idx);
-// }
-// if (idx < newVals.length) {
-// System.arraycopy(vals, idx + 1, newVals, idx, newVals.length -
idx);
-// }
-// return newVals;
-// }
+ static private long[] arrayDelete(long[] vals, int idx) {
+ long[] newVals = new long[vals.length - 1];
+ if (idx > 0) {
+ System.arraycopy(vals, 0, newVals, 0, idx);
+ }
+ if (idx < newVals.length) {
+ System.arraycopy(vals, idx + 1, newVals, idx, newVals.length -
idx);
+ }
+ return newVals;
+ }
@SuppressWarnings("unchecked")
static private <T> T[] arrayInsert(T[] vals, T val, int idx) {
@@ -457,6 +582,8 @@
public void setPage(Page<BTreeNode<Key, Value>> page) {
this.page = page;
}
+
+
}
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java?rev=688859&r1=688858&r2=688859&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
(original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
Mon Aug 25 13:11:14 2008
@@ -96,7 +96,7 @@
private boolean enablePageCaching=true;
private boolean enableAsyncWrites=false;
- private int pageCacheSize = 10;
+ private int pageCacheSize = 100;
private TreeMap<Long, PageWrite> writes=new TreeMap<Long, PageWrite>();
private Thread writerThread;
Modified:
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexBenchMark.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexBenchMark.java?rev=688859&r1=688858&r2=688859&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexBenchMark.java
(original)
+++
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexBenchMark.java
Mon Aug 25 13:11:14 2008
@@ -17,6 +17,9 @@
package org.apache.kahadb.page;
import java.io.File;
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.text.NumberFormat;
import org.apache.kahadb.LongMarshaller;
import org.apache.kahadb.Store;
@@ -24,6 +27,16 @@
public class BTreeIndexBenchMark extends IndexBenchmark {
+ private NumberFormat nf;
+
+ @Override
+ public void setUp() throws Exception {
+ super.setUp();
+ nf = NumberFormat.getIntegerInstance();
+ nf.setMinimumIntegerDigits(10);
+ nf.setGroupingUsed(false);
+ }
+
@Override
protected Index<String, Long> createIndex() throws Exception {
@@ -37,5 +50,20 @@
return index;
}
+
+ @Override
+ protected void dumpIndex(Index<String, Long> index) throws IOException {
+ Transaction tx = pf.tx();
+ ((BTreeIndex)index).printStructure(tx, System.out);
+ }
+
+ /**
+ * Overriding so that this generates keys that are the worst case for the
BTree. Keys that
+ * always insert to the end of the BTree.
+ */
+ @Override
+ protected String key(long i) {
+ return "a-long-message-id-like-key:"+nf.format(i);
+ }
}
Modified:
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java?rev=688859&r1=688858&r2=688859&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java
(original)
+++
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java
Mon Aug 25 13:11:14 2008
@@ -16,11 +16,24 @@
*/
package org.apache.kahadb.page;
+import java.io.PrintWriter;
+import java.text.NumberFormat;
+
import org.apache.kahadb.LongMarshaller;
import org.apache.kahadb.StringMarshaller;
public class BTreeIndexTest extends IndexTestSupport {
+ private NumberFormat nf;
+
+ @Override
+ protected void setUp() throws Exception {
+ super.setUp();
+ nf = NumberFormat.getIntegerInstance();
+ nf.setMinimumIntegerDigits(6);
+ nf.setGroupingUsed(false);
+ }
+
@Override
protected Index<String, Long> createIndex() throws Exception {
@@ -34,4 +47,76 @@
return index;
}
+ /**
+ * Yeah, the current implementation does NOT try to balance the tree.
Here is
+ * a test case showing that it gets out of balance.
+ *
+ * @throws Exception
+ */
+ public void disabled_testTreeBalancing() throws Exception {
+ createPageFileAndIndex(100);
+
+ BTreeIndex index = ((BTreeIndex)this.index);
+ this.index.load();
+
+ doInsert(50);
+
+ int minLeafDepth = index.getMinLeafDepth(tx);
+ int maxLeafDepth = index.getMaxLeafDepth(tx);
+ assertTrue("Tree is balanced", maxLeafDepth-minLeafDepth <= 1);
+
+ // Remove some of the data
+ doRemove(16);
+ minLeafDepth = index.getMinLeafDepth(tx);
+ maxLeafDepth = index.getMaxLeafDepth(tx);
+
+ System.out.println( "min:"+minLeafDepth );
+ System.out.println( "max:"+maxLeafDepth );
+ index.printStructure(tx, new PrintWriter(System.out));
+
+ assertTrue("Tree is balanced", maxLeafDepth-minLeafDepth <= 1);
+
+ this.index.unload();
+ }
+
+ public void testPruning() throws Exception {
+ createPageFileAndIndex(100);
+
+ BTreeIndex index = ((BTreeIndex)this.index);
+
+ String keyRoot = "key:";
+ this.index.load();
+
+ int minLeafDepth = index.getMinLeafDepth(tx);
+ int maxLeafDepth = index.getMaxLeafDepth(tx);
+ assertEquals(1, minLeafDepth);
+ assertEquals(1, maxLeafDepth);
+
+ doInsert(1000);
+
+ minLeafDepth = index.getMinLeafDepth(tx);
+ maxLeafDepth = index.getMaxLeafDepth(tx);
+ assertTrue("Depth of tree grew", minLeafDepth > 1);
+ assertTrue("Depth of tree grew", maxLeafDepth > 1);
+
+ // Remove the data.
+ doRemove(1000);
+ minLeafDepth = index.getMinLeafDepth(tx);
+ maxLeafDepth = index.getMaxLeafDepth(tx);
+
+ assertEquals(1, minLeafDepth);
+ assertEquals(1, maxLeafDepth);
+
+ this.index.unload();
+ }
+
+
+ /**
+ * Overriding so that this generates keys that are the worst case for the
BTree. Keys that
+ * always insert to the end of the BTree.
+ */
+ @Override
+ protected String key(int i) {
+ return "key:"+nf.format(i);
+ }
}
Modified:
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexBenchmark.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexBenchmark.java?rev=688859&r1=688858&r2=688859&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexBenchmark.java
(original)
+++
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexBenchmark.java
Mon Aug 25 13:11:14 2008
@@ -17,6 +17,7 @@
package org.apache.kahadb.page;
import java.io.File;
+import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
@@ -100,10 +101,10 @@
while (!shutdown.get()) {
long c = counter;
- String key = "a-long-message-id-like-key-" + c;
-
+ String key = key(c);
index.put(tx, key, c);
tx.commit();
+ Thread.yield(); // This avoids consumer starvation..
onProduced(counter++);
}
@@ -116,6 +117,11 @@
public void onProduced(long counter) {
}
}
+
+ protected String key(long c) {
+ return "a-long-message-id-like-key-" + c;
+ }
+
class Consumer extends Thread {
private final String name;
@@ -139,14 +145,15 @@
long counter = 0;
while (!shutdown.get()) {
long c = counter;
- String key = "a-long-message-id-like-key-" + c;
+ String key = key(c);
+
Long record = index.get(tx, key);
if (record != null) {
- index.remove(tx, key);
+ if( index.remove(tx, key) == null ) {
+ System.out.print("Remove failed...");
+ }
tx.commit();
onConsumed(counter++);
- } else {
- Thread.sleep(0);
}
}
} catch (Throwable e) {
@@ -158,6 +165,9 @@
}
}
+ protected void dumpIndex(Index<String, Long> index) throws IOException {
+ }
+
public void testLoad() throws Exception {
final Producer producers[] = new Producer[INDEX_COUNT];
Modified:
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexTestSupport.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexTestSupport.java?rev=688859&r1=688858&r2=688859&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexTestSupport.java
(original)
+++
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/IndexTestSupport.java
Mon Aug 25 13:11:14 2008
@@ -46,95 +46,102 @@
IOHelper.mkdirs(directory);
IOHelper.deleteChildren(directory);
+ }
+
+ protected void tearDown() throws Exception {
+ if( pf!=null ) {
+ pf.unload();
+ pf.delete();
+ }
+ }
+
+ protected void createPageFileAndIndex(int pageSize) throws Exception {
pf = new PageFile(directory, getClass().getName());
+ pf.setPageSize(pageSize);
pf.load();
tx = pf.tx();
-
this.index = createIndex();
}
-
+
abstract protected Index<String, Long> createIndex() throws Exception;
- public void testHashIndex() throws Exception {
- String keyRoot = "key:";
+ public void testIndex() throws Exception {
+ createPageFileAndIndex(500);
+
this.index.load();
- doInsert(keyRoot);
+ doInsert(COUNT);
this.index.unload();
this.index.load();
- checkRetrieve(keyRoot);
- doRemove(keyRoot);
+ checkRetrieve(COUNT);
+ doRemove(COUNT);
this.index.unload();
this.index.load();
- doInsert(keyRoot);
- doRemoveHalf(keyRoot);
- doInsertHalf(keyRoot);
+ doInsert(COUNT);
+ doRemoveHalf(COUNT);
+ doInsertHalf(COUNT);
this.index.unload();
this.index.load();
- checkRetrieve(keyRoot);
+ checkRetrieve(COUNT);
this.index.unload();
}
- void doInsert(String keyRoot) throws Exception {
- for (int i = 0; i < COUNT; i++) {
- index.put(tx, keyRoot + i, (long)i);
+ void doInsert(int count) throws Exception {
+ for (int i = 0; i < count; i++) {
+ index.put(tx, key(i), (long)i);
tx.commit();
}
}
- void checkRetrieve(String keyRoot) throws IOException {
- for (int i = 0; i < COUNT; i++) {
- Long item = index.get(tx, keyRoot + i);
- assertNotNull("Key missing: "+keyRoot + i, item);
+ protected String key(int i) {
+ return "key:"+i;
+ }
+
+ void checkRetrieve(int count) throws IOException {
+ for (int i = 0; i < count; i++) {
+ Long item = index.get(tx, key(i));
+ assertNotNull("Key missing: "+key(i), item);
}
}
- void doRemoveHalf(String keyRoot) throws Exception {
- for (int i = 0; i < COUNT; i++) {
+ void doRemoveHalf(int count) throws Exception {
+ for (int i = 0; i < count; i++) {
if (i % 2 == 0) {
- index.remove(tx, keyRoot + i);
+ assertNotNull("Expected remove to return value for index "+i,
index.remove(tx, key(i)));
tx.commit();
}
}
}
- void doInsertHalf(String keyRoot) throws Exception {
- for (int i = 0; i < COUNT; i++) {
+ void doInsertHalf(int count) throws Exception {
+ for (int i = 0; i < count; i++) {
if (i % 2 == 0) {
- index.put(tx, keyRoot + i, (long)i);
+ index.put(tx, key(i), (long)i);
tx.commit();
}
}
}
- void doRemove(String keyRoot) throws Exception {
- for (int i = 0; i < COUNT; i++) {
- index.remove(tx, keyRoot + i);
+ void doRemove(int count) throws Exception {
+ for (int i = 0; i < count; i++) {
+ assertNotNull("Expected remove to return value for index "+i,
index.remove(tx, key(i)));
tx.commit();
}
- for (int i = 0; i < COUNT; i++) {
- Long item = index.get(tx, keyRoot + i);
+ for (int i = 0; i < count; i++) {
+ Long item = index.get(tx, key(i));
assertNull(item);
}
}
- void doRemoveBackwards(String keyRoot) throws Exception {
- for (int i = COUNT - 1; i >= 0; i--) {
- index.remove(tx, keyRoot + i);
+ void doRemoveBackwards(int count) throws Exception {
+ for (int i = count - 1; i >= 0; i--) {
+ index.remove(tx, key(i));
tx.commit();
}
- for (int i = 0; i < COUNT; i++) {
- Long item = index.get(tx, keyRoot + i);
+ for (int i = 0; i < count; i++) {
+ Long item = index.get(tx, key(i));
assertNull(item);
}
}
- /**
- * @throws java.lang.Exception
- * @see junit.framework.TestCase#tearDown()
- */
- protected void tearDown() throws Exception {
- super.tearDown();
- pf.unload();
- }
}
