activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From chir...@apache.org
Subject svn commit: r688895 - in /activemq/sandbox/kahadb/src: main/java/org/apache/kahadb/page/ test/java/org/apache/kahadb/page/
Date Mon, 25 Aug 2008 22:01:07 GMT
Author: chirino
Date: Mon Aug 25 15:01:06 2008
New Revision: 688895

URL: http://svn.apache.org/viewvc?rev=688895&view=rev
Log:
- BTree leaf nodes are now linked for efficient iteration purposes.
- Added an iterator() method to the Index interface.


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/HashIndex.java
    activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java
    activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
    activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java
    activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.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=688895&r1=688894&r2=688895&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
15:01:06 2008
@@ -22,6 +22,8 @@
 import java.io.PrintWriter;
 import java.io.StringWriter;
 import java.io.Writer;
+import java.util.Iterator;
+import java.util.Map;
 import java.util.concurrent.atomic.AtomicBoolean;
 
 import org.apache.commons.logging.Log;
@@ -31,7 +33,8 @@
 /**
  * BTreeIndex represents a Variable Magnitude B+Tree in a Page File.
  * A BTree is a bit flexible in that it can be used for set or
- * map-based indexing.
+ * map-based indexing.  Leaf nodes are linked together for faster
+ * iteration of the values. 
  *
  * <br>
  * The Variable Magnitude attribute means that the BTree attempts
@@ -59,23 +62,6 @@
     private static final Log LOG = LogFactory.getLog(BTreeIndex.class);
 
     /**
-     * BTreeCallback is a callback interface for BTree queries.
-     *
-     * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007)
$
-     */
-    static public interface BTreeCallback<Key,Value> {
-
-        /**
-         * indexInfo is a callback method for index enumeration.
-         *
-         * @param value The Value being reported
-         * @param pointer The data pointer being reported
-         * @return false to cancel the enumeration
-         */
-        boolean onEntry(Key key, Value pointer);
-    }   
-    
-    /**
      * Interface used to determine the simple prefix of two keys.
      *
      * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007)
$
@@ -204,14 +190,9 @@
     }
 
     synchronized public void clear(Transaction tx) throws IOException {
-        throw new RuntimeException("Not implemented...");
+        root.clear(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);
     }
@@ -230,6 +211,10 @@
         pw.flush();
     }
 
+    synchronized public Iterator<Map.Entry<Key,Value>> iterator(final Transaction
tx) throws IOException {
+        return root.iterator(tx);
+    }
+    
     synchronized Value getFirst(Transaction tx) throws IOException {
         return root.getFirst(tx);
     }

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=688895&r1=688894&r2=688895&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
15:01:06 2008
@@ -21,6 +21,10 @@
 import java.io.IOException;
 import java.io.PrintWriter;
 import java.util.Arrays;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Map.Entry;
 
 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
@@ -47,6 +51,8 @@
     private Value[] values;
     // nodeId pointers to children BTreeNodes. Null if this is a leaf node.
     private long[] children;
+    // The next leaf node after this one.  Used for fast iteration of the entries.
+    private long next = -1;
     
     /**
      * The Marshaller is used to store and load the data in the BTreeNode into a Page.
@@ -90,6 +96,7 @@
                 for (int i = 0; i < count; i++) {
                     index.getValueMarshaller().writePayload(node.values[i], os);
                 }
+                os.writeLong(node.next);
             }
         }
 
@@ -113,6 +120,7 @@
                 for (int i = 0; i < count; i++) {
                     node.values[i] = index.getValueMarshaller().readPayload(is);
                 }
+                node.next = is.readLong();
             }
             return node;
         }
@@ -140,42 +148,53 @@
             return null;
         }
     }
-
+   
     public Value remove(Transaction tx, Key key) throws IOException {
 
         if(isBranch()) {
             int idx = Arrays.binarySearch(keys, key);
             idx = idx < 0 ? -(idx + 1) : idx + 1;
-            BTreeNode<Key, Value> node = getChild(tx, idx);
-            if( node.getPageId() == index.getRootPageId() ) {
+            BTreeNode<Key, Value> child = getChild(tx, idx);
+            if( child.getPageId() == index.getRootPageId() ) {
                 throw new IOException("BTree corrupted: Cylce detected.");
             }
-            Value rc = node.remove(tx, key);
+            Value rc = child.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];
+            // child node is now empty.. remove it from the branch node.
+            if( child.keys.length == 0 ) {
+                
+                // If the child node is a branch, promote
+                if( child.isBranch() ) {
+                    // This is cause branches are never really empty.. they just go down
to 1 child..
+                    children[idx] = child.children[0];
                 } else {
-                    // If it's not the last child
+                    
+                    // The child was a leaf. Then we need to actually remove it from this
branch node..
+
+                    // We need to update the previous child's next pointer to skip over the
child being removed....
+                    if( idx > 0 && children.length > 1) {
+                        BTreeNode<Key, Value> previousChild = getChild(tx, idx-1);
+                        previousChild.next = child.next;
+                        index.storeNode(tx, previousChild, true);
+                    }
+                    
                     if( idx < children.length-1 ) {
-                        // Then delete it and key to the right.
+                        // Delete it and key to the right.
                         setBranchData(arrayDelete(keys, idx), arrayDelete(children, idx));
                     } else {
-                        // Then delete it and key to the left
+                        // It was the last child.. 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;
+                        child = getChild(tx, 0);
+                        keys = child.keys;
+                        children = child.children;
+                        values = child.values;
                         // free up the page..
-                        tx.free(node.getPage());
+                        tx.free(child.getPage());
                     }
                     
                 }
@@ -332,11 +351,13 @@
             
         } else {
             BTreeNode<Key,Value> rNode = this.index.createNode(tx, parent);
-
+            
             if( isBranch() ) {
                 setBranchData(leftKeys, leftChildren);
                 rNode.setBranchData(rightKeys, rightChildren);
             } else {
+                rNode.setNext(next);
+                next = rNode.getPageId();
                 setLeafData(leftKeys, leftValues);
                 rNode.setLeafData(rightKeys, rightValues);
             }
@@ -422,6 +443,103 @@
             return null;
         }
     }
+    
+    public BTreeNode<Key,Value> getFirstLeafNode(Transaction tx) throws IOException
{
+        BTreeNode<Key, Value> node = this;
+        while( node .isBranch() ) {
+            node = node.getChild(tx, 0);
+        }
+        return node;
+    }
+    
+    
+    public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws
IOException {
+        
+        return new Iterator<Map.Entry<Key,Value>>() {
+            
+            BTreeNode<Key,Value> current = getFirstLeafNode(tx);
+            int nextIndex;
+            
+            Map.Entry<Key,Value> nextEntry;
+            
+            synchronized private void findNextPage() {
+                if( nextEntry!=null ) {
+                    return;
+                }
+                
+                try {
+                    while( current!=null ) {
+                        if( nextIndex >= current.keys.length ) {
+                            // we need to roll to the next leaf..
+                            if( current.next >= 0 ) {
+                                current = index.loadNode(tx, current.next, null);
+                                nextIndex=0;
+                            } else {
+                                break;
+                            }
+                        }  else {
+                            nextEntry = new Map.Entry<Key, Value>() {
+                                private final Key key = current.keys[nextIndex];
+                                private final Value value = current.values[nextIndex];
+                                
+                                public Key getKey() {
+                                    return key;
+                                }
+                                public Value getValue() {
+                                    return value;
+                                }
+                                public Value setValue(Value value) {
+                                    throw new UnsupportedOperationException();
+                                }
+                            };
+                            nextIndex++;
+                            break;
+                        }
+                        
+                    }
+                } catch (IOException e) {
+                }
+            }
+
+            public boolean hasNext() {
+                findNextPage();
+                return nextEntry !=null;
+            }
+
+            public Entry<Key, Value> next() {
+                findNextPage(); 
+                if( nextEntry !=null ) {
+                    Entry<Key, Value> lastEntry = nextEntry;
+                    nextEntry=null;
+                    return lastEntry;
+                } else {
+                    throw new NoSuchElementException();
+                }
+            }
+            
+            public void remove() {
+                throw new UnsupportedOperationException();
+            }
+
+        };
+    }
+    
+    public void clear(Transaction tx) throws IOException {
+        if( isBranch() ) {
+            for (int i = 0; i < children.length; i++) {
+                BTreeNode<Key, Value> node = index.loadNode(tx, children[i], this);
+                node.clear(tx);
+                tx.free(node.getPage());
+            }
+        }
+        // Reset the root node to be a leaf.
+        if( parent == null ) {
+            setLeafData(createKeyArray(0), createValueArray(0));
+            next=-1;
+            index.storeNode(tx, this, true);
+        }
+    }
+
 
     private static <Key,Value> BTreeNode<Key, Value> getLeafNode(Transaction
tx, final BTreeNode<Key, Value> node, Key key) throws IOException {
         BTreeNode<Key, Value> current = node;
@@ -461,18 +579,6 @@
         }
     }
 
-    void iterate(Transaction tx, BTreeIndex.BTreeCallback<Key,Value> callback) throws
IOException {
-        if(isBranch()) {
-            for (int i = 0; i < children.length; i++) {
-                getChild(tx, i).iterate(tx, callback);
-            }
-        } else {
-            for (int i = 0; i < keys.length; i++) {
-                callback.onEntry(keys[i], values[i]);
-            }
-        }
-    }
-
     ///////////////////////////////////////////////////////////////////
     // Implementation methods
     ///////////////////////////////////////////////////////////////////
@@ -583,6 +689,13 @@
         this.page = page;
     }
 
+    public long getNext() {
+        return next;
+    }
+
+    public void setNext(long next) {
+        this.next = next;
+    }
 
 }
 

Modified: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java (original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java Mon Aug 25
15:01:06 2008
@@ -22,7 +22,9 @@
 import java.io.DataOutputStream;
 import java.io.Externalizable;
 import java.io.IOException;
+import java.util.Iterator;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.concurrent.atomic.AtomicBoolean;
 
 import org.apache.commons.logging.Log;
@@ -338,6 +340,11 @@
         metadata.size = 0;
         metadata.binsActive = 0;
     }
+    
+    public Iterator<Entry<Key, Value>> iterator(Transaction tx) throws IOException,
UnsupportedOperationException {
+        throw new UnsupportedOperationException();
+    }
+
 
     /**
      * @param tx

Modified: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java (original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java Mon Aug 25 15:01:06
2008
@@ -17,6 +17,8 @@
 package org.apache.kahadb.page;
 
 import java.io.IOException;
+import java.util.Iterator;
+import java.util.Map;
 
 import org.apache.kahadb.Marshaller;
 import org.apache.kahadb.StoreEntry;
@@ -98,11 +100,14 @@
      * @return true if the index is transient
      */
     boolean isTransient();
