You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ka...@apache.org on 2014/05/28 11:22:25 UTC
svn commit: r1597950 - in /directory/mavibot/trunk/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
test/java/org/apache/directory/mavibot/btree/
Author: kayyagari
Date: Wed May 28 09:22:24 2014
New Revision: 1597950
URL: http://svn.apache.org/r1597950
Log:
o avoid copying pages and incrementing revision when the key and value already exist (MAVIBOT-39)
o do not create value holders in sub-btrees (MAVIBOT-38)
o updated serialization code in RecordManager to handle the changes made to sub-btrees
o added a new cursor to browse keys of sub-btree
o added test for KeyCursor
Added:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java
Modified:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java
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/BTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.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/PersistedBTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java Wed May 28 09:22:24 2014
@@ -423,7 +423,11 @@ import org.apache.directory.mavibot.btre
{
InsertResult<K, V> result = insert( key, value, -1L );
- if ( result instanceof ModifyResult )
+ if ( result instanceof ExistsResult )
+ {
+ existingValue = value;
+ }
+ else if ( result instanceof ModifyResult )
{
existingValue = ( ( ModifyResult<K, V> ) result ).getModifiedValue();
}
@@ -431,6 +435,7 @@ import org.apache.directory.mavibot.btre
// Commit now if it's not a sub-btree
if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
{
+ //FIXME when result type is ExistsResult then we should avoid writing the headers
transactionManager.commit();
}
@@ -998,6 +1003,37 @@ import org.apache.directory.mavibot.btre
/**
+ * {@inheritDoc}
+ */
+ public KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException
+ {
+ // Check that we have a TransactionManager
+ if ( transactionManager == null )
+ {
+ throw new BTreeCreationException( "We don't have a Transaction Manager" );
+ }
+
+ ReadTransaction transaction = beginReadTransaction();
+
+ if ( transaction == null )
+ {
+ return new KeyCursor<K>();
+ }
+ else
+ {
+ ParentPos<K, K>[] stack = (ParentPos<K, K>[]) Array.newInstance( ParentPos.class, 32 );
+
+ KeyCursor<K> cursor = getRootPage().browseKeys( transaction, stack, 0 );
+
+ // Set the position before the first element
+ cursor.beforeFirst();
+
+ return cursor;
+ }
+ }
+
+
+ /**
* Create a thread that is responsible of cleaning the transactions when
* they hit the timeout
*/
Modified: 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=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java Wed May 28 09:22:24 2014
@@ -314,6 +314,20 @@ import org.apache.directory.mavibot.btre
/**
+ * {@inheritDoc}
+ */
+ public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+ throws IOException
+ {
+ stack[depth++] = new ParentPos( this, 0 );
+
+ Page<K, V> page = children[0].getValue();
+
+ return page.browseKeys( transaction, stack, depth );
+ }
+
+
+ /**
* Selects the sibling (the previous or next page with the same parent) which has
* the more element assuming it's above N/2
*
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=1597950&r1=1597949&r2=1597950&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 Wed May 28 09:22:24 2014
@@ -257,6 +257,15 @@ public interface BTree<K, V>
/**
+ * Creates a cursor starting at the beginning of the tree
+ *
+ * @return A cursor on the B-tree keys
+ * @throws IOException
+ */
+ KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException;
+
+
+ /**
* @return the comparator
*/
Comparator<K> getComparator();
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java?rev=1597950&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java Wed May 28 09:22:24 2014
@@ -0,0 +1,32 @@
+/*
+ * 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 result of an insert operation, returned when the given <key,value> tuple
+ * already exists in the btree that doesn't support duplicates, or while inserting
+ * a <key, null> in a sub-btree that is used to hold the values of a key.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier*/ class ExistsResult<K, V> extends AbstractResult<K, V> implements InsertResult<K, V>
+{
+ public static final ExistsResult EXISTS = new ExistsResult();
+}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java Wed May 28 09:22:24 2014
@@ -681,6 +681,35 @@ import org.apache.directory.mavibot.btre
/**
+ * {@inheritDoc}
+ */
+ public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+ {
+ int pos = 0;
+ KeyCursor<K> cursor = null;
+
+ if ( nbElems == 0 )
+ {
+ // The tree is empty, it's the root, we have nothing to return
+ stack[depth] = new ParentPos<K, K>( null, -1 );
+
+ return new KeyCursor<K>( transaction, stack, depth );
+ }
+ else
+ {
+ // Start at the beginning of the page
+ ParentPos<K, K> parentPos = new ParentPos( this, pos );
+
+ stack[depth] = parentPos;
+
+ cursor = new KeyCursor<K>( transaction, stack, depth );
+ }
+
+ return cursor;
+ }
+
+
+ /**
* Copy the current page and all of the keys, values and children, if it's not a leaf.
*
* @param revision The new revision
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java?rev=1597950&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java Wed May 28 09:22:24 2014
@@ -0,0 +1,777 @@
+/*
+ * 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 java.io.IOException;
+import java.util.NoSuchElementException;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+
+/**
+ * A Cursor is used to fetch only keys in a BTree and is returned by the
+ * @see BTree#browseKeys method. The cursor <strng>must</strong> be closed
+ * when the user is done with it.
+ * <p>
+ *
+ * @param <K> The type for the Key
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class KeyCursor<K>
+{
+ /** A marker to tell that we are before the first element */
+ private static final int BEFORE_FIRST = -1;
+
+ /** A marker to tell that we are after the last element */
+ private static final int AFTER_LAST = -2;
+
+ /** The stack of pages from the root down to the leaf */
+ protected ParentPos<K, K>[] stack;
+
+ /** The stack's depth */
+ protected int depth = 0;
+
+ /** The transaction used for this cursor */
+ protected ReadTransaction<K, K> transaction;
+
+
+ /**
+ * Creates a new instance of Cursor.
+ */
+ protected KeyCursor()
+ {
+ }
+
+
+ /**
+ * 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
+ */
+ public KeyCursor( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+ {
+ this.transaction = transaction;
+ this.stack = stack;
+ this.depth = depth;
+ }
+
+
+ /**
+ * Change the position in the current cursor to set it after the last key
+ */
+ public void afterLast() throws IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ return;
+ }
+
+ Page<K, K> child = null;
+
+ for ( int i = 0; i < depth; i++ )
+ {
+ ParentPos<K, K> 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 = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
+ }
+
+ // and leaf
+ ParentPos<K, K> parentPos = stack[depth];
+
+ if ( child == null )
+ {
+ parentPos.pos = parentPos.page.getNbElems() - 1;
+ }
+ else
+ {
+ parentPos.page = child;
+ parentPos.pos = child.getNbElems() - 1;
+ }
+
+ parentPos.pos = AFTER_LAST;
+ }
+
+
+ /**
+ * Change the position in the current cursor before the first key
+ */
+ public void beforeFirst() throws IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ return;
+ }
+
+ Page<K, K> child = null;
+
+ for ( int i = 0; i < depth; i++ )
+ {
+ ParentPos<K, K> parentPos = stack[i];
+ parentPos.pos = 0;
+
+ if ( child != null )
+ {
+ parentPos.page = child;
+ }
+
+ child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( 0 );
+ }
+
+ // and leaf
+ ParentPos<K, K> parentPos = stack[depth];
+ parentPos.pos = BEFORE_FIRST;
+
+ if ( child != null )
+ {
+ parentPos.page = child;
+ }
+ }
+
+
+ /**
+ * Tells if the cursor can return a next element
+ *
+ * @return true if there are some more elements
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasNext() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ return false;
+ }
+
+ // Take the leaf and check if we have no mare keys
+ ParentPos<K, K> parentPos = stack[depth];
+
+ if ( parentPos.page == null )
+ {
+ // Empty BTree, get out
+ return false;
+ }
+
+ if ( parentPos.pos == AFTER_LAST )
+ {
+ return false;
+ }
+
+ if ( parentPos.pos == BEFORE_FIRST )
+ {
+ return true;
+ }
+
+ if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
+ {
+ // Not the last position, we have a next key
+ return true;
+ }
+ else
+ {
+ // Ok, here, we have reached the last key in the leaf. We have to go up and
+ // see if we have some remaining keys
+ int currentDepth = depth - 1;
+
+ while ( currentDepth >= 0 )
+ {
+ parentPos = stack[currentDepth];
+
+ if ( parentPos.pos < parentPos.page.getNbElems() )
+ {
+ // The parent has some remaining keys on the right, get out
+ return true;
+ }
+ else
+ {
+ currentDepth--;
+ }
+ }
+
+ // We are done, there are no more key left
+ return false;
+ }
+ }
+
+
+ /**
+ * Find the next key
+ *
+ * @return the found key
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public K next() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ throw new NoSuchElementException( "No Key is present" );
+ }
+
+ ParentPos<K, K> parentPos = stack[depth];
+
+ if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) )
+ {
+ // This is the end : no more keys
+ throw new NoSuchElementException( "No more keys present" );
+ }
+
+ if ( parentPos.pos == parentPos.page.getNbElems() )
+ {
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findNextParentPos();
+
+ // we also need to check for the type of page cause
+ // findNextParentPos will never return a null ParentPos
+ if ( ( parentPos == null ) || ( parentPos.page == null ) )
+ {
+ // This is the end : no more keys
+ throw new NoSuchElementException( "No more keys present" );
+ }
+ }
+
+ // Deal with the BeforeFirst case
+ if ( parentPos.pos == BEFORE_FIRST )
+ {
+ parentPos.pos++;
+ }
+ else
+ {
+ if ( parentPos.pos == parentPos.page.getNbElems() - 1 )
+ {
+ parentPos = findNextParentPos();
+
+ if ( ( parentPos == null ) || ( parentPos.page == null ) )
+ {
+ // This is the end : no more keys
+ throw new NoSuchElementException( "No more keys present" );
+ }
+ }
+ else
+ {
+ parentPos.pos++;
+ }
+ }
+
+ AbstractPage<K, K> leaf = ( AbstractPage<K, K> ) ( parentPos.page );
+
+ return leaf.getKey( parentPos.pos );
+ }
+
+
+ /**
+ * Get the next key.
+ */
+ public K nextKey() throws EndOfFileExceededException, IOException
+ {
+ return next();
+ }
+
+
+ /**
+ * Tells if the cursor can return a next key
+ *
+ * @return true if there are some more keys
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasNextKey() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ // This is the end : no more key
+ return false;
+ }
+
+ ParentPos<K, K> parentPos = stack[depth];
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more key
+ return false;
+ }
+
+ if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
+ {
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the next leaf
+ return hasNextParentPos();
+ }
+ else
+ {
+ return true;
+ }
+ }
+
+
+ /**
+ * Tells if the cursor can return a previous element
+ *
+ * @return true if there are some more elements
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasPrev() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ return false;
+ }
+
+ // Take the leaf and check if we have no mare keys
+ ParentPos<K, K> parentPos = stack[depth];
+
+ if ( parentPos.page == null )
+ {
+ // Empty BTree, get out
+ return false;
+ }
+
+ if ( parentPos.pos > 0 )
+ {
+ // get out, we have keys on the left
+ return true;
+ }
+ else
+ {
+ // Check that we are not before the first key
+ if ( parentPos.pos == BEFORE_FIRST )
+ {
+ return false;
+ }
+
+ if ( parentPos.pos == AFTER_LAST )
+ {
+ return true;
+ }
+
+ // Ok, here, we have reached the first key in the leaf. We have to go up and
+ // see if we have some remaining keys
+ int currentDepth = depth - 1;
+
+ while ( currentDepth >= 0 )
+ {
+ parentPos = stack[currentDepth];
+
+ if ( parentPos.pos > 0 )
+ {
+ // The parent has some remaining keys on the right, get out
+ return true;
+ }
+ else
+ {
+ currentDepth--;
+ }
+ }
+
+ return false;
+ }
+ }
+
+
+ /**
+ * Find the previous key
+ *
+ * @return the found key
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public K prev() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ throw new NoSuchElementException( "No more keys present" );
+ }
+
+ ParentPos<K, K> parentPos = stack[depth];
+
+ if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) )
+ {
+ // This is the end : no more keys
+ throw new NoSuchElementException( "No more keys present" );
+ }
+
+ // Deal with the AfterLast case
+ if ( parentPos.pos == AFTER_LAST )
+ {
+ parentPos.pos = parentPos.page.getNbElems() - 1;
+ }
+ else
+ {
+ if ( parentPos.pos == 0 )
+ {
+ parentPos = findPrevParentPos();
+
+ if ( ( parentPos == null ) || ( parentPos.page == null ) )
+ {
+ // This is the end : no more keys
+ throw new NoSuchElementException( "No more keys present" );
+ }
+ }
+ else
+ {
+ parentPos.pos--;
+ }
+ }
+
+ AbstractPage<K, K> leaf = ( AbstractPage<K, K> ) ( parentPos.page );
+
+ return leaf.getKey( parentPos.pos );
+ }
+
+
+ /**
+ * Get the previous key.
+ *
+ * @return the found key
+ * @throws EndOfFileExceededException
+ * @throws IOException
+ */
+ public K prevKey() throws EndOfFileExceededException, IOException
+ {
+ return prev();
+ }
+
+
+ /**
+ * Tells if the cursor can return a previous key
+ *
+ * @return true if there are some more keys
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasPrevKey() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ // This is the end : no more key
+ return false;
+ }
+
+ ParentPos<K, K> parentPos = stack[depth];
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more key
+ return false;
+ }
+
+ switch ( parentPos.pos )
+ {
+ case 0 :
+ // Beginning of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ return hasPrevParentPos();
+
+ case -1 :
+ // no previous key
+ return false;
+
+ default :
+ // we have a previous key
+ return true;
+ }
+ }
+
+
+ /**
+ * Tells if there is a next ParentPos
+ *
+ * @return the new ParentPos instance, or null if we have no following leaf
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ private boolean hasNextParentPos() throws EndOfFileExceededException, IOException
+ {
+ if ( depth == 0 )
+ {
+ // No need to go any further, there is only one leaf in the btree
+ return false;
+ }
+
+ int currentDepth = depth - 1;
+ Page<K, K> child = null;
+
+ // First, go up the tree until we find a Node which has some element on the right
+ while ( currentDepth >= 0 )
+ {
+ // We first go up the tree, until we reach a page whose current position
+ // is not the last one
+ ParentPos<K, K> parentPos = stack[currentDepth];
+
+ if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
+ {
+ // No more element on the right : go up
+ currentDepth--;
+ }
+ else
+ {
+ // We can pick the next element at this level
+ child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos + 1 );
+
+ // and go down the tree through the nodes
+ while ( currentDepth < depth - 1 )
+ {
+ currentDepth++;
+ child = ( ( AbstractPage<K, K> ) child ).getPage( 0 );
+ }
+
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+
+ /**
+ * Find the leaf containing the following elements.
+ *
+ * @return the new ParentPos instance, or null if we have no following leaf
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ private ParentPos<K, K> findNextParentPos() throws EndOfFileExceededException, IOException
+ {
+ if ( depth == 0 )
+ {
+ // No need to go any further, there is only one leaf in the btree
+ return null;
+ }
+
+ int currentDepth = depth - 1;
+ Page<K, K> child = null;
+
+ // First, go up the tree until we find a Node which has some element on the right
+ while ( currentDepth >= 0 )
+ {
+ // We first go up the tree, until we reach a page whose current position
+ // is not the last one
+ ParentPos<K, K> parentPos = stack[currentDepth];
+
+ if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
+ {
+ // No more element on the right : go up
+ currentDepth--;
+ }
+ else
+ {
+ // We can pick the next element at this level
+ parentPos.pos++;
+ child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
+
+ // and go down the tree through the nodes
+ while ( currentDepth < depth - 1 )
+ {
+ currentDepth++;
+ parentPos = stack[currentDepth];
+ parentPos.pos = 0;
+ parentPos.page = child;
+ child = ( ( AbstractPage<K, K> ) child ).getPage( 0 );
+ }
+
+ // and the leaf
+ parentPos = stack[depth];
+ parentPos.page = child;
+ parentPos.pos = 0;
+
+ return parentPos;
+ }
+ }
+
+ return null;
+ }
+
+
+ /**
+ * Find the leaf containing the previous elements.
+ *
+ * @return the new ParentPos instance, or null if we have no previous leaf
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ private ParentPos<K, K> findPrevParentPos() throws EndOfFileExceededException, IOException
+ {
+ if ( depth == 0 )
+ {
+ // No need to go any further, there is only one leaf in the btree
+ return null;
+ }
+
+ int currentDepth = depth - 1;
+ Page<K, K> child = null;
+
+ // First, go up the tree until we find a Node which has some element on the left
+ while ( currentDepth >= 0 )
+ {
+ // We first go up the tree, until we reach a page whose current position
+ // is not the last one
+ ParentPos<K, K> parentPos = stack[currentDepth];
+
+ if ( parentPos.pos == 0 )
+ {
+ // No more element on the right : go up
+ currentDepth--;
+ }
+ else
+ {
+ // We can pick the next element at this level
+ parentPos.pos--;
+ child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
+
+ // and go down the tree through the nodes
+ while ( currentDepth < depth - 1 )
+ {
+ currentDepth++;
+ parentPos = stack[currentDepth];
+ parentPos.pos = child.getNbElems();
+ parentPos.page = child;
+ child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.page.getNbElems() );
+ }
+
+ // and the leaf
+ parentPos = stack[depth];
+ parentPos.pos = child.getNbElems() - 1;
+ parentPos.page = child;
+
+ return parentPos;
+ }
+ }
+
+ return null;
+ }
+
+
+ /**
+ * Tells if there is a prev ParentPos
+ *
+ * @return the new ParentPos instance, or null if we have no previous leaf
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException
+ {
+ if ( depth == 0 )
+ {
+ // No need to go any further, there is only one leaf in the btree
+ return false;
+ }
+
+ int currentDepth = depth - 1;
+ Page<K, K> child = null;
+
+ // First, go up the tree until we find a Node which has some element on the right
+ while ( currentDepth >= 0 )
+ {
+ // We first go up the tree, until we reach a page whose current position
+ // is not the last one
+ ParentPos<K, K> parentPos = stack[currentDepth];
+
+ if ( parentPos.pos == 0 )
+ {
+ // No more element on the left : go up
+ currentDepth--;
+ }
+ else
+ {
+ // We can pick the previous element at this level
+ child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos - 1 );
+
+ // and go down the tree through the nodes
+ while ( currentDepth < depth - 1 )
+ {
+ currentDepth++;
+ child = ( ( AbstractPage<K, K> ) child ).getPage( child.getNbElems() );
+ }
+
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void close()
+ {
+ transaction.close();
+ }
+
+
+ /**
+ * Get the creation date
+ * @return The creation date for this cursor
+ */
+ public long getCreationDate()
+ {
+ return transaction.getCreationDate();
+ }
+
+
+ /**
+ * Get the current revision
+ *
+ * @return The revision this cursor is based on
+ */
+ public long getRevision()
+ {
+ return transaction.getRevision();
+ }
+
+
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "KeyCursor, 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/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java?rev=1597950&r1=1597949&r2=1597950&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 Wed May 28 09:22:24 2014
@@ -149,6 +149,18 @@ import org.apache.directory.mavibot.btre
/**
+ * Browses the keys of whole tree, and creates a Cursor on top of it.
+ *
+ * @param transaction The started transaction for this operation
+ * @param stack The stack of parents we go through to get to this page
+ * @return A Cursor to browse the keys
+ * @throws IOException If we have an error while trying to access the page
+ */
+ KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+ throws EndOfFileExceededException, IOException;
+
+
+ /**
* @return the revision
*/
long getRevision();
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java Wed May 28 09:22:24 2014
@@ -523,6 +523,11 @@ public class PersistedBTree<K, V> extend
BTreeHeader<K, V> btreeHeader = getBTreeHeader( getName() );
InsertResult<K, V> result = btreeHeader.getRootPage().insert( key, value, revision );
+ if ( result instanceof ExistsResult )
+ {
+ return result;
+ }
+
// Create a new BTreeHeader
BTreeHeader<K, V> newBtreeHeader = btreeHeader.copy();
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java Wed May 28 09:22:24 2014
@@ -26,7 +26,7 @@ import java.lang.reflect.Array;
import org.apache.directory.mavibot.btree.exception.DuplicateValueNotAllowedException;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
-
+import static org.apache.directory.mavibot.btree.BTreeTypeEnum.*;
/**
* A MVCC Leaf. It stores the keys and values. It does not have any children.
@@ -64,7 +64,10 @@ import org.apache.directory.mavibot.btre
PersistedLeaf( BTree<K, V> btree, long revision, int nbElems )
{
super( btree, revision, nbElems );
- values = ( ValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class, nbElems );
+ if( btree.getType() != BTreeTypeEnum.PERSISTED_SUB )
+ {
+ values = ( ValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class, nbElems );
+ }
}
@@ -76,12 +79,19 @@ import org.apache.directory.mavibot.btre
// Find the key into this leaf
int pos = findPos( key );
+ boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
+
if ( pos < 0 )
{
// We already have the key in the page : replace the value
// into a copy of this page, unless the page has already be copied
int index = -( pos + 1 );
+ if( isSubTree )
+ {
+ return ExistsResult.EXISTS;
+ }
+
// Replace the existing value in a copy of the current page
InsertResult<K, V> result = replaceElement( revision, key, value, index );
@@ -93,7 +103,16 @@ import org.apache.directory.mavibot.btre
{
// The current page is not full, it can contain the added element.
// We insert it into a copied page and return the result
- Page<K, V> modifiedPage = addElement( revision, key, value, pos );
+ Page<K, V> modifiedPage = null;
+
+ if ( isSubTree )
+ {
+ modifiedPage = addSubTreeElement( revision, key, pos );
+ }
+ else
+ {
+ modifiedPage = addElement( revision, key, value, pos );
+ }
InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
result.addCopiedPage( this );
@@ -104,7 +123,17 @@ import org.apache.directory.mavibot.btre
{
// The Page is already full : we split it and return the overflow element,
// after having created two pages.
- InsertResult<K, V> result = addAndSplit( revision, key, value, pos );
+ InsertResult<K, V> result = null;
+
+ if( isSubTree )
+ {
+ result = addAndSplitSubTree( revision, key, pos );
+ }
+ else
+ {
+ result = addAndSplit( revision, key, value, pos );
+ }
+
result.addCopiedPage( this );
return result;
@@ -143,7 +172,18 @@ import org.apache.directory.mavibot.btre
int index = -( pos + 1 );
- ValueHolder<V> valueHolder = values[index];
+ boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+
+ ValueHolder<V> valueHolder = null;
+
+ if( isNotSubTree )
+ {
+ valueHolder = values[index];
+ }
+ else // set value to null, just incase if a non-null value passed while deleting a key from from sub-btree
+ {
+ value = null;
+ }
if ( value == null )
{
@@ -265,8 +305,7 @@ import org.apache.directory.mavibot.btre
}
catch ( CloneNotSupportedException e )
{
- // TODO Auto-generated catch block
- e.printStackTrace();
+ throw new RuntimeException( e );
}
// The current page is added in the copied page list
@@ -292,6 +331,8 @@ import org.apache.directory.mavibot.btre
boolean isLeft, int pos )
throws EndOfFileExceededException, IOException
{
+ boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+
// Create the new page. It will contain N - 1 elements (the maximum number)
// as we merge two pages that contain N/2 elements minus the one we remove
PersistedLeaf<K, V> newLeaf = new PersistedLeaf<K, V>( btree, revision, btree.getPageSize() - 1 );
@@ -301,30 +342,48 @@ import org.apache.directory.mavibot.btre
// The sibling is on the left
// Copy all the elements from the sibling first
System.arraycopy( sibling.keys, 0, newLeaf.keys, 0, sibling.nbElems );
- System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
+ }
// Copy all the elements from the page up to the deletion position
System.arraycopy( keys, 0, newLeaf.keys, sibling.nbElems, pos );
- System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos );
+ }
// And copy the remaining elements after the deletion point
System.arraycopy( keys, pos + 1, newLeaf.keys, sibling.nbElems + pos, nbElems - pos - 1 );
- System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
+ }
}
else
{
// The sibling is on the right
// Copy all the elements from the page up to the deletion position
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
- System.arraycopy( values, 0, newLeaf.values, 0, pos );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
+ }
// Then copy the remaining elements after the deletion point
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, nbElems - pos - 1 );
- System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - pos - 1 );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - pos - 1 );
+ }
// And copy all the elements from the sibling
System.arraycopy( sibling.keys, 0, newLeaf.keys, nbElems - 1, sibling.nbElems );
- System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
+ }
}
// And create the result
@@ -352,9 +411,15 @@ import org.apache.directory.mavibot.btre
int pos )
throws IOException
{
+ boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[sibling.getNbElems() - 1].getKey();
- ValueHolder<V> siblingValue = sibling.values[sibling.getNbElems() - 1];
+ ValueHolder<V> siblingValue = null;
+ if ( isNotSubTree )
+ {
+ siblingValue = sibling.values[sibling.getNbElems() - 1];
+ }
// Create the new sibling, with one less element at the end
PersistedLeaf<K, V> newSibling = ( PersistedLeaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
@@ -365,15 +430,24 @@ import org.apache.directory.mavibot.btre
// Insert the borrowed element
newLeaf.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey );
- newLeaf.values[0] = siblingValue;
+ if ( isNotSubTree )
+ {
+ newLeaf.values[0] = siblingValue;
+ }
// Copy the keys and the values up to the insertion position,
System.arraycopy( keys, 0, newLeaf.keys, 1, pos );
- System.arraycopy( values, 0, newLeaf.values, 1, pos );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, 0, newLeaf.values, 1, pos );
+ }
// And copy the remaining elements
System.arraycopy( keys, pos + 1, newLeaf.keys, pos + 1, keys.length - pos - 1 );
- System.arraycopy( values, pos + 1, newLeaf.values, pos + 1, values.length - pos - 1 );
+ if( isNotSubTree )
+ {
+ System.arraycopy( values, pos + 1, newLeaf.values, pos + 1, values.length - pos - 1 );
+ }
DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf, newSibling, removedElement );
@@ -400,33 +474,51 @@ import org.apache.directory.mavibot.btre
int pos )
throws IOException
{
+ boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[0].getKey();
- ValueHolder<V> siblingHolder = sibling.values[0];
+ ValueHolder<V> siblingHolder = null;
+ if ( isNotSubTree )
+ {
+ siblingHolder = sibling.values[0];
+ }
// Create the new sibling
PersistedLeaf<K, V> newSibling = new PersistedLeaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
// Copy the keys and the values from 1 to N in the new sibling
System.arraycopy( sibling.keys, 1, newSibling.keys, 0, sibling.nbElems - 1 );
- System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
-
+ if ( isNotSubTree )
+ {
+ System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
+ }
+
// Create the new page and add the new element at the end
// First copy the current page, with the same size
PersistedLeaf<K, V> newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems );
// Insert the borrowed element at the end
newLeaf.keys[nbElems - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey );
- newLeaf.values[nbElems - 1] = siblingHolder;
-
+ if ( isNotSubTree )
+ {
+ newLeaf.values[nbElems - 1] = siblingHolder;
+ }
+
// Copy the keys and the values up to the deletion position,
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
- System.arraycopy( values, 0, newLeaf.values, 0, pos );
-
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
+ }
+
// And copy the remaining elements
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
- System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
-
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
+ }
+
DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newLeaf, newSibling, removedElement );
// Add the copied pages to the list
@@ -448,6 +540,8 @@ import org.apache.directory.mavibot.btre
private void copyAfterRemovingElement( boolean keyRemoved, V removedValue, PersistedLeaf<K, V> newLeaf, int pos )
throws IOException
{
+ boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+
if ( keyRemoved )
{
// Deal with the special case of a page with only one element by skipping
@@ -459,11 +553,17 @@ import org.apache.directory.mavibot.btre
// Copy the keys and the values up to the insertion position
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
- System.arraycopy( values, 0, newLeaf.values, 0, pos );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
+ }
// And copy the elements after the position
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
- System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
+ if ( isNotSubTree )
+ {
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
+ }
}
else
// one of the many values of the same key was removed, no change in the number of keys
@@ -797,6 +897,11 @@ import org.apache.directory.mavibot.btre
throw new DuplicateValueNotAllowedException( "Duplicate values are not allowed" );
}
+ if ( valueExists )
+ {
+ return ExistsResult.EXISTS;
+ }
+
if ( this.revision != revision )
{
// The page hasn't been modified yet, we need to copy it first
@@ -814,11 +919,12 @@ import org.apache.directory.mavibot.btre
}
else
{
+ // this block should be deleted after fixing MAVIBOT-39
// As strange as it sounds, we need to remove the value to reinject it.
// There are cases where the value retrieval just use one part of the
// value only (typically for LDAP Entries, where we use the DN)
- replacedValue = valueHolder.remove( value );
- valueHolder.add( value );
+ //replacedValue = valueHolder.remove( value );
+ //valueHolder.add( value );
}
// Create the result
@@ -967,6 +1073,11 @@ import org.apache.directory.mavibot.btre
*/
public K getLeftMostKey()
{
+ if( keys.length == 0 )
+ {
+ System.out.println("");
+ }
+
return keys[0].getKey();
}
@@ -1091,6 +1202,134 @@ import org.apache.directory.mavibot.btre
/**
+ * same as {@link #addElement(long, Object, Object, int)} except the values are not copied.
+ * This method is only used while inserting an element into a sub-BTree.
+ */
+ private Page<K, V> addSubTreeElement( long revision, K key, int pos )
+ {
+ // First copy the current page, but add one element in the copied page
+ PersistedLeaf<K, V> newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems + 1 );
+
+ // Deal with the special case of an empty page
+ if ( nbElems == 0 )
+ {
+ newLeaf.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
+ }
+ else
+ {
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
+
+ // Add the new element
+ newLeaf.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length - pos );
+ }
+
+ return newLeaf;
+ }
+
+
+ /**
+ * same as {@link #addAndSplit(long, Object, Object, int)} except the values are not copied.
+ * This method is only used while inserting an element into a sub-BTree.
+ */
+ private InsertResult<K, V> addAndSplitSubTree( long revision, K key, int pos )
+ {
+ int middle = btree.getPageSize() >> 1;
+ PersistedLeaf<K, V> leftLeaf = null;
+ PersistedLeaf<K, V> rightLeaf = null;
+
+ // Determinate where to store the new value
+ if ( pos <= middle )
+ {
+ // The left page will contain the new value
+ leftLeaf = new PersistedLeaf<K, V>( btree, revision, middle + 1 );
+
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, leftLeaf.keys, 0, pos );
+
+ // Add the new element
+ leftLeaf.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, leftLeaf.keys, pos + 1, middle - pos );
+
+ // Now, create the right page
+ rightLeaf = new PersistedLeaf<K, V>( btree, revision, middle );
+
+ // Copy the keys and the values in the right page
+ System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
+ }
+ else
+ {
+ // Create the left page
+ leftLeaf = new PersistedLeaf<K, V>( btree, revision, middle );
+
+ // Copy all the element into the left page
+ System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
+
+ // Now, create the right page
+ rightLeaf = new PersistedLeaf<K, V>( btree, revision, middle + 1 );
+
+ int rightPos = pos - middle;
+
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, middle, rightLeaf.keys, 0, rightPos );
+
+ // Add the new element
+ rightLeaf.keys[rightPos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems - pos );
+ }
+
+ // Get the pivot
+ K pivot = rightLeaf.keys[0].getKey();
+
+ if ( pivot == null )
+ {
+ pivot = rightLeaf.keys[0].getKey();
+ }
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
+
+ return result;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+ {
+ int pos = 0;
+ KeyCursor<K> cursor = null;
+
+ if ( nbElems == 0 )
+ {
+ // The tree is empty, it's the root, we have nothing to return
+ stack[depth] = new ParentPos<K, K>( null, -1 );
+
+ return new KeyCursor<K>( transaction, stack, depth );
+ }
+ else
+ {
+ // Start at the beginning of the page
+ ParentPos<K, K> parentPos = new ParentPos( this, pos );
+
+ stack[depth] = parentPos;
+
+ cursor = new KeyCursor<K>( transaction, stack, depth );
+ }
+
+ return cursor;
+ }
+
+
+ /**
* {@inheritDoc}
*/
public String dumpPage( String tabs )
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java Wed May 28 09:22:24 2014
@@ -140,7 +140,11 @@ import java.util.List;
// Ok, now, we have injected the <K, V> tuple down the tree. Let's check
// the result to see if we have to split the current page
- if ( result instanceof ModifyResult )
+ if ( result instanceof ExistsResult )
+ {
+ return result;
+ }
+ else if ( result instanceof ModifyResult )
{
// The child has been modified.
return replaceChild( revision, ( ModifyResult<K, V> ) result, pos );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java Wed May 28 09:22:24 2014
@@ -1042,37 +1042,42 @@ public class RecordManager extends Abstr
int[] keyLengths = new int[nbElems];
int[] valueLengths = new int[nbElems];
+ boolean isNotSubTree = ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB );
+
// Read each key and value
for ( int i = 0; i < nbElems; i++ )
{
- // Read the number of values
- int nbValues = byteBuffer.getInt();
- PersistedValueHolder<V> valueHolder = null;
-
- if ( nbValues < 0 )
- {
- // This is a sub-btree
- byte[] btreeOffsetBytes = new byte[LONG_SIZE];
- byteBuffer.get( btreeOffsetBytes );
-
- // Create the valueHolder. As the number of values is negative, we have to switch
- // to a positive value but as we start at -1 for 0 value, add 1.
- valueHolder = new PersistedValueHolder<V>( btree, 1 - nbValues, btreeOffsetBytes );
- }
- else
+ if ( isNotSubTree )
{
- // This is an array
- // Read the value's array length
- valueLengths[i] = byteBuffer.getInt();
-
- // This is an Array of values, read the byte[] associated with it
- byte[] arrayBytes = new byte[valueLengths[i]];
- byteBuffer.get( arrayBytes );
- valueHolder = new PersistedValueHolder<V>( btree, nbValues, arrayBytes );
+ // Read the number of values
+ int nbValues = byteBuffer.getInt();
+ PersistedValueHolder<V> valueHolder = null;
+
+ if ( nbValues < 0 )
+ {
+ // This is a sub-btree
+ byte[] btreeOffsetBytes = new byte[LONG_SIZE];
+ byteBuffer.get( btreeOffsetBytes );
+
+ // Create the valueHolder. As the number of values is negative, we have to switch
+ // to a positive value but as we start at -1 for 0 value, add 1.
+ valueHolder = new PersistedValueHolder<V>( btree, 1 - nbValues, btreeOffsetBytes );
+ }
+ else
+ {
+ // This is an array
+ // Read the value's array length
+ valueLengths[i] = byteBuffer.getInt();
+
+ // This is an Array of values, read the byte[] associated with it
+ byte[] arrayBytes = new byte[valueLengths[i]];
+ byteBuffer.get( arrayBytes );
+ valueHolder = new PersistedValueHolder<V>( btree, nbValues, arrayBytes );
+ }
+
+ BTreeFactory.setValue( btree, leaf, i, valueHolder );
}
- BTreeFactory.setValue( btree, leaf, i, valueHolder );
-
keyLengths[i] = byteBuffer.getInt();
byte[] data = new byte[keyLengths[i]];
byteBuffer.get( data );
@@ -1498,6 +1503,8 @@ public class RecordManager extends Abstr
{
int nbElems = page.getNbElems();
+ boolean isNotSubTree = ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB );
+
if ( nbElems == 0 )
{
return serializeRootPage( revision );
@@ -1549,7 +1556,11 @@ public class RecordManager extends Abstr
}
else
{
- dataSize += serializeLeafValue( ( PersistedLeaf<K, V> ) page, pos, serializedData );
+ if ( isNotSubTree )
+ {
+ dataSize += serializeLeafValue( ( PersistedLeaf<K, V> ) page, pos, serializedData );
+ }
+
dataSize += serializeLeafKey( ( PersistedLeaf<K, V> ) page, pos, serializedData );
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java Wed May 28 09:22:24 2014
@@ -35,7 +35,7 @@ import org.apache.directory.mavibot.btre
/* No qualifier */class ValueBTreeCursor<V> implements ValueCursor<V>
{
/** Store the current position in the array or in the BTree */
- private TupleCursor<V, V> cursor;
+ private KeyCursor<V> cursor;
/** The Value sub-btree */
private BTree<V, V> valueBtree;
@@ -53,7 +53,7 @@ import org.apache.directory.mavibot.btre
{
if ( valueBtree != null )
{
- cursor = valueBtree.browse();
+ cursor = valueBtree.browseKeys();
}
}
catch ( IOException e )
@@ -106,7 +106,7 @@ import org.apache.directory.mavibot.btre
{
try
{
- return cursor.next().getKey();
+ return cursor.next();
}
catch ( EndOfFileExceededException e )
{
@@ -198,7 +198,7 @@ import org.apache.directory.mavibot.btre
{
try
{
- return cursor.prev().getKey();
+ return cursor.prev();
}
catch ( EndOfFileExceededException e )
{
Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java?rev=1597950&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java Wed May 28 09:22:24 2014
@@ -0,0 +1,129 @@
+/*
+ * 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 static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.UUID;
+
+import org.apache.commons.io.FileUtils;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+/**
+ * Tests for KeyCursor of a persisted sub-Btree.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class PersistedSubBtreeKeyCursorTest
+{
+ private BTree<Integer, Integer> btree = null;
+
+ private RecordManager recordManager = null;
+
+ @Rule
+ public TemporaryFolder tempFolder = new TemporaryFolder();
+
+ private File dataDir = null;
+
+
+ @Before
+ public void createBTree()
+ {
+ dataDir = tempFolder.newFolder( UUID.randomUUID().toString() );
+
+ // Now, try to reload the file back
+ recordManager = new RecordManager( dataDir.getAbsolutePath() );
+
+ try
+ {
+ PersistedBTreeConfiguration<Integer, Integer> configuration = new PersistedBTreeConfiguration<Integer, Integer>();
+ configuration.setAllowDuplicates( false );
+ configuration.setKeySerializer( IntSerializer.INSTANCE );
+ configuration.setValueSerializer( IntSerializer.INSTANCE );
+ configuration.setName( "sub-btree" );
+ configuration.setBtreeType( BTreeTypeEnum.PERSISTED_SUB );
+
+ btree = BTreeFactory.createPersistedBTree( configuration );
+
+ recordManager.manage( btree, RecordManager.INTERNAL_BTREE );
+ }
+ catch ( Exception e )
+ {
+ throw new RuntimeException( e );
+ }
+ }
+
+
+ @After
+ public void cleanup() throws IOException
+ {
+ dataDir = new File( System.getProperty( "java.io.tmpdir" ) + "/recordman" );
+
+ btree.close();
+
+ if ( dataDir.exists() )
+ {
+ FileUtils.deleteDirectory( dataDir );
+ }
+
+ recordManager.close();
+ assertTrue( recordManager.isContextOk() );
+ }
+
+ @Test
+ public void testBrowseKeys() throws Exception
+ {
+ for( int i=0; i< 10; i++ )
+ {
+ // only the keys are stored, values are ignored
+ btree.insert( i, i );
+ }
+
+ KeyCursor<Integer> cursor = btree.browseKeys();
+
+ for( int i=0; i< 10; i++ )
+ {
+ assertTrue( cursor.hasNext() );
+ assertEquals( String.valueOf( i ), String.valueOf( cursor.next() ) );
+ }
+
+ assertFalse( cursor.hasNext() );
+
+ cursor.afterLast();
+
+ for( int i=9; i>= 0; i-- )
+ {
+ assertTrue( cursor.hasPrev() );
+ assertEquals( String.valueOf( i ), String.valueOf( cursor.prev() ) );
+ }
+
+ assertFalse( cursor.hasPrev() );
+ cursor.close();
+ }
+}