You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2013/12/18 12:01:11 UTC
svn commit: r1551908 [1/3] - in /directory/mavibot/trunk/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
main/java/org/apache/directory/mavibot/btree/persisted/
main/java/org/apache/directory/mavibot/btree/serializer/
test/java/org/apache/di...
Author: elecharny
Date: Wed Dec 18 11:01:10 2013
New Revision: 1551908
URL: http://svn.apache.org/r1551908
Log:
o Fixed MAVIBOT-20 (the allowDuplicate flag was ignored)
o Added many specific exceptions to replace the RuntimeException beig thrown (MAVIBOT-30)
o No need to call the BTree.init() method anymore for most of the cases
o Removed the RevisionName* classes from the persisted package
o Removed the spaces at the end of each line
Removed:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/RevisionName.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/RevisionNameComparator.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/RevisionNameSerializer.java
Modified:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeBuilder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedPageHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionNameSerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/BooleanSerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/ByteArraySerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/ByteSerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/CharArraySerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/CharSerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/IntSerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/LongSerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/ShortSerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/StringSerializer.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeDuplicateKeyTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeDuplicateKeyTest.java
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java?rev=1551908&r1=1551907&r2=1551908&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java Wed Dec 18 11:01:10 2013
@@ -31,7 +31,9 @@ import java.nio.channels.FileChannel;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.ReentrantLock;
+import org.apache.directory.mavibot.btree.exception.InitializationException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.exception.MissingSerializerException;
import org.apache.directory.mavibot.btree.serializer.BufferHandler;
import org.apache.directory.mavibot.btree.serializer.LongSerializer;
import org.slf4j.Logger;
@@ -40,7 +42,7 @@ import org.slf4j.LoggerFactory;
/**
* The B+Tree MVCC data structure.
- *
+ *
* @param <K> The type for the keys
* @param <V> The type for the stored values
*
@@ -76,7 +78,7 @@ import org.slf4j.LoggerFactory;
/**
- * Creates a new BTree, with no initialization.
+ * Creates a new BTree, with no initialization.
*/
/* no qualifier */ InMemoryBTree()
{
@@ -87,9 +89,9 @@ import org.slf4j.LoggerFactory;
/**
- * Creates a new in-memory BTree using the BTreeConfiguration to initialize the
+ * Creates a new in-memory BTree using the BTreeConfiguration to initialize the
* BTree
- *
+ *
* @param configuration The configuration to use
*/
/* no qualifier */ InMemoryBTree( InMemoryBTreeConfiguration<K, V> configuration )
@@ -140,14 +142,14 @@ import org.slf4j.LoggerFactory;
}
catch ( IOException ioe )
{
- throw new RuntimeException( ioe.getMessage() );
+ throw new InitializationException( ioe.getMessage() );
}
}
/**
* Initialize the BTree.
- *
+ *
* @throws IOException If we get some exception while initializing the BTree
*/
public void init() throws IOException
@@ -181,7 +183,7 @@ import org.slf4j.LoggerFactory;
{
if ( file.length() > 0 )
{
- // We have some existing file, load it
+ // We have some existing file, load it
load( file );
}
@@ -197,7 +199,7 @@ import org.slf4j.LoggerFactory;
applyJournal();
}
}
- else
+ else
{
setType( BTreeTypeEnum.IN_MEMORY );
}
@@ -229,12 +231,12 @@ import org.slf4j.LoggerFactory;
/**
- *
+ *
* Deletes the given <key,value> pair if both key and value match. If the given value is null
* and there is no null value associated with the given key then the entry with the given key
* will be removed.
*
- * @param key The key to be removed
+ * @param key The key to be removed
* @param value The value to be removed (can be null, and when no null value exists the key will be removed irrespective of the value)
* @param revision The revision to be associated with this operation
* @return
@@ -376,7 +378,7 @@ import org.slf4j.LoggerFactory;
/**
* Write the data in the ByteBuffer, and eventually on disk if needed.
- *
+ *
* @param channel The channel we want to write to
* @param bb The ByteBuffer we want to feed
* @param buffer The data to inject
@@ -445,12 +447,12 @@ import org.slf4j.LoggerFactory;
if ( keySerializer == null )
{
- throw new RuntimeException( "Cannot flush the btree without a Key serializer" );
+ throw new MissingSerializerException( "Cannot flush the btree without a Key serializer" );
}
if ( valueSerializer == null )
{
- throw new RuntimeException( "Cannot flush the btree without a Value serializer" );
+ throw new MissingSerializerException( "Cannot flush the btree without a Value serializer" );
}
// Write the number of elements first
@@ -492,9 +494,9 @@ import org.slf4j.LoggerFactory;
}
- /**
+ /**
* Inject all the modification from the journal into the btree
- *
+ *
* @throws IOException If we had some issue while reading the journal
*/
private void applyJournal() throws IOException
@@ -517,7 +519,7 @@ import org.slf4j.LoggerFactory;
{
while ( true )
{
- // Read the type
+ // Read the type
byte[] type = bufferHandler.read( 1 );
if ( type[0] == Modification.ADDITION )
@@ -555,9 +557,9 @@ import org.slf4j.LoggerFactory;
/**
- * Read the data from the disk into this BTree. All the existing data in the
+ * Read the data from the disk into this BTree. All the existing data in the
* BTree are kept, the read data will be associated with a new revision.
- *
+ *
* @param file
* @throws IOException
*/
@@ -615,7 +617,7 @@ import org.slf4j.LoggerFactory;
/**
* Get the rootPzge associated to a give revision.
- *
+ *
* @param revision The revision we are looking for
* @return The rootPage associated to this revision
* @throws IOException If we had an issue while accessing the underlying file
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java?rev=1551908&r1=1551907&r2=1551908&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java Wed Dec 18 11:01:10 2013
@@ -60,7 +60,6 @@ public class InMemoryBTreeBuilder<K, V>
public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException
{
BTree<K, V> btree = BTreeFactory.createInMemoryBTree( name, keySerializer, valueSerializer );
- btree.init();
List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>();
@@ -70,7 +69,7 @@ public class InMemoryBTreeBuilder<K, V>
lstLeaves.add( leaf1 );
int leafIndex = 0;
-
+
while ( sortedTupleItr.hasNext() )
{
Tuple<K, V> tuple = sortedTupleItr.next();
@@ -83,7 +82,7 @@ public class InMemoryBTreeBuilder<K, V>
leafIndex++;
totalTupleCount++;
-
+
if ( ( totalTupleCount % numKeysInNode ) == 0 )
{
leafIndex = 0;
@@ -99,7 +98,7 @@ public class InMemoryBTreeBuilder<K, V>
// remove null keys and values from the last leaf and resize
InMemoryLeaf<K, V> lastLeaf = (InMemoryLeaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
-
+
for ( int i = 0; i < lastLeaf.getNbElems(); i++ )
{
if ( lastLeaf.getKeys()[i] == null )
@@ -122,7 +121,7 @@ public class InMemoryBTreeBuilder<K, V>
Page<K, V> rootPage = attachNodes( lstLeaves, btree );
System.out.println("built rootpage : " + rootPage);
-
+
((AbstractBTree<K, V>)btree).setRootPage( rootPage );
return btree;
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java?rev=1551908&r1=1551907&r2=1551908&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java Wed Dec 18 11:01:10 2013
@@ -23,13 +23,14 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
import java.lang.reflect.Array;
+import org.apache.directory.mavibot.btree.exception.DuplicateValueNotAllowedException;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
/**
* 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
*
@@ -43,7 +44,7 @@ import org.apache.directory.mavibot.btre
/**
* Constructor used to create a new Leaf when we read it from a file.
- *
+ *
* @param btree The BTree this page belongs to.
*/
InMemoryLeaf( BTree<K, V> btree )
@@ -54,7 +55,7 @@ import org.apache.directory.mavibot.btre
/**
* 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
@@ -156,7 +157,7 @@ import org.apache.directory.mavibot.btre
if ( valueHolder.contains( value ) )
{
// this is a case to delete entire <K,sub-BTree> or <K,single-V>
- if ( valueHolder.size() == 1 )
+ if ( valueHolder.size() == 1 )
{
// Ok, we can remove the value
removedElement = new Tuple<K, V>( getKey( index ), null ); // the entire value was removed
@@ -213,7 +214,7 @@ import org.apache.directory.mavibot.btre
// 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( (InMemoryNode<K, V> ) parent, parentPos );
+ int siblingPos = selectSibling( parent, parentPos );
InMemoryLeaf<K, V> sibling = (InMemoryLeaf<K, V> ) ( ( (InMemoryNode<K, V> ) parent ).getPage( siblingPos ) );
if ( sibling.getNbElems() == halfSize )
@@ -273,7 +274,7 @@ import org.apache.directory.mavibot.btre
/**
* 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
@@ -335,12 +336,12 @@ import org.apache.directory.mavibot.btre
* 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
+ * @throws IOException If we have an error while trying to access the page
*/
private DeleteResult<K, V> borrowFromLeft( Tuple<K, V> removedElement, long revision, InMemoryLeaf<K, V> sibling, int pos )
throws IOException
@@ -382,12 +383,12 @@ import org.apache.directory.mavibot.btre
* 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
+ * @throws IOException If we have an error while trying to access the page
*/
private DeleteResult<K, V> borrowFromRight( Tuple<K, V> removedElement, long revision, InMemoryLeaf<K, V> sibling, int pos )
throws IOException
@@ -475,9 +476,9 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
InMemoryValueHolder<V> valueHolder = (InMemoryValueHolder<V> ) values[-( pos + 1 )];
-
+
V value = valueHolder.getCursor().next();
-
+
return value;
}
else
@@ -537,7 +538,7 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
ValueHolder<V> valueHolder = values[-( pos + 1 )];
-
+
return valueHolder.contains( value );
}
else
@@ -588,7 +589,7 @@ import org.apache.directory.mavibot.btre
// Start at the beginning of the page
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-
+
// Create the value cursor
parentPos.valueCursor = values[pos].getCursor();
@@ -605,7 +606,7 @@ import org.apache.directory.mavibot.btre
// Create the value cursor
parentPos.valueCursor = values[pos].getCursor();
-
+
stack[depth] = parentPos;
cursor = new TupleCursor<K, V>( transaction, stack, depth );
@@ -617,11 +618,11 @@ import org.apache.directory.mavibot.btre
// Create the value cursor
parentPos.valueCursor = values[nbElems - 1].getCursor();
-
+
stack[depth] = parentPos;
cursor = new TupleCursor<K, V>( transaction, stack, depth );
-
+
try
{
cursor.afterLast();
@@ -679,7 +680,7 @@ 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
* @return The copied page
@@ -698,7 +699,7 @@ 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 key The new key
* @param value the new value
@@ -711,6 +712,17 @@ import org.apache.directory.mavibot.btre
{
InMemoryLeaf<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 );
+
+ // Check we can add a new value
+ if ( !valueExists && !btree.isAllowDuplicates() )
+ {
+ throw new DuplicateValueNotAllowedException( "Duplicate values are not allowed" );
+ }
+
if ( this.revision != revision )
{
// The page hasn't been modified yet, we need to copy it first
@@ -718,10 +730,10 @@ import org.apache.directory.mavibot.btre
}
// Get the previous value from the leaf (it's a copy)
- ValueHolder<V> valueHolder = newLeaf.values[pos];
+ valueHolder = newLeaf.values[pos];
V replacedValue = null;
- if ( !valueHolder.contains( value ) )
+ if ( !valueExists )
{
valueHolder.add( value );
newLeaf.values[pos] = valueHolder;
@@ -746,7 +758,7 @@ import org.apache.directory.mavibot.btre
/**
* 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
@@ -794,7 +806,7 @@ import org.apache.directory.mavibot.btre
* 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
@@ -896,8 +908,8 @@ import org.apache.directory.mavibot.btre
return new Tuple<K, V>( getKey( nbElems - 1 ), val );
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -905,8 +917,8 @@ import org.apache.directory.mavibot.btre
{
return true;
}
-
-
+
+
/**
* {@inheritDoc}
*/
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java?rev=1551908&r1=1551907&r2=1551908&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java Wed Dec 18 11:01:10 2013
@@ -25,12 +25,13 @@ import java.lang.reflect.Array;
import java.util.Comparator;
import java.util.UUID;
+import org.apache.directory.mavibot.btree.exception.BTreeOperationException;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
/**
* A holder to store the Values
- *
+ *
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
* @param <V> The value type
*/
@@ -38,7 +39,7 @@ import org.apache.directory.mavibot.btre
{
/**
* Creates a new instance of a ValueHolder, containing the serialized values.
- *
+ *
* @param parentBtree the parent BTree
* @param valueSerializer The Value's serializer
* @param raw The raw data containing the values
@@ -59,7 +60,7 @@ import org.apache.directory.mavibot.btre
/**
* Creates a new instance of a ValueHolder, containing Values. This constructor is called
* when we need to create a new ValueHolder with deserialized values.
- *
+ *
* @param parentBtree The parent BTree
* @param values The Values stored in the ValueHolder
*/
@@ -139,8 +140,8 @@ import org.apache.directory.mavibot.btre
valueBtree = subBtree;
valueArray = null;
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -160,18 +161,18 @@ import org.apache.directory.mavibot.btre
return removedValue;
}
-
+
/**
* Remove the value from a sub btree
*/
private V removeFromBtree( V removedValue )
{
V returnedValue = null;
-
+
try
{
Tuple<V, V> removedTuple = valueBtree.delete( removedValue );
-
+
if ( removedTuple != null )
{
returnedValue = removedTuple.getKey();
@@ -179,7 +180,7 @@ import org.apache.directory.mavibot.btre
}
catch ( IOException e )
{
- throw new RuntimeException( e );
+ throw new BTreeOperationException( e );
}
if ( valueBtree.getNbElems() == 1 )
@@ -194,18 +195,18 @@ import org.apache.directory.mavibot.btre
}
catch ( EndOfFileExceededException e )
{
- throw new RuntimeException( e );
+ throw new BTreeOperationException( e );
}
catch ( IOException e )
{
- throw new RuntimeException( e );
+ throw new BTreeOperationException( e );
}
}
-
+
return returnedValue;
}
-
-
+
+
/**
* Remove a value from an array
*/
@@ -225,12 +226,12 @@ import org.apache.directory.mavibot.btre
{
V returnedValue = valueArray[0];
nbArrayElems = 0;
-
+
return returnedValue;
}
}
-
+
/**
* {@inheritDoc}
*/
@@ -254,7 +255,7 @@ import org.apache.directory.mavibot.btre
Comparator<V> comparator = valueSerializer.getComparator();
int result = comparator.compare( checkedValue, valueArray[0] );
-
+
return result == 0;
}
}
@@ -276,15 +277,15 @@ import org.apache.directory.mavibot.btre
else
{
sb.append( ", {" );
-
+
if ( size() != 0 )
{
sb.append( valueArray[0] );
}
-
+
sb.append( "}" );
}
-
+
sb.append( "]" );
return sb.toString();
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeBuilder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeBuilder.java?rev=1551908&r1=1551907&r2=1551908&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeBuilder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeBuilder.java Wed Dec 18 11:01:10 2013
@@ -62,10 +62,9 @@ public class PersistedBTreeBuilder<K, V>
public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws Exception
{
BTree<K, V> btree = BTreeFactory.createPersistedBTree( name, keySerializer, valueSerializer );
- btree.init();
rm.manage( btree );
-
+
List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>();
int totalTupleCount = 0;
@@ -78,7 +77,7 @@ public class PersistedBTreeBuilder<K, V>
while ( sortedTupleItr.hasNext() )
{
Tuple<K, V> tuple = sortedTupleItr.next();
-
+
BTreeFactory.setKey( btree, leaf1, leafIndex, tuple.getKey() );
PersistedValueHolder<V> eh = new PersistedValueHolder<V>( btree, tuple.getValue() );
@@ -90,13 +89,13 @@ public class PersistedBTreeBuilder<K, V>
if ( ( totalTupleCount % numKeysInNode ) == 0 )
{
leafIndex = 0;
-
- PersistedPageHolder<K, V> pageHolder = (PersistedPageHolder<K, V> ) rm.writePage( btree, leaf1, 1 );
-
+
+ PersistedPageHolder<K, V> pageHolder = rm.writePage( btree, leaf1, 1 );
+
leaf1 = (PersistedLeaf<K, V>)BTreeFactory.createLeaf( btree, 0, numKeysInNode );
lstLeaves.add( leaf1 );
}
-
+
//TODO build the whole tree in chunks rather than processing *all* leaves at first
}
@@ -122,7 +121,7 @@ public class PersistedBTreeBuilder<K, V>
lastLeaf.values = (PersistedValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class, n );
System.arraycopy( values, 0, lastLeaf.values, 0, n );
- PersistedPageHolder<K, V> pageHolder = (PersistedPageHolder<K, V> ) rm.writePage( btree, lastLeaf, 1 );
+ PersistedPageHolder<K, V> pageHolder = rm.writePage( btree, lastLeaf, 1 );
break;
}
@@ -134,13 +133,13 @@ public class PersistedBTreeBuilder<K, V>
//System.out.println("built rootpage : " + rootPage);
((PersistedBTree<K, V>)btree).setNbElems( totalTupleCount );
-
+
rm.updateBtreeHeader( btree, ( ( AbstractPage<K, V> ) rootPage ).getOffset() );
-
+
rm.addFreePages( btree, Arrays.asList( btree.getRootPage() ) );
-
+
((AbstractBTree<K, V>)btree).setRootPage( rootPage );
-
+
return btree;
}
@@ -177,8 +176,8 @@ public class PersistedBTreeBuilder<K, V>
if ( ( totalNodes % numChildren ) == 0 )
{
i = 0;
-
- PersistedPageHolder<K, V> pageHolder = (PersistedPageHolder<K, V> ) rm.writePage( btree, node, 1 );
+
+ PersistedPageHolder<K, V> pageHolder = rm.writePage( btree, node, 1 );
node = (PersistedNode<K, V>)BTreeFactory.createNode( btree, 0, numKeysInNode );
lstNodes.add( node );
@@ -199,7 +198,7 @@ public class PersistedBTreeBuilder<K, V>
lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) );
System.arraycopy( keys, 0, lastNode.getKeys(), 0, n );
- PersistedPageHolder<K, V> pageHolder = (PersistedPageHolder<K, V> ) rm.writePage( btree, lastNode, 1 );
+ PersistedPageHolder<K, V> pageHolder = rm.writePage( btree, lastNode, 1 );
break;
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java?rev=1551908&r1=1551907&r2=1551908&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java Wed Dec 18 11:01:10 2013
@@ -23,13 +23,14 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
import java.lang.reflect.Array;
+import org.apache.directory.mavibot.btree.exception.DuplicateValueNotAllowedException;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
/**
* 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
*
@@ -43,7 +44,7 @@ import org.apache.directory.mavibot.btre
/**
* Constructor used to create a new Leaf when we read it from a file.
- *
+ *
* @param btree The BTree this page belongs to.
*/
PersistedLeaf( BTree<K, V> btree )
@@ -54,7 +55,7 @@ import org.apache.directory.mavibot.btre
/**
* 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
@@ -203,7 +204,7 @@ import org.apache.directory.mavibot.btre
// 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( (PersistedNode<K, V> ) parent, parentPos );
+ int siblingPos = selectSibling( parent, parentPos );
PersistedLeaf<K, V> sibling = (PersistedLeaf<K, V> ) ( ( (PersistedNode<K, V> ) parent ).getPage( siblingPos ) );
if ( sibling.getNbElems() == halfSize )
@@ -252,13 +253,13 @@ import org.apache.directory.mavibot.btre
// Copy the keys and the values
System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
-
+
// Replace the ValueHolder now
try
{
ValueHolder<V> newValueHolder = valueHolder.clone();
newValueHolder.remove( value );
-
+
newLeaf.values[pos] = newValueHolder;
}
catch ( CloneNotSupportedException e )
@@ -277,7 +278,7 @@ import org.apache.directory.mavibot.btre
/**
* 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
@@ -338,12 +339,12 @@ import org.apache.directory.mavibot.btre
* 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
+ * @throws IOException If we have an error while trying to access the page
*/
private DeleteResult<K, V> borrowFromLeft( Tuple<K, V> removedElement, long revision, PersistedLeaf<K, V> sibling, int pos )
throws IOException
@@ -385,12 +386,12 @@ import org.apache.directory.mavibot.btre
* 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
+ * @throws IOException If we have an error while trying to access the page
*/
private DeleteResult<K, V> borrowFromRight( Tuple<K, V> removedElement, long revision, PersistedLeaf<K, V> sibling, int pos )
throws IOException
@@ -464,16 +465,16 @@ import org.apache.directory.mavibot.btre
{
System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
-
+
// We still have to clone the modified value holder
ValueHolder<V> valueHolder = newLeaf.values[pos];
-
+
try
{
ValueHolder<V> newValueHolder = valueHolder.clone();
-
+
newValueHolder.remove( removedValue );
-
+
newLeaf.values[pos] = newValueHolder;
}
catch ( CloneNotSupportedException e )
@@ -635,7 +636,7 @@ import org.apache.directory.mavibot.btre
// Start at the beginning of the page
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-
+
// Create the value cursor
parentPos.valueCursor = values[pos].getCursor();
@@ -664,11 +665,11 @@ import org.apache.directory.mavibot.btre
// Create the value cursor
parentPos.valueCursor = values[nbElems - 1].getCursor();
-
+
stack[depth] = parentPos;
cursor = new TupleCursor<K, V>( transaction, stack, depth );
-
+
try
{
cursor.afterLast();
@@ -711,7 +712,7 @@ import org.apache.directory.mavibot.btre
{
// Start at the beginning of the page
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-
+
// Create the value cursor
parentPos.valueCursor = values[0].getCursor();
@@ -726,7 +727,7 @@ 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
* @return The copied page
@@ -753,7 +754,7 @@ import org.apache.directory.mavibot.btre
// TODO Auto-generated catch block
e.printStackTrace();
}
-
+
// Stop when we have copied nbElems values
if ( pos == nbElems )
{
@@ -767,7 +768,7 @@ 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 key The new key
* @param value the new value
@@ -780,6 +781,17 @@ import org.apache.directory.mavibot.btre
{
PersistedLeaf<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 );
+
+ // Check we can add a new value
+ if ( !valueExists && !btree.isAllowDuplicates() )
+ {
+ throw new DuplicateValueNotAllowedException( "Duplicate values are not allowed" );
+ }
+
if ( this.revision != revision )
{
// The page hasn't been modified yet, we need to copy it first
@@ -787,10 +799,10 @@ import org.apache.directory.mavibot.btre
}
// Get the previous value from the leaf (it's a copy)
- ValueHolder<V> valueHolder = newLeaf.values[pos];
+ valueHolder = newLeaf.values[pos];
V replacedValue = null;
- if ( !valueHolder.contains( value ) )
+ if ( !valueExists )
{
valueHolder.add( value );
newLeaf.values[pos] = valueHolder;
@@ -815,7 +827,7 @@ import org.apache.directory.mavibot.btre
/**
* 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
@@ -864,7 +876,7 @@ import org.apache.directory.mavibot.btre
* 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
@@ -1016,8 +1028,8 @@ import org.apache.directory.mavibot.btre
cursor.close();
}
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -1025,8 +1037,8 @@ import org.apache.directory.mavibot.btre
{
return true;
}
-
-
+
+
/**
* {@inheritDoc}
*/
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedPageHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedPageHolder.java?rev=1551908&r1=1551907&r2=1551908&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedPageHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedPageHolder.java Wed Dec 18 11:01:10 2013
@@ -25,14 +25,15 @@ import java.io.IOException;
import net.sf.ehcache.Cache;
import net.sf.ehcache.Element;
+import org.apache.directory.mavibot.btree.exception.BTreeOperationException;
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.
- *
+ * 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
@@ -43,7 +44,7 @@ import org.apache.directory.mavibot.btre
{
/** The RecordManager */
private RecordManager recordManager;
-
+
/** The cache */
private Cache cache;
@@ -56,7 +57,7 @@ import org.apache.directory.mavibot.btre
/**
* Create a new holder storing an offset and a SoftReference containing the element.
- *
+ *
* @param page The element to store into a SoftReference
*/
public PersistedPageHolder( BTree<K, V> btree, Page<K, V> page )
@@ -76,7 +77,7 @@ import org.apache.directory.mavibot.btre
/**
* Create a new holder storing an offset and a SoftReference containing the element.
- *
+ *
* @param page The element to store into a SoftReference
*/
public PersistedPageHolder( BTree<K, V> btree, Page<K, V> page, long offset, long lastOffset )
@@ -99,8 +100,8 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
- * @throws IOException
- * @throws EndOfFileExceededException
+ * @throws IOException
+ * @throws EndOfFileExceededException
*/
public Page<K, V> getValue()
{
@@ -143,16 +144,16 @@ import org.apache.directory.mavibot.btre
try
{
Page<K, V> element = recordManager.deserialize( btree, offset );
-
+
return element;
}
catch ( EndOfFileExceededException eofee )
{
- throw new RuntimeException( eofee.getMessage() );
+ throw new BTreeOperationException( eofee.getMessage() );
}
catch ( IOException ioe )
{
- throw new RuntimeException( ioe.getMessage() );
+ throw new BTreeOperationException( ioe.getMessage() );
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java?rev=1551908&r1=1551907&r2=1551908&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java Wed Dec 18 11:01:10 2013
@@ -25,14 +25,16 @@ import java.lang.reflect.Array;
import java.util.Comparator;
import java.util.UUID;
+import org.apache.directory.mavibot.btree.exception.BTreeAlreadyCreatedException;
import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
+import org.apache.directory.mavibot.btree.exception.BTreeCreationException;
import org.apache.directory.mavibot.btree.serializer.IntSerializer;
import org.apache.directory.mavibot.btree.serializer.LongSerializer;
/**
* A holder to store the Values
- *
+ *
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
* @param <V> The value type
*/
@@ -43,17 +45,17 @@ import org.apache.directory.mavibot.btre
/** The serialized value */
private byte[] raw;
-
+
/** A flag set to true when the raw value has been deserialized */
private boolean isDeserialized = false;
-
+
/** A flag to signal that the raw value represent the serialized values in their last state */
private boolean isRawUpToDate = false;
/**
* Creates a new instance of a ValueHolder, containing the serialized values.
- *
+ *
* @param parentBtree the parent BTree
* @param raw The raw data containing the values
* @param nbValues the number of stored values
@@ -68,7 +70,7 @@ import org.apache.directory.mavibot.btre
valueThresholdUp = PersistedBTree.valueThresholdUp;
valueThresholdLow = PersistedBTree.valueThresholdLow;
- // We create the array of values if they fit in an array. If they are stored in a
+ // We create the array of values if they fit in an array. If they are stored in a
// BTree, we do nothing atm.
if ( nbValues <= valueThresholdUp )
{
@@ -81,7 +83,7 @@ import org.apache.directory.mavibot.btre
/**
* Creates a new instance of a ValueHolder, containing Values. This constructor is called
* whe we need to create a new ValueHolder with deserialized values.
- *
+ *
* @param parentBtree The parent BTree
* @param values The Values stored in the ValueHolder
*/
@@ -135,7 +137,7 @@ import org.apache.directory.mavibot.btre
// No value, we create an empty array
valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 0 );
}
-
+
isDeserialized = true;
}
@@ -156,8 +158,8 @@ import org.apache.directory.mavibot.btre
* @return the raw representation of the value holder. The serialized value will not be the same
* if the values are stored in an array or in a btree. <br/>
* If they are stored in a BTree, the raw value will contain the offset of the btree, otherwise
- * it will contain a byte[] which will contain each serialized value, prefixed by their length.
- *
+ * it will contain a byte[] which will contain each serialized value, prefixed by their length.
+ *
*/
/* No qualifier*/ byte[] getRaw()
{
@@ -179,35 +181,35 @@ import org.apache.directory.mavibot.btre
byte[][] valueBytes = new byte[valueArray.length * 2][];
int length = 0;
int pos = 0;
-
+
// Process each value now
for ( V value : valueArray )
{
// Serialize the value
byte[] bytes = valueSerializer.serialize( value );
length += bytes.length;
-
+
// Serialize the value's length
byte[] sizeBytes = IntSerializer.serialize( bytes.length );
length += sizeBytes.length;
-
+
// And store the two byte[]
valueBytes[pos++] = sizeBytes;
valueBytes[pos++] = bytes;
}
-
+
// Last, not least, create a buffer large enough to contain all the created byte[],
// and copy all those byte[] into this buffer
raw = new byte[length];
pos = 0;
-
+
for ( byte[] bytes : valueBytes )
{
System.arraycopy( bytes, 0, raw, pos, bytes.length );
pos += bytes.length;
}
}
-
+
// Update the flags
isRawUpToDate = true;
@@ -247,7 +249,7 @@ import org.apache.directory.mavibot.btre
configuration.setValueSerializer( valueSerializer );
configuration.setParentBTree( parentBtree );
configuration.setSubBtree( true );
-
+
valueBtree = BTreeFactory.createPersistedBTree( configuration );
try
@@ -258,12 +260,12 @@ import org.apache.directory.mavibot.btre
catch ( BTreeAlreadyManagedException e )
{
// should never happen
- throw new RuntimeException( e );
+ throw new BTreeAlreadyCreatedException( e );
}
}
catch ( IOException e )
{
- throw new RuntimeException( e );
+ throw new BTreeCreationException( e );
}
}
@@ -279,8 +281,8 @@ import org.apache.directory.mavibot.btre
isDeserialized = true;
isRawUpToDate = false;
}
-
-
+
+
/**
* Check that the values are stored as raw value
*/
@@ -314,13 +316,13 @@ import org.apache.directory.mavibot.btre
checkAndDeserialize();
super.add( value );
-
+
// The raw value is not anymore up to date with the content
isRawUpToDate = false;
raw = null;
}
-
-
+
+
/**
* Remove a value from an array
*/
@@ -346,14 +348,14 @@ import org.apache.directory.mavibot.btre
// Get the removed element
V removedValue = valueArray[pos];
-
+
// And switch the arrays
valueArray = newValueArray;
-
+
return removedValue;
}
-
+
/**
* Remove the value from a sub btree
*/
@@ -369,21 +371,21 @@ import org.apache.directory.mavibot.btre
if ( valueBtree.getNbElems() - 1 < PersistedBTree.valueThresholdLow )
{
int nbValues = (int)(valueBtree.getNbElems() - 1);
-
+
// We have to switch to an Array of values
valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
-
+
// Now copy all the value but the one we have removed
TupleCursor<V,V> cursor = valueBtree.browse();
V returnedValue = null;
int pos = 0;
-
+
while ( cursor.hasNext() )
{
Tuple<V, V> tuple = cursor.next();
-
+
V value = tuple.getKey();
-
+
if ( valueSerializer.getComparator().compare( removedValue, value ) == 0 )
{
// This is the removed value : skip it
@@ -394,13 +396,13 @@ import org.apache.directory.mavibot.btre
valueArray[pos++] = value;
}
}
-
+
return returnedValue;
}
else
{
Tuple<V, V> removedTuple = valueBtree.delete( removedValue );
-
+
if ( removedTuple != null )
{
return removedTuple.getKey();
@@ -431,7 +433,7 @@ import org.apache.directory.mavibot.btre
public V remove( V value )
{
V removedValue = null;
-
+
if ( valueArray != null )
{
removedValue = removeFromArray( value );
@@ -444,11 +446,11 @@ import org.apache.directory.mavibot.btre
// The raw value is not anymore up to date wth the content
isRawUpToDate = false;
raw = null;
-
+
return removedValue;
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -456,7 +458,7 @@ import org.apache.directory.mavibot.btre
{
// First, deserialize the value if it's still a byte[]
checkAndDeserialize();
-
+
return super.contains( checkedValue );
}
@@ -467,7 +469,7 @@ import org.apache.directory.mavibot.btre
* As we use a 0-based array, the negative position for 0 is -1.
* -1 means the element can be added in position 0
* -2 means the element can be added in position 1
- * ...
+ * ...
*/
private int findPos( V value )
{
@@ -596,14 +598,14 @@ import org.apache.directory.mavibot.btre
PersistedValueHolder<V> copy = (PersistedValueHolder<V> ) super.clone();
// copy the valueArray if it's not null
- // We don't clone the BTree, as we will create new revisions when
+ // We don't clone the BTree, as we will create new revisions when
// modifying it
if ( valueArray != null )
{
copy.valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length );
System.arraycopy( valueArray, 0, copy.valueArray, 0, valueArray.length );
}
-
+
// Also clone the raw value if its up to date
if ( isRawUpToDate )
{
@@ -651,11 +653,11 @@ import org.apache.directory.mavibot.btre
{
// Get the sub-btree offset
long offset = LongSerializer.deserialize( raw );
-
+
// and reload the sub btree
valueBtree = parentBtree.getRecordManager().loadDupsBTree( offset );
}
-
+
/**
* @return The sub-btree offset