activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From chir...@apache.org
Subject svn commit: r828106 - in /activemq/sandbox/activemq-apollo: activemq-util/src/main/java/org/apache/activemq/util/buffer/ hawtdb/src/main/java/org/apache/hawtdb/api/ hawtdb/src/main/java/org/apache/hawtdb/internal/index/ hawtdb/src/main/java/org/apache/...
Date Wed, 21 Oct 2009 17:02:29 GMT
Author: chirino
Date: Wed Oct 21 17:02:29 2009
New Revision: 828106

URL: http://svn.apache.org/viewvc?rev=828106&view=rev
Log:
btree tests and hast index tests now passing.

Modified:
    activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/Buffer.java
    activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/DataByteArrayOutputStream.java
    activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/api/BTreeIndexFactory.java
    activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeIndex.java
    activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeNode.java
    activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/HashIndex.java
    activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/io/MemoryMappedFile.java
    activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/Extent.java
    activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/HawtTransaction.java

Modified: activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/Buffer.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/Buffer.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/Buffer.java
(original)
+++ activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/Buffer.java
Wed Oct 21 17:02:29 2009
@@ -167,6 +167,10 @@
         return -1;
     }
 
+    public boolean startsWith(Buffer other) {
+        return indexOf(other, 0)==0;
+    }
+    
     public int indexOf(Buffer needle, int pos) {
         int max = length - needle.length;
         for (int i = pos; i < max; i++) {
@@ -210,6 +214,11 @@
         return new Buffer(data, 0, size);
     }
 
+    @Override
+    public String toString() {
+        return "{ offset: "+offset+", length: "+length+" }";
+    }
+    
     @Deprecated
     public String toStringUtf8() {
         return UTF8Buffer.decode(this);

Modified: activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/DataByteArrayOutputStream.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/DataByteArrayOutputStream.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/DataByteArrayOutputStream.java
(original)
+++ activemq/sandbox/activemq-apollo/activemq-util/src/main/java/org/apache/activemq/util/buffer/DataByteArrayOutputStream.java
Wed Oct 21 17:02:29 2009
@@ -259,11 +259,15 @@
     
     private void ensureEnoughBuffer(int newcount) {
         if (newcount > buf.length) {
-            byte newbuf[] = new byte[Math.max(buf.length << 1, newcount)];
-            System.arraycopy(buf, 0, newbuf, 0, pos);
-            buf = newbuf;
+            resize(newcount);
         }
     }
+
+    protected void resize(int newcount) {
+        byte newbuf[] = new byte[Math.max(buf.length << 1, newcount)];
+        System.arraycopy(buf, 0, newbuf, 0, pos);
+        buf = newbuf;
+    }
     
     /**
      * This method is called after each write to the buffer.  This should allow subclasses


Modified: activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/api/BTreeIndexFactory.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/api/BTreeIndexFactory.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/api/BTreeIndexFactory.java
(original)
+++ activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/api/BTreeIndexFactory.java
Wed Oct 21 17:02:29 2009
@@ -48,7 +48,7 @@
 
     private Marshaller<Key> keyMarshaller;
     private Marshaller<Value> valueMarshaller;
-    private boolean deferredEncoding;
+    private boolean deferredEncoding=true;
     private Prefixer<Key> prefixer;
 
     public Index<Key, Value> create(Paged paged, int page) {

Modified: activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeIndex.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeIndex.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeIndex.java
(original)
+++ activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeIndex.java
Wed Oct 21 17:02:29 2009
@@ -16,18 +16,24 @@
  */
 package org.apache.hawtdb.internal.index;
 
+import java.io.IOException;
 import java.io.OutputStream;
 import java.io.PrintWriter;
 import java.util.Iterator;
 import java.util.Map;
 
+import org.apache.activemq.util.buffer.Buffer;
+import org.apache.activemq.util.buffer.DataByteArrayInputStream;
+import org.apache.activemq.util.buffer.DataByteArrayOutputStream;
 import org.apache.activemq.util.marshaller.Marshaller;
 import org.apache.hawtdb.api.BTreeIndexFactory;
-import org.apache.hawtdb.api.IndexVisitor;
 import org.apache.hawtdb.api.Index;
+import org.apache.hawtdb.api.IndexException;
+import org.apache.hawtdb.api.IndexVisitor;
 import org.apache.hawtdb.api.Paged;
 import org.apache.hawtdb.api.Prefixer;
 import org.apache.hawtdb.internal.index.BTreeNode.Data;
+import org.apache.hawtdb.internal.page.Extent;
 
 
 /**
@@ -138,12 +144,48 @@
         return new BTreeNode<Key, Value>(paged.allocator().alloc(1), data);
     }
     
-    void storeNode(BTreeNode<Key, Value> node) {
-        if( deferredEncoding ) {
+    BTreeNode<Key, Value> createNode() {
+        return new BTreeNode<Key, Value>(paged.allocator().alloc(1));
+    }
+    
+    @SuppressWarnings("serial")
+    static class PageOverflowIOException extends IndexException {
+    }
+    
+    /**
+     * 
+     * @param node
+     * @return false if page overflow occurred
+     */
+    boolean storeNode(BTreeNode<Key, Value> node) {
+        // Leaf nodes are the only one they might need to be stored in an
+        // extent.
+        if (deferredEncoding) {
             paged.put(PAGE_ENCODER_DECODER, node.getPage(), node);
         } else {
-            PAGE_ENCODER_DECODER.store(paged, node.getPage(), node);
+            if (node.isLeaf()) {
+                PAGE_ENCODER_DECODER.store(paged, node.getPage(), node);
+                if( !node.allowPageOverflow() && node.pageCount>1 ) {
+                    PAGE_ENCODER_DECODER.remove(paged, node.getPage());
+                    return false;
+                }
+            } else {
+                DataByteArrayOutputStream os = new DataByteArrayOutputStream(paged.getPageSize())
{
+                    protected void resize(int newcount) {
+                        throw new PageOverflowIOException();
+                    };
+                };
+                try {
+                    node.writeExternal(os, this);
+                    paged.write(node.getPage(), os.toBuffer());
+                } catch (IOException e) {
+                    throw new IndexException("Could not write btree node");
+                } catch (PageOverflowIOException e) {
+                    return false;
+                }
+            }
         }
+        return true;
     }
     
     BTreeNode<Key, Value> loadNode(int page) {
@@ -151,7 +193,21 @@
         if( deferredEncoding ) {
             node = paged.get(PAGE_ENCODER_DECODER, page);
         } else {
-            node = PAGE_ENCODER_DECODER.load(paged, page);
+            Buffer buffer = new Buffer(paged.getPageSize());
+            paged.read(page, buffer);
+            if ( buffer.startsWith(Extent.DEFAULT_MAGIC) ) {
+                // Page data was stored in an extent..
+                node = PAGE_ENCODER_DECODER.load(paged, page);
+            } else {
+                // It was just in a plain page..
+                DataByteArrayInputStream is = new DataByteArrayInputStream(buffer);
+                node = new BTreeNode<Key, Value>();
+                try {
+                    node.readExternal(is, this);
+                } catch (IOException e) {
+                    throw new IndexException("Could not read btree node");
+                }
+            }
         }
         node.setPage(page);
         return node;
@@ -161,7 +217,11 @@
         if( deferredEncoding ) {
             paged.remove(PAGE_ENCODER_DECODER, page);
         } else {
-            PAGE_ENCODER_DECODER.remove(paged, page);
+            Buffer buffer = new Buffer(paged.getPageSize());
+            paged.read(page, buffer);
+            if ( buffer.startsWith(Extent.DEFAULT_MAGIC) ) {
+                PAGE_ENCODER_DECODER.remove(paged, page);
+            }
         }
         paged.allocator().free(page, 1);
     }

Modified: activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeNode.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeNode.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeNode.java
(original)
+++ activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/BTreeNode.java
Wed Oct 21 17:02:29 2009
@@ -16,7 +16,9 @@
  */
 package org.apache.hawtdb.internal.index;
 
+import java.io.DataInput;
 import java.io.DataInputStream;
+import java.io.DataOutput;
 import java.io.DataOutputStream;
 import java.io.IOException;
 import java.io.PrintWriter;
@@ -26,9 +28,10 @@
 import java.util.List;
 import java.util.Map;
 
-import org.apache.hawtdb.api.IndexVisitor;
+import org.apache.activemq.util.buffer.Buffer;
 import org.apache.hawtdb.api.EncoderDecoder;
 import org.apache.hawtdb.api.IndexException;
+import org.apache.hawtdb.api.IndexVisitor;
 import org.apache.hawtdb.api.Paged;
 import org.apache.hawtdb.api.Prefixer;
 import org.apache.hawtdb.internal.page.Extent;
@@ -47,17 +50,30 @@
 
     private static final Object [] EMPTY_ARRAY = new Object[]{};
     
-    // The page associated with this node
-    transient private int page;
+    @SuppressWarnings("unchecked")
+    private static final Data EMPTY_DATA = new Data();
+    
+    public static final Buffer BRANCH_MAGIC = new Buffer(new byte[]{ 'b', 'b'});
+    public static final Buffer LEAF_MAGIC = new Buffer(new byte[]{ 'b', 'l'});
+    
+    static class Data<Key, Value> {
 
-    // The number of pages that this node takes on disk if known. -1 if it is
-    // not yet known.
-    transient int pageCount = -1;
+        // The parent node or -1 if this is the root node of the BTree
+        final int parent;
 
-    Data<Key, Value> data;
+        // Order list of keys in the node
+        final Key[] keys;
 
-    static class Data<Key, Value> {
+        // Values associated with the Keys. Null if this is a branch node.
+        final Value[] values;
+
+        // nodeId pointers to children BTreeNodes. Null if this is a leaf node.
+        final int[] children;
 
+        // The next leaf node after this one. Used for fast iteration of the
+        // entries. -1 if this is the last node.
+        final int next;
+        
         @SuppressWarnings("unchecked")
         public Data() {
             this(-1, (Key[])EMPTY_ARRAY, null, (Value[])EMPTY_ARRAY, -1);
@@ -69,23 +85,16 @@
             this.values = values;
             this.children = children;
             this.next = next;
+        }        
+        
+        @Override
+        public String toString() {
+            return "{ parent: "+parent+", next: "+next+", type: "+(isBranch()?"branch":"leaf")+",
keys: "+Arrays.toString(keys)+" }";
+        }
+        
+        private boolean isBranch() {
+            return children != null;
         }
-
-        // The parent node or -1 if this is the root node of the BTree
-        int parent;
-
-        // Order list of keys in the node
-        Key[] keys;
-
-        // Values associated with the Keys. Null if this is a branch node.
-        Value[] values;
-
-        // nodeId pointers to children BTreeNodes. Null if this is a leaf node.
-        int[] children;
-
-        // The next leaf node after this one. Used for fast iteration of the
-        // entries. -1 if this is the last node.
-        int next;
 
         public Data<Key, Value> values(Value[] values) {
             return new Data<Key, Value>(parent, keys, children, values, next);
@@ -127,6 +136,10 @@
             return new Data<Key, Value>(parent, keys, null, values, next);
         }
 
+        public Data<Key, Value> parent(int parent) {
+            return new Data<Key, Value>(parent, keys, children, values, next);
+        }
+
     }
 
     static public class BTreeNodeEncoderDecoder<Key, Value> implements EncoderDecoder<BTreeNode<Key,
Value>> {
@@ -138,7 +151,6 @@
         }
 
         public List<Integer> store(Paged paged, int page, BTreeNode<Key, Value>
node) {
-
             short count = (short) node.data.keys.length; // cast may truncate
                                                          // value...
             if (count != node.data.keys.length) {
@@ -152,29 +164,8 @@
             ExtentOutputStream eos = new ExtentOutputStream(paged, page, (short) 1, (short)
128);
             DataOutputStream os = new DataOutputStream(eos);
             try {
-                os.writeInt(node.data.parent);
-                os.writeShort(count);
-                for (int i = 0; i < node.data.keys.length; i++) {
-                    index.getKeyMarshaller().writePayload(node.data.keys[i], os);
-                }
-
-                if (node.isBranch()) {
-                    // If this is a branch...
-                    os.writeBoolean(true);
-                    for (int i = 0; i < count + 1; i++) {
-                        os.writeInt(node.data.children[i]);
-                    }
-
-                } else {
-                    // If this is a leaf
-                    os.writeBoolean(false);
-                    for (int i = 0; i < count; i++) {
-                        index.getValueMarshaller().writePayload(node.data.values[i], os);
-                    }
-                    os.writeInt(node.data.next);
-                }
+                node.writeExternal(os, index);
                 os.close();
-
             } catch (IOException e) {
                 throw new IndexException(e);
             }
@@ -191,41 +182,15 @@
             return rc;
         }
 
-        @SuppressWarnings("unchecked")
         public BTreeNode<Key, Value> load(Paged paged, int page) {
             ExtentInputStream eis = new ExtentInputStream(paged, page);
             DataInputStream is = new DataInputStream(eis);
-
             try {
-                int parent = is.readInt();
-                int count = is.readShort();
-                Key[] keys = (Key[]) new Object[count];
-                int[] children = null;
-                Value[] values = null;
-                int next = -1;
-
-                for (int i = 0; i < count; i++) {
-                    keys[i] = index.getKeyMarshaller().readPayload(is);
-                }
-
-                if (is.readBoolean()) {
-                    children = new int[count + 1];
-                    for (int i = 0; i < count + 1; i++) {
-                        children[i] = is.readInt();
-                    }
-                } else {
-                    values = (Value[]) new Object[count];
-                    for (int i = 0; i < count; i++) {
-                        values[i] = index.getValueMarshaller().readPayload(is);
-                    }
-                    next = is.readInt();
-                }
+                BTreeNode<Key, Value> node = new BTreeNode<Key, Value>();
+                node.readExternal(is, index);
                 is.close();
-
-                BTreeNode<Key, Value> node = new BTreeNode<Key, Value>(new Data<Key,
Value>(parent, keys, children, values, next));
                 node.pageCount = eis.getPages().size();
                 return node;
-
             } catch (IOException e) {
                 throw new IndexException(e);
             }
@@ -238,8 +203,19 @@
 
     }
 
+    // The persistent data of the node.
+    Data<Key, Value> data;
+    // The page associated with this node
+    private int page;
+    // The number of pages that this node takes on disk if known. -1 if it is not yet known.
+    int pageCount = -1;
+    
+    public BTreeNode() {
+    }
+    
+    @SuppressWarnings("unchecked")
     public BTreeNode(int page) {
-        this(page, new Data<Key, Value>());
+        this(page, EMPTY_DATA);
     }
 
     public BTreeNode(Data<Key, Value> data) {
@@ -250,8 +226,72 @@
         this.page = page;
         this.data = data;
     }
+    
+    
+    void writeExternal(DataOutput os, BTreeIndex<Key, Value> index) throws IOException
{
+        int count = data.keys.length;
+        if( data.isBranch() ) {
+            os.write(BRANCH_MAGIC.data, BRANCH_MAGIC.offset, BRANCH_MAGIC.length);
+        } else {
+            os.write(LEAF_MAGIC.data, LEAF_MAGIC.offset, LEAF_MAGIC.length);
+        }
+        
+        os.writeInt(data.parent);
+        os.writeShort(count);
+        for (int i = 0; i < data.keys.length; i++) {
+            index.getKeyMarshaller().writePayload(data.keys[i], os);
+        }
 
+        if (data.isBranch()) {
+            for (int i = 0; i < count + 1; i++) {
+                os.writeInt(data.children[i]);
+            }
+        } else {
+            for (int i = 0; i < count; i++) {
+                index.getValueMarshaller().writePayload(data.values[i], os);
+            }
+            os.writeInt(data.next);
+        }
+    }
+    
+    @SuppressWarnings("unchecked") void readExternal(DataInput is, BTreeIndex<Key, Value>
index) throws IOException {
+        Buffer magic = new Buffer(BRANCH_MAGIC.length);
+        is.readFully(magic.data, magic.offset, magic.length);
+        boolean branch;
+        if( magic.equals(BRANCH_MAGIC)) {
+            branch = true;
+        } else if( magic.equals(LEAF_MAGIC)) {
+            branch = false;
+        } else {
+            throw new IndexException("Page did not contain the expected btree headers");
+        }
+        
+        int parent = is.readInt();
+        int count = is.readShort();
+        Key[] keys = (Key[]) new Object[count];
+        int[] children = null;
+        Value[] values = null;
+        int next = -1;
 
+        for (int i = 0; i < count; i++) {
+            keys[i] = index.getKeyMarshaller().readPayload(is);
+        }
+
+        if (branch) {
+            children = new int[count + 1];
+            for (int i = 0; i < count + 1; i++) {
+                children[i] = is.readInt();
+            }
+        } else {
+            values = (Value[]) new Object[count];
+            for (int i = 0; i < count; i++) {
+                values[i] = index.getValueMarshaller().readPayload(is);
+            }
+            next = is.readInt();
+        }
+        this.data = new Data<Key, Value>(parent, keys, children, values, next);
+    }    
+    
     /**
      * Internal (to the BTreeNode) method. Because this method is called only by
      * BTreeNode itself, no synchronization done inside of this method.
@@ -259,7 +299,7 @@
      * @throws IOException
      */
     private BTreeNode<Key, Value> getChild(BTreeIndex<Key, Value> index, int
idx) {
-        if (isBranch() && idx >= 0 && idx < data.children.length) {
+        if (data.isBranch() && idx >= 0 && idx < data.children.length)
{
             BTreeNode<Key, Value> result = index.loadNode(data.children[idx]);
             return result;
         } else {
@@ -269,7 +309,7 @@
 
     public Value remove(BTreeIndex<Key, Value> index, Key key) {
 
-        if (isBranch()) {
+        if (data.isBranch()) {
             int idx = Arrays.binarySearch(data.keys, key);
             idx = idx < 0 ? -(idx + 1) : idx + 1;
             BTreeNode<Key, Value> child = getChild(index, idx);
@@ -282,11 +322,11 @@
             if (child.data.keys.length == 0) {
 
                 // If the child node is a branch, promote
-                if (child.isBranch()) {
+                if (child.data.isBranch()) {
                     // This is cause branches are never really empty.. they just
                     // go down to 1 child..
-                    data = data.children(arrayUpdate(data.children, idx,child.data.children[0]));
-                    
+                    data = data.children(arrayUpdate(data.children, idx, child.data.children[0]));
+                    linkChild(index, child.data.children[0]);
                 } else {
 
                     // The child was a leaf. Then we need to actually remove it
@@ -351,7 +391,7 @@
             throw new IllegalArgumentException("Key cannot be null");
         }
 
-        if (isBranch()) {
+        if (data.isBranch()) {
             return getLeafNode(index, this, key).put(index, key, value);
         } else {
             int idx = Arrays.binarySearch(data.keys, key);
@@ -367,11 +407,13 @@
                 data = data.leaf(arrayInsert(data.keys, key, idx), arrayInsert(data.values,
value, idx));
             }
 
-            if (splitNeeded()) {
-                split(index);
-            } else {
-                index.storeNode(this);
-            }
+//            if (splitNeeded()) {
+//                split(index);
+//            } else {
+                if( !index.storeNode(this) ) {
+                    split(index);
+                }
+//            }
 
             return oldValue;
         }
@@ -383,11 +425,14 @@
         idx = idx < 0 ? -(idx + 1) : idx + 1;
         data = data.branch(arrayInsert(data.keys, key, idx), arrayInsert(data.children, nodeId,
idx + 1));
 
-        if (splitNeeded()) {
-            split(index);
-        } else {
-            index.storeNode(this);
-        }
+//        if (splitNeeded()) {
+//            split(index);
+//        } else {
+            if ( !index.storeNode(this) ) {
+                // overflow.. 
+                split(index);
+            }
+//        }
 
     }
 
@@ -407,7 +452,7 @@
         int pivot = vc / 2;
 
         // Split the node into two nodes
-        if (isBranch()) {
+        if (data.isBranch()) {
 
             leftKeys = createKeyArray(pivot);
             leftChildren = new int[leftKeys.length + 1];
@@ -449,15 +494,17 @@
         if (data.parent == -1) {
 
             // This can only happen if this is the root
-            BTreeNode<Key, Value> rNode;
-            BTreeNode<Key, Value> lNode;
+            BTreeNode<Key, Value> lNode = index.createNode();
+            BTreeNode<Key, Value> rNode = index.createNode();
 
-            if (isBranch()) {
-                rNode = index.createNode(data.branch(page, rightKeys, rightChildren));
-                lNode = index.createNode(data.branch(page, leftKeys, leftChildren));
+            if (data.isBranch()) {
+                rNode.data = data.branch(page, rightKeys, rightChildren);
+                rNode.linkChildren(index);
+                lNode.data = data.branch(page, leftKeys, leftChildren);
+                lNode.linkChildren(index);
             } else {
-                rNode = index.createNode(data.leaf(page, rightKeys, rightValues));
-                lNode = index.createNode(data.leaf(page, leftKeys, leftValues, rNode.getPage()));
+                rNode.data = data.leaf(page, rightKeys, rightValues);
+                lNode.data = data.leaf(page, leftKeys, leftValues, rNode.getPage());
             }
 
             Key[] v = createKeyArray(1);
@@ -471,8 +518,9 @@
         } else {
             BTreeNode<Key, Value> rNode;
 
-            if (isBranch()) {
+            if (data.isBranch()) {
                 rNode = index.createNode(data.branch(data.parent, rightKeys, rightChildren));
+                rNode.linkChildren(index);
                 data = data.branch(leftKeys, leftChildren);
             } else {
                 rNode = index.createNode(data.leaf(data.parent, rightKeys, rightValues, data.next));
@@ -486,19 +534,34 @@
     }
 
 
+    private void linkChildren(BTreeIndex<Key, Value> index) {
+        if( data ==null || data.children ==null ) {
+            throw new NullPointerException();
+        }
+       for (int child : data.children) {
+           linkChild(index, child);
+       }
+    }
+
+    private void linkChild(BTreeIndex<Key, Value> index, int child) {
+        BTreeNode<Key, Value> node = index.loadNode(child);
+        node.data = node.data.parent(page);
+        index.storeNode(node);
+    }
+
     public void printStructure(BTreeIndex<Key, Value> index, PrintWriter out, String
prefix) {
         if (prefix.length() > 0 && data.parent == -1) {
             throw new IllegalStateException("Cycle back to root node detected.");
         }
 
-        if (isBranch()) {
+        if (data.isBranch()) {
             for (int i = 0; i < data.children.length; i++) {
                 BTreeNode<Key, Value> child = getChild(index, i);
                 if (i == data.children.length - 1) {
-                    out.println(prefix + "\\- " + child.getPage() + (child.isBranch() ? "
(" + child.data.children.length + ")" : ""));
+                    out.println(prefix + "\\- " + child.getPage() + (child.data.isBranch()
? " (" + child.data.children.length + ")" : ""));
                     child.printStructure(index, out, prefix + "   ");
                 } else {
-                    out.println(prefix + "|- " + child.getPage() + (child.isBranch() ? "
(" + child.data.children.length + ")" : "") + " : " + data.keys[i]);
+                    out.println(prefix + "|- " + child.getPage() + (child.data.isBranch()
? " (" + child.data.children.length + ")" : "") + " : " + data.keys[i]);
                     child.printStructure(index, out, prefix + "   ");
                 }
             }
@@ -507,7 +570,7 @@
 
     public int getMinLeafDepth(BTreeIndex<Key, Value> index, int depth) {
         depth++;
-        if (isBranch()) {
+        if (data.isBranch()) {
             int min = Integer.MAX_VALUE;
             for (int i = 0; i < data.children.length; i++) {
                 min = Math.min(min, getChild(index, i).getMinLeafDepth(index, depth));
@@ -523,7 +586,7 @@
         int rc=0;
         
         BTreeNode<Key, Value> node = this;
-        while (node.isBranch()) {
+        while (node.data.isBranch()) {
             node = node.getChild(index, 0);
         }
         while (node!=null) {
@@ -539,7 +602,7 @@
 
     public int getMaxLeafDepth(BTreeIndex<Key, Value> index, int depth) {
         depth++;
-        if (isBranch()) {
+        if (data.isBranch()) {
             int v = 0;
             for (int i = 0; i < data.children.length; i++) {
                 v = Math.max(v, getChild(index, i).getMaxLeafDepth(index, depth));
@@ -553,7 +616,7 @@
         if (key == null) {
             throw new IllegalArgumentException("Key cannot be null");
         }
-        if (isBranch()) {
+        if (data.isBranch()) {
             return getLeafNode(index, this, key).get(index, key);
         } else {
             int idx = Arrays.binarySearch(data.keys, key);
@@ -574,7 +637,7 @@
             return;
         }
 
-        if (isBranch()) {
+        if (data.isBranch()) {
             for (int i = 0; i < this.data.children.length; i++) {
                 Key key1 = null;
                 if (i != 0) {
@@ -596,7 +659,7 @@
 
     public Map.Entry<Key, Value> getFirst(BTreeIndex<Key, Value> index) {
         BTreeNode<Key, Value> node = this;
-        while (node.isBranch()) {
+        while (node.data.isBranch()) {
             node = node.getChild(index, 0);
         }
         if (node.data.values.length > 0) {
@@ -608,7 +671,7 @@
 
     public Map.Entry<Key, Value> getLast(BTreeIndex<Key, Value> index) {
         BTreeNode<Key, Value> node = this;
-        while (node.isBranch()) {
+        while (node.data.isBranch()) {
             node = node.getChild(index, node.data.children.length - 1);
         }
         if (node.data.values.length > 0) {
@@ -621,7 +684,7 @@
 
     public BTreeNode<Key, Value> getFirstLeafNode(BTreeIndex<Key, Value> index)
{
         BTreeNode<Key, Value> node = this;
-        while (node.isBranch()) {
+        while (node.data.isBranch()) {
             node = node.getChild(index, 0);
         }
         return node;
@@ -631,7 +694,7 @@
         if (startKey == null) {
             return iterator(index);
         }
-        if (isBranch()) {
+        if (data.isBranch()) {
             return getLeafNode(index, this, startKey).iterator(index, startKey);
         } else {
             int idx = Arrays.binarySearch(data.keys, startKey);
@@ -648,7 +711,7 @@
 
     @SuppressWarnings("unchecked")
     public void clear(BTreeIndex<Key, Value> index) {
-        if (isBranch()) {
+        if (data.isBranch()) {
             for (int i = 0; i < data.children.length; i++) {
                 BTreeNode<Key, Value> node = index.loadNode(data.children[i]);
                 node.clear(index);
@@ -665,7 +728,7 @@
     private static <Key, Value> BTreeNode<Key, Value> getLeafNode(BTreeIndex<Key,
Value> index, final BTreeNode<Key, Value> node, Key key) {
         BTreeNode<Key, Value> current = node;
         while (true) {
-            if (current.isBranch()) {
+            if (current.data.isBranch()) {
                 int idx = Arrays.binarySearch(current.data.keys, key);
                 idx = idx < 0 ? -(idx + 1) : idx + 1;
                 BTreeNode<Key, Value> child = current.getChild(index, idx);
@@ -688,7 +751,7 @@
             throw new IllegalArgumentException("Key cannot be null");
         }
 
-        if (isBranch()) {
+        if (data.isBranch()) {
             return getLeafNode(index, this, key).contains(index, key);
         } else {
             int idx = Arrays.binarySearch(data.keys, key);
@@ -704,9 +767,13 @@
     // Implementation methods
     // /////////////////////////////////////////////////////////////////
 
+    boolean allowPageOverflow() {
+        return data.keys.length < 4;
+    }
+    
     private boolean splitNeeded() {
         if (pageCount > 1 && data.keys.length > 1) {
-            if (pageCount > 128 || data.keys.length > 4) {
+            if (pageCount > 128 || !allowPageOverflow() ) {
                 return true;
             }
         }
@@ -726,14 +793,14 @@
     @SuppressWarnings("unchecked")
     static private <T> T[] arrayUpdate(T[] vals, int idx, T value) {
         T[] newVals = (T[]) new Object[vals.length];
-        System.arraycopy(vals, 0, newVals, 0, idx);
+        System.arraycopy(vals, 0, newVals, 0, vals.length);
         newVals[idx] = value;
         return newVals;
     }
     
     static private int[] arrayUpdate(int[] vals, int idx, int value) {
         int[] newVals = new int[vals.length];
-        System.arraycopy(vals, 0, newVals, 0, idx);
+        System.arraycopy(vals, 0, newVals, 0, vals.length);
         newVals[idx] = value;
         return newVals;
     }    
@@ -787,13 +854,6 @@
         return newVals;
     }
 
-    // /////////////////////////////////////////////////////////////////
-    // Property Accessors
-    // /////////////////////////////////////////////////////////////////
-    private boolean isBranch() {
-        return data.children != null;
-    }
-
     public int getParent() {
         return data.parent;
     }
@@ -811,7 +871,15 @@
 
     @Override
     public String toString() {
-        return "[BTreeNode " + (isBranch() ? "branch" : "leaf") + ": " + Arrays.asList(data.keys)
+ "]";
+        return "{ page: "+page+", data: "+data.toString()+" }";
+    }
+
+    public boolean isLeaf() {
+        return !data.isBranch();
+    }
+    
+    public boolean isBranch() {
+        return data.isBranch();
     }
 
 

Modified: activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/HashIndex.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/HashIndex.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/HashIndex.java
(original)
+++ activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/index/HashIndex.java
Wed Oct 21 17:02:29 2009
@@ -44,21 +44,6 @@
     
     private static final Log LOG = LogFactory.getLog(HashIndex.class);
 
-//    static private class Header extends Struct {
-//        public final UTF8String magic = new UTF8String(4);
-//        public final Signed32 page = new Signed32();
-//        public final Signed32 capacity = new Signed32();
-//        public final Signed32 size = new Signed32();
-//        public final Signed32 active = new Signed32();
-//        
-//        static Header create(ByteBuffer buffer) {
-//            Header header = new Header();
-//            header.setByteBuffer(buffer, buffer.position());
-//            return header;
-//        }
-//    }
-    
-
     /** 
      * This is the data stored in the index header.  It knows where
      * the hash buckets are stored at an keeps usage statistics about
@@ -66,7 +51,7 @@
      */
     static private class Buckets<Key,Value> {
         
-        public static final int HEADER_SIZE = headerSize();
+        public static final int HEADER_SIZE = 16;
         public static final Buffer MAGIC = new Buffer(new byte[] {'h', 'a', 's', 'h'});
 
         final HashIndex<Key,Value> index;
@@ -112,12 +97,6 @@
             index.buckets.active = 0;
             index.buckets.calcThresholds();
         }
-        
-        private static int headerSize() {
-            DataByteArrayOutputStream os = new DataByteArrayOutputStream();
-            new Buckets<Object, Object>(null).writeExternal(os);
-            return os.toBuffer().getLength();
-        }
 
         void store() {
             DataByteArrayOutputStream os = new DataByteArrayOutputStream(HEADER_SIZE);
@@ -135,7 +114,8 @@
         
         private void writeExternal(DataByteArrayOutputStream os) {
             try {
-                os.write(MAGIC.data, MAGIC.offset, MAGIC.length);
+                Buffer magic2 = MAGIC;
+                os.write(magic2.data, MAGIC.offset, MAGIC.length);
                 os.writeInt(this.bucketsPage);
                 os.writeInt(this.capacity);
                 os.writeInt(this.size);

Modified: activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/io/MemoryMappedFile.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/io/MemoryMappedFile.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/io/MemoryMappedFile.java
(original)
+++ activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/io/MemoryMappedFile.java
Wed Oct 21 17:02:29 2009
@@ -116,7 +116,7 @@
                 throw new IOPagingException(e);
             }
         }
-        return (ByteBuffer) buffer.limit(buffer.position()+length);
+        return ((ByteBuffer) buffer.limit(buffer.position()+length)).slice();
     }
     
     public void unslice(ByteBuffer buffer) {

Modified: activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/Extent.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/Extent.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/Extent.java
(original)
+++ activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/Extent.java
Wed Oct 21 17:02:29 2009
@@ -17,8 +17,7 @@
 package org.apache.hawtdb.internal.page;
 
 import java.nio.ByteBuffer;
-
-import javolution.io.Struct;
+import java.nio.IntBuffer;
 
 import org.apache.activemq.util.buffer.Buffer;
 import org.apache.hawtdb.api.IOPagingException;
@@ -41,91 +40,85 @@
  */
 public class Extent {
     
-    public final static byte MAGIC_VALUE = 'x'; 
-    
-    static private class Header extends Struct {
-        /**
-         * A constant prefix that can be used to identify the page type.
-         */
-        public final Signed8 magic = new Signed8();
-        /** 
-         * The number of bytes in the extent, including the header.
-         */
-        public final Signed32 length = new Signed32();
-        /**
-         * The page of the next extent or -1.
-         */
-        public final Signed32 next = new Signed32();
-    }
-
-    private final Extent.Header header = new Header();
+    public final static Buffer DEFAULT_MAGIC = new Buffer(new byte[]{'x'}); 
 
     private final Paged paged;
     private final int page;
-    private ByteBuffer buffer;
-
-    private int bufferStartPosition;
+    private final Buffer magic;
 
+    private ByteBuffer buffer;
+    
+    private int length;
+    private int next;
+    
     public Extent(Paged paged, int page) {
+        this(paged, page, DEFAULT_MAGIC);
+    }
+    
+    public Extent(Paged paged, int page, Buffer magic) {
         this.paged = paged;
         this.page = page;
+        this.magic = magic;
     }
     
     @Override
     public String toString() {
-        int position = 0;
-        int limit=0;
+        Integer position = null;
+        Integer limit = null;
         if( buffer!=null ) {
-            position = buffer.position()-bufferStartPosition;
-            limit = buffer.limit()-bufferStartPosition;
+            position = buffer.position();
+            limit = buffer.limit();
         }
         return "{ page: "+page+", position: "+position+", limit: "+limit+" }";
     }
     
-    public void readOpen() {
+    
+    public void readHeader() {
         buffer = paged.slice(SliceType.READ, page, 1);
-        header.setByteBuffer(buffer, buffer.position());
-        if( header.magic.get() != MAGIC_VALUE ) {
+        
+        Buffer m = new Buffer(magic.length);
+        buffer.get(m.data);
+        
+        if( !magic.equals(m) ) {
             throw new IOPagingException("Invalid extent read request.  The requested page
was not an extent: "+page);
         }
         
-        int length = header.length.get();
+        IntBuffer ib = buffer.asIntBuffer();
+        length = ib.get();
+        next = ib.get();
+    }
+    
+    public void readOpen() {
+        readHeader();
         int pages = paged.pages(length);
         if( pages > 1 ) {
             paged.unslice(buffer);
             buffer = paged.slice(SliceType.READ, page, pages);
-            header.setByteBuffer(buffer, buffer.position());
         }
-        
-        bufferStartPosition = buffer.position();
-        buffer.position(bufferStartPosition+header.size());
-        buffer.limit(bufferStartPosition+length);
+        buffer.position(magic.length+8);
+        buffer.limit(length);
     }
 
     public void writeOpen(short size) {
         buffer = paged.slice(SliceType.WRITE, page, size);
-        header.setByteBuffer(buffer, buffer.position());
-        bufferStartPosition = buffer.position();
-        buffer.position(bufferStartPosition+header.size());
+        buffer.position(magic.length+8);
     }
 
-    public void writeCloseLinked(int next) {
-        int length = buffer.position()-bufferStartPosition;
-        header.magic.set(MAGIC_VALUE);
-        header.next.set(next);
-        header.length.set(length);
+    public int writeCloseLinked(int next) {
+        this.next = next;
+        length = buffer.position();
+        buffer.position(0);
+        buffer.put(magic.data, magic.offset, magic.length);
+        IntBuffer ib = buffer.asIntBuffer();
+        ib.put(length);
+        ib.put(next);
         paged.unslice(buffer);
+        return length;
     }
 
     public void writeCloseEOF() {
-        
-        int length = buffer.position()-bufferStartPosition;
-        header.magic.set(MAGIC_VALUE);
-        header.next.set(-1);
-        header.length.set(length);
-        paged.unslice(buffer);
-
-        int originalPages = paged.pages(buffer.limit()-bufferStartPosition);
+        int length = writeCloseLinked(-1);
+        int originalPages = paged.pages(buffer.limit());
         int usedPages = paged.pages(length);
         int remainingPages = originalPages-usedPages;
         
@@ -182,9 +175,8 @@
     }
 
     public int getNext() {
-        return header.next.get();
+        return next;
     }
-
     
     /**
      * Frees the linked extents at the provided page id.
@@ -193,16 +185,15 @@
      * @param page
      */
     public static void freeLinked(Paged paged, int page) {
-        ByteBuffer buffer = paged.slice(SliceType.READ, page, 1);
-        Header header = new Header();
-        header.setByteBuffer(buffer, buffer.position());
-        if( header.magic.get() != MAGIC_VALUE ) {
-            throw new IOPagingException("Invalid extent read request.  The requested page
was not an extent: "+page);
-        }
-        int next = header.next.get();
-        free(paged, next);
+        freeLinked(paged, page, DEFAULT_MAGIC);
     }
     
+    public static void freeLinked(Paged paged, int page, Buffer magic) {
+        Extent extent = new Extent(paged, page, magic);
+        extent.readHeader();
+        free(paged, extent.getNext());
+    }    
+    
     /**
      * Frees the extent at the provided page id.
      * 
@@ -210,20 +201,17 @@
      * @param page
      */
     public static void free(Paged paged, int page) {
+        free(paged, page, DEFAULT_MAGIC);
+    }    
+    public static void free(Paged paged, int page, Buffer magic) {
         while( page>=0 ) {
-            ByteBuffer buffer = paged.slice(SliceType.READ, page, 1);
+            Extent extent = new Extent(paged, page, magic);
+            extent.readHeader();
             try {
-                Header header = new Header();
-                header.setByteBuffer(buffer, buffer.position());
-                if( header.magic.get() != MAGIC_VALUE ) {
-                    throw new IOPagingException("Invalid extent read request.  The requested
page was not an extent: "+page);
-                }
-
-                int next = header.next.get();
-                paged.allocator().free(page, paged.pages(header.length.get()));
-                page=next;
+                paged.allocator().free(page, paged.pages(extent.getLength()));
+                page=extent.getNext();
             } finally {
-                paged.unslice(buffer);
+                extent.readClose();
             }
         }
     }
@@ -236,20 +224,17 @@
      * @param page
      */
     public static void unfree(Paged paged, int page) {
+        unfree(paged, page, DEFAULT_MAGIC);
+    }
+    public static void unfree(Paged paged, int page, Buffer magic) {
         while( page>=0 ) {
-            ByteBuffer buffer = paged.slice(SliceType.READ, page, 1);
+            Extent extent = new Extent(paged, page, magic);
+            extent.readHeader();
             try {
-                Header header = new Header();
-                header.setByteBuffer(buffer, buffer.position());
-                if( header.magic.get() != MAGIC_VALUE ) {
-                    throw new IOPagingException("Invalid extent read request.  The requested
page was not an extent: "+page);
-                }
-                
-                int next = header.next.get();
-                paged.allocator().unfree(page, paged.pages(header.length.get()));
-                page=next;
+                paged.allocator().unfree(page, paged.pages(extent.length));
+                page=extent.next;
             } finally {
-                paged.unslice(buffer);
+                extent.readClose();
             }
         }
     }
@@ -259,6 +244,6 @@
     }
     
     public int getLength() {
-        return header.length.get();
+        return length;
     }
 }
\ No newline at end of file

Modified: activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/HawtTransaction.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/HawtTransaction.java?rev=828106&r1=828105&r2=828106&view=diff
==============================================================================
--- activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/HawtTransaction.java
(original)
+++ activemq/sandbox/activemq-apollo/hawtdb/src/main/java/org/apache/hawtdb/internal/page/HawtTransaction.java
Wed Oct 21 17:02:29 2009
@@ -60,11 +60,7 @@
             int end = pageId+count;
             for (int key = pageId; key < end; key++) {
                 Integer previous = getUpdates().put(key, HawtPageFile.PAGE_FREED);
-                
-                // If it was an allocation that was done in this
-                // tx, then we can directly release it.
-                assert previous!=null;
-                if( previous == HawtPageFile.PAGE_ALLOCATED) {
+                if( previous!=null && previous==HawtPageFile.PAGE_ALLOCATED) {
                     getUpdates().remove(key);
                     HawtTransaction.this.parent.allocator.free(key, 1);
                 }
@@ -149,10 +145,11 @@
         Integer updatedPageId = updates == null ? null : updates.get(pageId);
         if (updatedPageId != null) {
             switch (updatedPageId) {
-            case HawtPageFile.PAGE_ALLOCATED:
             case HawtPageFile.PAGE_FREED:
-                // TODO: Perhaps use a RuntimeException subclass.
-                throw new PagingException("You should never try to read a page that has been
allocated or freed.");
+                throw new PagingException("You should never try to read a page that has been
freed.");
+            case HawtPageFile.PAGE_ALLOCATED:
+                parent.pageFile.read(pageId, buffer);
+                break;
             default:
                 // read back in the updated we had done.
                 parent.pageFile.read(updatedPageId, buffer);



Mime
View raw message