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 2015/11/02 00:01:01 UTC
svn commit: r1711861 [2/4] - in
/directory/mavibot/branches/single-value/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
main/java/org/apache/directory/mavibot/btree/exception/
test/java/org/apache/directory/mavibot/btree/
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/MavibotInspector.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/MavibotInspector.java?rev=1711861&r1=1711860&r2=1711861&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/MavibotInspector.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/MavibotInspector.java Sun Nov 1 23:01:00 2015
@@ -440,10 +440,10 @@ public class MavibotInspector
checkOffset( recordManager, btreeInfoOffset );
- BtreeInfo<K, V> btreeInfo = checkBtreeInfo( recordManager, checkedPages, btreeInfoOffset, btreeRevision );
+ BTreeInfo<K, V> btreeInfo = checkBtreeInfo( recordManager, checkedPages, btreeInfoOffset, btreeRevision );
// Update the checked pages
- updateCheckedPages( checkedPages.get( btreeInfo.btreeName ), recordManager.pageSize, btreeHeaderPageIos );
+ updateCheckedPages( checkedPages.get( btreeInfo.getBtreeName() ), recordManager.pageSize, btreeHeaderPageIos );
updateCheckedPages( checkedPages.get( GLOBAL_PAGES_NAME ), recordManager.pageSize, btreeHeaderPageIos );
// And now, process the rootPage
@@ -454,13 +454,13 @@ public class MavibotInspector
/**
* Check the Btree of Btrees rootPage
*/
- private static <K, V> void checkBtreePage( RecordManager recordManager, BtreeInfo<K, V> btreeInfo,
+ private static <K, V> void checkBtreePage( RecordManager recordManager, BTreeInfo<K, V> btreeInfo,
Map<String, int[]> checkedPages, long pageOffset ) throws Exception
{
PageIO[] pageIos = recordManager.readPageIOs( pageOffset, Long.MAX_VALUE );
// Update the checkedPages array
- updateCheckedPages( checkedPages.get( btreeInfo.btreeName ), recordManager.pageSize, pageIos );
+ updateCheckedPages( checkedPages.get( btreeInfo.getBtreeName() ), recordManager.pageSize, pageIos );
updateCheckedPages( checkedPages.get( GLOBAL_PAGES_NAME ), recordManager.pageSize, pageIos );
// Deserialize the page now
@@ -507,10 +507,10 @@ public class MavibotInspector
* Check the Btree info page
* @throws ClassNotFoundException
*/
- private static <K, V> BtreeInfo<K, V> checkBtreeInfo( RecordManager recordManager, Map<String, int[]> checkedPages,
+ private static <K, V> BTreeInfo<K, V> checkBtreeInfo( RecordManager recordManager, Map<String, int[]> checkedPages,
long btreeInfoOffset, long btreeRevision ) throws IOException
{
- BtreeInfo<K, V> btreeInfo = new BtreeInfo<K, V>();
+ BTreeInfo<K, V> btreeInfo = new BTreeInfo<K, V>();
PageIO[] btreeInfoPagesIos = recordManager.readPageIOs( btreeInfoOffset, Long.MAX_VALUE );
@@ -532,7 +532,7 @@ public class MavibotInspector
{
String keySerializerFqcn = Strings.utf8ToString( keySerializerBytes );
- btreeInfo.keySerializer = getSerializer( keySerializerFqcn );
+ btreeInfo.setKeySerializer( ( ( ElementSerializer<K> ) getSerializer( keySerializerFqcn ) ) );
}
dataPos += RecordManager.INT_SIZE + keySerializerBytes.limit();
@@ -544,7 +544,7 @@ public class MavibotInspector
{
String valueSerializerFqcn = Strings.utf8ToString( valueSerializerBytes );
- btreeInfo.valueSerializer = getSerializer( valueSerializerFqcn );
+ btreeInfo.setValueSerializer( ( ( ElementSerializer<V> ) getSerializer( valueSerializerFqcn ) ) );
}
dataPos += RecordManager.INT_SIZE + valueSerializerBytes.limit();
@@ -560,7 +560,7 @@ public class MavibotInspector
//btreeName = btreeName + "<" + btreeRevision + ">";
}
- btreeInfo.btreeName = btreeName;
+ btreeInfo.setBtreeName( btreeName );
// Update the checkedPages
int[] checkedPagesArray = checkedPages.get( btreeName );
@@ -754,7 +754,7 @@ public class MavibotInspector
/**
* Check a Btree leaf.
*/
- private static <K, V> void checkBtreeLeaf( RecordManager recordManager, BtreeInfo<K, V> btreeInfo,
+ private static <K, V> void checkBtreeLeaf( RecordManager recordManager, BTreeInfo<K, V> btreeInfo,
Map<String, int[]> checkedPages, int nbElems, long revision, ByteBuffer byteBuffer, PageIO[] pageIos )
throws Exception
{
@@ -779,19 +779,19 @@ public class MavibotInspector
byteBuffer.getInt();
// The key itself
- btreeInfo.keySerializer.deserialize( byteBuffer );
+ btreeInfo.getKeySerializer().deserialize( byteBuffer );
}
else
{
// just deserialize the keys and values
// The value
byteBuffer.getInt();
- btreeInfo.valueSerializer.deserialize( byteBuffer );
+ btreeInfo.getValueSerializer().deserialize( byteBuffer );
// the key
byteBuffer.getInt();
- btreeInfo.keySerializer.deserialize( byteBuffer );
+ btreeInfo.getKeySerializer().deserialize( byteBuffer );
}
}
catch ( BufferUnderflowException bue )
@@ -872,7 +872,7 @@ public class MavibotInspector
/**
* Check a Btree node.
*/
- private static <K, V> long[] checkBtreeNode( RecordManager recordManager, BtreeInfo<K, V> btreeInfo,
+ private static <K, V> long[] checkBtreeNode( RecordManager recordManager, BTreeInfo<K, V> btreeInfo,
Map<String, int[]> checkedPages, int nbElems, long revision, ByteBuffer byteBuffer, PageIO[] pageIos )
throws Exception
{
@@ -899,7 +899,7 @@ public class MavibotInspector
byteBuffer.getInt();
// The key itself
- btreeInfo.keySerializer.deserialize( byteBuffer );
+ btreeInfo.getKeySerializer().deserialize( byteBuffer );
}
catch ( BufferUnderflowException bue )
{
@@ -1428,30 +1428,3 @@ public class MavibotInspector
}
}
-/**
- * A class used to store some information about the Btree
- */
-final class BtreeInfo<K, V>
-{
- // The btree name
- /* no qualifier */String btreeName;
-
- // The key serializer
- /* no qualifier */ElementSerializer<K> keySerializer;
-
- // The value serializer
- /* no qualifier */ElementSerializer<V> valueSerializer;
-
-
- public String toString()
- {
- StringBuilder sb = new StringBuilder();
-
- sb.append( "B-tree Info :" );
- sb.append( "\n name : " ).append( btreeName );
- sb.append( "\n key serializer : " ).append( keySerializer.getClass().getName() );
- sb.append( "\n value serializer : " ).append( valueSerializer.getClass().getName() );
-
- return sb.toString();
- }
-}
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java?rev=1711861&r1=1711860&r2=1711861&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java Sun Nov 1 23:01:00 2015
@@ -37,7 +37,7 @@ import org.apache.directory.mavibot.btre
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-/* No qualifier*/interface Page<K, V>
+/* No qualifier*/interface Page<K, V> extends WALObject
{
/**
* @return The number of keys present in this page
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PageReclaimer.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PageReclaimer.java?rev=1711861&r1=1711860&r2=1711861&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PageReclaimer.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PageReclaimer.java Sun Nov 1 23:01:00 2015
@@ -127,7 +127,7 @@ public class PageReclaimer
// no new txn is needed for the operations on BoB
// and also no need to traverse BoB if the tree is a sub-btree
- if ( ( lastRemovedRev != -1 ) && !tree.isAllowDuplicates() )
+ if ( ( lastRemovedRev != -1 ) )
{
// we SHOULD NOT delete the latest revision from BoB
NameRevision nr = new NameRevision( name, latestRev );
@@ -176,10 +176,10 @@ public class PageReclaimer
}
catch ( Exception e )
{
- running = false;
- rm.rollback();
- LOG.warn( "Errors while reclaiming", e );
- throw new RuntimeException( e );
+ running = false;
+ rm.rollback();
+ LOG.warn( "Errors while reclaiming", e );
+ throw new RuntimeException( e );
}
}
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/ParentPos.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/ParentPos.java?rev=1711861&r1=1711860&r2=1711861&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/ParentPos.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/ParentPos.java Sun Nov 1 23:01:00 2015
@@ -22,7 +22,7 @@ package org.apache.directory.mavibot.btr
/**
* This class is used to store the parent page and the position in it during
- * a browse operation. We have as many ParentPos instance than the depth of the tree.
+ * a browse operation. We have as many ParentPos instance as the depth of the tree.
*
* @param <K> The type for the Key
* @param <V> The type for the stored value
@@ -37,13 +37,6 @@ package org.apache.directory.mavibot.btr
/** The current position in the page */
/* no qualifier */int pos;
- /** The current position of the duplicate container in the page */
- /* no qualifier */int dupPos;
-
- /** The current position of the duplicate container in the page */
- /* no qualifier */ValueCursor<V> valueCursor;
-
-
/**
* Creates a new instance of ParentPos
* @param page The current Page
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java?rev=1711861&r1=1711860&r2=1711861&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java Sun Nov 1 23:01:00 2015
@@ -56,22 +56,9 @@ public class PersistedBTree<K, V> extend
/** The cache size, default to 1000 elements */
protected int cacheSize = DEFAULT_CACHE_SIZE;
- /** The number of stored Values before we switch to a B-tree */
- private static final int DEFAULT_VALUE_THRESHOLD_UP = 8;
-
- /** The number of stored Values before we switch back to an array */
- private static final int DEFAULT_VALUE_THRESHOLD_LOW = 1;
-
- /** The configuration for the array <-> B-tree switch */
- /*No qualifier*/static int valueThresholdUp = DEFAULT_VALUE_THRESHOLD_UP;
- /*No qualifier*/static int valueThresholdLow = DEFAULT_VALUE_THRESHOLD_LOW;
-
/** The BtreeInfo offset */
private long btreeInfoOffset = RecordManager.NO_PAGE;
- /** The internal recordManager */
- private RecordManager recordManager;
-
/**
* Creates a new BTree, with no initialization.
@@ -102,7 +89,6 @@ public class PersistedBTree<K, V> extend
setPageSize( configuration.getPageSize() );
setKeySerializer( configuration.getKeySerializer() );
setValueSerializer( configuration.getValueSerializer() );
- setAllowDuplicates( configuration.isAllowDuplicates() );
setType( configuration.getBtreeType() );
readTimeOut = configuration.getReadTimeOut();
@@ -132,12 +118,6 @@ public class PersistedBTree<K, V> extend
currentBtreeHeader = btreeHeader;
break;
- case PERSISTED_SUB:
- init( ( PersistedBTree<K, V> ) configuration.getParentBTree() );
- btreeRevisions.put( 0L, btreeHeader );
- currentBtreeHeader = btreeHeader;
- break;
-
default:
// We will create a new cache and a new readTransactions map
init( null );
@@ -245,7 +225,7 @@ public class PersistedBTree<K, V> extend
*
* @return The recordManager if the B-tree is managed
*/
- /* No qualifier */RecordManager getRecordManager()
+ public RecordManager getRecordManager()
{
return recordManager;
}
@@ -258,8 +238,6 @@ public class PersistedBTree<K, V> extend
*/
/* No qualifier */void setRecordManager( RecordManager recordManager )
{
- // The RecordManager is also the TransactionManager
- transactionManager = recordManager;
this.recordManager = recordManager;
}
@@ -385,16 +363,6 @@ public class PersistedBTree<K, V> extend
break;
- case PERSISTED_SUB:
- // Sub-B-trees are only updating the CopiedPage B-tree
- recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
-
- //btreeRevisions.put( revision, newBtreeHeader );
-
- currentRevision.set( revision );
-
- break;
-
case BTREE_OF_BTREES:
// The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters
recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L );
@@ -472,9 +440,6 @@ public class PersistedBTree<K, V> extend
{
switch ( btreeType )
{
- case PERSISTED_SUB:
- return getBtreeHeader();
-
case BTREE_OF_BTREES:
return recordManager.getNewBTreeHeader( RecordManager.BTREE_OF_BTREES_NAME );
@@ -489,11 +454,6 @@ public class PersistedBTree<K, V> extend
private BTreeHeader<K, V> getNewBTreeHeader( String name )
{
- if ( btreeType == BTreeTypeEnum.PERSISTED_SUB )
- {
- return getBtreeHeader();
- }
-
BTreeHeader<K, V> btreeHeader = recordManager.getNewBTreeHeader( getName() );
return btreeHeader;
@@ -591,17 +551,6 @@ public class PersistedBTree<K, V> extend
break;
- case PERSISTED_SUB:
- // Sub-B-trees are only updating the CopiedPage B-tree
- recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
-
- // Store the new revision
- storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
-
- currentRevision.set( revision );
-
- break;
-
case BTREE_OF_BTREES:
// The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters
recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L );
@@ -807,8 +756,6 @@ public class PersistedBTree<K, V> extend
sb.append( keySerializer.getComparator().getClass().getSimpleName() );
}
- sb.append( ", DuplicatesAllowed: " ).append( isAllowDuplicates() );
-
sb.append( ") : \n" );
sb.append( getBTreeHeader( getName() ).getRootPage().dumpPage( "" ) );
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeConfiguration.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeConfiguration.java?rev=1711861&r1=1711860&r2=1711861&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeConfiguration.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTreeConfiguration.java Sun Nov 1 23:01:00 2015
@@ -63,9 +63,6 @@ public class PersistedBTreeConfiguration
*/
private long readTimeOut = PersistedBTree.DEFAULT_READ_TIMEOUT;
- /** Flag to enable duplicate key support */
- private boolean allowDuplicates;
-
/** The B-tree type */
private BTreeTypeEnum btreeType = BTreeTypeEnum.PERSISTED;
@@ -213,28 +210,6 @@ public class PersistedBTreeConfiguration
}
- /**
- * @return true if duplicate key support is enabled
- */
- public boolean isAllowDuplicates()
- {
- return allowDuplicates;
- }
-
-
- /**
- * enable duplicate key support
- *
- * @param allowDuplicates
- * @throws IllegalStateException if the B-tree was already initialized or when tried to turn off duplicate suport on
- * an existing B-tree containing duplicate keys
- */
- public void setAllowDuplicates( boolean allowDuplicates )
- {
- this.allowDuplicates = allowDuplicates;
- }
-
-
/**
* @return the cacheSize
*/
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java?rev=1711861&r1=1711860&r2=1711861&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java Sun Nov 1 23:01:00 2015
@@ -20,11 +20,10 @@
package org.apache.directory.mavibot.btree;
-import static org.apache.directory.mavibot.btree.BTreeTypeEnum.PERSISTED_SUB;
-
import java.io.IOException;
import java.lang.reflect.Array;
+import org.apache.directory.mavibot.btree.exception.CursorException;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
@@ -65,10 +64,7 @@ import org.apache.directory.mavibot.btre
PersistedLeaf( BTree<K, V> btree, long revision, int nbElems )
{
super( btree, revision, nbElems );
- if ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB )
- {
- values = ( ValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class, nbElems );
- }
+ values = ( ValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class, nbElems );
}
@@ -80,19 +76,12 @@ import org.apache.directory.mavibot.btre
// Find the key into this leaf
int pos = findPos( key );
- boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
-
if ( pos < 0 )
{
// We already have the key in the page : replace the value
// into a copy of this page, unless the page has already be copied
int index = -( pos + 1 );
- if ( isSubTree )
- {
- return ExistsResult.EXISTS;
- }
-
// Replace the existing value in a copy of the current page
InsertResult<K, V> result = replaceElement( revision, key, value, index );
@@ -106,14 +95,7 @@ import org.apache.directory.mavibot.btre
// We insert it into a copied page and return the result
Page<K, V> modifiedPage = null;
- if ( isSubTree )
- {
- modifiedPage = addSubTreeElement( revision, key, pos );
- }
- else
- {
- modifiedPage = addElement( revision, key, value, pos );
- }
+ modifiedPage = addElement( revision, key, value, pos );
InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
result.addCopiedPage( this );
@@ -126,14 +108,7 @@ import org.apache.directory.mavibot.btre
// after having created two pages.
InsertResult<K, V> result = null;
- if ( isSubTree )
- {
- result = addAndSplitSubTree( revision, key, pos );
- }
- else
- {
- result = addAndSplit( revision, key, value, pos );
- }
+ result = addAndSplit( revision, key, value, pos );
result.addCopiedPage( this );
@@ -169,36 +144,19 @@ import org.apache.directory.mavibot.btre
Tuple<K, V> removedElement = null;
// flag to detect if a key was completely removed
- boolean keyRemoved = false;
-
int index = -( pos + 1 );
- boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
-
- ValueHolder<V> valueHolder = null;
-
- if ( isNotSubTree )
- {
- valueHolder = values[index];
- }
- else
- // set value to null, just incase if a non-null value passed while deleting a key from from sub-btree
- {
- value = null;
- }
+ 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
- keyRemoved = true;
}
else
{
if ( valueHolder.contains( value ) )
{
- keyRemoved = ( valueHolder.size() == 1 );
-
removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // only one value was removed
}
else
@@ -209,16 +167,8 @@ import org.apache.directory.mavibot.btre
PersistedLeaf<K, V> newLeaf = null;
- if ( keyRemoved )
- {
- // No value, we can remove the key
- newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems - 1 );
- }
- else
- {
- // Copy the page as we will delete a value from a ValueHolder
- newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems );
- }
+ // No value, we can remove the key
+ newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems - 1 );
// Create the result
DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );
@@ -227,14 +177,14 @@ import org.apache.directory.mavibot.btre
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( keyRemoved, value, newLeaf, index );
+ copyAfterRemovingElement( value, newLeaf, index );
// The current page is added in the copied page list
defaultResult.addCopiedPage( this );
return defaultResult;
}
- else if ( keyRemoved )
+ else
{
// The current page is not the root. Check if the leaf has more than N/2
// elements
@@ -282,7 +232,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( true, value, newLeaf, index );
+ copyAfterRemovingElement( value, newLeaf, index );
// The current page is added in the copied page list
defaultResult.addCopiedPage( this );
@@ -290,31 +240,6 @@ import org.apache.directory.mavibot.btre
return defaultResult;
}
}
- else
- {
- // Last, not least : we can copy the full page
- // Copy the keys and the values
- System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
- System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
-
- // Replace the ValueHolder now
- try
- {
- ValueHolder<V> newValueHolder = valueHolder.clone();
- newValueHolder.remove( value );
-
- newLeaf.values[pos] = newValueHolder;
- }
- catch ( CloneNotSupportedException e )
- {
- throw new RuntimeException( e );
- }
-
- // The current page is added in the copied page list
- defaultResult.addCopiedPage( this );
-
- return defaultResult;
- }
}
@@ -333,8 +258,6 @@ import org.apache.directory.mavibot.btre
boolean isLeft, int pos )
throws EndOfFileExceededException, IOException
{
- boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
-
// Create the new page. It will contain N - 1 elements (the maximum number)
// as we merge two pages that contain N/2 elements minus the one we remove
PersistedLeaf<K, V> newLeaf = new PersistedLeaf<K, V>( btree, revision, btree.getPageSize() - 1 );
@@ -344,48 +267,30 @@ import org.apache.directory.mavibot.btre
// The sibling is on the left
// Copy all the elements from the sibling first
System.arraycopy( sibling.keys, 0, newLeaf.keys, 0, sibling.nbElems );
- if ( isNotSubTree )
- {
- System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
- }
+ System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
// Copy all the elements from the page up to the deletion position
System.arraycopy( keys, 0, newLeaf.keys, sibling.nbElems, pos );
- if ( isNotSubTree )
- {
- System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos );
- }
+ System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos );
// And copy the remaining elements after the deletion point
System.arraycopy( keys, pos + 1, newLeaf.keys, sibling.nbElems + pos, nbElems - pos - 1 );
- if ( isNotSubTree )
- {
- System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
- }
+ System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
}
else
{
// The sibling is on the right
// Copy all the elements from the page up to the deletion position
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
- if ( isNotSubTree )
- {
- System.arraycopy( values, 0, newLeaf.values, 0, pos );
- }
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
// Then copy the remaining elements after the deletion point
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, nbElems - pos - 1 );
- if ( isNotSubTree )
- {
- System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - pos - 1 );
- }
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - pos - 1 );
// And copy all the elements from the sibling
System.arraycopy( sibling.keys, 0, newLeaf.keys, nbElems - 1, sibling.nbElems );
- if ( isNotSubTree )
- {
- System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
- }
+ System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
}
// And create the result
@@ -413,15 +318,10 @@ import org.apache.directory.mavibot.btre
int pos )
throws IOException
{
- boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
-
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[sibling.getNbElems() - 1].getKey();
ValueHolder<V> siblingValue = null;
- if ( isNotSubTree )
- {
- siblingValue = sibling.values[sibling.getNbElems() - 1];
- }
+ siblingValue = sibling.values[sibling.getNbElems() - 1];
// Create the new sibling, with one less element at the end
PersistedLeaf<K, V> newSibling = ( PersistedLeaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
@@ -432,24 +332,15 @@ import org.apache.directory.mavibot.btre
// Insert the borrowed element
newLeaf.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey );
- if ( isNotSubTree )
- {
- newLeaf.values[0] = siblingValue;
- }
+ newLeaf.values[0] = siblingValue;
// Copy the keys and the values up to the insertion position,
System.arraycopy( keys, 0, newLeaf.keys, 1, pos );
- if ( isNotSubTree )
- {
- System.arraycopy( values, 0, newLeaf.values, 1, pos );
- }
+ System.arraycopy( values, 0, newLeaf.values, 1, pos );
// And copy the remaining elements
System.arraycopy( keys, pos + 1, newLeaf.keys, pos + 1, keys.length - pos - 1 );
- if ( isNotSubTree )
- {
- System.arraycopy( values, pos + 1, newLeaf.values, pos + 1, values.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 );
@@ -476,25 +367,17 @@ import org.apache.directory.mavibot.btre
int pos )
throws IOException
{
- boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
-
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[0].getKey();
ValueHolder<V> siblingHolder = null;
- if ( isNotSubTree )
- {
- siblingHolder = sibling.values[0];
- }
+ siblingHolder = sibling.values[0];
// Create the new sibling
PersistedLeaf<K, V> newSibling = new PersistedLeaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
// Copy the keys and the values from 1 to N in the new sibling
System.arraycopy( sibling.keys, 1, newSibling.keys, 0, sibling.nbElems - 1 );
- if ( isNotSubTree )
- {
- System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
- }
+ System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
// Create the new page and add the new element at the end
// First copy the current page, with the same size
@@ -502,24 +385,15 @@ import org.apache.directory.mavibot.btre
// Insert the borrowed element at the end
newLeaf.keys[nbElems - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey );
- if ( isNotSubTree )
- {
- newLeaf.values[nbElems - 1] = siblingHolder;
- }
+ newLeaf.values[nbElems - 1] = siblingHolder;
// Copy the keys and the values up to the deletion position,
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
- if ( isNotSubTree )
- {
- System.arraycopy( values, 0, newLeaf.values, 0, pos );
- }
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
// And copy the remaining elements
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
- if ( isNotSubTree )
- {
- System.arraycopy( values, pos + 1, newLeaf.values, pos, values.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 );
@@ -539,57 +413,23 @@ 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( boolean keyRemoved, V removedValue, PersistedLeaf<K, V> newLeaf, int pos )
+ private void copyAfterRemovingElement( V removedValue, PersistedLeaf<K, V> newLeaf, int pos )
throws IOException
{
- boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
-
- if ( keyRemoved )
+ // Deal with the special case of a page with only one element by skipping
+ // the copy, as we won't have any remaining element in the page
+ if ( nbElems == 1 )
{
- // Deal with the special case of a page with only one element by skipping
- // the copy, as we won't have any remaining element in the page
- if ( nbElems == 1 )
- {
- return;
- }
-
- // Copy the keys and the values up to the insertion position
- System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
- if ( isNotSubTree )
- {
- System.arraycopy( values, 0, newLeaf.values, 0, pos );
- }
-
- // And copy the elements after the position
- System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
- if ( isNotSubTree )
- {
- System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
- }
+ return;
}
- else
- // one of the many values of the same key was removed, no change in the number of keys
- {
- System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
- System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
-
- // We still have to clone the modified value holder
- ValueHolder<V> valueHolder = newLeaf.values[pos];
-
- try
- {
- ValueHolder<V> newValueHolder = valueHolder.clone();
- newValueHolder.remove( removedValue );
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
- newLeaf.values[pos] = newValueHolder;
- }
- catch ( CloneNotSupportedException e )
- {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
+ // And copy the elements after the position
+ System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
}
@@ -602,22 +442,7 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- ValueHolder<V> valueHolder = values[-( pos + 1 )];
-
- ValueCursor<V> cursor = valueHolder.getCursor();
-
- cursor.beforeFirst();
-
- if ( cursor.hasNext() )
- {
- V value = cursor.next();
-
- return value;
- }
- else
- {
- return null;
- }
+ return values[-( pos + 1 )].get();
}
else
{
@@ -645,32 +470,6 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- @Override
- public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
- {
- if ( !btree.isAllowDuplicates() )
- {
- throw new IllegalArgumentException( "Duplicates are not allowed in this tree" );
- }
-
- int pos = findPos( key );
-
- if ( pos < 0 )
- {
- ValueHolder<V> valueHolder = values[-( pos + 1 )];
-
- return valueHolder.getCursor();
- }
- else
- {
- throw KeyNotFoundException.INSTANCE;
- }
- }
-
-
- /**
- * {@inheritDoc}
- */
public boolean hasKey( K key )
{
int pos = findPos( key );
@@ -748,7 +547,7 @@ import org.apache.directory.mavibot.btre
// Depending on the position, we will proceed differently :
// 1) if the key is found in the page, the cursor will be
- // set to this position.
+ // 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
@@ -762,9 +561,6 @@ import org.apache.directory.mavibot.btre
// Start at the found position in the page
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
- // Create the value cursor
- parentPos.valueCursor = values[pos].getCursor();
-
// And store this position in the stack
stack[depth] = parentPos;
@@ -780,9 +576,6 @@ import org.apache.directory.mavibot.btre
// This will be the starting point.
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
- // Create the value cursor
- parentPos.valueCursor = values[pos].getCursor();
-
stack[depth] = parentPos;
return cursor;
@@ -801,7 +594,7 @@ import org.apache.directory.mavibot.btre
{
cursor.afterLast();
}
- catch ( IOException e )
+ catch ( CursorException e )
{
e.printStackTrace();
}
@@ -835,7 +628,7 @@ import org.apache.directory.mavibot.btre
{
cursor.afterLast();
}
- catch ( IOException e )
+ catch ( CursorException e )
{
e.printStackTrace();
}
@@ -869,12 +662,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();
-
stack[depth] = parentPos;
-
cursor = new TupleCursor<K, V>( transaction, stack, depth );
}
@@ -956,22 +744,18 @@ import org.apache.directory.mavibot.btre
valueHolder = newLeaf.values[pos];
V replacedValue = null;
- if ( !valueExists && btree.isAllowDuplicates() )
+ if ( !valueExists )
{
- valueHolder.add( value );
+ valueHolder.set( value );
newLeaf.values[pos] = valueHolder;
}
- else if ( valueExists && btree.isAllowDuplicates() )
+ else
{
// As strange as it sounds, we need to remove the value to reinject it.
// There are cases where the value retrieval just use one part of the
// value only (typically for LDAP Entries, where we use the DN)
replacedValue = valueHolder.remove( value );
- valueHolder.add( value );
- }
- else if ( !btree.isAllowDuplicates() )
- {
- replacedValue = valueHolder.replaceValueArray( value );
+ valueHolder.set( value );
}
// Create the result
@@ -1135,32 +919,7 @@ import org.apache.directory.mavibot.btre
{
K key = keys[0].getKey();
- boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
-
- if ( isSubTree )
- {
- return new Tuple<K, V>( key, null );
- }
-
- ValueCursor<V> cursor = values[0].getCursor();
-
- try
- {
- cursor.beforeFirst();
- if ( cursor.hasNext() )
- {
- return new Tuple<K, V>( key, cursor.next() );
- }
- else
- {
- // Null value
- return new Tuple<K, V>( key, null );
- }
- }
- finally
- {
- cursor.close();
- }
+ return new Tuple<K, V>( key, values[0].get() );
}
@@ -1171,34 +930,9 @@ import org.apache.directory.mavibot.btre
{
K key = keys[nbElems - 1].getKey();
+ V value = values[nbElems - 1].get();
- boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
-
- if ( isSubTree )
- {
- return new Tuple<K, V>( key, null );
- }
-
- ValueCursor<V> cursor = values[nbElems - 1].getCursor();
-
- try
- {
- cursor.afterLast();
-
- if ( cursor.hasPrev() )
- {
- return new Tuple<K, V>( key, cursor.prev() );
- }
- else
- {
- // Null value
- return new Tuple<K, V>( key, null );
- }
- }
- finally
- {
- cursor.close();
- }
+ return new Tuple<K, V>( key, value );
}
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java?rev=1711861&r1=1711860&r2=1711861&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java Sun Nov 1 23:01:00 2015
@@ -21,17 +21,6 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
-import java.lang.reflect.Array;
-import java.util.Comparator;
-import java.util.Iterator;
-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.exception.KeyNotFoundException;
-import org.apache.directory.mavibot.btree.serializer.IntSerializer;
-import org.apache.directory.mavibot.btree.serializer.LongSerializer;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -68,98 +57,33 @@ import org.slf4j.LoggerFactory;
* @param nbValues the number of stored values
* @param raw the byte[] containing either the serialized array of values or the sub-btree offset
*/
- PersistedValueHolder( BTree<?, V> parentBtree, int nbValues, byte[] raw )
+ PersistedValueHolder( BTree<?, V> parentBtree, byte[] raw )
{
this.parentBtree = ( PersistedBTree<V, V> ) parentBtree;
this.valueSerializer = parentBtree.getValueSerializer();
this.raw = raw;
isRawUpToDate = true;
- valueThresholdUp = PersistedBTree.valueThresholdUp;
- valueThresholdLow = PersistedBTree.valueThresholdLow;
-
- // 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 )
- {
- // The values are contained into an array
- valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
- }
}
/**
- * Creates a new instance of a ValueHolder, containing Values. This constructor is called
+ * Creates a new instance of a ValueHolder, containing a Value. 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
+ * @param values The Value stored in the ValueHolder
*/
- PersistedValueHolder( BTree<?, V> parentBtree, V... values )
+ PersistedValueHolder( BTree<?, V> parentBtree, V value )
{
this.parentBtree = ( PersistedBTree<V, V> ) parentBtree;
this.valueSerializer = parentBtree.getValueSerializer();
- valueThresholdUp = PersistedBTree.valueThresholdUp;
- valueThresholdLow = PersistedBTree.valueThresholdLow;
-
- if ( values != null )
- {
- int nbValues = values.length;
-
- if ( nbValues < PersistedBTree.valueThresholdUp )
- {
- // Keep an array
- valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
-
- try
- {
- System.arraycopy( values, 0, valueArray, 0, values.length );
- }
- catch ( ArrayStoreException ase )
- {
- ase.printStackTrace();
- throw ase;
- }
- }
- else
- {
- // Use a sub btree, now that we have reached the threshold
- createSubTree();
-
- try
- {
- build( ( PersistedBTree<V, V> ) valueBtree, values );
- }
- catch ( Exception e )
- {
- throw new RuntimeException( e );
- }
-
- manageSubTree();
- }
- }
- else
- {
- // No value, we create an empty array
- valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 0 );
- }
+ set( value );
isDeserialized = true;
}
/**
- * @return a cursor on top of the values
- */
- public ValueCursor<V> getCursor()
- {
- // Check that the values are deserialized before doing anything
- checkAndDeserialize();
-
- return super.getCursor();
- }
-
-
- /**
* @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
@@ -174,158 +98,60 @@ import org.slf4j.LoggerFactory;
return raw;
}
- if ( isSubBtree() )
- {
- // The values are stored into a subBtree, return the offset of this subBtree
- long btreeOffset = ( ( PersistedBTree<V, V> ) valueBtree ).getBtreeOffset();
- raw = LongSerializer.serialize( btreeOffset );
- }
- else
- {
- // Create as many byte[] as we have length and serialized values to store
- 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;
- }
- }
+ // Process the value
+ // Serialize the value
+ raw = valueSerializer.serialize( value );
// Update the flags
isRawUpToDate = true;
return raw;
}
-
-
+
+
/**
- * {@inheritDoc}
+ * Deserialize the stored raw value
+ * @throws IOException
*/
- public int size()
+ private void deserialize() throws IOException
{
- checkAndDeserialize();
-
- if ( valueArray == null )
- {
- return ( int ) valueBtree.getNbElems();
- }
- else
- {
- return valueArray.length;
- }
+ // We haven't yet deserialized the values. Let's do it now.
+ V value = valueSerializer.fromBytes( raw, 0 );
}
/**
- * Create a new Sub-BTree to store the values.
- */
- protected void createSubTree()
- {
- PersistedBTreeConfiguration<V, V> configuration = new PersistedBTreeConfiguration<V, V>();
- configuration.setAllowDuplicates( false );
- configuration.setKeySerializer( valueSerializer );
- configuration.setName( UUID.randomUUID().toString() );
- configuration.setValueSerializer( valueSerializer );
- configuration.setParentBTree( parentBtree );
- configuration.setBtreeType( BTreeTypeEnum.PERSISTED_SUB );
-
- valueBtree = BTreeFactory.createPersistedBTree( configuration );
- ( ( PersistedBTree<V, V> ) valueBtree ).setRecordManager( parentBtree.getRecordManager() );
- }
-
-
- /**
- * Push the sub-BTree into the RecordManager
+ * Check that the values are stored as raw value
+ * @throws IOException
*/
- protected void manageSubTree()
+ private void checkAndDeserialize() throws IOException
{
- try
- {
- parentBtree.getRecordManager().manageSubBtree( valueBtree );
- raw = null;
- }
- catch ( BTreeAlreadyManagedException e )
- {
- // should never happen
- throw new BTreeAlreadyCreatedException( e );
- }
- catch ( IOException e )
+ if ( !isDeserialized )
{
- throw new BTreeCreationException( e );
+ // The values are stored into an array. Deserialize it now
+ deserialize();
}
- }
-
- /**
- * Set the subBtree in the ValueHolder
- */
- /* No qualifier*/void setSubBtree( BTree<V, V> subBtree )
- {
- valueBtree = subBtree;
- raw = null;
- valueArray = null;
+ // Change the flag
isDeserialized = true;
- isRawUpToDate = false;
}
/**
- * Check that the values are stored as raw value
+ * {@inheritDoc}
*/
- private void checkAndDeserialize()
+ public V get()
{
- if ( !isDeserialized )
- {
- if ( valueArray == null )
- {
- // the values are stored into a sub-btree. Read it now if it's not already done
- deserializeSubBtree();
- }
- else
- {
- // The values are stored into an array. Deserialize it now
- deserializeArray();
- }
-
- // Change the flag
- isDeserialized = true;
- }
+ return value;
}
/**
* {@inheritDoc}
*/
- public void add( V value )
+ public void set( V value )
{
- // First check that we have a loaded BTree
- checkAndDeserialize();
-
- super.add( value );
+ super.set( value );
// The raw value is not anymore up to date with the content
isRawUpToDate = false;
@@ -334,138 +160,25 @@ import org.slf4j.LoggerFactory;
/**
- * Remove a value from an array
- */
- private V removeFromArray( V value )
- {
- checkAndDeserialize();
-
- // First check that the value is not already present in the ValueHolder
- int pos = findPos( value );
-
- if ( pos < 0 )
- {
- // The value does not exists : nothing to do
- return null;
- }
-
- // Ok, we just have to delete the new element at the right position
- // First, copy the array
- V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length - 1 );
-
- System.arraycopy( valueArray, 0, newValueArray, 0, pos );
- System.arraycopy( valueArray, pos + 1, newValueArray, pos, valueArray.length - pos - 1 );
-
- // Get the removed element
- V removedValue = valueArray[pos];
-
- // And switch the arrays
- valueArray = newValueArray;
-
- return removedValue;
- }
-
-
- /**
- * Remove the value from a sub btree
- */
- private V removeFromBtree( V removedValue )
- {
- // First check that we have a loaded BTree
- checkAndDeserialize();
-
- if ( btreeContains( removedValue ) )
- {
- try
- {
- 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
- returnedValue = value;
- }
- else
- {
- valueArray[pos++] = value;
- }
- }
-
- cursor.close();
-
- return returnedValue;
- }
- else
- {
- Tuple<V, V> removedTuple = valueBtree.delete( removedValue );
-
- if ( removedTuple != null )
- {
- return removedTuple.getKey();
- }
- else
- {
- return null;
- }
- }
- }
- catch ( IOException e )
- {
- // TODO Auto-generated catch block
- e.printStackTrace();
- return null;
- }
- catch ( KeyNotFoundException knfe )
- {
- // TODO Auto-generated catch block
- knfe.printStackTrace();
- return null;
- }
- }
- else
- {
- return null;
- }
- }
-
-
- /**
* {@inheritDoc}
*/
public V remove( V value )
{
- V removedValue = null;
-
- if ( valueArray != null )
+ if ( contains( value ) )
{
- removedValue = removeFromArray( value );
+ V removedValue = this.value;
+ this.value = null;
+
+ // The raw value is not anymore up to date with the content
+ isRawUpToDate = false;
+ raw = null;
+
+ return removedValue;
}
- else
- {
- removedValue = removeFromBtree( value );
+ else
+ {
+ return null;
}
-
- // The raw value is not anymore up to date wth the content
- isRawUpToDate = false;
- raw = null;
-
- return removedValue;
}
@@ -475,136 +188,17 @@ import org.slf4j.LoggerFactory;
public boolean contains( V checkedValue )
{
// First, deserialize the value if it's still a byte[]
- checkAndDeserialize();
-
- return super.contains( checkedValue );
- }
-
-
- /**
- * Find the position of a given value in the array, or the position where we
- * would insert the element (in this case, the position will be negative).
- * 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 )
- {
- if ( valueArray.length == 0 )
- {
- return -1;
- }
-
- // Do a search using dichotomy
- int pivot = valueArray.length / 2;
- int low = 0;
- int high = valueArray.length - 1;
- Comparator<V> comparator = valueSerializer.getComparator();
-
- while ( high > low )
+ try
{
- switch ( high - low )
- {
- case 1:
- // We have 2 elements
- int result = comparator.compare( value, valueArray[pivot] );
-
- if ( result == 0 )
- {
- return pivot;
- }
-
- if ( result < 0 )
- {
- if ( pivot == low )
- {
- return -( low + 1 );
- }
- else
- {
- result = comparator.compare( value, valueArray[low] );
-
- if ( result == 0 )
- {
- return low;
- }
-
- if ( result < 0 )
- {
- return -( low + 1 );
- }
- else
- {
- return -( low + 2 );
- }
- }
- }
- else
- {
- if ( pivot == high )
- {
- return -( high + 2 );
- }
- else
- {
- result = comparator.compare( value, valueArray[high] );
-
- if ( result == 0 )
- {
- return high;
- }
-
- if ( result < 0 )
- {
- return -( high + 1 );
- }
- else
- {
- return -( high + 2 );
- }
- }
- }
-
- default:
- // We have 3 elements
- result = comparator.compare( value, valueArray[pivot] );
-
- if ( result == 0 )
- {
- return pivot;
- }
-
- if ( result < 0 )
- {
- high = pivot - 1;
- }
- else
- {
- low = pivot + 1;
- }
-
- pivot = ( high + low ) / 2;
-
- continue;
- }
+ checkAndDeserialize();
}
-
- int result = comparator.compare( value, valueArray[pivot] );
-
- if ( result == 0 )
+ catch ( IOException e )
{
- return pivot;
+ // TODO Auto-generated catch block
+ e.printStackTrace();
}
- if ( result < 0 )
- {
- return -( pivot + 1 );
- }
- else
- {
- return -( pivot + 2 );
- }
+ return super.contains( checkedValue );
}
@@ -615,15 +209,6 @@ import org.slf4j.LoggerFactory;
{
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
- // 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 )
{
@@ -635,122 +220,6 @@ import org.slf4j.LoggerFactory;
}
- @Override
- public V replaceValueArray( V newValue )
- {
- V val = super.replaceValueArray( newValue );
- // The raw value is not anymore up to date with the content
- isRawUpToDate = false;
-
- return val;
- }
-
-
- /**
- * Deserialize the values stored in an array
- */
- private void deserializeArray()
- {
- // We haven't yet deserialized the values. Let's do it now. The values are
- // necessarily stored in an array at this point
- int index = 0;
- int pos = 0;
-
- while ( pos < raw.length )
- {
- try
- {
- int size = IntSerializer.deserialize( raw, pos );
- pos += 4;
-
- V value = valueSerializer.fromBytes( raw, pos );
- pos += size;
- valueArray[index++] = value;
- }
- catch ( IOException e )
- {
- e.printStackTrace();
- }
- }
- }
-
-
- /**
- * Deserialize the values stored in a sub-btree
- */
- private void deserializeSubBtree()
- {
- // Get the sub-btree offset
- long offset = LongSerializer.deserialize( raw );
-
- // and reload the sub btree
- valueBtree = parentBtree.getRecordManager().loadDupsBtree( offset, parentBtree );
- }
-
-
- /**
- * @return The sub-btree offset
- */
- /* No qualifier */long getOffset()
- {
- if ( valueArray == null )
- {
- return ( ( PersistedBTree<V, V> ) valueBtree ).getBtreeOffset();
- }
- else
- {
- return -1L;
- }
- }
-
-
- /**
- * Constructs the sub-BTree using bulkload instead of performing sequential inserts.
- *
- * @param btree the sub-BTtree to be constructed
- * @param dupKeyValues the array of values to be inserted as keys
- * @return The created BTree
- * @throws Exception
- */
- private BTree<V, V> build( PersistedBTree<V, V> btree, final V[] dupKeyValues ) throws Exception
- {
- Iterator<Tuple<V, V>> valueIterator = new Iterator<Tuple<V, V>>()
- {
- int pos = 0;
-
-
- @Override
- public Tuple<V, V> next()
- {
- // We can now return the found value
- V value = dupKeyValues[pos];
- pos++;
-
- return new Tuple<V, V>( value, value );
- }
-
-
- @Override
- public boolean hasNext()
- {
- // Check that we have at least one element to read
- return pos < dupKeyValues.length;
- }
-
-
- @Override
- public void remove()
- {
- }
-
- };
-
- BulkLoader.load( btree, valueIterator, dupKeyValues.length );
-
- return btree;
- }
-
-
/**
* @see Object#toString()
*/
@@ -766,32 +235,8 @@ import org.slf4j.LoggerFactory;
}
else
{
- if ( valueArray == null )
- {
- sb.append( ", SubBTree" );
- }
- else
- {
- sb.append( ", array{" );
-
- boolean isFirst = true;
-
- for ( V value : valueArray )
- {
- if ( isFirst )
- {
- isFirst = false;
- }
- else
- {
- sb.append( "/" );
- }
-
- sb.append( value );
- }
-
- sb.append( "}" );
- }
+ sb.append( ", " );
+ sb.append( value );
}
sb.append( "]" );