-
-
+    
     /**
-     * return the size of the index
+     * @param tx
      * @return
+     * @throws IOException
+     * @trhows UnsupportedOperationException 
+     *         if the index does not support fast iteration of the elements.
      */
-    int size(Transaction tx);
+    Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws IOException,
UnsupportedOperationException;
+    
 }

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=688895&r1=688894&r2=688895&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
15:01:06 2008
@@ -634,14 +634,14 @@
         /**
          * @see org.apache.kahadb.page.Transaction#iterator(boolean)
          */
-        public <T> Iterator<Page<T>> iterator(final boolean includeFreePages)
{
+        public Iterator<Page> iterator(final boolean includeFreePages) {
             
             assertLoaded();
 
-            return new Iterator<Page<T>>() {
+            return new Iterator<Page>() {
                 long nextId;
-                Page<T> nextPage;
-                Page<T> lastPage;
+                Page nextPage;
+                Page lastPage;
                 
                 private void findNextPage() {
                     if( !loaded.get() ) {
@@ -655,7 +655,7 @@
                     try {
                         while( nextId < PageFile.this.nextFreePageId ) {
                             
-                            Page<T> page = load(nextId, null);
+                            Page page = load(nextId, null);
                             
                             if( includeFreePages || page.getType()!=Page.PAGE_FREE_TYPE )
{
                                 nextPage = page;
@@ -673,7 +673,7 @@
                     return nextPage !=null;
                 }
 
-                public Page<T> next() {
+                public Page next() {
                     findNextPage(); 
                     if( nextPage !=null ) {
                         lastPage = nextPage;

Modified: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java (original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java Mon Aug
25 15:01:06 2008
@@ -219,7 +219,7 @@
      * @throws IllegalStateException
      *         if the PageFile is not loaded
      */
-    public <T> Iterator<Page<T>> iterator();
+    public Iterator<Page> iterator();
 
     /**
      * Allows you to iterate through all active Pages in this object.  You can optionally
include free pages in the pages

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=688895&r1=688894&r2=688895&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 15:01:06 2008
@@ -18,6 +18,8 @@
 
 import java.io.PrintWriter;
 import java.text.NumberFormat;
+import java.util.Iterator;
+import java.util.Map;
 
 import org.apache.kahadb.LongMarshaller;
 import org.apache.kahadb.StringMarshaller;
@@ -82,9 +84,8 @@
     public void testPruning() throws Exception {
         createPageFileAndIndex(100);
 
-        BTreeIndex index = ((BTreeIndex)this.index);
+        BTreeIndex<String,Long> index = ((BTreeIndex<String,Long>)this.index);
 
-        String keyRoot = "key:";
         this.index.load();
      
         int minLeafDepth = index.getMinLeafDepth(tx);
@@ -110,7 +111,35 @@
         this.index.unload();
     }
 
+    public void testIteration() throws Exception {
+        createPageFileAndIndex(100);
+        BTreeIndex<String,Long> index = ((BTreeIndex<String,Long>)this.index);
+        this.index.load();
+          
+        // Insert in reverse order..
+        doInsertReverse(1000);
+        
+        this.index.unload();
+        this.index.load();
+
+        // BTree should iterate it in sorted order.
+        int counter=0;
+        for (Iterator<Map.Entry<String,Long>> i = index.iterator(tx); i.hasNext();)
{
+            Map.Entry<String,Long> entry = (Map.Entry<String,Long>)i.next();
+            assertEquals(key(counter),entry.getKey());
+            assertEquals(counter,(long)entry.getValue());
+            counter++;
+        }
+
+        this.index.unload();
+    }
     
+    void doInsertReverse(int count) throws Exception {
+        for (int i = count-1; i >= 0; i--) {
+            index.put(tx, key(i), (long)i);
+            tx.commit();
+        }
+    }
     /**
      * Overriding so that this generates keys that are the worst case for the BTree. Keys
that
      * always insert to the end of the BTree.  



Mime
View raw message