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 [4/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/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,1031 @@
+/*
+ * 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.apache.directory.mavibot.btree.InternalUtil.setDupsContainer;
+
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.LinkedList;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+
+
+/**
+ * A MVCC Leaf. It stores the keys and values. It does not have any children.
+ *
+ * @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 Leaf<K, V> extends AbstractPage<K, V>
+{
+ /** Values associated with keys */
+ protected ElementHolder<V, K, V>[] values;
+
+
+ /**
+ * Constructor used to create a new Leaf when we read it from a file.
+ *
+ * @param btree The BTree this page belongs to.
+ */
+ /* No qualifier */Leaf( BTree<K, V> btree )
+ {
+ super( btree );
+ }
+
+
+ /**
+ * Internal constructor used to create Page instance used when a page is being copied or overflow
+ *
+ * @param btree The BTree this page belongs to.
+ * @param revision The page revision
+ * @param nbElems The number of elements this page will contain
+ */
+ @SuppressWarnings("unchecked")
+ // Cannot create an array of generic objects
+ /* No qualifier */Leaf( BTree<K, V> btree, long revision, int nbElems )
+ {
+ super( btree, revision, nbElems );
+
+ if ( btree.isAllowDuplicates() )
+ {
+ this.values = ( DuplicateKeyMemoryHolder<K, V>[] ) Array.newInstance( DuplicateKeyMemoryHolder.class,
+ nbElems );
+ }
+ else
+ {
+ this.values = ( MemoryHolder<K, V>[] ) Array.newInstance( MemoryHolder.class, nbElems );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public InsertResult<K, V> insert( long revision, K key, V value ) throws IOException
+ {
+ // Find the key into this leaf
+ int pos = findPos( key );
+
+ 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 );
+
+ // Replace the existing value in a copy of the current page
+ InsertResult<K, V> result = replaceElement( revision, key, value, index );
+
+ return result;
+ }
+
+ // The key is not present in the leaf. We have to add it in the page
+ if ( nbElems < btree.getPageSize() )
+ {
+ // 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 );
+
+ InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+ else
+ {
+ // 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 );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @SuppressWarnings("unchecked")
+ public DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos )
+ throws IOException
+ {
+ // Check that the leaf is not empty
+ if ( nbElems == 0 )
+ {
+ // Empty leaf
+ return NotPresentResult.NOT_PRESENT;
+ }
+
+ // Find the key in the page
+ int pos = findPos( key );
+
+ if ( pos >= 0 )
+ {
+ // Not found : return the not present result.
+ return NotPresentResult.NOT_PRESENT;
+ }
+
+ // Get the removed element
+ Tuple<K, V> removedElement = null;
+
+ // flag to detect if a key was completely removed
+ boolean keyRemoved = false;
+
+ int index = -( pos + 1 );
+
+ if ( btree.isAllowDuplicates() )
+ {
+ BTree<V, V> dups = ( BTree<V, V> ) values[index].getValue( btree );
+
+ if ( dups.hasKey( value ) )
+ {
+ dups.delete( value );
+
+ if ( dups.getNbElems() == 0 )
+ {
+ keyRemoved = true;
+ }
+
+ removedElement = new Tuple<K, V>( keys[index], value ); // we deleted only one value (even if it is from a tree of size 1)
+ }
+ else if ( value == null ) // this is a case to delete entire <K,dupsTree>
+ {
+ removedElement = new Tuple<K, V>( keys[index], ( V ) dups ); // the entire tree was removed so pass it as the value
+ keyRemoved = true;
+ }
+ else
+ // value is not found
+ {
+ return NotPresentResult.NOT_PRESENT;
+ }
+ }
+ else
+ {
+ V existing = values[index].getValue( btree );
+
+ if ( ( ( existing == null ) && ( value == null ) ) || ( value == null ) )
+ {
+ removedElement = new Tuple<K, V>( keys[index], existing );
+ keyRemoved = true;
+ }
+ else if ( btree.getValueSerializer().compare( value, existing ) == 0 )
+ {
+ removedElement = new Tuple<K, V>( keys[index], value );
+ keyRemoved = true;
+ }
+ else
+ {
+ return NotPresentResult.NOT_PRESENT;
+ }
+ }
+
+ Leaf<K, V> newLeaf = null;
+
+ if ( keyRemoved )
+ {
+ newLeaf = new Leaf<K, V>( btree, revision, nbElems - 1 );
+ }
+ else
+ {
+ newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+ }
+
+ // Create the result
+ DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );
+
+ // If the parent is null, then this page is the root page.
+ if ( parent == null )
+ {
+ // Just remove the entry if it's present
+ copyAfterRemovingElement( keyRemoved, newLeaf, index );
+
+ // The current page is added in the copied page list
+ defaultResult.addCopiedPage( this );
+
+ return defaultResult;
+ }
+ else if ( keyRemoved )
+ {
+ // The current page is not the root. Check if the leaf has more than N/2
+ // elements
+ int halfSize = btree.getPageSize() / 2;
+
+ if ( nbElems == halfSize )
+ {
+ // We have to find a sibling now, and either borrow an entry from it
+ // if it has more than N/2 elements, or to merge the two pages.
+ // Check in both next and previous page, if they have the same parent
+ // and select the biggest page with the same parent to borrow an element.
+ int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
+ Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue( btree ) );
+
+ if ( sibling.getNbElems() == halfSize )
+ {
+ // We will merge the current page with its sibling
+ DeleteResult<K, V> result = mergeWithSibling( removedElement, revision, sibling,
+ ( siblingPos < parentPos ), index );
+
+ return result;
+ }
+ else
+ {
+ // We can borrow the element from the left sibling
+ if ( siblingPos < parentPos )
+ {
+ DeleteResult<K, V> result = borrowFromLeft( removedElement, revision, sibling, index );
+
+ return result;
+ }
+ else
+ {
+ // Borrow from the right sibling
+ DeleteResult<K, V> result = borrowFromRight( removedElement, revision, sibling, index );
+
+ return result;
+ }
+ }
+ }
+ else
+ {
+ // The page has more than N/2 elements.
+ // We simply remove the element from the page, and if it was the leftmost,
+ // we return the new pivot (it will replace any instance of the removed
+ // key in its parents)
+ copyAfterRemovingElement( keyRemoved, newLeaf, index );
+
+ // The current page is added in the copied page list
+ defaultResult.addCopiedPage( this );
+
+ return defaultResult;
+ }
+ }
+ else
+ {
+ // Last, not least : we can copy the full page
+ // Copy the keys and the values
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
+
+ // The current page is added in the copied page list
+ defaultResult.addCopiedPage( this );
+
+ return defaultResult;
+ }
+ }
+
+
+ /**
+ * Merges the sibling with the current leaf, after having removed the element in the page.
+ *
+ * @param revision The new revision
+ * @param sibling The sibling we will merge with
+ * @param isLeft Tells if the sibling is on the left or on the right
+ * @param pos The position of the removed element
+ * @return The new created leaf containing the sibling and the old page.
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> mergeWithSibling( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling,
+ boolean isLeft, int pos )
+ throws EndOfFileExceededException, IOException
+ {
+ // 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
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, btree.getPageSize() - 1 );
+
+ if ( isLeft )
+ {
+ // 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 );
+
+ // 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 );
+
+ // 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 );
+ }
+ 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 );
+
+ // 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 );
+
+ // 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 );
+ }
+
+ // And create the result
+ DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( newLeaf,
+ removedElement );
+
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * Borrows an element from the left sibling, creating a new sibling with one
+ * less element and creating a new page where the element to remove has been
+ * deleted and the borrowed element added on the left.
+ *
+ * @param revision The new revision for all the pages
+ * @param sibling The left sibling
+ * @param pos The position of the element to remove
+ * @return The resulting pages
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> borrowFromLeft( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling, int pos )
+ throws IOException
+ {
+ // The sibling is on the left, borrow the rightmost element
+ K siblingKey = sibling.keys[sibling.getNbElems() - 1];
+ ElementHolder<V, K, V> siblingValue = sibling.values[sibling.getNbElems() - 1];
+
+ // Create the new sibling, with one less element at the end
+ Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
+
+ // Create the new page and add the new element at the beginning
+ // First copy the current page, with the same size
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+
+ // Insert the borrowed element
+ newLeaf.keys[0] = siblingKey;
+ 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 );
+
+ // 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 );
+
+ DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf, newSibling, removedElement );
+
+ // Add the copied pages to the list
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * Borrows an element from the right sibling, creating a new sibling with one
+ * less element and creating a new page where the element to remove has been
+ * deleted and the borrowed element added on the right.
+ *
+ * @param revision The new revision for all the pages
+ * @param sibling The right sibling
+ * @param pos The position of the element to remove
+ * @return The resulting pages
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> borrowFromRight( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling, int pos )
+ throws IOException
+ {
+ // The sibling is on the left, borrow the rightmost element
+ K siblingKey = sibling.keys[0];
+ ElementHolder<V, K, V> siblingHolder = sibling.values[0];
+
+ // Create the new sibling
+ Leaf<K, V> newSibling = new Leaf<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 );
+
+ // Create the new page and add the new element at the end
+ // First copy the current page, with the same size
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+
+ // Insert the borrowed element at the end
+ newLeaf.keys[nbElems - 1] = siblingKey;
+ 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 );
+
+ // 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 );
+
+ DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newLeaf, newSibling, removedElement );
+
+ // Add the copied pages to the list
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * Copies the elements of the current page to a new page
+ *
+ * @param keyRemoved a flag stating if the key was removed
+ * @param newLeaf The new page into which the remaining keys and values will be copied
+ * @param pos The position into the page of the element to remove
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private void copyAfterRemovingElement( boolean keyRemoved, Leaf<K, V> newLeaf, int pos ) throws IOException
+ {
+ if ( keyRemoved )
+ {
+ // Deal with the special case of a page with only one element by skipping
+ // the copy, as we won't have any remaining element in the page
+ if ( nbElems == 1 )
+ {
+ return;
+ }
+
+ // 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 );
+
+ // 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 );
+ }
+ else
+ // one of the many values of the same key was removed, no change in the number of keys
+ {
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public V get( K key ) throws KeyNotFoundException, IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ V v = values[-( pos + 1 )].getValue( btree );
+
+ if ( btree.isAllowDuplicates() )
+ {
+ // always return the first value for get(key) when duplicates are allowed
+ BTree<V, V> dupTree = ( ( BTree<V, V> ) v );
+ return dupTree.rootPage.getLeftMostKey();
+ }
+
+ return v;
+ }
+ else
+ {
+ throw new KeyNotFoundException( "Cannot find an entry for key " + key );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public BTree<V, V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ {
+ if ( !btree.isAllowDuplicates() )
+ {
+ throw new IllegalArgumentException( "Duplicates are not allowed in this tree" );
+ }
+
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ V v = values[-( pos + 1 )].getValue( btree );
+
+ return ( ( BTree<V, V> ) v );
+ }
+ else
+ {
+ throw new KeyNotFoundException( "Cannot find an entry for key " + key );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean hasKey( K key )
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ return true;
+ }
+
+ return false;
+ }
+
+
+ @Override
+ public boolean contains( K key, V value ) throws IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ V v = values[-( pos + 1 )].getValue( btree );
+
+ if ( btree.isAllowDuplicates() )
+ {
+ // always return the first value for get(key) when duplicates are allowed
+ BTree<V, V> dupTree = ( ( BTree<V, V> ) v );
+ return dupTree.hasKey( value );
+ }
+ else
+ {
+ return ( btree.getValueSerializer().compare( value, v ) == 0 );
+ }
+ }
+ else
+ {
+ return false;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public ElementHolder<V, K, V> getValue( int pos )
+ {
+ if ( pos < nbElems )
+ {
+ return values[pos];
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+
+ /**
+ * Sets the value at a give position
+ * @param pos The position in the values array
+ * @param value the value to inject
+ */
+ public void setValue( int pos, ElementHolder<V, K, V> value )
+ {
+ values[pos] = value;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Cursor<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ {
+ int pos = findPos( key );
+ Cursor<K, V> cursor = null;
+
+ if ( pos < 0 )
+ {
+ int index = -( pos + 1 );
+
+ // The first element has been found. Create the cursor
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
+ setDupsContainer( parentPos, btree );
+ stack.push( parentPos );
+
+ cursor = new Cursor<K, V>( btree, transaction, stack );
+ }
+ else
+ {
+ // The key has not been found. Select the value just above, if we have one
+ if ( pos < nbElems )
+ {
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+ setDupsContainer( parentPos, btree );
+ stack.push( parentPos );
+
+ cursor = new Cursor<K, V>( btree, transaction, stack );
+ }
+ else
+ {
+ // Not found : return a null cursor
+ stack.push( new ParentPos<K, V>( null, -1 ) );
+
+ return new Cursor<K, V>( btree, transaction, stack );
+ }
+ }
+
+ return cursor;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Cursor<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ {
+ int pos = 0;
+ Cursor<K, V> cursor = null;
+
+ if ( nbElems == 0 )
+ {
+ // The tree is empty, it's the root, we have nothing to return
+ stack.push( new ParentPos<K, V>( null, -1 ) );
+
+ return new Cursor<K, V>( btree, transaction, stack );
+ }
+ else
+ {
+ // Start at the beginning of the page
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+
+ setDupsContainer( parentPos, btree );
+
+ stack.push( parentPos );
+
+ cursor = new Cursor<K, V>( btree, transaction, stack );
+ }
+
+ 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
+ * @param nbElems The number of elements to copy
+ * @return The copied page
+ */
+ private Page<K, V> copy( long revision, int nbElems )
+ {
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+
+ // Copy the keys and the values
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
+
+ return newLeaf;
+ }
+
+
+ /**
+ * Copy the current page if needed, and replace the value at the position we have found the key.
+ *
+ * @param revision The new page revision
+ * @param key The new key
+ * @param value the new value
+ * @param pos The position of the key in the page
+ * @return The copied page
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private InsertResult<K, V> replaceElement( long revision, K key, V value, int pos )
+ throws IOException
+ {
+ Leaf<K, V> newLeaf = this;
+
+ if ( this.revision != revision )
+ {
+ // The page hasn't been modified yet, we need to copy it first
+ newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
+ }
+
+ V oldValue = null;
+
+ if ( btree.isAllowDuplicates() )
+ {
+ BTree<V, V> dupValues = ( BTree<V, V> ) newLeaf.values[pos].getValue( btree );
+
+ // return value will always be null here
+ if ( !dupValues.hasKey( value ) )
+ {
+ dupValues.insert( value, null, 0 );
+ }
+ else
+ {
+ oldValue = value;
+ }
+ }
+ else
+ {
+ // Now we can inject the value
+ oldValue = newLeaf.values[pos].getValue( btree );
+ newLeaf.values[pos] = btree.createHolder( value );
+ }
+
+ // Create the result
+ InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+
+
+ /**
+ * Adds a new <K, V> into a copy of the current page at a given position. We return the
+ * modified page. The new page will have one more element than the current page.
+ *
+ * @param revision The revision of the modified page
+ * @param key The key to insert
+ * @param value The value to insert
+ * @param pos The position into the page
+ * @return The modified page with the <K,V> element added
+ */
+ private Page<K, V> addElement( long revision, K key, V value, int pos )
+ {
+ // First copy the current page, but add one element in the copied page
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
+
+ // Atm, store the value in memory
+
+ ElementHolder valueHolder = null;
+
+ if ( btree.isAllowDuplicates() )
+ {
+ valueHolder = new DuplicateKeyMemoryHolder<K, V>( btree, value );
+ }
+ else
+ {
+ valueHolder = new MemoryHolder<K, V>( btree, value );
+ }
+
+ //ValueHolder<K, V> valueHolder = btree.createHolder( value );
+
+ // Deal with the special case of an empty page
+ if ( nbElems == 0 )
+ {
+ newLeaf.keys[0] = key;
+
+ newLeaf.values[0] = valueHolder;
+ }
+ else
+ {
+ //FIXME do not copy the duplicate key's value container, this will improve the perf significantly
+ // 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 );
+
+ // Add the new element
+ newLeaf.keys[pos] = key;
+ newLeaf.values[pos] = valueHolder;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length - pos );
+ System.arraycopy( values, pos, newLeaf.values, pos + 1, values.length - pos );
+ }
+
+ return newLeaf;
+ }
+
+
+ /**
+ * Split a full page into two new pages, a left, a right and a pivot element. The new pages will
+ * each contains half of the original elements. <br/>
+ * The pivot will be computed, depending on the place
+ * we will inject the newly added element. <br/>
+ * If the newly added element is in the middle, we will use it
+ * as a pivot. Otherwise, we will use either the last element in the left page if the element is added
+ * on the left, or the first element in the right page if it's added on the right.
+ *
+ * @param revision The new revision for all the created pages
+ * @param key The key to add
+ * @param value The value to add
+ * @param pos The position of the insertion of the new element
+ * @return An OverflowPage containing the pivot, and the new left and right pages
+ */
+ private InsertResult<K, V> addAndSplit( long revision, K key, V value, int pos )
+ {
+ int middle = btree.getPageSize() >> 1;
+ Leaf<K, V> leftLeaf = null;
+ Leaf<K, V> rightLeaf = null;
+ ElementHolder<V, K, V> valueHolder = btree.createHolder( value );
+
+ // Determinate where to store the new value
+ if ( pos <= middle )
+ {
+ // The left page will contain the new value
+ leftLeaf = new Leaf<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 );
+ System.arraycopy( values, 0, leftLeaf.values, 0, pos );
+
+ // Add the new element
+ leftLeaf.keys[pos] = key;
+ leftLeaf.values[pos] = valueHolder;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, leftLeaf.keys, pos + 1, middle - pos );
+ System.arraycopy( values, pos, leftLeaf.values, pos + 1, middle - pos );
+
+ // Now, create the right page
+ rightLeaf = new Leaf<K, V>( btree, revision, middle );
+
+ // Copy the keys and the values in the right page
+ System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
+ System.arraycopy( values, middle, rightLeaf.values, 0, middle );
+ }
+ else
+ {
+ // Create the left page
+ leftLeaf = new Leaf<K, V>( btree, revision, middle );
+
+ // Copy all the element into the left page
+ System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
+ System.arraycopy( values, 0, leftLeaf.values, 0, middle );
+
+ // Now, create the right page
+ rightLeaf = new Leaf<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 );
+ System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
+
+ // Add the new element
+ rightLeaf.keys[rightPos] = key;
+ rightLeaf.values[rightPos] = valueHolder;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems - pos );
+ System.arraycopy( values, pos, rightLeaf.values, rightPos + 1, nbElems - pos );
+ }
+
+ // Get the pivot
+ K pivot = rightLeaf.keys[0];
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
+
+ return result;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getLeftMostKey()
+ {
+ return keys[0];
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getRightMostKey()
+ {
+ return keys[nbElems - 1];
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Tuple<K, V> findLeftMost() throws IOException
+ {
+ V val = null;
+
+ if ( btree.isAllowDuplicates() )
+ {
+ BTree<V, V> dupTree = ( BTree<V, V> ) values[0].getValue( btree );
+ val = dupTree.rootPage.getLeftMostKey();
+ }
+ else
+ {
+ val = values[0].getValue( btree );
+ }
+
+ return new Tuple<K, V>( keys[0], val );
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
+ {
+ V val = null;
+
+ if ( btree.isAllowDuplicates() )
+ {
+ BTree<V, V> dupTree = ( BTree<V, V> ) values[nbElems - 1].getValue( btree );
+ val = dupTree.rootPage.getRightMostKey();
+ }
+ else
+ {
+ val = values[nbElems - 1].getValue( btree );
+ }
+
+ return new Tuple<K, V>( keys[nbElems - 1], val );
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "Leaf[" );
+ sb.append( super.toString() );
+
+ sb.append( "] -> {" );
+
+ if ( nbElems > 0 )
+ {
+ boolean isFirst = true;
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( "<" ).append( keys[i] ).append( "," ).append( values[i] ).append( ">" );
+ }
+ }
+
+ sb.append( "}" );
+
+ return sb.toString();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public String dumpPage( String tabs )
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( tabs );
+
+ if ( nbElems > 0 )
+ {
+ boolean isFirst = true;
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( "<" ).append( keys[i] ).append( "," ).append( values[i] ).append( ">" );
+ }
+ }
+
+ sb.append( "\n" );
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MemoryHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MemoryHolder.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MemoryHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MemoryHolder.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,80 @@
+/*
+ * 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 In-Memory Value holder. The value is always present in memory.
+ *
+ * @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 MemoryHolder<K, V> implements ElementHolder<V, K, V>
+{
+ /** The BTree */
+ private BTree<K, V> btree;
+
+ /** The reference to the Value instance, or null if it's not present */
+ private V value;
+
+
+ /**
+ * 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 MemoryHolder( BTree<K, V> btree, V value )
+ {
+ this.btree = btree;
+ this.value = value;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public V getValue( BTree<K, V> btree )
+ {
+ return value;
+ }
+
+
+ /**
+ * @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/MergedWithSiblingResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MergedWithSiblingResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MergedWithSiblingResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MergedWithSiblingResult.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,76 @@
+/*
+ * 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 MergedWithSiblingResult<K, V> extends AbstractDeleteResult<K, V>
+{
+ /**
+ * The default constructor for RemoveResult.
+ *
+ * @param modifiedPage The modified page
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */MergedWithSiblingResult( Page<K, V> modifiedPage, Tuple<K, V> removedElement )
+ {
+ super( modifiedPage, removedElement );
+ }
+
+
+ /**
+ * A constructor for RemoveResult which takes a list of copied page.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */MergedWithSiblingResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Tuple<K, V> removedElement )
+ {
+ super( copiedPages, modifiedPage, removedElement );
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "MergedWithSiblingResult" );
+ sb.append( "\n removed element : " ).append( getRemovedElement() );
+ sb.append( "\n modifiedPage : " ).append( getModifiedPage() );
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Modification.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Modification.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Modification.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Modification.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,50 @@
+/*
+ * 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 abstract class used to store a 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 abstract class Modification<K, V> extends Tuple<K, V>
+{
+ /** The byte used to define an Addition in the serialized journal */
+ public static final byte ADDITION = 0;
+
+ /** The byte used to define a Deletion in the serialized journal */
+ public static final byte DELETION = 1;
+
+
+ /**
+ * Create a new Modification instance.
+ *
+ * @param key The key being modified
+ * @param value The value being modified
+ */
+ protected Modification( K key, V value )
+ {
+ super( key, value );
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ModifyResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ModifyResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ModifyResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ModifyResult.java Sun Aug 4 09:22:56 2013
@@ -0,0 +1,104 @@
+/*
+ * 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 an insert operation, when the child has not been split. It contains the
+ * reference to the modified page.
+ *
+ * @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 ModifyResult<K, V> extends AbstractResult<K, V> implements InsertResult<K, V>
+{
+ /** The modified page reference */
+ protected Page<K, V> modifiedPage;
+
+ /** The modified value if the key was found in the tree*/
+ protected V modifiedValue;
+
+
+ /**
+ * The default constructor for ModifyResult.
+ *
+ * @param modifiedPage The modified page
+ * @param modifiedvalue The modified value (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */ModifyResult( Page<K, V> modifiedPage, V modifiedValue )
+ {
+ super();
+ this.modifiedPage = modifiedPage;
+ this.modifiedValue = modifiedValue;
+ }
+
+
+ /**
+ * A constructor for ModifyResult which takes a list of copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param modifiedvalue The modified value (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */ModifyResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage, V modifiedValue )
+ {
+ super( copiedPages );
+ this.modifiedPage = modifiedPage;
+ this.modifiedValue = modifiedValue;
+ }
+
+
+ /**
+ * @return the modifiedPage
+ */
+ /* No qualifier */Page<K, V> getModifiedPage()
+ {
+ return modifiedPage;
+ }
+
+
+ /**
+ * @return the modifiedValue
+ */
+ /* No qualifier */V getModifiedValue()
+ {
+ return modifiedValue;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "ModifyResult, old value = " ).append( modifiedValue );
+ sb.append( ", modifiedPage = " ).append( modifiedPage );
+ sb.append( super.toString() );
+
+ return sb.toString();
+ }
+}