You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2017/02/24 07:16:38 UTC
svn commit: r1784232 [3/9] - in
/directory/mavibot/branches/single-value/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
main/java/org/apache/directory/mavibot/btree/serializer/
test/java/org/apache/directory/mavibot/btree/
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java?rev=1784232&r1=1784231&r2=1784232&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java Fri Feb 24 07:16:37 2017
@@ -22,10 +22,13 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
import java.lang.reflect.Array;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
-import org.apache.directory.mavibot.btree.exception.CursorException;
-import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
/**
@@ -39,7 +42,7 @@ import org.apache.directory.mavibot.btre
/* No qualifier */class Leaf<K, V> extends AbstractPage<K, V>
{
/** Values associated with keys */
- protected ValueHolder<V>[] values;
+ private ValueHolder<V>[] values;
/**
@@ -58,20 +61,21 @@ import org.apache.directory.mavibot.btre
*
* @param btree The BTree this page belongs to.
* @param revision The page revision
- * @param nbElems The number of elements this page will contain
+ * @param nbPageElems The number of elements this page will contain
*/
@SuppressWarnings("unchecked")
- Leaf( BTree<K, V> btree, long revision, int nbElems )
+ Leaf( BTree<K, V> btree, long revision, int nbPageElems )
{
- super( btree, revision, nbElems );
- values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolderImpl.class, btree.getPageSize() );
+ super( btree, revision, nbPageElems );
+ values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, btree.getPageNbElem() );
}
/**
* {@inheritDoc}
*/
- public InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
+ @Override
+ public InsertResult<K, V> insert( WriteTransaction transaction, K key, V value ) throws IOException
{
// Find the key into this leaf
int pos = findPos( key );
@@ -80,39 +84,21 @@ import org.apache.directory.mavibot.btre
{
// 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;
+ return replaceElement( transaction, value, -( pos + 1 ) );
}
// The key is not present in the leaf. We have to add it in the page
- if ( nbElems < btree.getPageSize() )
+ if ( nbPageElems < btree.getPageNbElem() )
{
// 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 = null;
-
- modifiedPage = addElement( revision, key, value, pos );
-
- InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
- result.addCopiedPage( this );
-
- return result;
+ return modifyLeaf( transaction, key, value, pos );
}
else
{
// The Page is already full : we split it and return the overflow element,
// after having created two pages.
- InsertResult<K, V> result = null;
-
- result = addAndSplit( revision, key, value, pos );
-
- result.addCopiedPage( this );
-
- return result;
+ return addAndSplit( transaction, key, value, pos );
}
}
@@ -121,11 +107,14 @@ import org.apache.directory.mavibot.btre
* {@inheritDoc}
*/
@SuppressWarnings("unchecked")
- /* no qualifier */DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
+ @Override
+ /* no qualifier */DeleteResult<K, V> delete( WriteTransaction transaction, K key, Page<K, V> parent, int parentPos )
throws IOException
{
+ long revision = transaction.getRevision();
+
// Check that the leaf is not empty
- if ( nbElems == 0 )
+ if ( nbPageElems == 0 )
{
// Empty leaf
return NotPresentResult.NOT_PRESENT;
@@ -141,43 +130,30 @@ import org.apache.directory.mavibot.btre
}
// Get the removed element
- Tuple<K, V> removedElement = null;
+ Tuple<K, V> removedElement;
// flag to detect if a key was completely removed
int index = -( pos + 1 );
ValueHolder<V> valueHolder = values[index];
- if ( value == null )
- {
- // we have to delete the whole value
- removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // the entire value was removed
- }
- else
- {
- if ( valueHolder.contains( value ) )
- {
- removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // only one value was removed
- }
- else
- {
- return NotPresentResult.NOT_PRESENT;
- }
- }
+ // we have to delete the whole value
+ removedElement = new Tuple<>( keys[index].getKey(), valueHolder.get() ); // the entire value was removed
- Leaf<K, V> newLeaf = null;
+ Leaf<K, V> newLeaf;
// No value, we can remove the key
- newLeaf = new Leaf<K, V>( btree, revision, nbElems - 1 );
+ newLeaf = new Leaf<>( btree, revision, nbPageElems - 1 );
+ newLeaf.initId( transaction.getRecordManagerHeader() );
// Create the result
- DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );
+ DeleteResult<K, V> defaultResult = new RemoveResult<>( 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, or replace it if we have more than one value in the ValueHolder
- copyAfterRemovingElement( value, newLeaf, index );
+ copyAfterRemovingElement( newLeaf, index );
// The current page is added in the copied page list
defaultResult.addCopiedPage( this );
@@ -188,41 +164,34 @@ import org.apache.directory.mavibot.btre
{
// The current page is not the root. Check if the leaf has more than N/2
// elements
- int halfSize = btree.getPageSize() / 2;
+ int halfSize = btree.getPageNbElem() / 2;
- if ( nbElems == halfSize )
+ if ( nbPageElems == 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( parent, parentPos );
+ int siblingPos = selectSibling( transaction, parent, parentPos );
Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent )
.getPage( siblingPos ) );
- if ( sibling.getNbElems() == halfSize )
+ if ( sibling.nbPageElems == halfSize )
{
// We will merge the current page with its sibling
- DeleteResult<K, V> result = mergeWithSibling( removedElement, revision, sibling,
- ( siblingPos < parentPos ), index );
-
- return result;
+ return mergeWithSibling( transaction, removedElement, sibling, siblingPos < parentPos , index );
}
else
{
// We can borrow the element from the left sibling
if ( siblingPos < parentPos )
{
- DeleteResult<K, V> result = borrowFromLeft( removedElement, revision, sibling, index );
-
- return result;
+ return borrowFromLeft( transaction, removedElement, sibling, index );
}
else
{
// Borrow from the right sibling
- DeleteResult<K, V> result = borrowFromRight( removedElement, revision, sibling, index );
-
- return result;
+ return borrowFromRight( transaction, removedElement, sibling, index );
}
}
}
@@ -232,7 +201,7 @@ import org.apache.directory.mavibot.btre
// 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( value, newLeaf, index );
+ copyAfterRemovingElement( newLeaf, index );
// The current page is added in the copied page list
defaultResult.addCopiedPage( this );
@@ -253,29 +222,30 @@ import org.apache.directory.mavibot.btre
* @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
+ private DeleteResult<K, V> mergeWithSibling( WriteTransaction transaction, Tuple<K, V> removedElement,
+ Leaf<K, V> sibling, boolean isLeft, int pos ) throws IOException
{
+ long revision = transaction.getRevision();
+
// 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 );
+ Leaf<K, V> newLeaf = new Leaf<>( btree, revision, btree.getPageNbElem() - 1 );
+ newLeaf.initId( transaction.getRecordManagerHeader() );
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 );
+ System.arraycopy( sibling.keys, 0, newLeaf.keys, 0, sibling.nbPageElems );
+ System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbPageElems );
// 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 );
+ System.arraycopy( keys, 0, newLeaf.keys, sibling.nbPageElems, pos );
+ System.arraycopy( values, 0, newLeaf.values, sibling.nbPageElems, 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 );
+ System.arraycopy( keys, pos + 1, newLeaf.keys, sibling.nbPageElems + pos, nbPageElems - pos - 1 );
+ System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbPageElems + pos, nbPageElems - pos - 1 );
}
else
{
@@ -285,16 +255,16 @@ import org.apache.directory.mavibot.btre
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 );
+ System.arraycopy( keys, pos + 1, newLeaf.keys, pos, nbPageElems - pos - 1 );
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, nbPageElems - 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 );
+ System.arraycopy( sibling.keys, 0, newLeaf.keys, nbPageElems - 1, sibling.nbPageElems );
+ System.arraycopy( sibling.values, 0, newLeaf.values, nbPageElems - 1, sibling.nbPageElems );
}
// And create the result
- DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( newLeaf, removedElement );
+ DeleteResult<K, V> result = new MergedWithSiblingResult<>( newLeaf, removedElement );
result.addCopiedPage( this );
result.addCopiedPage( sibling );
@@ -314,24 +284,28 @@ import org.apache.directory.mavibot.btre
* @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,
+ private DeleteResult<K, V> borrowFromLeft( WriteTransaction transaction, Tuple<K, V> removedElement, Leaf<K, V> sibling,
int pos )
throws IOException
{
+ long revision = transaction.getRevision();
+
// The sibling is on the left, borrow the rightmost element
- K siblingKey = sibling.keys[sibling.getNbElems() - 1].getKey();
- ValueHolder<V> siblingValue = null;
- siblingValue = sibling.values[sibling.getNbElems() - 1];
+ K siblingKey = sibling.keys[sibling.nbPageElems - 1].getKey();
+ ValueHolder<V> siblingValue;
+ siblingValue = sibling.values[sibling.nbPageElems - 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 );
+ Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( transaction, sibling.nbPageElems - 1 );
+ newSibling.initId( transaction.getRecordManagerHeader() );
// 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 );
+ Leaf<K, V> newLeaf = new Leaf<>( btree, revision, nbPageElems );
+ newLeaf.initId( transaction.getRecordManagerHeader() );
// Insert the borrowed element
- newLeaf.keys[0] = new KeyHolderImpl<K>( btree.getKeySerializer(), siblingKey );
+ newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
newLeaf.values[0] = siblingValue;
// Copy the keys and the values up to the insertion position,
@@ -342,7 +316,7 @@ import org.apache.directory.mavibot.btre
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 );
+ DeleteResult<K, V> result = new BorrowedFromLeftResult<>( newLeaf, newSibling, removedElement );
// Add the copied pages to the list
result.addCopiedPage( this );
@@ -363,29 +337,33 @@ import org.apache.directory.mavibot.btre
* @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,
+ private DeleteResult<K, V> borrowFromRight( WriteTransaction transaction, Tuple<K, V> removedElement, Leaf<K, V> sibling,
int pos )
throws IOException
{
+ long revision = transaction.getRevision();
+
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[0].getKey();
- ValueHolder<V> siblingHolder = null;
+ ValueHolder<V> siblingHolder;
siblingHolder = sibling.values[0];
// Create the new sibling
- Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
+ Leaf<K, V> newSibling = new Leaf<>( btree, revision, sibling.nbPageElems - 1 );
+ newSibling.initId( transaction.getRecordManagerHeader() );
// 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 );
+ System.arraycopy( sibling.keys, 1, newSibling.keys, 0, sibling.nbPageElems - 1 );
+ System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbPageElems - 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 );
+ Leaf<K, V> newLeaf = new Leaf<>( btree, revision, nbPageElems );
+ newLeaf.initId( transaction.getRecordManagerHeader() );
// Insert the borrowed element at the end
- newLeaf.keys[nbElems - 1] = new KeyHolderImpl<K>( btree.getKeySerializer(), siblingKey );
- newLeaf.values[nbElems - 1] = siblingHolder;
+ newLeaf.keys[nbPageElems - 1] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
+ newLeaf.values[nbPageElems - 1] = siblingHolder;
// Copy the keys and the values up to the deletion position,
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
@@ -395,7 +373,7 @@ import org.apache.directory.mavibot.btre
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 );
+ DeleteResult<K, V> result = new BorrowedFromRightResult<>( newLeaf, newSibling, removedElement );
// Add the copied pages to the list
result.addCopiedPage( this );
@@ -413,12 +391,12 @@ import org.apache.directory.mavibot.btre
* @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( V removedValue, Leaf<K, V> newLeaf, int pos )
+ private void copyAfterRemovingElement( Leaf<K, V> newLeaf, int pos )
throws IOException
{
// 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 )
+ if ( nbPageElems == 1 )
{
return;
}
@@ -436,6 +414,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
+ @Override
public V get( K key ) throws KeyNotFoundException, IOException
{
int pos = findPos( key );
@@ -456,7 +435,7 @@ import org.apache.directory.mavibot.btre
*/
/* No qualifier */KeyHolder<K> getKeyHolder( int pos )
{
- if ( pos < nbElems )
+ if ( pos < nbPageElems )
{
return keys[pos];
}
@@ -470,6 +449,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
+ @Override
public boolean hasKey( K key )
{
int pos = findPos( key );
@@ -506,7 +486,7 @@ import org.apache.directory.mavibot.btre
*/
/* no qualifier */ValueHolder<V> getValue( int pos )
{
- if ( pos < nbElems )
+ if ( pos < nbPageElems )
{
return values[pos];
}
@@ -522,6 +502,7 @@ import org.apache.directory.mavibot.btre
* @param pos The position in the values array
* @param value the value to inject
*/
+ @Override
/* no qualifier */void setValue( int pos, ValueHolder<V> value )
{
values[pos] = value;
@@ -531,139 +512,88 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- public TupleCursor<K, V> browse( K key, ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
+ @Override
+ public TupleCursor<K, V> browse( Transaction transaction, K key, ParentPos<K, V>[] stack, int depth )
{
int pos = findPos( key );
// First use case : the leaf is empty (this is a root page)
- if ( nbElems == 0 )
+ if ( nbPageElems == 0 )
{
// We have to return an empty cursor
- return new EmptyTupleCursor<K, V>();
+ return new EmptyTupleCursor<>();
}
// The cursor we will return
- TupleCursor<K, V> cursor = new TupleCursor<K, V>( transaction, stack, depth );
+ TupleCursor<K, V> cursor = new TupleCursor<>( transaction, stack, depth );
// Depending on the position, we will proceed differently :
// 1) if the key is found in the page, the cursor will be
- // set to the previous position (or BEFORE_FIRST).
- // 2) The key has not been found, but is in the middle of the
- // page (ie, other keys above the one we are looking for exist),
- // the cursor will be set to the current position
- // 3) The key has not been found, and we are at the end of
- // the page. We have to fetch the next key in yhe B-tree
+ // set to its position
+ // 2) The key has not been found, we set the position to the
+ // value findPos returned
if ( pos < 0 )
{
// The key has been found.
pos = -( pos + 1 );
// Start at the found position in the page
- ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-
- // And store this position in the stack
- stack[depth] = parentPos;
-
- return cursor;
+ stack[depth] = new ParentPos<>( this, pos );
}
else
{
// The key has not been found, there are keys above this one.
- // Select the value just above
- if ( pos < nbElems )
+ // Select the value just above if we have some
+ if ( pos == 0 )
+ {
+ // We are before the first value
+ stack[depth] = new ParentPos<>( this, pos );
+
+ cursor.beforeFirst();
+ }
+ else if ( pos < nbPageElems )
{
// There is at least one key above the one we are looking for.
// This will be the starting point.
- ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-
- stack[depth] = parentPos;
-
- return cursor;
+ stack[depth] = new ParentPos<>( this, pos );
}
else
{
- // We are at the end of a leaf. We have to see if we have other
- // keys on the right.
- if ( depth == 0 )
- {
- // No children, we are at the end of the root page
- stack[depth] = new ParentPos<K, V>( this, pos );
-
- // As we are done, set the cursor at the end
- try
- {
- cursor.afterLast();
- }
- catch ( CursorException e )
- {
- e.printStackTrace();
- }
+ // We are at the end of the tree.
+ // No children, we are at the end of the root page
+ stack[depth] = new ParentPos<>( this, pos );
- return cursor;
- }
- else
- {
- // We have to find the adjacent key in the B-tree
- boolean isLast = true;
- stack[depth] = new ParentPos<K, V>( this, pos );
-
- // Check each upper node, starting from the direct parent
- int stackIndex = depth - 1;
-
- for ( int i = stackIndex; i >= 0; i-- )
- {
- if ( stack[i].pos < stack[i].page.getNbElems() )
- {
- isLast = false;
- break;
- }
-
- stackIndex--;
- }
-
- if ( isLast )
- {
- // We don't have any more elements
- try
- {
- cursor.afterLast();
- }
- catch ( CursorException e )
- {
- e.printStackTrace();
- }
-
- return cursor;
- }
-
- return cursor;
- }
+ // As we are done, set the cursor at the end
+ cursor.afterLast();
}
}
+
+ return cursor;
}
/**
* {@inheritDoc}
*/
- public TupleCursor<K, V> browse( ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
+ @Override
+ public TupleCursor<K, V> browse( Transaction transaction, ParentPos<K, V>[] stack, int depth )
{
int pos = 0;
- TupleCursor<K, V> cursor = null;
+ TupleCursor<K, V> cursor;
- if ( nbElems == 0 )
+ if ( nbPageElems == 0 )
{
// The tree is empty, it's the root, we have nothing to return
- stack[depth] = new ParentPos<K, V>( null, -1 );
+ stack[depth] = new ParentPos<>( null, -1 );
- return new TupleCursor<K, V>( transaction, stack, depth );
+ return new TupleCursor<>( transaction, stack, depth );
}
else
{
// Start at the beginning of the page
- ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+ ParentPos<K, V> parentPos = new ParentPos<>( this, pos );
stack[depth] = parentPos;
- cursor = new TupleCursor<K, V>( transaction, stack, depth );
+ cursor = new TupleCursor<>( transaction, stack, depth );
}
return cursor;
@@ -674,15 +604,16 @@ import org.apache.directory.mavibot.btre
* 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
+ * @param nbPageElems The number of elements to copy
* @return The copied page
*/
- public Page<K, V> copy( long revision, int nbElems )
+ public Page<K, V> copy( WriteTransaction transaction, int nbPageElems )
{
- Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+ Leaf<K, V> newLeaf = new Leaf<>( btree, transaction.getRevision(), nbPageElems );
+ newLeaf.setId( id );
// Copy the keys and the values
- System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbPageElems );
if ( values != null )
{
@@ -692,18 +623,20 @@ import org.apache.directory.mavibot.btre
for ( ValueHolder<V> valueHolder : values )
{
- try
- {
- newLeaf.values[pos++] = valueHolder.clone();
- }
- catch ( CloneNotSupportedException e )
+ if ( valueHolder != null )
{
- // TODO Auto-generated catch block
- e.printStackTrace();
+ try
+ {
+ newLeaf.values[pos++] = valueHolder.clone();
+ }
+ catch ( CloneNotSupportedException e )
+ {
+ e.printStackTrace();
+ }
}
- // Stop when we have copied nbElems values
- if ( pos == nbElems )
+ // Stop when we have copied nbPageElems values
+ if ( pos == nbPageElems )
{
break;
}
@@ -718,17 +651,21 @@ import org.apache.directory.mavibot.btre
* 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
+ * @param nbPageElems The number of elements to copy
* @return The copied page
*/
- public Page<K, V> copy( long revision )
+ @Override
+ public Page<K, V> copy( WriteTransaction transaction )
{
- Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+ long revision = transaction.getRevision();
+
+ Leaf<K, V> newLeaf = new Leaf<>( btree, revision, nbPageElems );
+ newLeaf.initId( transaction.getRecordManagerHeader() );
// Copy the keys and the values
- System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbPageElems );
- if ( values != null )
+ if ( ( values != null ) && ( nbPageElems > 0 ) )
{
// It' not enough to copy the ValueHolder, we have to clone them
// as ValueHolders are mutable
@@ -742,12 +679,11 @@ import org.apache.directory.mavibot.btre
}
catch ( CloneNotSupportedException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
}
- // Stop when we have copied nbElems values
- if ( pos == nbElems )
+ // Stop when we have copied nbPageElems values
+ if ( pos == nbPageElems )
{
break;
}
@@ -761,54 +697,102 @@ import org.apache.directory.mavibot.btre
/**
* 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 transaction The {@link WriteTransaction} we are processing this update in
* @param key The new key
* @param value the new value
* @param pos The position of the key in the page
- * @return The copied page
+ * @return A {@link InserResult} instance, containing the reference to the new page, or an
+ * {@link ExistsResult} instance, if the value already exists in the 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 )
+ private InsertResult<K, V> replaceElement( WriteTransaction transaction, V value, int pos )
throws IOException
{
Leaf<K, V> newLeaf = this;
-
+
// Get the previous value from the leaf (it's a copy)
ValueHolder<V> valueHolder = values[pos];
boolean valueExists = valueHolder.contains( value );
-
- if ( this.revision != revision )
+
+ // Check if the value does not already exist in the leaf
+ if ( valueExists )
{
- // The page hasn't been modified yet, we need to copy it first
- newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
+ // Nothing to do, just return
+ return ExistsResult.EXISTS;
}
- // Get the previous value from the leaf (it's a copy)
- valueHolder = newLeaf.values[pos];
- V replacedValue = null;
-
- if ( !valueExists )
- {
- valueHolder.set( value );
- newLeaf.values[pos] = valueHolder;
- }
- else
+ // If the page was created in a previous revision, copy it
+ if ( revision != transaction.getRevision() )
{
- // As strange as it sounds, we need to remove the value to reinject it.
- // There are cases where the value retrieval just use one part of the
- // value only (typically for LDAP Entries, where we use the DN)
- replacedValue = valueHolder.remove( value );
- valueHolder.set( value );
+ newLeaf = ( Leaf<K, V> ) copy( transaction, nbPageElems );
}
+ // Get the previous value from the leaf
+ V replacedValue = newLeaf.values[pos].get();
+ newLeaf.values[pos].set( value );
+
// Create the result
- InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue );
- result.addCopiedPage( this );
+ InsertResult<K, V> result = new ModifyResult<>( newLeaf, replacedValue );
+
+ // If we have copied a page, put it in the transaction
+ if ( revision != transaction.getRevision() )
+ {
+ transaction.addWALObject( newLeaf );
+
+ // And store the old leaf into teh CopiedPages B-tree, if we are not
+ // processing the CopiedPages B-tree itself
+ if ( btree.getType() != BTreeTypeEnum.COPIED_PAGES_BTREE )
+ {
+ transaction.addCopiedWALObject( this );
+ }
+ }
return result;
}
+
+ /**
+ * Add a new element in a page, at a gven position. The page will not be fulled up by this addition.
+ *
+ * @param transaction The {@link WriteTransaction} we are processing this update in
+ * @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 {@link InserResult} instance, containing a reference to the newly created Leaf.
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private InsertResult<K, V> modifyLeaf( WriteTransaction transaction, K key, V value, int pos ) throws IOException
+ {
+ Leaf<K, V> newLeaf = this;
+
+ // If the page was created in a previous revision, copy it
+ if ( revision != transaction.getRevision() )
+ {
+ newLeaf = ( Leaf<K, V> ) copy( transaction, nbPageElems );
+ }
+
+ // Inject the <K, V> into the new leaf
+ Page<K, V> modifiedPage = newLeaf.addElement( key, value, pos );
+
+ // And return a modified result
+ InsertResult<K, V> result = new ModifyResult<>( modifiedPage, null );
+
+ // Add the new leaf in the transaction pages map, and add
+ // the old leaf into the CopiedPages B-tree, if needed
+ if ( revision != transaction.getRevision() )
+ {
+ transaction.addWALObject( newLeaf );
+
+ if ( btree.getType() != BTreeTypeEnum.COPIED_PAGES_BTREE )
+ {
+ transaction.addCopiedWALObject( this );
+ }
+ }
+
+ return result;
+ }
+
/**
* Adds a new <K, V> into the current page at a given position. We return the
@@ -820,30 +804,30 @@ import org.apache.directory.mavibot.btre
* @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 )
+ private Page<K, V> addElement( K key, V value, int pos )
{
// Create the value holder
- ValueHolder<V> valueHolder = new ValueHolderImpl<V>( btree, value );
+ ValueHolder<V> valueHolder = new ValueHolder<>( btree, value );
// Deal with the special case of an empty page
- if ( nbElems == 0 )
+ if ( nbPageElems == 0 )
{
- keys[0] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+ keys[0] = new KeyHolder<>( btree.getKeySerializer(), key );
values[0] = valueHolder;
}
else
{
// Copy the keys and the values from the insertion point one position to the right
- int nbElementToMove = nbElems - pos;
+ int nbElementToMove = nbPageElems - pos;
System.arraycopy( keys, pos, keys, pos + 1, nbElementToMove );
System.arraycopy( values, pos, values, pos + 1, nbElementToMove );
// Add the new element
- keys[pos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+ keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
values[pos] = valueHolder;
}
- nbElems++;
+ nbPageElems++;
return this;
}
@@ -852,37 +836,40 @@ import org.apache.directory.mavibot.btre
/**
* 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/>
+ * 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 transaction The {@link WriteTransaction} we are processing this update in
* @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
+ * @return An {@SplitResult} instance containing the pivot, and the new left and right pages. We haven't
+ * created the new parent Node yet.
+ * @throws IOException If we have an error while trying to access the page
*/
- private InsertResult<K, V> addAndSplit( long revision, K key, V value, int pos )
+ private SplitResult<K, V> addAndSplit( WriteTransaction transaction, K key, V value, int pos ) throws IOException
{
- int middle = btree.getPageSize() >> 1;
- Leaf<K, V> leftLeaf = null;
- Leaf<K, V> rightLeaf = null;
- ValueHolder<V> valueHolder = new ValueHolderImpl<V>( btree, value );
+ long revision = transaction.getRevision();
+ int middle = btree.getPageNbElem() >> 1;
+ Leaf<K, V> leftLeaf;
+ Leaf<K, V> rightLeaf;
+ ValueHolder<V> valueHolder = new ValueHolder<>( btree, 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 );
+ leftLeaf = new Leaf<>( btree, revision, middle + 1 );
+ leftLeaf.initId( transaction.getRecordManagerHeader() );
// 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] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+ leftLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
leftLeaf.values[pos] = valueHolder;
// And copy the remaining elements
@@ -890,7 +877,8 @@ import org.apache.directory.mavibot.btre
System.arraycopy( values, pos, leftLeaf.values, pos + 1, middle - pos );
// Now, create the right page
- rightLeaf = new Leaf<K, V>( btree, revision, middle );
+ rightLeaf = new Leaf<>( btree, revision, middle );
+ rightLeaf.initId( transaction.getRecordManagerHeader() );
// Copy the keys and the values in the right page
System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
@@ -899,14 +887,16 @@ import org.apache.directory.mavibot.btre
else
{
// Create the left page
- leftLeaf = new Leaf<K, V>( btree, revision, middle );
+ leftLeaf = new Leaf<>( btree, revision, middle );
+ leftLeaf.initId( transaction.getRecordManagerHeader() );
// 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 );
+ rightLeaf = new Leaf<>( btree, revision, middle + 1 );
+ rightLeaf.initId( transaction.getRecordManagerHeader() );
int rightPos = pos - middle;
@@ -915,27 +905,39 @@ import org.apache.directory.mavibot.btre
System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
// Add the new element
- rightLeaf.keys[rightPos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+ rightLeaf.keys[rightPos] = new KeyHolder<>( btree.getKeySerializer(), 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 );
+ System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbPageElems - pos );
+ System.arraycopy( values, pos, rightLeaf.values, rightPos + 1, nbPageElems - pos );
}
// Get the pivot
K pivot = rightLeaf.keys[0].getKey();
+
+ // Inject the created leaves in the transaction
+ transaction.addWALObject( leftLeaf );
+ transaction.addWALObject( rightLeaf );
+
+ // And remove the original page from the transaction
+ transaction.removeWALObject( id );
+
+ // Add the old page into the CopiedPages B-tree if we aren't processing it
+ if ( btree.getType() != BTreeTypeEnum.COPIED_PAGES_BTREE )
+ {
+ transaction.addCopiedWALObject( this );
+ }
// Create the result
- InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
-
- return result;
+ return new SplitResult<>( pivot, leftLeaf, rightLeaf );
}
/**
* {@inheritDoc}
*/
+ @Override
public K getLeftMostKey()
{
return keys[0].getKey();
@@ -945,39 +947,43 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
+ @Override
public K getRightMostKey()
{
- return keys[nbElems - 1].getKey();
+ return keys[nbPageElems - 1].getKey();
}
/**
* {@inheritDoc}
*/
+ @Override
public Tuple<K, V> findLeftMost() throws IOException
{
K key = keys[0].getKey();
- return new Tuple<K, V>( key, values[0].get() );
+ return new Tuple<>( key, values[0].get() );
}
/**
* {@inheritDoc}
*/
- public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
+ @Override
+ public Tuple<K, V> findRightMost() throws IOException
{
- K key = keys[nbElems - 1].getKey();
- V value = values[nbElems - 1].get();
+ K key = keys[nbPageElems - 1].getKey();
+ V value = values[nbPageElems - 1].get();
- return new Tuple<K, V>( key, value );
+ return new Tuple<>( key, value );
}
/**
* {@inheritDoc}
*/
+ @Override
public boolean isLeaf()
{
return true;
@@ -987,6 +993,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
+ @Override
public boolean isNode()
{
return false;
@@ -994,8 +1001,222 @@ import org.apache.directory.mavibot.btre
/**
+ * Serialize a Leaf's Value.
+ */
+ private int serializeLeafValue( int pos, List<byte[]> serializedData )
+ throws IOException
+ {
+ ValueHolder<V> valueHolder = getValue( pos );
+ int dataSize = 0;
+
+ // We have a serialized value. Just flush it
+ byte[] data = valueHolder.getRaw();
+
+ // Store the data if it's not 0
+ if ( data.length > 0 )
+ {
+ serializedData.add( data );
+ dataSize = data.length;
+ }
+
+ return dataSize;
+ }
+
+
+ /**
+ * Serialize a Leaf's key
+ */
+ private int serializeLeafKey( int pos, List<byte[]> serializedData )
+ {
+ int dataSize = 0;
+ KeyHolder<K> keyHolder = getKeyHolder( pos );
+ byte[] keyData = keyHolder.getRaw();
+
+ if ( keyData != null )
+ {
+ // We have to store the serialized key data
+ serializedData.add( keyData );
+ dataSize += keyData.length;
+ }
+ else
+ {
+ throw new RuntimeException( "Key cannot be null" );
+ }
+
+ return dataSize;
+ }
+
+
+ /**
+ * Write a root page with no elements in it
+ */
+ private PageIO[] serializeRootPage( WriteTransaction transaction, long revision ) throws IOException
+ {
+ RecordManager recordManager = transaction.getRecordManager();
+ RecordManagerHeader recordManagerHeader = transaction.getRecordManagerHeader();
+
+ // We will have 1 single page if we have no elements
+ int bufferSize = RecordManager.LONG_SIZE + RecordManager.LONG_SIZE + RecordManager.INT_SIZE;
+
+ // This is either a new root page or a new page that will be filled later
+ pageIOs = recordManager.getFreePageIOs( recordManagerHeader, bufferSize );
+
+ // We need first to create a byte[] that will contain all the data
+ // For the root page, this is easy, as we only have to store the revision,
+ // and the number of elements, which is 0.
+ long position = 0L;
+
+ position = recordManager.store( recordManagerHeader, position, id, pageIOs[0] );
+ position = recordManager.store( recordManagerHeader, position, revision, pageIOs[0] );
+ position = recordManager.store( recordManagerHeader, position, 0, pageIOs[0] );
+
+ // Update the page size now
+ pageIOs[0].setSize( ( int ) position );
+
+ offset = pageIOs[0].getOffset();
+
+ return pageIOs;
+ }
+
+
+ /**
+ * Serialize a new Leaf. It will contain the following data :<br/>
+ * <ul>
+ * <li>the revision : a long</li>
+ * <li>the number of elements in the page : a positive int </li>
+ * <li>the keys : an array of serialized keys</li>
+ * <li>the values : an array of serialized values</li>
+ * </ul>
+ * {@inheritDoc}
+ */
+ @Override
+ public PageIO[] serialize( WriteTransaction transaction ) throws IOException
+ {
+ RecordManager recordManager = transaction.getRecordManager();
+ RecordManagerHeader recordManagerHeader = transaction.getRecordManagerHeader();
+
+ if ( nbPageElems == 0 )
+ {
+ return serializeRootPage( transaction, revision );
+ }
+ else
+ {
+ // Prepare a list of byte[] that will contain the serialized page
+ int nbBuffers = 1 + 1 + 1 + 1 + nbPageElems * 2;
+ int dataSize = 0;
+ int serializedSize = 0;
+
+ // Now, we can create the list with the right size
+ List<byte[]> serializedData = new ArrayList<>( nbBuffers );
+
+ // The id
+ byte[] buffer = LongSerializer.serialize( id );
+ serializedData.add( buffer );
+ serializedSize += buffer.length;
+
+ // The revision
+ buffer = LongSerializer.serialize( revision );
+ serializedData.add( buffer );
+ serializedSize += buffer.length;
+
+ // The number of elements
+ buffer = IntSerializer.serialize( nbPageElems );
+ serializedData.add( buffer );
+ serializedSize += buffer.length;
+
+ // Iterate on the keys and values. We first serialize the value, then the key
+ // until we are done with all of them. If we are serializing a page, we have
+ // to serialize one more value
+ for ( int pos = 0; pos < nbPageElems; pos++ )
+ {
+ // Start with the value
+ dataSize += serializeLeafValue( pos, serializedData );
+ dataSize += serializeLeafKey( pos, serializedData );
+ }
+
+ // Store the data size
+ buffer = IntSerializer.serialize( dataSize );
+ serializedData.add( 3, buffer );
+ serializedSize += buffer.length;
+
+ serializedSize += dataSize;
+
+ // We are done. Allocate the pages we need to store the data, if we don't have
+ // a pageIOs or not enough room in it.
+ if ( pageIOs != null )
+ {
+ int nbNeededPages = RecordManager.computeNbPages( recordManagerHeader, dataSize );
+
+ if ( nbNeededPages > pageIOs.length )
+ {
+ pageIOs = recordManager.getFreePageIOs( recordManagerHeader, serializedSize );
+ }
+ else
+ {
+ // Resize the page
+ pageIOs[0].setSize( serializedSize );
+ }
+ }
+ else
+ {
+ pageIOs = recordManager.getFreePageIOs( recordManagerHeader, serializedSize );
+ }
+
+ // And store the data into those pages
+ long position = 0L;
+
+ for ( byte[] bytes : serializedData )
+ {
+ position = recordManager.storeRaw( recordManagerHeader, position, bytes, pageIOs );
+ }
+
+ offset = pageIOs[0].getOffset();
+
+ return pageIOs;
+ }
+ }
+
+
+ /**
+ * Deserialize a Leaf. It will contain the following data :<br/>
+ * <ul>
+ * <li>the ID : a long</li>
+ * <li>the revision : a long</li>
+ * <li>the number of elements in the page : a positive int </li>
+ * <li>the size of the values/keys when serialized
+ * <li>the keys : an array of serialized keys</li>
+ * <li>the values : an array of serialized values</li>
+ * </ul>
+ *
+ * The three first values have already been deserialized by the caller.
+ * {@inheritDoc}
+ */
+ @Override
+ public Page<K, V> deserialize( Transaction transaction, ByteBuffer byteBuffer ) throws IOException
+ {
+ // Iterate on the keys and values. We first serialize the value, then the key
+ // until we are done with all of them. If we are serializing a page, we have
+ // to serialize one more value
+ for ( int pos = 0; pos < nbPageElems; pos++ )
+ {
+ // Start with the value
+ V value = btree.getValueSerializer().deserialize( byteBuffer );
+ ValueHolder<V> valueHolder = new ValueHolder<>( btree, value );
+ BTreeFactory.setValue( btree, this, pos, valueHolder );
+
+ // Then the key
+ K key = btree.getKeySerializer().deserialize( byteBuffer );
+ BTreeFactory.setKey( btree, this, pos, key );
+ }
+
+ return this;
+ }
+
+
+ /**
* @see Object#toString()
*/
+ @Override
public String toString()
{
StringBuilder sb = new StringBuilder();
@@ -1005,11 +1226,11 @@ import org.apache.directory.mavibot.btre
sb.append( "] -> {" );
- if ( nbElems > 0 )
+ if ( nbPageElems > 0 )
{
boolean isFirst = true;
- for ( int i = 0; i < nbElems; i++ )
+ for ( int i = 0; i < nbPageElems; i++ )
{
if ( isFirst )
{
@@ -1045,15 +1266,18 @@ import org.apache.directory.mavibot.btre
* same as {@link #addElement(long, Object, Object, int)} except the values are not copied.
* This method is only used while inserting an element into a sub-BTree.
*/
- private Page<K, V> addSubTreeElement( long revision, K key, int pos )
+ private Page<K, V> addSubTreeElement( WriteTransaction transaction, K key, int pos )
{
+ long revision = transaction.getRevision();
+
// 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 );
+ Leaf<K, V> newLeaf = new Leaf<>( btree, revision, nbPageElems + 1 );
+ newLeaf.initId( transaction.getRecordManagerHeader() );
// Deal with the special case of an empty page
- if ( nbElems == 0 )
+ if ( nbPageElems == 0 )
{
- newLeaf.keys[0] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+ newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
}
else
{
@@ -1061,7 +1285,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
// Add the new element
- newLeaf.keys[pos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+ newLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
// And copy the remaining elements
System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length - pos );
@@ -1075,29 +1299,33 @@ import org.apache.directory.mavibot.btre
* same as {@link #addAndSplit(long, Object, Object, int)} except the values are not copied.
* This method is only used while inserting an element into a sub-BTree.
*/
- private InsertResult<K, V> addAndSplitSubTree( long revision, K key, int pos )
+ private InsertResult<K, V> addAndSplitSubTree( WriteTransaction transaction, K key, int pos )
{
- int middle = btree.getPageSize() >> 1;
- Leaf<K, V> leftLeaf = null;
- Leaf<K, V> rightLeaf = null;
+ long revision = transaction.getRevision();
+
+ int middle = btree.getPageNbElem() >> 1;
+ Leaf<K, V> leftLeaf;
+ Leaf<K, V> rightLeaf;
// 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 );
+ leftLeaf = new Leaf<>( btree, revision, middle + 1 );
+ leftLeaf.initId( transaction.getRecordManagerHeader() );
// Copy the keys and the values up to the insertion position
System.arraycopy( keys, 0, leftLeaf.keys, 0, pos );
// Add the new element
- leftLeaf.keys[pos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+ leftLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
// And copy the remaining elements
System.arraycopy( keys, pos, leftLeaf.keys, pos + 1, middle - pos );
// Now, create the right page
- rightLeaf = new Leaf<K, V>( btree, revision, middle );
+ rightLeaf = new Leaf<>( btree, revision, middle );
+ rightLeaf.initId( transaction.getRecordManagerHeader() );
// Copy the keys and the values in the right page
System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
@@ -1105,13 +1333,15 @@ import org.apache.directory.mavibot.btre
else
{
// Create the left page
- leftLeaf = new Leaf<K, V>( btree, revision, middle );
+ leftLeaf = new Leaf<>( btree, revision, middle );
+ leftLeaf.initId( transaction.getRecordManagerHeader() );
// Copy all the element into the left page
System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
// Now, create the right page
- rightLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+ rightLeaf = new Leaf<>( btree, revision, middle + 1 );
+ rightLeaf.initId( transaction.getRecordManagerHeader() );
int rightPos = pos - middle;
@@ -1119,36 +1349,34 @@ import org.apache.directory.mavibot.btre
System.arraycopy( keys, middle, rightLeaf.keys, 0, rightPos );
// Add the new element
- rightLeaf.keys[rightPos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+ rightLeaf.keys[rightPos] = new KeyHolder<K>( btree.getKeySerializer(), key );
// And copy the remaining elements
- System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems - pos );
+ System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbPageElems - pos );
}
// Get the pivot
K pivot = rightLeaf.keys[0].getKey();
// Create the result
- InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
-
- return result;
+ return new SplitResult<>( pivot, leftLeaf, rightLeaf );
}
/**
* {@inheritDoc}
*/
- public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+ public KeyCursor<K> browseKeys( ReadTransaction transaction, ParentPos<K, K>[] stack, int depth )
{
int pos = 0;
- KeyCursor<K> cursor = null;
+ KeyCursor<K> cursor;
- if ( nbElems == 0 )
+ if ( nbPageElems == 0 )
{
// The tree is empty, it's the root, we have nothing to return
- stack[depth] = new ParentPos<K, K>( null, -1 );
+ stack[depth] = new ParentPos<>( null, -1 );
- return new KeyCursor<K>( transaction, stack, depth );
+ return new KeyCursor<>( transaction, stack, depth );
}
else
{
@@ -1157,7 +1385,7 @@ import org.apache.directory.mavibot.btre
stack[depth] = parentPos;
- cursor = new KeyCursor<K>( transaction, stack, depth );
+ cursor = new KeyCursor<>( transaction, stack, depth );
}
return cursor;
@@ -1175,19 +1403,65 @@ import org.apache.directory.mavibot.btre
/**
+ * @return the values
+ */
+ /* no qualifier */ValueHolder<V>[] getValues()
+ {
+ return values;
+ }
+
+
+ /**
+ * @param values the values to set
+ */
+ /* no qualifier */void setValues( ValueHolder<V>[] values )
+ {
+ this.values = values;
+ }
+
+
+ /**
* {@inheritDoc}
*/
+ @Override
+ public String prettyPrint()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "{Leaf(" ).append( id ).append( ")@" );
+
+ if ( offset == RecordManager.NO_PAGE )
+ {
+ sb.append( "---" );
+ }
+ else
+ {
+ sb.append( String.format( "0x%4X", offset ) );
+ }
+
+ sb.append( ",<" );
+ sb.append( getName() ).append( ':' ).append( getRevision() );
+ sb.append( ">}" );
+
+ return sb.toString();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
public String dumpPage( String tabs )
{
StringBuilder sb = new StringBuilder();
sb.append( tabs );
- if ( nbElems > 0 )
+ if ( nbPageElems > 0 )
{
boolean isFirst = true;
- for ( int i = 0; i < nbElems; i++ )
+ for ( int i = 0; i < nbPageElems; i++ )
{
if ( isFirst )
{
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/LevelInfo.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/LevelInfo.java?rev=1784232&r1=1784231&r2=1784232&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/LevelInfo.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/LevelInfo.java Fri Feb 24 07:16:37 2017
@@ -82,7 +82,7 @@ public class LevelInfo<K, V>
/**
* @return the nbElems
*/
- public int getNbElems()
+ public int getNbPageElems()
{
return nbElems;
}
@@ -254,7 +254,7 @@ public class LevelInfo<K, V>
sb.append( "\n nbAddedElems = " ).append( nbAddedElems );
sb.append( "\n currentPos = " ).append( currentPos );
sb.append( "\n currentPage" );
- sb.append( "\n nbKeys : " ).append( currentPage.getNbElems() );
+ sb.append( "\n nbKeys : " ).append( currentPage.getNbPageElems() );
return sb.toString();
}