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 2013/08/04 11:22:58 UTC
svn commit: r1510115 [3/13] - in /directory/mavibot/trunk: ./ mavibot/
mavibot/src/main/java/org/apache/directory/
mavibot/src/main/java/org/apache/directory/mavibot/
mavibot/src/main/java/org/apache/directory/mavibot/btree/
mavibot/src/main/java/org/a...
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,361 @@
+/*
+ * 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.util.concurrent.atomic.AtomicLong;
+
+
+/**
+ * Store in memory the information associated with a BTree. <br>
+ * A BTree Header on disk contains the following elements :
+ * <pre>
+ * +--------------------+-------------+
+ * | revision | 8 bytes |
+ * +--------------------+-------------+
+ * | nbElems | 8 bytes |
+ * +--------------------+-------------+
+ * | rootPageOffset | 8 bytes |
+ * +--------------------+-------------+
+ * | nextBtreeHeader | 8 bytes |
+ * +--------------------+-------------+
+ * | pageSize | 4 bytes |
+ * +--------------------+-------------+
+ * | name | 4 bytes + N |
+ * +--------------------+-------------+
+ * | keySerializeFQCN | 4 bytes + N |
+ * +--------------------+-------------+
+ * | valueSerializeFQCN | 4 bytes + N |
+ * +--------------------+-------------+
+ * </pre>
+ * Each BtreeHeader will be written starting on a new page.
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+/* No qualifier*/class BTreeHeader
+{
+ /** The current revision */
+ private AtomicLong revision = new AtomicLong( 0L );
+
+ /** The number of elements in this BTree */
+ private AtomicLong nbElems = new AtomicLong( 0L );
+
+ /** The offset of the BTree RootPage */
+ private long rootPageOffset;
+
+ /** The offset of the next BTree */
+ private long nextBTreeOffset;
+
+ /** The number of elements in a page for this BTree */
+ private int pageSize;
+
+ /** The BTree name */
+ private String name;
+
+ /** The FQCN of the Key serializer */
+ private String keySerializerFQCN;
+
+ /** The FQCN of the Value serializer */
+ private String valueSerializerFQCN;
+
+ // Those are data which aren't serialized : they are in memory only */
+ /** The position in the file */
+ private long btreeOffset;
+
+ /** The existing versions */
+ private long[] versions;
+
+ private int allowDuplicates = 0;
+
+ /**
+ * Creates a BTreeHeader instance
+ */
+ public BTreeHeader()
+ {
+ }
+
+
+ /**
+ * @return the name
+ */
+ public String getName()
+ {
+ return name;
+ }
+
+
+ /**
+ * @param name the name to set
+ */
+ public void setName( String name )
+ {
+ this.name = name;
+ }
+
+
+ /**
+ * @return the versions
+ */
+ public long[] getVersions()
+ {
+ return versions;
+ }
+
+
+ /**
+ * @param versions the versions to set
+ */
+ /* No qualifier*/void setVersions( long[] versions )
+ {
+ this.versions = versions;
+ }
+
+
+ /**
+ * @return the btreeOffset
+ */
+ /* No qualifier*/long getBTreeOffset()
+ {
+ return btreeOffset;
+ }
+
+
+ /**
+ * @param btreeOffset the btreeOffset to set
+ */
+ /* No qualifier*/void setBTreeOffset( long btreeOffset )
+ {
+ this.btreeOffset = btreeOffset;
+ }
+
+
+ /**
+ * @return the rootPageOffset
+ */
+ /* No qualifier*/long getRootPageOffset()
+ {
+ return rootPageOffset;
+ }
+
+
+ /**
+ * @param rootPageOffset the rootPageOffset to set
+ */
+ /* No qualifier*/void setRootPageOffset( long rootPageOffset )
+ {
+ this.rootPageOffset = rootPageOffset;
+ }
+
+
+ /**
+ * @return the revision
+ */
+ public long getRevision()
+ {
+ return revision.get();
+ }
+
+
+ /**
+ * @param revision the revision to set
+ */
+ /* No qualifier*/void setRevision( long revision )
+ {
+ this.revision.set( revision );
+ }
+
+
+ /**
+ * Increment the revision
+ *
+ * @return the new revision
+ */
+ /* No qualifier*/long incrementRevision()
+ {
+ return revision.incrementAndGet();
+ }
+
+
+ /**
+ * @return the nbElems
+ */
+ public long getNbElems()
+ {
+ return nbElems.get();
+ }
+
+
+ /**
+ * Increment the number of elements
+ */
+ /* No qualifier*/void incrementNbElems()
+ {
+ nbElems.incrementAndGet();
+ }
+
+
+ /**
+ * Decrement the number of elements
+ */
+ /* No qualifier*/void decrementNbElems()
+ {
+ nbElems.decrementAndGet();
+ }
+
+
+ /**
+ * @param nbElems the nbElems to set
+ */
+ public void setNbElems( long nbElems )
+ {
+ this.nbElems.set( nbElems );
+ }
+
+
+ /**
+ * @return the nextBTreeOffset
+ */
+ /* No qualifier*/long getNextBTreeOffset()
+ {
+ return nextBTreeOffset;
+ }
+
+
+ /**
+ * @param nextBtreeOffset the nextBtreeOffset to set
+ */
+ /* No qualifier*/void setNextBTreeOffset( long nextBTreeOffset )
+ {
+ this.nextBTreeOffset = nextBTreeOffset;
+ }
+
+
+ /**
+ * @return the pageSize
+ */
+ public int getPageSize()
+ {
+ return pageSize;
+ }
+
+
+ /**
+ * @param pageSize the pageSize to set
+ */
+ public void setPageSize( int pageSize )
+ {
+ this.pageSize = pageSize;
+ }
+
+
+ /**
+ * @return the keySerializerFQCN
+ */
+ /* No qualifier*/String getKeySerializerFQCN()
+ {
+ return keySerializerFQCN;
+ }
+
+
+ /**
+ * @param keySerializerFQCN the keySerializerFQCN to set
+ */
+ /* No qualifier*/void setKeySerializerFQCN( String keySerializerFQCN )
+ {
+ this.keySerializerFQCN = keySerializerFQCN;
+ }
+
+
+ /**
+ * @return the valueSerializerFQCN
+ */
+ /* No qualifier*/String getValueSerializerFQCN()
+ {
+ return valueSerializerFQCN;
+ }
+
+
+ /**
+ * @param valueSerializerFQCN the valueSerializerFQCN to set
+ */
+ /* No qualifier*/void setValueSerializerFQCN( String valueSerializerFQCN )
+ {
+ this.valueSerializerFQCN = valueSerializerFQCN;
+ }
+
+
+ /* No qualifier*/boolean isAllowDuplicates()
+ {
+ return ( allowDuplicates == 1 );
+ }
+
+
+ /* No qualifier*/void setAllowDuplicates( boolean allowDuplicates )
+ {
+ this.allowDuplicates = ( allowDuplicates ? 1 : 0 );
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "Btree '" ).append( name ).append( "'" );
+ sb.append( ", revision[" ).append( revision ).append( "]" );
+ sb.append( ", btreeOffset[" ).append( btreeOffset ).append( "]" );
+ sb.append( ", rootPageOffset[" ).append( rootPageOffset ).append( "]" );
+ sb.append( ", nextBTree[" ).append( nextBTreeOffset ).append( "]" );
+ sb.append( ", nbElems[" ).append( nbElems ).append( "]" );
+ sb.append( ", pageSize[" ).append( pageSize ).append( "]" );
+ sb.append( ", hasDuplicates[" ).append( isAllowDuplicates() ).append( "]" );
+ sb.append( "{\n" );
+ sb.append( " Key serializer : " ).append( keySerializerFQCN ).append( "\n" );
+ sb.append( " Value serializer : " ).append( valueSerializerFQCN ).append( "\n" );
+ sb.append( "}\n" );
+
+ if ( ( versions != null ) && ( versions.length != 0 ) )
+ {
+ sb.append( "Versions : \n" );
+ sb.append( "{\n" );
+
+ boolean isFirst = true;
+
+ for ( long version : versions )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ",\n" );
+ }
+
+ sb.append( " " ).append( version );
+ }
+
+ sb.append( "}\n" );
+ }
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,43 @@
+/*
+ * 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;
+
+
+/**
+ * An enum to describe the BTree type. We have three possible type :
+ * <ul>
+ * <li>IN_MEMORY : the BTree will remain in memory, and won't be persisted on disk</li>
+ * <li>PERSISTENT : the BTree is in memory, but will be persisted on disk</li>
+ * <li>MANAGED : the BTree is managed by a RecordManager, and some pages may
+ * be swapped out from memory on demand</li>
+ * </ul>
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public enum BTreeTypeEnum
+{
+ /** Pure in-memory BTree, not persisted on disk */
+ IN_MEMORY,
+
+ /** In-memory BTree but persisted on disk */
+ PERSISTENT,
+
+ /** A BTree associated with a RecordManager */
+ MANAGED
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromLeftResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromLeftResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromLeftResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromLeftResult.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,81 @@
+/*
+ * 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.util.List;
+
+
+/**
+ * The result of a delete operation, when the child has not been merged, and when
+ * we have borrowed an element from the left sibling. It contains the
+ * reference to the modified page, and the removed element.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+/* No qualifier */class BorrowedFromLeftResult<K, V> extends AbstractBorrowedFromSiblingResult<K, V>
+{
+ /**
+ * The default constructor for BorrowedFromLeftResult.
+ *
+ * @param modifiedPage The modified page
+ * @param modifiedSibling The modified sibling
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */BorrowedFromLeftResult( Page<K, V> modifiedPage, Page<K, V> modifiedSibling,
+ Tuple<K, V> removedElement )
+ {
+ super( modifiedPage, modifiedSibling, removedElement, AbstractBorrowedFromSiblingResult.SiblingPosition.LEFT );
+ }
+
+
+ /**
+ * A constructor for BorrowedFromLeftResult which takes a list of copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param modifiedSibling The modified sibling
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */BorrowedFromLeftResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Page<K, V> modifiedSibling,
+ Tuple<K, V> removedElement )
+ {
+ super( copiedPages, modifiedPage, modifiedSibling, removedElement,
+ AbstractBorrowedFromSiblingResult.SiblingPosition.LEFT );
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "Borrowed from left" );
+ sb.append( super.toString() );
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromRightResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromRightResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromRightResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromRightResult.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,79 @@
+/*
+ * 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.util.List;
+
+
+/**
+ * The result of a delete operation, when the child has not been merged. It contains the
+ * reference to the modified page, and the removed element.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+/* No qualifier */class BorrowedFromRightResult<K, V> extends AbstractBorrowedFromSiblingResult<K, V>
+{
+ /**
+ * The default constructor for BorrowedFromRightResult.
+ *
+ * @param modifiedPage The modified page
+ * @param modifiedSibling The modified sibling
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */BorrowedFromRightResult( Page<K, V> modifiedPage, Page<K, V> modifiedSibling,
+ Tuple<K, V> removedElement )
+ {
+ super( modifiedPage, modifiedSibling, removedElement, AbstractBorrowedFromSiblingResult.SiblingPosition.RIGHT );
+ }
+
+
+ /**
+ * A constructor for BorrowedFromRightResult which takes a list of copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param modifiedSibling The modified sibling
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */BorrowedFromRightResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Page<K, V> modifiedSibling, Tuple<K, V> removedElement )
+ {
+ super( copiedPages, modifiedPage, modifiedSibling, removedElement,
+ AbstractBorrowedFromSiblingResult.SiblingPosition.RIGHT );
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "Borrowed from right" );
+ sb.append( super.toString() );
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromSiblingResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromSiblingResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromSiblingResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromSiblingResult.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,53 @@
+/*
+ * 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 delete operation, when we have borrowed some element from a sibling.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+interface BorrowedFromSiblingResult<K, V> extends DeleteResult<K, V>
+{
+ /**
+ * @return the modifiedSibling
+ */
+ Page<K, V> getModifiedSibling();
+
+
+ /**
+ * Tells if the sibling is on the left
+ *
+ * @return True if the sibling is on the left
+ */
+ boolean isFromLeft();
+
+
+ /**
+ * Tells if the sibling is on the right
+ *
+ * @return True if the sibling is on the right
+ */
+ boolean isFromRight();
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,581 @@
+/*
+ * 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.LinkedList;
+import java.util.NoSuchElementException;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+import static org.apache.directory.mavibot.btree.InternalUtil.*;
+
+/**
+ * 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>
+ *
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ */
+public class Cursor<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 LinkedList<ParentPos<K, V>> stack;
+
+ /** The BTree we are walking */
+ private BTree<K, V> btree;
+
+ private boolean allowDuplicates;
+
+ /** a copy of the stack given at the time of initializing the cursor. This is used for moving the cursor to start position */
+ private LinkedList<ParentPos<K, V>> _initialStack;
+
+ /**
+ * 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
+ */
+ /* No qualifier */Cursor( BTree<K, V> btree, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ {
+ this.transaction = transaction;
+ this.stack = stack;
+ this.btree = btree;
+ this.allowDuplicates = btree.isAllowDuplicates();
+
+ _initialStack = new LinkedList<ParentPos<K,V>>();
+
+ cloneStack( stack, _initialStack );
+ }
+
+
+ /**
+ * Find the next key/value
+ *
+ * @return A Tuple containing the found key and value
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public Tuple<K, V> next() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.getFirst();
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples 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.page == null || ( parentPos.page instanceof Node ) )
+ {
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
+ }
+ }
+
+ // can happen if next() is called after prev()
+ if ( parentPos.pos < 0 )
+ {
+ parentPos.pos = 0;
+ }
+
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+ tuple.setKey( leaf.keys[parentPos.pos] );
+
+ if( allowDuplicates )
+ {
+ setDupsContainer( parentPos, btree );
+
+ // can happen if next() is called after prev()
+ if ( parentPos.dupPos < 0 )
+ {
+ parentPos.dupPos = 0;
+ }
+
+ tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
+ parentPos.dupPos++;
+
+ if( parentPos.dupsContainer.getNbElems() == parentPos.dupPos )
+ {
+ parentPos.pos++;
+ changeNextDupsContainer( parentPos, btree );
+ }
+ }
+ else
+ {
+ tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
+ parentPos.pos++;
+ }
+
+ return tuple;
+ }
+
+
+ /**
+ * 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, V> findNextParentPos() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> lastParentPos = null;
+
+ while ( true )
+ {
+ // We first go up the tree, until we reach a page whose current position
+ // is not the last one
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos == null )
+ {
+ stack.push( lastParentPos );
+ return lastParentPos;
+ }
+
+ if ( parentPos.pos == parentPos.page.getNbElems() )
+ {
+ lastParentPos = stack.pop();
+ continue;
+ }
+ else
+ {
+ // Then we go down the tree until we find a leaf which position is not the last one.
+ int newPos = ++parentPos.pos;
+ ParentPos<K, V> newParentPos = parentPos;
+
+ while ( newParentPos.page instanceof Node )
+ {
+ Node<K, V> node = ( Node<K, V> ) newParentPos.page;
+
+ newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), 0 );
+
+ stack.push( newParentPos );
+
+ newPos = 0;
+ }
+
+ if( allowDuplicates )
+ {
+ changeNextDupsContainer( newParentPos, btree );
+ }
+
+ return newParentPos;
+ }
+ }
+ }
+
+
+ /**
+ * 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, V> findPreviousParentPos() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> lastParentPos = null;
+
+ while ( true )
+ {
+ // We first go up the tree, until we reach a page which current position
+ // is not the first one
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos == null )
+ {
+ stack.push( lastParentPos );
+ return lastParentPos;
+ }
+
+ if ( parentPos.pos == 0 )
+ {
+ lastParentPos = stack.pop();
+ continue;
+ }
+ else
+ {
+ // Then we go down the tree until we find a leaf which position is not the first one.
+ int newPos = --parentPos.pos;
+ ParentPos<K, V> newParentPos = parentPos;
+
+ while ( newParentPos.page instanceof Node )
+ {
+ Node<K, V> node = ( Node<K, V> ) newParentPos.page;
+
+ newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), node.children[newPos]
+ .getValue( btree ).getNbElems() );
+
+ stack.push( newParentPos );
+
+ newPos = node.getNbElems();
+ }
+
+ if( allowDuplicates )
+ {
+ changePrevDupsContainer( newParentPos, btree );
+ }
+
+ return newParentPos;
+ }
+ }
+ }
+
+
+ /**
+ * Find the previous key/value
+ *
+ * @return A Tuple containing the found key and value
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public Tuple<K, V> prev() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
+ }
+
+ if ( parentPos.pos == 0 && parentPos.dupPos == 0 )
+ {
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findPreviousParentPos();
+
+ // we also need to check for the type of page cause
+ // findPrevParentPos will never return a null ParentPos
+ if ( parentPos.page == null || ( parentPos.page instanceof Node ) )
+ {
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
+ }
+ }
+
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+
+ if( allowDuplicates )
+ {
+ setDupsContainer( parentPos, btree );
+
+ // can happen if prev() was called after next()
+ if( parentPos.pos == parentPos.page.getNbElems() )
+ {
+ parentPos.pos--;
+ }
+
+ if( parentPos.dupPos == parentPos.dupsContainer.getNbElems() )
+ {
+ parentPos.dupPos--;
+ }
+ else if( parentPos.dupPos == 0 )
+ {
+ changePrevDupsContainer( parentPos, btree );
+ parentPos.pos--;
+ parentPos.dupPos--;
+ }
+ else
+ {
+ parentPos.dupPos--;
+ }
+
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
+ }
+ else
+ {
+ parentPos.pos--;
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
+ }
+
+ return tuple;
+ }
+
+
+ /**
+ * 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
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
+ {
+ return false;
+ }
+
+ for( ParentPos<K, V> p : stack )
+ {
+ if( allowDuplicates && ( p.page instanceof Leaf ) )
+ {
+ if ( ( p.dupPos != p.dupsContainer.getNbElems() )
+ && ( p.pos != p.page.getNbElems() ) )
+ {
+ return true;
+ }
+ }
+ else if ( p.pos != p.page.getNbElems() )
+ {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+
+ /**
+ * 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
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
+ {
+ return false;
+ }
+
+ for( ParentPos<K, V> p : stack )
+ {
+ if( allowDuplicates && ( p.page instanceof Leaf ) )
+ {
+ if( ( p.dupPos != 0 )
+ || ( p.pos != 0 ) )
+ {
+ return true;
+ }
+ }
+ else if ( p.pos != 0 )
+ {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+
+ /**
+ * Closes the cursor, thus releases the associated transaction
+ */
+ public void close()
+ {
+ transaction.close();
+ }
+
+
+ /**
+ * @return The revision this cursor is based on
+ */
+ public long getRevision()
+ {
+ return transaction.getRevision();
+ }
+
+
+ /**
+ * @return The creation date for this cursor
+ */
+ public long getCreationDate()
+ {
+ return transaction.getCreationDate();
+ }
+
+
+ /**
+ * Moves the cursor to the next non-duplicate key.
+
+ * If the BTree contains
+ *
+ * <ul>
+ * <li><1,0></li>
+ * <li><1,1></li>
+ * <li><2,0></li>
+ * <li><2,1></li>
+ * </ul>
+ *
+ * and cursor is present at <1,0> then the cursor will move to <2,0>
+ *
+ * @throws EndOfFileExceededException
+ * @throws IOException
+ */
+ public void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.getFirst();
+
+ if ( parentPos.page == null )
+ {
+ return;
+ }
+
+ 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 leaf
+ // increment the position cause findNextParentPos checks "parentPos.pos == parentPos.page.getNbElems()"
+ parentPos.pos++;
+ ParentPos<K, V> nextPos = findNextParentPos();
+
+ // if the returned value is a Node OR if it is same as the parentPos
+ // that means cursor is already at the last position
+ // call afterLast() to restore the stack with the path to the right most element
+ if( ( nextPos.page instanceof Node ) || ( nextPos == parentPos ) )
+ {
+ afterLast();
+ }
+ else
+ {
+ parentPos = nextPos;
+ }
+ }
+ else
+ {
+ parentPos.pos++;
+ changeNextDupsContainer( parentPos, btree );
+ }
+ }
+
+
+ /**
+ * Moves the cursor to the previous non-duplicate key
+ * If the BTree contains
+ *
+ * <ul>
+ * <li><1,0></li>
+ * <li><1,1></li>
+ * <li><2,0></li>
+ * <li><2,1></li>
+ * </ul>
+ *
+ * and cursor is present at <2,1> then the cursor will move to <1,1>
+ *
+ * @throws EndOfFileExceededException
+ * @throws IOException
+ */
+ public void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more value
+ return;
+ }
+
+ if ( parentPos.pos == 0 )
+ {
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findPreviousParentPos();
+
+ // if the returned value is a Node that means cursor is already at the first position
+ // call beforeFirst() to restore the stack to the initial state
+ if( parentPos.page instanceof Node )
+ {
+ beforeFirst();
+ }
+ }
+ else
+ {
+ changePrevDupsContainer( parentPos, btree );
+ parentPos.pos--;
+ }
+ }
+
+
+ /**
+ * moves the cursor to the same position that was given at the time of instantiating the cursor.
+ *
+ * For example, if the cursor was created using browse() method, then beforeFirst() will
+ * place the cursor before the 0th position.
+ *
+ * If the cursor was created using browseFrom(K), then calling beforeFirst() will reset the position
+ * to the just before the position where K is present.
+ */
+ public void beforeFirst() throws IOException
+ {
+ cloneStack( _initialStack, stack );
+ }
+
+
+ /**
+ * Places the cursor at the end of the last position
+ *
+ * @throws IOException
+ */
+ public void afterLast() throws IOException
+ {
+ stack.clear();
+ stack = ( LinkedList<ParentPos<K, V>> ) BTreeFactory.getPathToRightMostLeaf( btree );
+ }
+
+
+ /**
+ * clones the original stack of ParentPos objects
+ *
+ * @param original the original stack
+ * @param clone the stack where the cloned ParentPos objects to be copied
+ */
+ private void cloneStack( LinkedList<ParentPos<K, V>> original, LinkedList<ParentPos<K, V>> clone )
+ {
+ clone.clear();
+
+ // preserve the first position
+ for( ParentPos<K, V> o : original )
+ {
+ ParentPos<K, V> tmp = new ParentPos<K, V>( o.page, o.pos );
+ tmp.dupPos = o.dupPos;
+ tmp.dupsContainer = o.dupsContainer;
+ clone.add( tmp );
+ }
+ }
+
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DeleteResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DeleteResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DeleteResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DeleteResult.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,43 @@
+/*
+ * 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 delete operation.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+interface DeleteResult<K, V> extends Result<K, V>
+{
+ /**
+ * @return the modifiedPage
+ */
+ Page<K, V> getModifiedPage();
+
+
+ /**
+ * @return the removed element
+ */
+ Tuple<K, V> getRemovedElement();
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Deletion.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Deletion.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Deletion.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Deletion.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,42 @@
+/*
+ * 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 class used to store a Delete modification done on a BTree.
+ *
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ *
+ * @param <K> The key type
+ * @param <V> The value type
+ */
+public class Deletion<K, V> extends Modification<K, V>
+{
+ /**
+ * Create a new Deletion instance.
+ *
+ * @param key The key to be deleted
+ */
+ public Deletion( K key )
+ {
+ super( key, null );
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyMemoryHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyMemoryHolder.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyMemoryHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyMemoryHolder.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,167 @@
+/*
+ * 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.lang.ref.SoftReference;
+import java.util.UUID;
+
+import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
+
+
+/**
+ * A holder for values of duplicate keys. The values are either present in memory
+ * or loaded on the fly from disk when needed.
+ *
+ * @param <K> The type of the BTree key
+ * @param <V> The type of the BTree value
+ *
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public class DuplicateKeyMemoryHolder<K, V> implements ElementHolder<V, K, V>
+{
+ /** The BTree */
+ private BTree<K, V> btree;
+
+ /** the offset of the value container btree. This value is set only when the parent BTree is in managed mode */
+ private long valContainerOffset = -1;
+
+ /** The reference to the Value instance, or null if it's not present. This will be null when the parent BTree is in managed mode */
+ private BTree<V, V> valueContainer;
+
+ /** This value is set only when the parent BTree is in managed mode */
+ private SoftReference<BTree<V, V>> reference;
+
+
+ /**
+ * Create a new holder storing an offset and a SoftReference containing the value.
+ *
+ * @param offset The offset in disk for this value
+ * @param value The value to store into a SoftReference
+ */
+ public DuplicateKeyMemoryHolder( BTree<K, V> btree, V value )
+ {
+ this.btree = btree;
+
+ try
+ {
+ BTree<V, V> valueContainer = new BTree<V, V>( UUID.randomUUID().toString(), btree.getValueSerializer(),
+ btree.getValueSerializer() );
+
+ if ( btree.isManaged() )
+ {
+ try
+ {
+ btree.getRecordManager().manage( valueContainer, true );
+ valContainerOffset = valueContainer.getBtreeOffset();
+ }
+ catch ( BTreeAlreadyManagedException e )
+ {
+ // should never happen
+ throw new RuntimeException( e );
+ }
+
+ reference = new SoftReference<BTree<V, V>>( valueContainer );
+ }
+ else
+ {
+ this.valueContainer = valueContainer;
+ }
+
+ valueContainer.insert( value, null, 0 );
+ }
+ catch ( IOException e )
+ {
+ throw new RuntimeException( e );
+ }
+ }
+
+
+ /**
+ *
+ * Creates a new instance of DuplicateKeyMemoryHolder.
+ *
+ * Note: the valueContainer should have a valid offset, in other words
+ * the valueContainer should always be the one that is already
+ * managed by RecordManager
+ *
+ * @param btree the parent BTree
+ * @param valueContainer the BTree holding the values of a duplicate key
+ * present in the parent tree
+ */
+ /* No qualifier */DuplicateKeyMemoryHolder( BTree<K, V> btree, BTree<V, V> valueContainer )
+ {
+ this.btree = btree;
+
+ if ( btree.isManaged() )
+ {
+ valContainerOffset = valueContainer.getBtreeOffset();
+ reference = new SoftReference<BTree<V, V>>( valueContainer );
+ }
+ else
+ {
+ this.valueContainer = valueContainer;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public V getValue( BTree<K, V> btree )
+ {
+ if ( !btree.isManaged() )
+ {
+ // wrong cast to please compiler
+ return ( V ) valueContainer;
+ }
+
+ BTree<V, V> valueContainer = reference.get();
+
+ if ( valueContainer == null )
+ {
+ valueContainer = btree.getRecordManager().loadDupsBTree( valContainerOffset );
+ reference = new SoftReference<BTree<V, V>>( valueContainer );
+ }
+
+ return ( V ) valueContainer;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "'" );
+
+ V value = getValue( btree );
+
+ sb.append( value );
+
+ sb.append( "'" );
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ElementHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ElementHolder.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ElementHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ElementHolder.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,49 @@
+/*
+ * 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 org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+
+/**
+ * A Value holder. As we may not store all the values in memory (except for an in-memory
+ * BTree), we will use a SoftReference to keep a reference to a Value, and if it's null,
+ * then we will load the Value from the underlying physical support, using the offset.
+ *
+ * @param <E> The type for the stored element (either a value or a page)
+ * @param <K> The type of the BTree key
+ * @param <V> The type of the BTree value
+ *
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public interface ElementHolder<E, K, V>
+{
+ /**
+ * Get back the element
+ *
+ * @param btree The Btree storing the element
+ *
+ * @return The stored element
+ */
+ E getValue( BTree<K, V> btree ) throws EndOfFileExceededException, IOException;
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InsertResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InsertResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InsertResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InsertResult.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,35 @@
+/*
+ * 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. This is just a container that stores either
+ * the new pivot that has been extracted after a page split, or a modified page if
+ * the child page hasn't been split.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+interface InsertResult<K, V> extends Result<K, V>
+{
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,127 @@
+/*
+ * 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;
+
+
+/**
+ * A class containing utility methods to be used internally.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+@SuppressWarnings("all")
+/* No qualifier */class InternalUtil
+{
+
+ /**
+ * Sets the multi-value container(a.k.a dupsContainer) of the key at the given position.
+ *
+ * This method will not update the existing value of 'dupsPos'. To change this value
+ * use {@link #changeNextDupsContainer(ParentPos, BTree)} or {@link #changePrevDupsContainer(ParentPos, BTree)}
+ *
+ * @param parentPos the parent position object
+ * @param btree the BTree
+ */
+ public static void setDupsContainer( ParentPos parentPos, BTree btree )
+ {
+ if ( !btree.isAllowDuplicates() )
+ {
+ return;
+ }
+
+ try
+ {
+ if ( parentPos.dupsContainer == null )
+ {
+ Leaf leaf = ( Leaf ) ( parentPos.page );
+ BTree dupsContainer = ( BTree ) leaf.values[parentPos.pos].getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ }
+ }
+ catch ( IOException e )
+ {
+ throw new RuntimeException( e );
+ }
+ }
+
+
+ /**
+ * Sets the multi-value container(a.k.a dupsContainer) of the key at the given position
+ * and resets the 'dupsPos' to zero. This is mostly used by Cursor while navigating using
+ * next()
+ *
+ * @param parentPos the parent position object
+ * @param btree the BTree
+ */
+ public static void changeNextDupsContainer( ParentPos parentPos, BTree btree ) throws IOException
+ {
+ if ( !btree.isAllowDuplicates() )
+ {
+ return;
+ }
+
+ if ( parentPos.pos < parentPos.page.getNbElems() )
+ {
+ Leaf leaf = ( Leaf ) ( parentPos.page );
+ BTree dupsContainer = ( BTree ) leaf.values[parentPos.pos].getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ parentPos.dupPos = 0;
+ }
+ }
+
+
+ /**
+ * Sets the multi-value container(a.k.a dupsContainer) of the key at the index below the given position( i.e pos - 1)
+ * and resets the 'dupsPos' to the number of elements present in the multi-value container.
+ * This is used by Cursor while navigating using prev()
+ *
+ * @param parentPos the parent position object
+ * @param btree the BTree
+ */
+ public static void changePrevDupsContainer( ParentPos parentPos, BTree btree ) throws IOException
+ {
+ if ( !btree.isAllowDuplicates() )
+ {
+ return;
+ }
+
+ int index = parentPos.pos - 1;
+ if ( index >= 0 )
+ {
+ Leaf leaf = ( Leaf ) ( parentPos.page );
+ BTree dupsContainer = ( BTree ) leaf.values[index].getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ parentPos.dupPos = ( int ) parentPos.dupsContainer.getNbElems();
+ }
+ }
+
+
+ /**
+ * Same as @see #changePrevDupsContainer(ParentPos, BTree) but with a different name
+ * to make it sound semantically right when used inside {@link BTreeFactory#getPathToRightMostLeaf(BTree)}
+ */
+ public static void setLastDupsContainer( ParentPos parentPos, BTree btree ) throws IOException
+ {
+ changePrevDupsContainer( parentPos, btree );
+ }
+}