You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2013/12/13 11:13:22 UTC
svn commit: r1550673 [1/2] - in /directory/mavibot/trunk/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
main/java/org/apache/directory/mavibot/btree/managed/
main/java/org/apache/directory/mavibot/btree/memory/
test/java/org/apache/director...
Author: elecharny
Date: Fri Dec 13 10:13:21 2013
New Revision: 1550673
URL: http://svn.apache.org/r1550673
Log:
Some more refactoring :
o An AbstractPage has been created which share the methods and fileds for the two types of trees, and the AbstractPage in managed and in-memory have been renamed
o An AbstractTupleCursor holds the shared methods and fields for the TupleCursor implementations
o A KeyHolder class has been created and is now used by he two BTrees
o The getKeyType() method has been removed
o The ElementHolder class has been removed
Added:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPersistedPage.java
- copied, changed from r1550580, directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedKeyHolder.java
- copied, changed from r1550046, directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractInMemoryPage.java
- copied, changed from r1550580, directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractPage.java
Removed:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ElementHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractPage.java
Modified:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTreeBuilder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ValueHolder.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeBuilderTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/LeafTest.java
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java?rev=1550673&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java Fri Dec 13 10:13:21 2013
@@ -0,0 +1,339 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree;
+
+
+import org.apache.directory.mavibot.btree.KeyHolder;
+import org.apache.directory.mavibot.btree.Page;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+
+
+/**
+ * A MVCC abstract Page. It stores the field and the methods shared by the Node and Leaf
+ * classes.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public abstract class AbstractPage<K, V> implements Page<K, V>
+{
+ /** Parent B+Tree. */
+ protected transient BTree<K, V> btree;
+
+ /** Keys of children nodes */
+ protected KeyHolder<K>[] keys;
+
+ /** The number of current values in the Page */
+ protected int nbElems;
+
+ /** This BPage's revision */
+ protected long revision;
+
+ /** The first {@link PageIO} storing the serialized Page on disk */
+ protected long offset = -1L;
+
+ /** The last {@link PageIO} storing the serialized Page on disk */
+ protected long lastOffset = -1L;
+
+ /** A static Exception used to avoid creating a new one every time */
+ protected KeyNotFoundException KEY_NOT_FOUND_EXCEPTION = new KeyNotFoundException(
+ "Cannot find an entry associated with this key" );
+
+ /**
+ * Creates a default empty AbstractPage
+ *
+ * @param btree The associated BTree
+ */
+ protected AbstractPage( BTree<K, V> btree )
+ {
+ this.btree = btree;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int getNbElems()
+ {
+ return nbElems;
+ }
+
+
+ public void setNbElems( int nbElems )
+ {
+ this.nbElems = nbElems;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getKey( int pos )
+ {
+ if ( ( pos < nbElems ) && ( keys[pos] != null ) )
+ {
+ return keys[pos].getKey();
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getLeftMostKey()
+ {
+ return keys[0].getKey();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getRightMostKey()
+ {
+ return keys[nbElems - 1].getKey();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public long getOffset()
+ {
+ return offset;
+ }
+
+
+ /**
+ * @param offset the offset to set
+ */
+ public void setOffset( long offset )
+ {
+ this.offset = offset;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public long getLastOffset()
+ {
+ return lastOffset;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void setLastOffset( long lastOffset )
+ {
+ this.lastOffset = lastOffset;
+ }
+
+
+ /**
+ * @return the leys
+ */
+ public KeyHolder<K>[] getKeys()
+ {
+ return keys;
+ }
+
+
+ /**
+ * @param revision the keys to set
+ */
+ public void setKeys( KeyHolder<K>[] keys )
+ {
+ this.keys = keys;
+ }
+
+
+ /**
+ * @return the revision
+ */
+ public long getRevision()
+ {
+ return revision;
+ }
+
+
+ /**
+ * @param revision the revision to set
+ */
+ public void setRevision( long revision )
+ {
+ this.revision = revision;
+ }
+
+
+ /**
+ * Compares two keys
+ *
+ * @param key1 The first key
+ * @param key2 The second key
+ * @return -1 if the first key is above the second one, 1 if it's below, and 0
+ * if the two keys are equal
+ */
+ protected final int compare( K key1, K key2 )
+ {
+ if ( key1 == key2 )
+ {
+ return 0;
+ }
+
+ if ( key1 == null )
+ {
+ return 1;
+ }
+
+ if ( key2 == null )
+ {
+ return -1;
+ }
+
+ return btree.getComparator().compare( key1, key2 );
+ }
+
+
+ /**
+ * Finds the position of the given key in the page. If we have found the key,
+ * we will return its position as a negative value.
+ * <p/>
+ * Assuming that the array is zero-indexed, the returned value will be : <br/>
+ * position = - ( position + 1)
+ * <br/>
+ * So for the following table of keys : <br/>
+ * <pre>
+ * +---+---+---+---+
+ * | b | d | f | h |
+ * +---+---+---+---+
+ * 0 1 2 3
+ * </pre>
+ * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
+ * Computing the real position is just a matter to get -(position++).
+ * <p/>
+ * If we don't find the key in the table, we will return the position of the key
+ * immediately above the key we are looking for. <br/>
+ * For instance, looking for :
+ * <ul>
+ * <li>'a' will return 0</li>
+ * <li>'b' will return -1</li>
+ * <li>'c' will return 1</li>
+ * <li>'d' will return -2</li>
+ * <li>'e' will return 2</li>
+ * <li>'f' will return -3</li>
+ * <li>'g' will return 3</li>
+ * <li>'h' will return -4</li>
+ * <li>'i' will return 4</li>
+ * </ul>
+ *
+ *
+ * @param key The key to find
+ * @return The position in the page.
+ */
+ public int findPos( K key )
+ {
+ // Deal with the special key where we have an empty page
+ if ( nbElems == 0 )
+ {
+ return 0;
+ }
+
+ int min = 0;
+ int max = nbElems - 1;
+
+ // binary search
+ while ( min < max )
+ {
+ int middle = ( min + max + 1 ) >> 1;
+
+ int comp = compare( keys[middle].getKey(), key );
+
+ if ( comp < 0 )
+ {
+ min = middle + 1;
+ }
+ else if ( comp > 0 )
+ {
+ max = middle - 1;
+ }
+ else
+ {
+ // Special case : the key already exists,
+ // we can return immediately. The value will be
+ // negative, and as the index may be 0, we subtract 1
+ return -( middle + 1 );
+ }
+ }
+
+ // Special case : we don't know if the key is present
+ int comp = compare( keys[max].getKey(), key );
+
+ if ( comp == 0 )
+ {
+ return -( max + 1 );
+ }
+ else
+ {
+ if ( comp < 0 )
+ {
+ return max + 1;
+ }
+ else
+ {
+ return max;
+ }
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public String dumpPage( String tabs )
+ {
+ return "";
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "r" ).append( revision );
+ sb.append( ", nbElems:" ).append( nbElems );
+
+ if ( offset > 0 )
+ {
+ sb.append( ", offset:" ).append( offset );
+ }
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java?rev=1550673&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractTupleCursor.java Fri Dec 13 10:13:21 2013
@@ -0,0 +1,151 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree;
+
+/**
+ * A Cursor is used to fetch elements in a BTree and is returned by the
+ * @see BTree#browse method. The cursor <strng>must</strong> be closed
+ * when the user is done with it.
+ * <p>
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public abstract class AbstractTupleCursor<K, V> implements TupleCursor<K, V>
+{
+ /** The stack of pages from the root down to the leaf */
+ protected ParentPos<K, V>[] stack;
+
+ /** The stack's depth */
+ protected int depth = 0;
+
+ /** The transaction used for this cursor */
+ protected Transaction<K, V> transaction;
+
+ /** The Tuple used to return the results */
+ protected Tuple<K, V> tuple = new Tuple<K, V>();
+
+ /**
+ * Creates a new instance of Cursor, starting on a page at a given position.
+ *
+ * @param transaction The transaction this operation is protected by
+ * @param stack The stack of parent's from root to this page
+ */
+ protected AbstractTupleCursor( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
+ {
+ this.transaction = transaction;
+ this.stack = stack;
+ this.depth = depth;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ *
+ public void afterLast() throws IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ return;
+ }
+
+ Page<K, V> child = null;
+
+ for ( int i = 0; i < depth; i++ )
+ {
+ ParentPos<K, V> parentPos = stack[i];
+
+ if ( child != null )
+ {
+ parentPos.page = child;
+ parentPos.pos = child.getNbElems();
+ }
+ else
+ {
+ // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
+ parentPos.pos = parentPos.page.getNbElems();
+ }
+
+ child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
+ }
+
+ // and leaf
+ ParentPos<K, V> parentPos = stack[depth];
+
+ if ( child == null )
+ {
+ parentPos.pos = parentPos.page.getNbElems() - 1;
+ }
+ else
+ {
+ parentPos.page = child;
+ parentPos.pos = child.getNbElems() - 1;
+ }
+
+ parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
+ parentPos.valueCursor.afterLast();
+ parentPos.pos = AFTER_LAST;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void close()
+ {
+ transaction.close();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public long getCreationDate()
+ {
+ return transaction.getCreationDate();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public long getRevision()
+ {
+ return transaction.getRevision();
+ }
+
+
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "TupleCursor, depth = " ).append( depth ).append( "\n" );
+
+ for ( int i = 0; i <= depth; i++ )
+ {
+ sb.append( " " ).append( stack[i] ).append( "\n" );
+ }
+
+ return sb.toString();
+ }
+}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java Fri Dec 13 10:13:21 2013
@@ -297,12 +297,6 @@ public interface BTree<K, V>
/**
- * @return the type for the keys
- */
- Class<?> getKeyType();
-
-
- /**
* @param keySerializer the Key serializer to set
*/
void setKeySerializer( ElementSerializer<K> keySerializer );
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java?rev=1550673&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java Fri Dec 13 10:13:21 2013
@@ -0,0 +1,62 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree;
+
+/**
+ * The data structure holding a key and the way to access it
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ *
+ * <K> The key type
+ */
+public class KeyHolder<K>
+{
+ /** The deserialized key */
+ protected K key;
+
+
+ /**
+ * Create a new KeyHolder instance
+ *
+ * @param key The key to store
+ */
+ public KeyHolder( K key )
+ {
+ this.key = key;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void setKey( K key )
+ {
+ this.key = key;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getKey()
+ {
+ return key;
+ }
+}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java Fri Dec 13 10:13:21 2013
@@ -168,9 +168,8 @@ public interface Page<K, V>
* down in the leftmost children to recursively find the leftmost key.
*
* @return The leftmost key in the tree
- * @throws IOException If we have an error while trying to access the page
*/
- K getLeftMostKey() throws IOException;
+ K getLeftMostKey();
/**
@@ -178,9 +177,8 @@ public interface Page<K, V>
* down in the rightmost children to recursively find the rightmost key.
*
* @return The rightmost key in the tree
- * @throws IOException If we have an error while trying to access the page
*/
- K getRightMostKey() throws IOException;
+ K getRightMostKey();
/**
Copied: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPersistedPage.java (from r1550580, directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java)
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPersistedPage.java?p2=directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPersistedPage.java&p1=directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java&r1=1550580&r2=1550673&rev=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPersistedPage.java Fri Dec 13 10:13:21 2013
@@ -23,9 +23,10 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
import java.lang.reflect.Array;
+import org.apache.directory.mavibot.btree.AbstractPage;
import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.KeyHolder;
import org.apache.directory.mavibot.btree.Page;
-import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
/**
@@ -37,39 +38,16 @@ import org.apache.directory.mavibot.btre
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-/* No qualifier */abstract class AbstractPage<K, V> implements Page<K, V>
+/* No qualifier */abstract class AbstractPersistedPage<K, V> extends AbstractPage<K, V>
{
- /** Parent B+Tree. */
- protected transient BTree<K, V> btree;
-
- /** This BPage's revision */
- protected long revision;
-
- /** Keys of children nodes */
- protected KeyHolder<K>[] keys;
-
- /** The number of current values in the Page */
- protected int nbElems;
-
- /** The first {@link PageIO} storing the serialized Page on disk */
- private long offset = -1L;
-
- /** The last {@link PageIO} storing the serialized Page on disk */
- private long lastOffset = -1L;
-
- /** A static Exception used to avoid creating a new one every time */
- protected KeyNotFoundException KEY_NOT_FOUND_EXCEPTION = new KeyNotFoundException(
- "Cannot find an entry associated with this key" );
-
-
/**
* Creates a default empty AbstractPage
*
* @param btree The associated BTree
*/
- protected AbstractPage( BTree<K, V> btree )
+ protected AbstractPersistedPage( BTree<K, V> btree )
{
- this.btree = btree;
+ super( btree );
}
@@ -78,9 +56,9 @@ import org.apache.directory.mavibot.btre
*/
@SuppressWarnings("unchecked")
// Cannot create an array of generic objects
- protected AbstractPage( BTree<K, V> btree, long revision, int nbElems )
+ protected AbstractPersistedPage( BTree<K, V> btree, long revision, int nbElems )
{
- this.btree = btree;
+ super( btree );
this.revision = revision;
this.nbElems = nbElems;
this.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, nbElems );
@@ -130,161 +108,6 @@ import org.apache.directory.mavibot.btre
/**
- * {@inheritDoc}
- */
- public int getNbElems()
- {
- return nbElems;
- }
-
-
- /**
- * Finds the position of the given key in the page. If we have found the key,
- * we will return its position as a negative value.
- * <p/>
- * Assuming that the array is zero-indexed, the returned value will be : <br/>
- * position = - ( position + 1)
- * <br/>
- * So for the following table of keys : <br/>
- * <pre>
- * +---+---+---+---+
- * | b | d | f | h |
- * +---+---+---+---+
- * 0 1 2 3
- * </pre>
- * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
- * Computing the real position is just a matter to get -(position++).
- * <p/>
- * If we don't find the key in the table, we will return the position of the key
- * immediately above the key we are looking for. <br/>
- * For instance, looking for :
- * <ul>
- * <li>'a' will return 0</li>
- * <li>'b' will return -1</li>
- * <li>'c' will return 1</li>
- * <li>'d' will return -2</li>
- * <li>'e' will return 2</li>
- * <li>'f' will return -3</li>
- * <li>'g' will return 3</li>
- * <li>'h' will return -4</li>
- * <li>'i' will return 4</li>
- * </ul>
- *
- *
- * @param key The key to find
- * @return The position in the page.
- */
- public int findPos( K key )
- {
- // Deal with the special key where we have an empty page
- if ( nbElems == 0 )
- {
- return 0;
- }
-
- int min = 0;
- int max = nbElems - 1;
-
- // binary search
- while ( min < max )
- {
- int middle = ( min + max + 1 ) >> 1;
-
- int comp = compare( keys[middle].getKey(), key );
-
- if ( comp < 0 )
- {
- min = middle + 1;
- }
- else if ( comp > 0 )
- {
- max = middle - 1;
- }
- else
- {
- // Special case : the key already exists,
- // we can return immediately. The value will be
- // negative, and as the index may be 0, we subtract 1
- return -( middle + 1 );
- }
- }
-
- // Special case : we don't know if the key is present
- int comp = compare( keys[max].getKey(), key );
-
- if ( comp == 0 )
- {
- return -( max + 1 );
- }
- else
- {
- if ( comp < 0 )
- {
- return max + 1;
- }
- else
- {
- return max;
- }
- }
- }
-
-
- /**
- * Compares two keys
- *
- * @param key1 The first key
- * @param key2 The second key
- * @return -1 if the first key is above the second one, 1 if it's below, and 0
- * if the two keys are equal
- */
- private final int compare( K key1, K key2 )
- {
- if ( key1 == key2 )
- {
- return 0;
- }
-
- if ( key1 == null )
- {
- return 1;
- }
-
- if ( key2 == null )
- {
- return -1;
- }
-
- return btree.getComparator().compare( key1, key2 );
- }
-
-
- /**
- * {@inheritDoc}
- */
- public long getRevision()
- {
- return revision;
- }
-
-
- /**
- * {@inheritDoc}
- */
- public K getKey( int pos )
- {
- if ( pos < nbElems )
- {
- return keys[pos].getKey();
- }
- else
- {
- return null;
- }
- }
-
-
- /**
* Sets the key at a give position
*
* @param pos The position in the keys array
@@ -292,7 +115,7 @@ import org.apache.directory.mavibot.btre
*/
/* No qualifier*/void setKey( int pos, K key )
{
- keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
+ keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
}
@@ -304,70 +127,6 @@ import org.apache.directory.mavibot.btre
*/
/* No qualifier*/void setKey( int pos, byte[] buffer )
{
- keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), buffer );
- }
-
-
- /**
- * {@inheritDoc}
- */
- public long getOffset()
- {
- return offset;
- }
-
-
- /**
- * @param offset the offset to set
- */
- /* No qualifier */void setOffset( long offset )
- {
- this.offset = offset;
- }
-
-
- /**
- * {@inheritDoc}
- */
- public long getLastOffset()
- {
- return lastOffset;
- }
-
-
- /**
- * {@inheritDoc}
- */
- /* No qualifier */void setLastOffset( long lastOffset )
- {
- this.lastOffset = lastOffset;
- }
-
-
- /**
- * @see Object#toString()
- */
- public String toString()
- {
- StringBuilder sb = new StringBuilder();
-
- sb.append( "r" ).append( revision );
- sb.append( ", nbElems:" ).append( nbElems );
-
- if ( offset > 0 )
- {
- sb.append( ", offset:" ).append( offset );
- }
-
- return sb.toString();
- }
-
-
- /**
- * {@inheritDoc}
- */
- public String dumpPage( String tabs )
- {
- return "";
+ keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), buffer );
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java Fri Dec 13 10:13:21 2013
@@ -233,7 +233,7 @@ public class BTreeFactory
*/
public static <K, V> void setKey( Page<K, V> page, int pos, K key )
{
- ( ( AbstractPage<K, V> ) page ).setKey( pos, key );
+ ( ( AbstractPersistedPage<K, V> ) page ).setKey( pos, key );
}
@@ -245,7 +245,7 @@ public class BTreeFactory
*/
public static <K, V> void setKey( Page<K, V> page, int pos, byte[] buffer )
{
- ( ( AbstractPage<K, V> ) page ).setKey( pos, buffer );
+ ( ( AbstractPersistedPage<K, V> ) page ).setKey( pos, buffer );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java Fri Dec 13 10:13:21 2013
@@ -28,6 +28,7 @@ import org.apache.directory.mavibot.btre
import org.apache.directory.mavibot.btree.BorrowedFromRightResult;
import org.apache.directory.mavibot.btree.DeleteResult;
import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.KeyHolder;
import org.apache.directory.mavibot.btree.ModifyResult;
import org.apache.directory.mavibot.btree.NotPresentResult;
import org.apache.directory.mavibot.btree.Page;
@@ -50,7 +51,7 @@ import org.apache.directory.mavibot.btre
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-/* No qualifier */class Leaf<K, V> extends AbstractPage<K, V>
+/* No qualifier */class Leaf<K, V> extends AbstractPersistedPage<K, V>
{
/** Values associated with keys */
protected ValueHolder<V>[] values;
@@ -377,7 +378,7 @@ import org.apache.directory.mavibot.btre
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
// Insert the borrowed element
- newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
+ newLeaf.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey );
newLeaf.values[0] = siblingValue;
// Copy the keys and the values up to the insertion position,
@@ -428,7 +429,7 @@ import org.apache.directory.mavibot.btre
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
// Insert the borrowed element at the end
- newLeaf.keys[nbElems - 1] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
+ newLeaf.keys[nbElems - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey );
newLeaf.values[nbElems - 1] = siblingHolder;
// Copy the keys and the values up to the deletion position,
@@ -850,7 +851,7 @@ import org.apache.directory.mavibot.btre
// Deal with the special case of an empty page
if ( nbElems == 0 )
{
- newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
+ newLeaf.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
newLeaf.values[0] = valueHolder;
}
@@ -861,7 +862,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( values, 0, newLeaf.values, 0, pos );
// Add the new element
- newLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
+ newLeaf.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
newLeaf.values[pos] = valueHolder;
// And copy the remaining elements
@@ -906,7 +907,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( values, 0, leftLeaf.values, 0, pos );
// Add the new element
- leftLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
+ leftLeaf.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
leftLeaf.values[pos] = valueHolder;
// And copy the remaining elements
@@ -939,7 +940,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
// Add the new element
- rightLeaf.keys[rightPos] = new KeyHolder<K>( btree.getKeySerializer(), key );
+ rightLeaf.keys[rightPos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
rightLeaf.values[rightPos] = valueHolder;
// And copy the remaining elements
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java Fri Dec 13 10:13:21 2013
@@ -30,6 +30,7 @@ import org.apache.directory.mavibot.btre
import org.apache.directory.mavibot.btree.BorrowedFromRightResult;
import org.apache.directory.mavibot.btree.DeleteResult;
import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.KeyHolder;
import org.apache.directory.mavibot.btree.ModifyResult;
import org.apache.directory.mavibot.btree.NotPresentResult;
import org.apache.directory.mavibot.btree.Page;
@@ -53,7 +54,7 @@ import org.apache.directory.mavibot.btre
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-/* No qualifier */class Node<K, V> extends AbstractPage<K, V>
+/* No qualifier */class Node<K, V> extends AbstractPersistedPage<K, V>
{
/** Children pages associated with keys. */
protected PageHolder<K, V>[] children;
@@ -104,9 +105,9 @@ import org.apache.directory.mavibot.btre
// Create the keys array and store the pivot into it
// We get the type of array to create from the btree
// Yes, this is an hack...
- keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, btree.getPageSize() );
+ keys = ( KeyHolder<K>[] ) Array.newInstance( PersistedKeyHolder.class, btree.getPageSize() );
- keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
+ keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
}
@@ -137,7 +138,7 @@ import org.apache.directory.mavibot.btre
// Create the keys array and store the pivot into it
keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, btree.getPageSize() );
- keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
+ keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
}
@@ -305,7 +306,7 @@ import org.apache.directory.mavibot.btre
int index = Math.abs( pos );
// Copy the key and children from sibling
- newNode.keys[nbElems - 1] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey ); // 1
+ newNode.keys[nbElems - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey ); // 1
newNode.children[nbElems] = sibling.children[0]; // 8
if ( index < 2 )
@@ -329,7 +330,7 @@ import org.apache.directory.mavibot.btre
}
// Inject the new modified page key
- newNode.keys[index - 2] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ newNode.keys[index - 2] = new PersistedKeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
.getLeftMostKey() ); // 2
if ( index < nbElems )
@@ -395,7 +396,7 @@ import org.apache.directory.mavibot.btre
if ( index < 2 )
{
- newNode.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ newNode.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
.getLeftMostKey() );
System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
@@ -406,7 +407,7 @@ import org.apache.directory.mavibot.btre
else
{
// Set the first key
- newNode.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), children[0].getValue( btree )
+ newNode.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), children[0].getValue( btree )
.getLeftMostKey() ); //2
if ( index > 2 )
@@ -416,7 +417,7 @@ import org.apache.directory.mavibot.btre
}
// Inject the modified key
- newNode.keys[index - 1] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ newNode.keys[index - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
.getLeftMostKey() ); // 3
if ( index < nbElems )
@@ -479,7 +480,7 @@ import org.apache.directory.mavibot.btre
// Then copy all the elements up to the deletion point
if ( index < 2 )
{
- newNode.keys[half] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ newNode.keys[half] = new PersistedKeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
.getLeftMostKey() );
System.arraycopy( keys, 1, newNode.keys, half + 1, half - 1 );
@@ -491,7 +492,7 @@ import org.apache.directory.mavibot.btre
{
// Copy the left part of the node keys up to the deletion point
// Insert the new key
- newNode.keys[half] = new KeyHolder<K>( btree.getKeySerializer(), children[0].getValue( btree )
+ newNode.keys[half] = new PersistedKeyHolder<K>( btree.getKeySerializer(), children[0].getValue( btree )
.getLeftMostKey() ); // 3
if ( index > 2 )
@@ -500,7 +501,7 @@ import org.apache.directory.mavibot.btre
}
// Inject the new merged key
- newNode.keys[half + index - 1] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult
+ newNode.keys[half + index - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), mergedResult
.getModifiedPage().getLeftMostKey() ); //5
if ( index < half )
@@ -545,7 +546,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( children, 0, newNode.children, 0, index - 1 ); //6
// Inject the modified key
- newNode.keys[index - 2] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ newNode.keys[index - 2] = new PersistedKeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
.getLeftMostKey() ); //2
// Inject the modified children
@@ -563,7 +564,7 @@ import org.apache.directory.mavibot.btre
}
// Inject the new key from sibling
- newNode.keys[half - 1] = new KeyHolder<K>( btree.getKeySerializer(), sibling.findLeftMost().getKey() ); //3
+ newNode.keys[half - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), sibling.findLeftMost().getKey() ); //3
// Copy the sibling keys
System.arraycopy( sibling.keys, 0, newNode.keys, half, half );
@@ -728,8 +729,8 @@ import org.apache.directory.mavibot.btre
if ( borrowedResult.isFromRight() )
{
// Update the keys
- newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost().getKey() );
- newPage.keys[pos + 1] = new KeyHolder<K>( btree.getKeySerializer(), modifiedSibling.findLeftMost()
+ newPage.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost().getKey() );
+ newPage.keys[pos + 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), modifiedSibling.findLeftMost()
.getKey() );
// Update the children
@@ -739,7 +740,7 @@ import org.apache.directory.mavibot.btre
else
{
// Update the keys
- newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost().getKey() );
+ newPage.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost().getKey() );
// Update the children
newPage.children[pos] = createHolder( modifiedSibling );
@@ -751,7 +752,7 @@ import org.apache.directory.mavibot.btre
if ( borrowedResult.isFromRight() )
{
// Update the keys
- newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedSibling.findLeftMost().getKey() );
+ newPage.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), modifiedSibling.findLeftMost().getKey() );
// Update the children
newPage.children[pos] = createHolder( modifiedPage );
@@ -760,7 +761,7 @@ import org.apache.directory.mavibot.btre
else
{
// Update the keys
- newPage.keys[pos - 1] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost()
+ newPage.keys[pos - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost()
.getKey() );
// Update the children
@@ -813,7 +814,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( keys, 0, newNode.keys, 0, index );
}
- newNode.keys[index] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ newNode.keys[index] = new PersistedKeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
.findLeftMost().getKey() );
if ( index < nbElems - 2 )
@@ -1090,7 +1091,7 @@ import org.apache.directory.mavibot.btre
}
// Add the new key and children
- newNode.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
+ newNode.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
// If the BTree is managed, we now have to write the modified page on disk
// and to add this page to the list of modified pages
@@ -1149,7 +1150,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( children, 0, newLeftPage.children, 0, pos );
// Add the new element
- newLeftPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), pivot );
+ newLeftPage.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), pivot );
newLeftPage.children[pos] = createHolder( leftPage );
newLeftPage.children[pos + 1] = createHolder( rightPage );
@@ -1206,7 +1207,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( children, middle + 1, newRightPage.children, 0, pos - middle - 1 );
// Add the new element
- newRightPage.keys[pos - middle - 1] = new KeyHolder<K>( btree.getKeySerializer(), pivot );
+ newRightPage.keys[pos - middle - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), pivot );
newRightPage.children[pos - middle - 1] = createHolder( leftPage );
newRightPage.children[pos - middle] = createHolder( rightPage );
@@ -1254,25 +1255,51 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- public K getLeftMostKey() throws EndOfFileExceededException, IOException
+ public K getLeftMostKey()
{
- return children[0].getValue( btree ).getLeftMostKey();
+ try
+ {
+ return children[0].getValue( btree ).getLeftMostKey();
+ }
+ catch ( EndOfFileExceededException eofe )
+ {
+ eofe.printStackTrace();
+ return null;
+ }
+ catch ( IOException ioe )
+ {
+ ioe.printStackTrace();
+ return null;
+ }
}
/**
* {@inheritDoc}
*/
- public K getRightMostKey() throws EndOfFileExceededException, IOException
+ public K getRightMostKey()
{
int index = ( nbElems + 1 ) - 1;
- if ( children[index] != null )
+ try
{
- return children[index].getValue( btree ).getRightMostKey();
+ if ( children[index] != null )
+ {
+ return children[index].getValue( btree ).getRightMostKey();
+ }
+
+ return children[nbElems - 1].getValue( btree ).getRightMostKey();
+ }
+ catch ( EndOfFileExceededException eofe )
+ {
+ eofe.printStackTrace();
+ return null;
+ }
+ catch ( IOException ioe )
+ {
+ ioe.printStackTrace();
+ return null;
}
-
- return children[nbElems - 1].getValue( btree ).getRightMostKey();
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageHolder.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageHolder.java Fri Dec 13 10:13:21 2013
@@ -65,8 +65,8 @@ public class PageHolder<K, V>
if ( page instanceof Page<?, ?> )
{
- ( ( AbstractPage<K, V> ) page ).setOffset( offset );
- ( ( AbstractPage<K, V> ) page ).setLastOffset( lastOffset );
+ ( ( AbstractPersistedPage<K, V> ) page ).setOffset( offset );
+ ( ( AbstractPersistedPage<K, V> ) page ).setLastOffset( lastOffset );
}
((PersistedBTree<K, V>)btree).getCache().put( new Element( offset, page ) );
@@ -86,8 +86,8 @@ public class PageHolder<K, V>
if ( page instanceof Page<?, ?> )
{
- ( ( AbstractPage<K, V> ) page ).setOffset( offset );
- ( ( AbstractPage<K, V> ) page ).setLastOffset( lastOffset );
+ ( ( AbstractPersistedPage<K, V> ) page ).setOffset( offset );
+ ( ( AbstractPersistedPage<K, V> ) page ).setLastOffset( lastOffset );
}
((PersistedBTree<K, V>)btree).getCache().put( new Element( offset, page ) );
@@ -123,8 +123,8 @@ public class PageHolder<K, V>
if ( page instanceof Page<?, ?> )
{
- ( ( AbstractPage<K, V> ) page ).setOffset( offset );
- ( ( AbstractPage<K, V> ) page ).setLastOffset( lastOffset );
+ ( ( AbstractPersistedPage<K, V> ) page ).setOffset( offset );
+ ( ( AbstractPersistedPage<K, V> ) page ).setLastOffset( lastOffset );
}
((PersistedBTree<K, V>)btree).getCache().put( new Element( offset, page ) );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTree.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTree.java Fri Dec 13 10:13:21 2013
@@ -31,7 +31,6 @@ import net.sf.ehcache.Cache;
import net.sf.ehcache.config.CacheConfiguration;
import org.apache.directory.mavibot.btree.AbstractBTree;
-import org.apache.directory.mavibot.btree.BTree;
import org.apache.directory.mavibot.btree.BTreeHeader;
import org.apache.directory.mavibot.btree.DeleteResult;
import org.apache.directory.mavibot.btree.InsertResult;
@@ -445,11 +444,11 @@ public class PersistedBTree<K, V> extend
revision );
// Store the offset on disk in the page in memory
- ( ( AbstractPage<K, V> ) modifiedPage ).setOffset( ( ( PageHolder<K, V> ) holder )
+ ( ( AbstractPersistedPage<K, V> ) modifiedPage ).setOffset( ( ( PageHolder<K, V> ) holder )
.getOffset() );
// Store the last offset on disk in the page in memory
- ( ( AbstractPage<K, V> ) modifiedPage )
+ ( ( AbstractPersistedPage<K, V> ) modifiedPage )
.setLastOffset( ( ( PageHolder<K, V> ) holder )
.getLastOffset() );
@@ -465,7 +464,7 @@ public class PersistedBTree<K, V> extend
// We have to update the rootPage on disk
// Update the BTree header now
- recordManager.updateBtreeHeader( this, ( ( AbstractPage<K, V> ) rootPage ).getOffset() );
+ recordManager.updateBtreeHeader( this, ( ( AbstractPersistedPage<K, V> ) rootPage ).getOffset() );
}
recordManager.addFreePages( this, result.getCopiedPages() );
@@ -576,7 +575,7 @@ public class PersistedBTree<K, V> extend
recordManager.updateRecordManagerHeader();
// Update the BTree header now
- recordManager.updateBtreeHeader( this, ( ( AbstractPage<K, V> ) rootPage ).getOffset() );
+ recordManager.updateBtreeHeader( this, ( ( AbstractPersistedPage<K, V> ) rootPage ).getOffset() );
// Moved the free pages into the list of free pages
recordManager.addFreePages( this, result.getCopiedPages() );
@@ -654,15 +653,6 @@ public class PersistedBTree<K, V> extend
/**
- * @return the type for the keys
- */
- public Class<?> getKeyType()
- {
- return KeyHolder.class;
- }
-
-
- /**
* @see Object#toString()
*/
public String toString()
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTreeBuilder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTreeBuilder.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTreeBuilder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedBTreeBuilder.java Fri Dec 13 10:13:21 2013
@@ -34,6 +34,7 @@ import java.util.Iterator;
import java.util.List;
import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.KeyHolder;
import org.apache.directory.mavibot.btree.Page;
import org.apache.directory.mavibot.btree.Tuple;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
@@ -116,16 +117,16 @@ public class PersistedBTreeBuilder<K, V>
// remove null keys and values from the last leaf and resize
Leaf<K, V> lastLeaf = ( Leaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
- for ( int i = 0; i < lastLeaf.nbElems; i++ )
+ for ( int i = 0; i < lastLeaf.getNbElems(); i++ )
{
- if ( lastLeaf.keys[i] == null )
+ if ( lastLeaf.getKey( i ) == null )
{
int n = i;
- lastLeaf.nbElems = n;
- KeyHolder<K>[] keys = lastLeaf.keys;
+ lastLeaf.setNbElems( n );
+ KeyHolder<K>[] keys = lastLeaf.getKeys();
- lastLeaf.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n );
- System.arraycopy( keys, 0, lastLeaf.keys, 0, n );
+ lastLeaf.setKeys( ( KeyHolder[] ) Array.newInstance( PersistedKeyHolder.class, n ) );
+ System.arraycopy( keys, 0, lastLeaf.getKeys(), 0, n );
ValueHolder<V>[] values = lastLeaf.values;
lastLeaf.values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, n );
@@ -144,7 +145,7 @@ public class PersistedBTreeBuilder<K, V>
//System.out.println("built rootpage : " + rootPage);
((PersistedBTree<K, V>)btree).setNbElems( totalTupleCount );
- rm.updateBtreeHeader( btree, ( ( AbstractPage<K, V> ) rootPage ).getOffset() );
+ rm.updateBtreeHeader( btree, ( ( AbstractPersistedPage<K, V> ) rootPage ).getOffset() );
rm.addFreePages( btree, Arrays.asList( btree.getRootPage() ) );
@@ -195,18 +196,18 @@ public class PersistedBTreeBuilder<K, V>
}
// remove null keys and values from the last node and resize
- AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
+ AbstractPersistedPage<K, V> lastNode = ( AbstractPersistedPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
- for ( int j = 0; j < lastNode.nbElems; j++ )
+ for ( int j = 0; j < lastNode.getNbElems(); j++ )
{
- if ( lastNode.keys[j] == null )
+ if ( lastNode.getKey( j ) == null )
{
int n = j;
- lastNode.nbElems = n;
- KeyHolder<K>[] keys = lastNode.keys;
+ lastNode.setNbElems( n );
+ KeyHolder<K>[] keys = lastNode.getKeys();
- lastNode.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n );
- System.arraycopy( keys, 0, lastNode.keys, 0, n );
+ lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) );
+ System.arraycopy( keys, 0, lastNode.getKeys(), 0, n );
PageHolder<K, V> pageHolder = ( PageHolder<K, V> ) rm.writePage( btree, lastNode, 1 );
Copied: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedKeyHolder.java (from r1550046, directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java)
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedKeyHolder.java?p2=directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedKeyHolder.java&p1=directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java&r1=1550046&r2=1550673&rev=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PersistedKeyHolder.java Fri Dec 13 10:13:21 2013
@@ -22,6 +22,7 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
+import org.apache.directory.mavibot.btree.KeyHolder;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
@@ -32,11 +33,8 @@ import org.apache.directory.mavibot.btre
*
* <K> The key type
*/
-public class KeyHolder<K>
+public class PersistedKeyHolder<K> extends KeyHolder<K>
{
- /** The deserialized key */
- private K key;
-
/** The ByteBuffer storing the key */
private byte[] raw;
@@ -49,9 +47,9 @@ public class KeyHolder<K>
* @param keySerializer The KeySerializer instance
* @param key The key to store
*/
- /* No Qualifier */KeyHolder( ElementSerializer<K> keySerializer, K key )
+ PersistedKeyHolder( ElementSerializer<K> keySerializer, K key )
{
- this.key = key;
+ super( key );
this.keySerializer = keySerializer;
raw = keySerializer.serialize( key );
}
@@ -62,9 +60,9 @@ public class KeyHolder<K>
* @param keySerializer The KeySerializer instance
* @param raw the bytes representing the serialized key
*/
- /* No Qualifier */KeyHolder( ElementSerializer<K> keySerializer, byte[] raw )
+ PersistedKeyHolder( ElementSerializer<K> keySerializer, byte[] raw )
{
- this.key = null;
+ super( null );
this.keySerializer = keySerializer;
this.raw = raw;
}
@@ -117,7 +115,7 @@ public class KeyHolder<K>
{
StringBuilder sb = new StringBuilder();
- sb.append( "KeyHolder[" );
+ sb.append( "PersistedKeyHolder[" );
if ( key != null )
{
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java Fri Dec 13 10:13:21 2013
@@ -34,6 +34,7 @@ import java.util.Set;
import java.util.concurrent.atomic.AtomicLong;
import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.KeyHolder;
import org.apache.directory.mavibot.btree.Page;
import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
@@ -568,8 +569,8 @@ public class RecordManager
Page<K, V> page = readPage( btree, rootPageIos );
- ( ( AbstractPage<K, V> ) page ).setOffset( rootPageIos[0].getOffset() );
- ( ( AbstractPage<K, V> ) page ).setLastOffset( rootPageIos[rootPageIos.length - 1].getOffset() );
+ ( ( AbstractPersistedPage<K, V> ) page ).setOffset( rootPageIos[0].getOffset() );
+ ( ( AbstractPersistedPage<K, V> ) page ).setLastOffset( rootPageIos[rootPageIos.length - 1].getOffset() );
return page;
}
@@ -1240,7 +1241,7 @@ public class RecordManager
private <K, V> int serializeNodeKey( Node<K, V> node, int pos, List<byte[]> serializedData )
{
KeyHolder<K> holder = node.getKeyHolder( pos );
- byte[] buffer = holder.getRaw();
+ byte[] buffer = ((PersistedKeyHolder<K>)holder).getRaw();
// We have to store the serialized key length
byte[] length = IntSerializer.serialize( buffer.length );
@@ -1283,7 +1284,7 @@ public class RecordManager
{
int dataSize = 0;
KeyHolder<K> keyHolder = leaf.getKeyHolder( pos );
- byte[] keyData = keyHolder.getRaw();
+ byte[] keyData = ((PersistedKeyHolder<K>)keyHolder).getRaw();
if ( keyData != null )
{
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java Fri Dec 13 10:13:21 2013
@@ -23,6 +23,7 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
import java.util.NoSuchElementException;
+import org.apache.directory.mavibot.btree.AbstractTupleCursor;
import org.apache.directory.mavibot.btree.BTree;
import org.apache.directory.mavibot.btree.Page;
import org.apache.directory.mavibot.btree.ParentPos;
@@ -43,25 +44,11 @@ import org.apache.directory.mavibot.btre
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-public class TupleCursorImpl<K, V> implements TupleCursor<K, V>
+public class TupleCursorImpl<K, V> extends AbstractTupleCursor<K, V>
{
- /** The transaction used for this cursor */
- private Transaction<K, V> transaction;
-
- /** The Tuple used to return the results */
- private Tuple<K, V> tuple = new Tuple<K, V>();
-
- /** The stack of pages from the root down to the leaf */
- private ParentPos<K, V>[] stack;
-
- /** The stack's depth */
- private int depth = 0;
-
/** The BTree we are walking */
- private BTree<K, V> btree;
-
- private boolean allowDuplicates;
-
+ protected BTree<K, V> btree;
+
/**
* Creates a new instance of Cursor, starting on a page at a given position.
@@ -71,11 +58,9 @@ public class TupleCursorImpl<K, V> imple
*/
TupleCursorImpl( BTree<K, V> btree, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
{
- this.transaction = transaction;
- this.stack = stack;
+ super( transaction, stack, depth );
+
this.btree = btree;
- this.allowDuplicates = btree.isAllowDuplicates();
- this.depth = depth;
}
@@ -157,7 +142,7 @@ public class TupleCursorImpl<K, V> imple
}
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
- tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+ tuple.setKey( leaf.getKey( parentPos.pos ) );
tuple.setValue( value );
return tuple;
@@ -367,7 +352,7 @@ public class TupleCursorImpl<K, V> imple
parentPos = stack[currentDepth];
parentPos.pos = child.getNbElems();
parentPos.page = child;
- child = ((Node<K, V>)parentPos.page).children[((Node<K, V>)parentPos.page).nbElems].getValue( btree );
+ child = ((Node<K, V>)parentPos.page).children[parentPos.page.getNbElems()].getValue( btree );
}
// and the leaf
@@ -466,7 +451,7 @@ public class TupleCursorImpl<K, V> imple
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
- tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+ tuple.setKey( leaf.getKey( parentPos.pos ) );
tuple.setValue( value );
return tuple;
@@ -602,33 +587,6 @@ public class TupleCursorImpl<K, V> imple
/**
* {@inheritDoc}
*/
- public void close()
- {
- transaction.close();
- }
-
-
- /**
- * {@inheritDoc}
- */
- public long getRevision()
- {
- return transaction.getRevision();
- }
-
-
- /**
- * {@inheritDoc}
- */
- public long getCreationDate()
- {
- return transaction.getCreationDate();
- }
-
-
- /**
- * {@inheritDoc}
- */
public boolean hasNextKey() throws EndOfFileExceededException, IOException
{
// First check that we have elements in the BTree
@@ -711,7 +669,7 @@ public class TupleCursorImpl<K, V> imple
// The key
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
- tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+ tuple.setKey( leaf.getKey( parentPos.pos ) );
// The value
ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
@@ -804,7 +762,7 @@ public class TupleCursorImpl<K, V> imple
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
// The key
- tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+ tuple.setKey( leaf.getKey( parentPos.pos ) );
// The value
ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
@@ -879,12 +837,12 @@ public class TupleCursorImpl<K, V> imple
if ( child != null )
{
parentPos.page = child;
- parentPos.pos = ((Node<K, V>)child).nbElems;
+ parentPos.pos = child.getNbElems();
}
else
{
// We have N+1 children if the page is a Node, so we don't decrement the nbElems field
- parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
+ parentPos.pos = parentPos.page.getNbElems();
}
child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue( btree );
@@ -895,12 +853,12 @@ public class TupleCursorImpl<K, V> imple
if ( child == null )
{
- parentPos.pos = ((Leaf<K, V>)parentPos.page).nbElems - 1;
+ parentPos.pos = parentPos.page.getNbElems() - 1;
}
else
{
parentPos.page = child;
- parentPos.pos = ((Leaf<K, V>)child).nbElems - 1;
+ parentPos.pos = child.getNbElems() - 1;
}
parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
Copied: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractInMemoryPage.java (from r1550580, directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractPage.java)
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractInMemoryPage.java?p2=directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractInMemoryPage.java&p1=directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractPage.java&r1=1550580&r2=1550673&rev=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractPage.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/AbstractInMemoryPage.java Fri Dec 13 10:13:21 2013
@@ -23,9 +23,12 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
import java.lang.reflect.Array;
+import org.apache.directory.mavibot.btree.AbstractPage;
import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.KeyHolder;
import org.apache.directory.mavibot.btree.Page;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.managed.PersistedKeyHolder;
/**
@@ -37,57 +40,31 @@ import org.apache.directory.mavibot.btre
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-/* No qualifier */abstract class AbstractPage<K, V> implements Page<K, V>
+/* No qualifier */abstract class AbstractInMemoryPage<K, V> extends AbstractPage<K, V>
{
- /** Parent B+Tree. */
- protected transient BTree<K, V> btree;
-
- /** This BPage's revision */
- protected long revision;
-
- /** Keys of children nodes */
- protected K[] keys;
-
- /** The number of current values in the Page */
- protected int nbElems;
-
- /** The first {@link PageIO} storing the serialized Page on disk */
- private long offset = -1L;
-
- /** The last {@link PageIO} storing the serialized Page on disk */
- private long lastOffset = -1L;
-
- /** A static Exception used to avoid creating a new one every time */
- protected KeyNotFoundException KEY_NOT_FOUND_EXCEPTION = new KeyNotFoundException(
- "Cannot find an entry associated with this key" );
-
-
/**
- * Creates a default empty AbstractPage
- *
- * @param btree The associated BTree
+ * Internal constructor used to create Page instance used when a page is being copied or overflow
*/
- protected AbstractPage( BTree<K, V> btree )
+ protected AbstractInMemoryPage( BTree<K, V> btree )
{
- this.btree = btree;
+ super( btree );
}
-
-
+
+
/**
* Internal constructor used to create Page instance used when a page is being copied or overflow
*/
@SuppressWarnings("unchecked")
// Cannot create an array of generic objects
- protected AbstractPage( BTree<K, V> btree, long revision, int nbElems )
+ protected AbstractInMemoryPage( BTree<K, V> btree, long revision, int nbElems )
{
- this.btree = btree;
+ super( btree );
this.revision = revision;
this.nbElems = nbElems;
// We get the type of array to create from the btree
// Yes, this is an hack...
- Class<?> keyType = btree.getKeyType();
- this.keys = ( K[] ) Array.newInstance( keyType, nbElems );
+ this.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, nbElems ) );
}
@@ -134,161 +111,6 @@ import org.apache.directory.mavibot.btre
/**
- * {@inheritDoc}
- */
- public int getNbElems()
- {
- return nbElems;
- }
-
-
- /**
- * Finds the position of the given key in the page. If we have found the key,
- * we will return its position as a negative value.
- * <p/>
- * Assuming that the array is zero-indexed, the returned value will be : <br/>
- * position = - ( position + 1)
- * <br/>
- * So for the following table of keys : <br/>
- * <pre>
- * +---+---+---+---+
- * | b | d | f | h |
- * +---+---+---+---+
- * 0 1 2 3
- * </pre>
- * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
- * Computing the real position is just a matter to get -(position++).
- * <p/>
- * If we don't find the key in the table, we will return the position of the key
- * immediately above the key we are looking for. <br/>
- * For instance, looking for :
- * <ul>
- * <li>'a' will return 0</li>
- * <li>'b' will return -1</li>
- * <li>'c' will return 1</li>
- * <li>'d' will return -2</li>
- * <li>'e' will return 2</li>
- * <li>'f' will return -3</li>
- * <li>'g' will return 3</li>
- * <li>'h' will return -4</li>
- * <li>'i' will return 4</li>
- * </ul>
- *
- *
- * @param key The key to find
- * @return The position in the page.
- */
- public int findPos( K key )
- {
- // Deal with the special key where we have an empty page
- if ( nbElems == 0 )
- {
- return 0;
- }
-
- int min = 0;
- int max = nbElems - 1;
-
- // binary search
- while ( min < max )
- {
- int middle = ( min + max + 1 ) >> 1;
-
- int comp = compare( keys[middle], key );
-
- if ( comp < 0 )
- {
- min = middle + 1;
- }
- else if ( comp > 0 )
- {
- max = middle - 1;
- }
- else
- {
- // Special case : the key already exists,
- // we can return immediately. The value will be
- // negative, and as the index may be 0, we subtract 1
- return -( middle + 1 );
- }
- }
-
- // Special case : we don't know if the key is present
- int comp = compare( keys[max], key );
-
- if ( comp == 0 )
- {
- return -( max + 1 );
- }
- else
- {
- if ( comp < 0 )
- {
- return max + 1;
- }
- else
- {
- return max;
- }
- }
- }
-
-
- /**
- * Compares two keys
- *
- * @param key1 The first key
- * @param key2 The second key
- * @return -1 if the first key is above the second one, 1 if it's below, and 0
- * if the two keys are equal
- */
- private final int compare( K key1, K key2 )
- {
- if ( key1 == key2 )
- {
- return 0;
- }
-
- if ( key1 == null )
- {
- return 1;
- }
-
- if ( key2 == null )
- {
- return -1;
- }
-
- return btree.getComparator().compare( key1, key2 );
- }
-
-
- /**
- * {@inheritDoc}
- */
- public long getRevision()
- {
- return revision;
- }
-
-
- /**
- * {@inheritDoc}
- */
- public K getKey( int pos )
- {
- if ( pos < nbElems )
- {
- return keys[pos];
- }
- else
- {
- return null;
- }
- }
-
-
- /**
* Sets the key at a give position
*
* @param pos The position in the keys array
@@ -296,70 +118,6 @@ import org.apache.directory.mavibot.btre
*/
/* No qualifier*/void setKey( int pos, K key )
{
- keys[pos] = key;
- }
-
-
- /**
- * {@inheritDoc}
- */
- public long getOffset()
- {
- return offset;
- }
-
-
- /**
- * @param offset the offset to set
- */
- /* No qualifier */void setOffset( long offset )
- {
- this.offset = offset;
- }
-
-
- /**
- * {@inheritDoc}
- */
- public long getLastOffset()
- {
- return lastOffset;
- }
-
-
- /**
- * {@inheritDoc}
- */
- /* No qualifier */void setLastOffset( long lastOffset )
- {
- this.lastOffset = lastOffset;
- }
-
-
- /**
- * @see Object#toString()
- */
- public String toString()
- {
- StringBuilder sb = new StringBuilder();
-
- sb.append( "r" ).append( revision );
- sb.append( ", nbElems:" ).append( nbElems );
-
- if ( offset > 0 )
- {
- sb.append( ", offset:" ).append( offset );
- }
-
- return sb.toString();
- }
-
-
- /**
- * {@inheritDoc}
- */
- public String dumpPage( String tabs )
- {
- return "";
+ keys[pos] = new KeyHolder<K>( key );
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java Fri Dec 13 10:13:21 2013
@@ -191,7 +191,7 @@ public class BTreeFactory
*/
public static <K, V> void setKey( Page<K, V> page, int pos, K key )
{
- ( ( AbstractPage<K, V> ) page ).setKey( pos, key );
+ ( ( AbstractInMemoryPage<K, V> ) page ).setKey( pos, key );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java Fri Dec 13 10:13:21 2013
@@ -26,11 +26,8 @@ import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.RandomAccessFile;
-import java.lang.reflect.ParameterizedType;
-import java.lang.reflect.Type;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
-import java.util.Comparator;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.ReentrantLock;
@@ -47,13 +44,11 @@ import org.apache.directory.mavibot.btre
import org.apache.directory.mavibot.btree.ModifyResult;
import org.apache.directory.mavibot.btree.NotPresentResult;
import org.apache.directory.mavibot.btree.Page;
-import org.apache.directory.mavibot.btree.ParentPos;
import org.apache.directory.mavibot.btree.RemoveResult;
import org.apache.directory.mavibot.btree.SplitResult;
import org.apache.directory.mavibot.btree.Transaction;
import org.apache.directory.mavibot.btree.Tuple;
import org.apache.directory.mavibot.btree.TupleCursor;
-import org.apache.directory.mavibot.btree.ValueCursor;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
import org.apache.directory.mavibot.btree.serializer.BufferHandler;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
@@ -85,8 +80,6 @@ public class InMemoryBTree<K, V> extends
public static final String JOURNAL_SUFFIX = ".log";
/** The type to use to create the keys */
- protected Class<?> keyType;
-
/** The associated file. If null, this is an in-memory btree */
private File file;
@@ -307,24 +300,6 @@ public class InMemoryBTree<K, V> extends
// Create the queue containing the pending read transactions
readTransactions = new ConcurrentLinkedQueue<Transaction<K, V>>();
- // We will extract the Type to use for keys, using the comparator for that
- Class<?> comparatorClass = keySerializer.getComparator().getClass();
- Type[] types = comparatorClass.getGenericInterfaces();
-
- if ( types[0] instanceof Class )
- {
- keyType = ( Class<?> ) types[0];
- }
- else
- {
- Type[] argumentTypes = ( ( ParameterizedType ) types[0] ).getActualTypeArguments();
-
- if ( ( argumentTypes != null ) && ( argumentTypes.length > 0 ) && ( argumentTypes[0] instanceof Class<?> ) )
- {
- keyType = ( Class<?> ) argumentTypes[0];
- }
- }
-
writeLock = new ReentrantLock();
// Check the files and create them if missing
@@ -548,15 +523,6 @@ public class InMemoryBTree<K, V> extends
/**
- * @return the type for the keys
- */
- public Class<?> getKeyType()
- {
- return keyType;
- }
-
-
- /**
* Write the data in the ByteBuffer, and eventually on disk if needed.
*
* @param channel The channel we want to write to
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java?rev=1550673&r1=1550672&r2=1550673&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java Fri Dec 13 10:13:21 2013
@@ -32,7 +32,9 @@ import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
+import org.apache.directory.mavibot.btree.AbstractPage;
import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.KeyHolder;
import org.apache.directory.mavibot.btree.Page;
import org.apache.directory.mavibot.btree.Tuple;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
@@ -105,17 +107,16 @@ public class InMemoryBTreeBuilder<K, V>
// remove null keys and values from the last leaf and resize
Leaf<K, V> lastLeaf = ( Leaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
- for ( int i = 0; i < lastLeaf.nbElems; i++ )
+ for ( int i = 0; i < lastLeaf.getNbElems(); i++ )
{
- if ( lastLeaf.keys[i] == null )
+ if ( lastLeaf.getKeys()[i] == null )
{
int n = i;
- lastLeaf.nbElems = n;
- K[] keys = lastLeaf.keys;
+ lastLeaf.setNbElems( n );
+ KeyHolder<K>[] keys = lastLeaf.getKeys();
- Class<?> keyType = btree.getKeyType();
- lastLeaf.keys = ( K[] ) Array.newInstance( keyType, n );
- System.arraycopy( keys, 0, lastLeaf.keys, 0, n );
+ lastLeaf.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) );
+ System.arraycopy( keys, 0, lastLeaf.getKeys(), 0, n );
ValueHolder<V>[] values = lastLeaf.values;
lastLeaf.values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, n );
@@ -175,17 +176,16 @@ public class InMemoryBTreeBuilder<K, V>
// remove null keys and values from the last node and resize
AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
- for ( int j = 0; j < lastNode.nbElems; j++ )
+ for ( int j = 0; j < lastNode.getNbElems(); j++ )
{
- if ( lastNode.keys[j] == null )
+ if ( lastNode.getKey( j ) == null )
{
int n = j;
- lastNode.nbElems = n;
- K[] keys = lastNode.keys;
+ lastNode.setNbElems( n );
+ KeyHolder<K>[] keys = lastNode.getKeys();
- Class<?> keyType = btree.getKeyType();
- lastNode.keys = ( K[] ) Array.newInstance( keyType, n );
- System.arraycopy( keys, 0, lastNode.keys, 0, n );
+ lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) );
+ System.arraycopy( keys, 0, lastNode.getKeys(), 0, n );
break;
}