activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From chir...@apache.org
Subject svn commit: r688859 - in /activemq/sandbox/kahadb/src: main/java/org/apache/kahadb/page/ test/java/org/apache/kahadb/page/
Date Mon, 25 Aug 2008 20:11:14 GMT
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();
-    }
 }



Mime
View raw message