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/10/27 09:48:08 UTC
svn commit: r1536066 [1/3] - in /directory/mavibot/trunk/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
main/java/org/apache/directory/mavibot/btree/managed/
main/java/org/apache/directory/mavibot/btree/memory/
main/java/org/apache/director...
Author: elecharny
Date: Sun Oct 27 08:48:07 2013
New Revision: 1536066
URL: http://svn.apache.org/r1536066
Log:
Applied a lot of changes to be able to inject more than 50 000 entries in a BTree (mainly dealing with the replacement of WeakReference with a cache).
We now have two different ind of BTrees :
- managed (ie, written on disk)
- in-memory
Duplicate values are stored as an array of values up to a number of values, then a sub-btree is created (for managed btrees only).
Added:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueCursor.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java
Removed:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/DuplicateKeyVal.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MemoryHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MultipleMemoryHolder.java
Modified:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.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/managed/AbstractPage.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RevisionNameSerializer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/CursorImpl.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.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/ElementSerializer.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/LongArraySerializer.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/managed/RecordManagerFreePageTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/RecordManagerTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeBuilderTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/MultiThreadedBtreeTest.java
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java Sun Oct 27 08:48:07 2013
@@ -32,33 +32,12 @@ import org.apache.directory.mavibot.btre
* <p>
*
* @param <K> The type for the Key
- * @param <V> The type for the stored value
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-public interface Cursor<K, V>
+public interface Cursor<K>
{
/**
- * Find the next key/value
- *
- * @return A Tuple containing the found key and value
- * @throws IOException
- * @throws EndOfFileExceededException
- */
- Tuple<K, V> next() throws EndOfFileExceededException, IOException;
-
-
- /**
- * Find the previous key/value
- *
- * @return A Tuple containing the found key and value
- * @throws IOException
- * @throws EndOfFileExceededException
- */
- Tuple<K, V> prev() throws EndOfFileExceededException, IOException;
-
-
- /**
* Tells if the cursor can return a next element
* @return true if there are some more elements
* @throws IOException
@@ -83,57 +62,6 @@ public interface Cursor<K, V>
/**
- * @return The revision this cursor is based on
- */
- long getRevision();
-
-
- /**
- * @return The creation date for this cursor
- */
- long getCreationDate();
-
-
- /**
- * Moves the cursor to the next non-duplicate key.
-
- * If the BTree contains
- *
- * <ul>
- * <li><1,0></li>
- * <li><1,1></li>
- * <li><2,0></li>
- * <li><2,1></li>
- * </ul>
- *
- * and cursor is present at <1,0> then the cursor will move to <2,0>
- *
- * @throws EndOfFileExceededException
- * @throws IOException
- */
- void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException;
-
-
- /**
- * Moves the cursor to the previous non-duplicate key
- * If the BTree contains
- *
- * <ul>
- * <li><1,0></li>
- * <li><1,1></li>
- * <li><2,0></li>
- * <li><2,1></li>
- * </ul>
- *
- * and cursor is present at <2,1> then the cursor will move to <1,1>
- *
- * @throws EndOfFileExceededException
- * @throws IOException
- */
- void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException;
-
-
- /**
* moves the cursor to the same position that was given at the time of instantiating the cursor.
*
* For example, if the cursor was created using browse() method, then beforeFirst() will
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionNameSerializer.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionNameSerializer.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionNameSerializer.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionNameSerializer.java Sun Oct 27 08:48:07 2013
@@ -86,6 +86,42 @@ public class RevisionNameSerializer exte
/**
+ * A static method used to deserialize a RevisionName from a byte array.
+ *
+ * @param in The byte array containing the RevisionName
+ * @return A RevisionName instance
+ */
+ public RevisionName fromBytes( byte[] in )
+ {
+ return deserialize( in, 0 );
+ }
+
+
+ /**
+ * A static method used to deserialize a RevisionName from a byte array.
+ *
+ * @param in The byte array containing the RevisionName
+ * @param start the position in the byte[] we will deserialize the RevisionName from
+ * @return A RevisionName instance
+ */
+ public RevisionName fromBytes( byte[] in, int start )
+ {
+ // The buffer must be 8 bytes plus 4 bytes long (the revision is a long, and the name is a String
+ if ( ( in == null ) || ( in.length < 12 + start ) )
+ {
+ throw new RuntimeException( "Cannot extract a RevisionName from a buffer with not enough bytes" );
+ }
+
+ long revision = LongSerializer.deserialize( in, start );
+ String name = StringSerializer.deserialize( in, 8 + start );
+
+ RevisionName revisionName = new RevisionName( revision, name );
+
+ return revisionName;
+ }
+
+
+ /**
* {@inheritDoc}
*/
@Override
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java?rev=1536066&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java Sun Oct 27 08:48:07 2013
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree;
+
+
+import java.io.IOException;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+
+/**
+ * A Cursor is used to fetch elements in a BTree and is returned by the
+ * @see BTree#browse method. The cursor <strng>must</strong> be closed
+ * when the user is done with it.
+ * <p>
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public interface TupleCursor<K, V> extends Cursor<K>
+{
+ /**
+ * Find the next key/value
+ *
+ * @return A Tuple containing the found key and value
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ Tuple<K, V> next() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * Find the previous key/value
+ *
+ * @return A Tuple containing the found key and value
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ Tuple<K, V> prev() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * @return The revision this cursor is based on
+ */
+ long getRevision();
+
+
+ /**
+ * @return The creation date for this cursor
+ */
+ long getCreationDate();
+
+
+ /**
+ * Moves the cursor to the next non-duplicate key.
+
+ * If the BTree contains
+ *
+ * <ul>
+ * <li><1,0></li>
+ * <li><1,1></li>
+ * <li><2,0></li>
+ * <li><2,1></li>
+ * </ul>
+ *
+ * and cursor is present at <1,0> then the cursor will move to <2,0>
+ *
+ * @throws EndOfFileExceededException
+ * @throws IOException
+ */
+ void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * Moves the cursor to the previous non-duplicate key
+ * If the BTree contains
+ *
+ * <ul>
+ * <li><1,0></li>
+ * <li><1,1></li>
+ * <li><2,0></li>
+ * <li><2,1></li>
+ * </ul>
+ *
+ * and cursor is present at <2,1> then the cursor will move to <1,1>
+ *
+ * @throws EndOfFileExceededException
+ * @throws IOException
+ */
+ void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException;
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueCursor.java?rev=1536066&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueCursor.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueCursor.java Sun Oct 27 08:48:07 2013
@@ -0,0 +1,64 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree;
+
+
+import java.io.IOException;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+
+/**
+ * A Cursor is used to fetch elements in a BTree and is returned by the
+ * @see BTree#browse method. The cursor <strng>must</strong> be closed
+ * when the user is done with it.
+ * <p>
+ *
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public interface ValueCursor<V> extends Cursor<V>
+{
+ /**
+ * Find the next key/value
+ *
+ * @return A Tuple containing the found key and value
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ V next() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * Find the previous key/value
+ *
+ * @return A Tuple containing the found key and value
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ V prev() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * @return The number of elements stored in the cursor
+ */
+ int size();
+}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java Sun Oct 27 08:48:07 2013
@@ -22,7 +22,6 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
import java.lang.reflect.Array;
-import java.nio.ByteBuffer;
/**
@@ -285,7 +284,7 @@ import java.nio.ByteBuffer;
*/
/* No qualifier*/void setKey( int pos, K key )
{
- keys[pos] = new KeyHolder<K>( key, null, btree.getKeySerializer() );
+ keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
}
@@ -293,11 +292,11 @@ import java.nio.ByteBuffer;
* Sets the key at a give position
*
* @param pos The position in the keys array
- * @param key the key to inject
+ * @param buffer the serialized key to inject
*/
- /* No qualifier*/void setKey( int pos, ByteBuffer buffer, K key )
+ /* No qualifier*/void setKey( int pos, byte[] buffer )
{
- keys[pos] = new KeyHolder<K>( key, buffer, btree.getKeySerializer() );
+ keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), buffer );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java Sun Oct 27 08:48:07 2013
@@ -22,8 +22,6 @@ package org.apache.directory.mavibot.btr
import java.io.Closeable;
import java.io.IOException;
-import java.lang.reflect.ParameterizedType;
-import java.lang.reflect.Type;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.util.Comparator;
@@ -36,6 +34,8 @@ import net.sf.ehcache.config.CacheConfig
import org.apache.directory.mavibot.btree.BTreeHeader;
import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.TupleCursor;
+import org.apache.directory.mavibot.btree.ValueCursor;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
import org.slf4j.Logger;
@@ -85,18 +85,12 @@ public class BTree<K, V> implements Clos
/** The size of the buffer used to write data in disk */
private int writeBufferSize;
- /** The type to use to create the keys */
- protected Class<?> keyType;
-
/** The Key serializer used for this tree.*/
private ElementSerializer<K> keySerializer;
/** The Value serializer used for this tree. */
private ElementSerializer<V> valueSerializer;
- /** The associated file. If null, this is an in-memory btree */
- //private File file;
-
/** The RecordManager if the BTree is managed */
private RecordManager recordManager;
@@ -121,6 +115,16 @@ public class BTree<K, V> implements Clos
/** The default number of pages to keep in memory */
private static final int DEFAULT_CACHE_SIZE = 1000;
+ /** The number of stored Values before we switch to a BTree */
+ 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 <-> BTree switch */
+ /*No qualifier*/static int valueThresholdUp = DEFAULT_VALUE_THRESHOLD_UP;
+ /*No qualifier*/static int valueThresholdLow = DEFAULT_VALUE_THRESHOLD_LOW;
+
/**
* Create a thread that is responsible of cleaning the transactions when
@@ -365,24 +369,6 @@ public class BTree<K, V> implements Clos
// Create the queue containing the pending read transactions
readTransactions = new ConcurrentLinkedQueue<Transaction<K, V>>();
- // We will extract the Type to use for keys, using the comparator for that
- Class<?> comparatorClass = comparator.getClass();
- Type[] types = comparatorClass.getGenericInterfaces();
-
- if ( types[0] instanceof Class )
- {
- keyType = ( Class<?> ) types[0];
- }
- else
- {
- Type[] argumentTypes = ( ( ParameterizedType ) types[0] ).getActualTypeArguments();
-
- if ( ( argumentTypes != null ) && ( argumentTypes.length > 0 ) && ( argumentTypes[0] instanceof Class<?> ) )
- {
- keyType = ( Class<?> ) argumentTypes[0];
- }
- }
-
writeLock = new ReentrantLock();
// Initialize the caches
@@ -785,7 +771,7 @@ public class BTree<K, V> implements Clos
/**
* @see Page#getValues(Object)
*/
- public DuplicateKeyVal<V> getValues( K key ) throws IOException, KeyNotFoundException
+ public ValueCursor<V> getValues( K key ) throws IOException, KeyNotFoundException
{
return rootPage.getValues( key );
}
@@ -889,7 +875,7 @@ public class BTree<K, V> implements Clos
* @return A cursor on the btree
* @throws IOException
*/
- public CursorImpl<K, V> browse() throws IOException
+ public TupleCursor<K, V> browse() throws IOException
{
Transaction<K, V> transaction = beginReadTransaction();
@@ -1085,15 +1071,6 @@ public class BTree<K, V> implements Clos
/**
- * @return the type for the keys
- */
- /* No qualifier*/Class<?> getKeyType()
- {
- return keyType;
- }
-
-
- /**
* @return the comparator
*/
public Comparator<K> getComparator()
@@ -1256,17 +1233,10 @@ public class BTree<K, V> implements Clos
* @param value The value to store
* @return The value holder
*/
- /* no qualifier */ElementHolder<V, K, V> createValueHolder( V value )
+ @SuppressWarnings("unchecked")
+ /* no qualifier */ValueHolder<V> createValueHolder( V value )
{
- if ( isAllowDuplicates() )
- {
- return new MultipleMemoryHolder<K, V>( this, value );
- }
- else
- {
- // Atm, keep the values in memory
- return new MemoryHolder<K, V>( this, value );
- }
+ return new ValueHolder<V>( recordManager, valueSerializer, value );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java Sun Oct 27 08:48:07 2013
@@ -76,13 +76,15 @@ public class BTreeBuilder<K, V>
lstLeaves.add( leaf1 );
int leafIndex = 0;
+
while ( sortedTupleItr.hasNext() )
{
Tuple<K, V> tuple = sortedTupleItr.next();
setKey( leaf1, leafIndex, tuple.getKey() );
- MemoryHolder<K, V> eh = new MemoryHolder<K, V>( btree, tuple.getValue() );
+ ValueHolder<V> eh = new ValueHolder<V>( btree.getRecordManager(), btree.getValueSerializer(),
+ tuple.getValue() );
setValue( leaf1, leafIndex, eh );
@@ -111,12 +113,11 @@ public class BTreeBuilder<K, V>
lastLeaf.nbElems = n;
KeyHolder<K>[] keys = lastLeaf.keys;
- Class<?> keyType = btree.getKeyType();
- lastLeaf.keys = ( KeyHolder[] ) Array.newInstance( keyType, n );
+ lastLeaf.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n );
System.arraycopy( keys, 0, lastLeaf.keys, 0, n );
- ElementHolder<V, K, V>[] values = lastLeaf.values;
- lastLeaf.values = ( MemoryHolder<K, V>[] ) Array.newInstance( MemoryHolder.class, n );
+ ValueHolder<V>[] values = lastLeaf.values;
+ lastLeaf.values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, n );
System.arraycopy( values, 0, lastLeaf.values, 0, n );
break;
@@ -179,8 +180,7 @@ public class BTreeBuilder<K, V>
lastNode.nbElems = n;
KeyHolder<K>[] keys = lastNode.keys;
- Class<?> keyType = btree.getKeyType();
- lastNode.keys = ( KeyHolder[] ) Array.newInstance( keyType, n );
+ lastNode.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n );
System.arraycopy( keys, 0, lastNode.keys, 0, n );
break;
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java Sun Oct 27 08:48:07 2013
@@ -21,7 +21,6 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
-import java.nio.ByteBuffer;
import java.util.LinkedList;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
@@ -227,11 +226,12 @@ public class BTreeFactory
/**
* Set the key at a give position
* @param pos The position in the keys array
- * @param key the key to inject
+ * @param pos the position of this key in the page
+ * @param buffer the byte[] containing the serialized key
*/
- public static <K, V> void setKey( Page<K, V> page, int pos, ByteBuffer buffer, K key )
+ public static <K, V> void setKey( Page<K, V> page, int pos, byte[] buffer )
{
- ( ( AbstractPage<K, V> ) page ).setKey( pos, buffer, key );
+ ( ( AbstractPage<K, V> ) page ).setKey( pos, buffer );
}
@@ -240,7 +240,7 @@ public class BTreeFactory
* @param pos The position in the values array
* @param value the value to inject
*/
- public static <K, V> void setValue( Leaf<K, V> page, int pos, ElementHolder<V, K, V> value )
+ public static <K, V> void setValue( Leaf<K, V> page, int pos, ValueHolder<V> value )
{
page.setValue( pos, value );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java Sun Oct 27 08:48:07 2013
@@ -22,14 +22,13 @@ package org.apache.directory.mavibot.btr
import static org.apache.directory.mavibot.btree.managed.InternalUtil.changeNextDupsContainer;
import static org.apache.directory.mavibot.btree.managed.InternalUtil.changePrevDupsContainer;
-import static org.apache.directory.mavibot.btree.managed.InternalUtil.setDupsContainer;
import java.io.IOException;
import java.util.LinkedList;
import java.util.NoSuchElementException;
-import org.apache.directory.mavibot.btree.Cursor;
import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.TupleCursor;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
@@ -44,7 +43,7 @@ import org.apache.directory.mavibot.btre
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-public class CursorImpl<K, V> implements Cursor<K, V>
+public class CursorImpl<K, V> implements TupleCursor<K, V>
{
/** The transaction used for this cursor */
private Transaction<K, V> transaction;
@@ -124,40 +123,9 @@ public class CursorImpl<K, V> implements
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
tuple.setKey( leaf.keys[parentPos.pos].getKey() );
- if ( allowDuplicates )
- {
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
-
- if ( mvHolder.isSingleValue() )
- {
- tuple.setValue( mvHolder.getValue( btree ) );
- parentPos.pos++;
- }
- else
- {
- setDupsContainer( parentPos, btree );
-
- // can happen if next() is called after prev()
- if ( parentPos.dupPos < 0 )
- {
- parentPos.dupPos = 0;
- }
-
- tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
- parentPos.dupPos++;
-
- if ( parentPos.dupsContainer.getNbElems() == parentPos.dupPos )
- {
- parentPos.pos++;
- changeNextDupsContainer( parentPos, btree );
- }
- }
- }
- else
- {
- tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
- parentPos.pos++;
- }
+ ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+ tuple.setValue( valueHolder.getCursor().next() );
+ parentPos.pos++;
return tuple;
}
@@ -309,86 +277,9 @@ public class CursorImpl<K, V> implements
}
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
-
- if ( allowDuplicates )
- {
- boolean posDecremented = false;
-
- // can happen if prev() was called after next()
- if ( parentPos.pos == parentPos.page.getNbElems() )
- {
- parentPos.pos--;
- posDecremented = true;
- }
-
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
-
- boolean prevHasSubtree = false;
- // if the current key has only one value then advance to previous position
- if ( mvHolder.isSingleValue() )
- {
- if ( !posDecremented )
- {
- parentPos.pos--;
- mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
- posDecremented = true;
- }
-
- if ( mvHolder.isSingleValue() )
- {
- tuple.setKey( leaf.keys[parentPos.pos].getKey() );
- tuple.setValue( mvHolder.getValue( btree ) );
- }
- else
- {
- prevHasSubtree = true;
- }
- }
- else
- {
- prevHasSubtree = true;
- }
-
- if ( prevHasSubtree )
- {
- setDupsContainer( parentPos, btree );
-
- if ( parentPos.dupPos == parentPos.dupsContainer.getNbElems() )
- {
- parentPos.dupPos--;
- }
- else if ( parentPos.dupPos == 0 )
- {
- changePrevDupsContainer( parentPos, btree );
- parentPos.pos--;
-
- if ( parentPos.dupsContainer != null )
- {
- parentPos.dupPos--;
- }
- }
- else
- {
- parentPos.dupPos--;
- }
-
- tuple.setKey( leaf.keys[parentPos.pos].getKey() );
- if ( parentPos.dupsContainer != null )
- {
- tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
- }
- else
- {
- tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
- }
- }
- }
- else
- {
- parentPos.pos--;
- tuple.setKey( leaf.keys[parentPos.pos].getKey() );
- tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
- }
+ ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+ tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+ tuple.setValue( valueHolder.getCursor().next() );
return tuple;
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java Sun Oct 27 08:48:07 2013
@@ -52,12 +52,8 @@ import java.io.IOException;
if ( parentPos.dupsContainer == null )
{
Leaf leaf = ( Leaf ) ( parentPos.page );
- MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
- if( !mvHolder.isSingleValue() )
- {
- BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
- parentPos.dupsContainer = dupsContainer;
- }
+ ValueHolder valueHolder = leaf.values[parentPos.pos];
+
}
}
@@ -80,13 +76,7 @@ import java.io.IOException;
if ( parentPos.pos < parentPos.page.getNbElems() )
{
Leaf leaf = ( Leaf ) ( parentPos.page );
- MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
- if( !mvHolder.isSingleValue() )
- {
- BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
- parentPos.dupsContainer = dupsContainer;
- parentPos.dupPos = 0;
- }
+ ValueHolder valueHolder = leaf.values[parentPos.pos];
}
}
@@ -107,21 +97,11 @@ import java.io.IOException;
}
int index = parentPos.pos - 1;
+
if ( index >= 0 )
{
Leaf leaf = ( Leaf ) ( parentPos.page );
- MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[index];
- if( !mvHolder.isSingleValue() )
- {
- BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
- parentPos.dupsContainer = dupsContainer;
- parentPos.dupPos = ( int ) parentPos.dupsContainer.getNbElems();
- }
- else
- {
- parentPos.dupsContainer = null;
- parentPos.dupPos = -1;
- }
+ ValueHolder valueHolder = leaf.values[index];
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java Sun Oct 27 08:48:07 2013
@@ -21,10 +21,8 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
-import java.nio.ByteBuffer;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
-import org.apache.directory.mavibot.btree.util.Strings;
/**
@@ -40,7 +38,7 @@ public class KeyHolder<K>
private K key;
/** The ByteBuffer storing the key */
- private ByteBuffer raw;
+ private byte[] raw;
/** The Key serializer */
private ElementSerializer<K> keySerializer;
@@ -48,36 +46,27 @@ public class KeyHolder<K>
/**
* Create a new KeyHolder instance
- * @param key The key to store
* @param keySerializer The KeySerializer instance
+ * @param key The key to store
*/
- /* No Qualifier */KeyHolder( K key, ElementSerializer<K> keySerializer )
+ /* No Qualifier */KeyHolder( ElementSerializer<K> keySerializer, K key )
{
this.key = key;
this.keySerializer = keySerializer;
- raw = ByteBuffer.wrap( keySerializer.serialize( key ) );
+ raw = keySerializer.serialize( key );
}
/**
* Create a new KeyHolder instance
- * @param key The key to store
- * @param raw the bytes representing the serialized key
* @param keySerializer The KeySerializer instance
+ * @param raw the bytes representing the serialized key
*/
- /* No Qualifier */KeyHolder( K key, ByteBuffer raw, ElementSerializer<K> keySerializer )
+ /* No Qualifier */KeyHolder( ElementSerializer<K> keySerializer, byte[] raw )
{
- this.key = key;
+ this.key = null;
this.keySerializer = keySerializer;
-
- if ( raw != null )
- {
- this.raw = raw;
- }
- else
- {
- raw = ByteBuffer.wrap( keySerializer.serialize( key ) );
- }
+ this.raw = raw;
}
@@ -90,7 +79,7 @@ public class KeyHolder<K>
{
try
{
- key = keySerializer.deserialize( raw );
+ key = keySerializer.fromBytes( raw );
}
catch ( IOException ioe )
{
@@ -108,14 +97,14 @@ public class KeyHolder<K>
public void setKey( K key )
{
this.key = key;
- raw = ByteBuffer.wrap( keySerializer.serialize( key ) );
+ raw = keySerializer.serialize( key );
}
/**
* @return The internal serialized byte[]
*/
- /* No qualifier */ByteBuffer getBuffer()
+ /* No qualifier */byte[] getBuffer()
{
return raw;
}
@@ -135,17 +124,18 @@ public class KeyHolder<K>
sb.append( key );
sb.append( ", " );
}
+ else
+ {
+ sb.append( "null," );
+ }
- if ( raw.isDirect() )
+ if ( raw != null )
{
- byte[] bytes = new byte[raw.limit()];
- raw.get( bytes );
- raw.rewind();
- Strings.dumpBytes( bytes );
+ sb.append( raw.length );
}
else
{
- sb.append( Strings.dumpBytes( raw.array() ) );
+ sb.append( "null" );
}
sb.append( "]" );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java Sun Oct 27 08:48:07 2013
@@ -27,6 +27,7 @@ import java.lang.reflect.Array;
import java.util.LinkedList;
import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.ValueCursor;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
@@ -42,7 +43,7 @@ import org.apache.directory.mavibot.btre
/* No qualifier */class Leaf<K, V> extends AbstractPage<K, V>
{
/** Values associated with keys */
- protected ElementHolder<V, K, V>[] values;
+ protected ValueHolder<V>[] values;
/**
@@ -68,16 +69,7 @@ import org.apache.directory.mavibot.btre
/* No qualifier */Leaf( BTree<K, V> btree, long revision, int nbElems )
{
super( btree, revision, nbElems );
-
- if ( btree.isAllowDuplicates() )
- {
- this.values = ( MultipleMemoryHolder<K, V>[] ) Array.newInstance( MultipleMemoryHolder.class,
- nbElems );
- }
- else
- {
- this.values = ( MemoryHolder<K, V>[] ) Array.newInstance( MemoryHolder.class, nbElems );
- }
+ values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, nbElems );
}
@@ -156,79 +148,30 @@ import org.apache.directory.mavibot.btre
int index = -( pos + 1 );
- if ( btree.isAllowDuplicates() )
- {
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[index];
-
- //FIXME should the internal sub-tree should be deleted from RM?
+ ValueHolder<V> valueHolder = values[index];
- V existingVal = mvHolder.getValue( btree );
-
- if ( value == null ) // this is a case to delete entire <K,sub-BTree> or <K,single-V>
- {
- removedElement = new Tuple<K, V>( keys[index].getKey(), existingVal ); // the entire value was removed
- keyRemoved = true;
- }
- else
+ 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 ) )
{
- if ( mvHolder.isSingleValue() )
+ if ( valueHolder.size() == 1 )
{
- if ( btree.getValueSerializer().compare( value, existingVal ) == 0 )
- {
- removedElement = new Tuple<K, V>( keys[index].getKey(), existingVal ); // the entire value was removed
- keyRemoved = true;
- }
- else
- // value is not found
- {
- return NotPresentResult.NOT_PRESENT;
- }
+ removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // the entire value was removed
+ keyRemoved = true;
}
else
{
- BTree<V, V> dups = ( BTree<V, V> ) existingVal;
-
- if ( dups.hasKey( value ) )
- {
- dups.delete( value );
-
- if ( dups.getNbElems() == 0 )
- {
- keyRemoved = true;
- }
- else
- {
- if ( dups.getNbElems() == 1 )
- {
- //FIXME switch to single value mode
- mvHolder.switchToSingleValMode();
- }
- }
+ removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // the entire value was removed
- removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // we deleted only one value (even if it is from a tree of size 1)
- }
- else
- // value is not found
- {
- return NotPresentResult.NOT_PRESENT;
- }
+ valueHolder.remove( value );
}
}
- }
- else
- {
- V existing = values[index].getValue( btree );
-
- if ( ( ( existing == null ) && ( value == null ) ) || ( value == null ) )
- {
- removedElement = new Tuple<K, V>( keys[index].getKey(), existing );
- keyRemoved = true;
- }
- else if ( btree.getValueSerializer().compare( value, existing ) == 0 )
- {
- removedElement = new Tuple<K, V>( keys[index].getKey(), value );
- keyRemoved = true;
- }
else
{
return NotPresentResult.NOT_PRESENT;
@@ -406,7 +349,7 @@ import org.apache.directory.mavibot.btre
{
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[sibling.getNbElems() - 1].getKey();
- ElementHolder<V, K, V> siblingValue = sibling.values[sibling.getNbElems() - 1];
+ ValueHolder<V> siblingValue = sibling.values[sibling.getNbElems() - 1];
// Create the new sibling, with one less element at the end
Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
@@ -416,7 +359,7 @@ import org.apache.directory.mavibot.btre
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
// Insert the borrowed element
- newLeaf.keys[0] = new KeyHolder<K>( siblingKey, btree.getKeySerializer() );
+ newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
newLeaf.values[0] = siblingValue;
// Copy the keys and the values up to the insertion position,
@@ -453,7 +396,7 @@ import org.apache.directory.mavibot.btre
{
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[0].getKey();
- ElementHolder<V, K, V> siblingHolder = sibling.values[0];
+ ValueHolder<V> siblingHolder = sibling.values[0];
// Create the new sibling
Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
@@ -467,7 +410,7 @@ import org.apache.directory.mavibot.btre
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
// Insert the borrowed element at the end
- newLeaf.keys[nbElems - 1] = new KeyHolder<K>( siblingKey, btree.getKeySerializer() );
+ newLeaf.keys[nbElems - 1] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
newLeaf.values[nbElems - 1] = siblingHolder;
// Copy the keys and the values up to the deletion position,
@@ -533,26 +476,22 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- if ( btree.isAllowDuplicates() )
- {
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
+ ValueHolder<V> valueHolder = values[-( pos + 1 )];
- if ( mvHolder.isSingleValue() )
- {
- return mvHolder.getValue( btree );
- }
- else
- {
- // always return the first value for get(key) when duplicates are allowed
- BTree<V, V> dupTree = ( BTree<V, V> ) mvHolder.getValue( btree );
+ ValueCursor<V> cursor = valueHolder.getCursor();
- return dupTree.rootPage.getLeftMostKey();
- }
- }
+ cursor.beforeFirst();
- V v = values[-( pos + 1 )].getValue( btree );
+ if ( cursor.hasNext() )
+ {
+ V value = cursor.next();
- return v;
+ return value;
+ }
+ else
+ {
+ return null;
+ }
}
else
{
@@ -581,7 +520,7 @@ import org.apache.directory.mavibot.btre
* {@inheritDoc}
*/
@Override
- public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
{
if ( !btree.isAllowDuplicates() )
{
@@ -592,14 +531,9 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
-
- if ( mvHolder.isSingleValue() )
- {
- return new DuplicateKeyVal<V>( mvHolder.getValue( btree ) );
- }
+ ValueHolder<V> valueHolder = values[-( pos + 1 )];
- return new DuplicateKeyVal<V>( ( BTree<V, V> ) mvHolder.getValue( btree ) );
+ return valueHolder.getCursor();
}
else
{
@@ -631,25 +565,9 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- if ( btree.isAllowDuplicates() )
- {
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
- if ( mvHolder.isSingleValue() )
- {
- return ( btree.getValueSerializer().compare( value, mvHolder.getValue( btree ) ) == 0 );
- }
- else
- {
- // always return the first value for get(key) when duplicates are allowed
- BTree<V, V> dupTree = ( ( BTree<V, V> ) mvHolder.getValue( btree ) );
- return dupTree.hasKey( value );
- }
- }
- else
- {
- V v = values[-( pos + 1 )].getValue( btree );
- return ( btree.getValueSerializer().compare( value, v ) == 0 );
- }
+ ValueHolder<V> valueHolder = values[-( pos + 1 )];
+
+ return valueHolder.contains( value );
}
else
{
@@ -661,7 +579,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- public ElementHolder<V, K, V> getValue( int pos )
+ public ValueHolder<V> getValue( int pos )
{
if ( pos < nbElems )
{
@@ -679,7 +597,7 @@ import org.apache.directory.mavibot.btre
* @param pos The position in the values array
* @param value the value to inject
*/
- public void setValue( int pos, ElementHolder<V, K, V> value )
+ public void setValue( int pos, ValueHolder<V> value )
{
values[pos] = value;
}
@@ -772,7 +690,23 @@ 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 );
+
+ // It' not enough to copy the ValueHolder, we have to clone them
+ // as ValueHolders are mutable
+ int pos = 0;
+
+ for ( ValueHolder<V> valueHolder : values )
+ {
+ try
+ {
+ newLeaf.values[pos++] = valueHolder.clone();
+ }
+ catch ( CloneNotSupportedException e )
+ {
+ // TODO Auto-generated catch block
+ e.printStackTrace();
+ }
+ }
return newLeaf;
}
@@ -799,54 +733,17 @@ import org.apache.directory.mavibot.btre
newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
}
- V oldValue = null;
-
- if ( btree.isAllowDuplicates() )
- {
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) newLeaf.values[pos];
+ // Get the previous value from the leaf (it's a copy)
+ ValueHolder<V> valueHolder = newLeaf.values[pos];
- if ( mvHolder.isSingleValue() )
- {
- V singleVal = mvHolder.getValue( btree );
-
- // see if the given value already matches
- if ( btree.getValueSerializer().compare( value, singleVal ) == 0 )
- {
- oldValue = value;
- }
- else
- // create a sub-tree
- {
- mvHolder.createAndSwitchToSubTree();
- }
- }
-
- // if oldValue is null then the given 'value' is different and needs to be added
- // ('oldValue' will be not null if it matched with the 'singleValue', see above nested if block )
- if ( oldValue == null )
- {
- BTree<V, V> dupValues = ( BTree<V, V> ) mvHolder.getValue( btree );
-
- // return value will always be null here
- if ( !dupValues.hasKey( value ) )
- {
- dupValues.insert( value, null, 0 );
- }
- else
- {
- oldValue = value;
- }
- }
- }
- else
+ if ( !valueHolder.contains( value ) )
{
- // Now we can inject the value
- oldValue = newLeaf.values[pos].getValue( btree );
- newLeaf.values[pos] = btree.createValueHolder( value );
+ valueHolder.add( value );
+ newLeaf.values[pos] = valueHolder;
}
// Create the result
- InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue );
+ InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, ( V ) valueHolder );
result.addCopiedPage( this );
return result;
@@ -868,25 +765,13 @@ import org.apache.directory.mavibot.btre
// First copy the current page, but add one element in the copied page
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
- // Atm, store the value in memory
-
- ElementHolder<V, K, V> valueHolder = null;
-
- if ( btree.isAllowDuplicates() )
- {
- valueHolder = new MultipleMemoryHolder<K, V>( btree, value );
- }
- else
- {
- valueHolder = new MemoryHolder<K, V>( btree, value );
- }
-
- //ValueHolder<K, V> valueHolder = btree.createHolder( value );
+ // Create the value holder
+ ValueHolder<V> valueHolder = btree.createValueHolder( value );
// Deal with the special case of an empty page
if ( nbElems == 0 )
{
- newLeaf.keys[0] = new KeyHolder<K>( key, btree.getKeySerializer() );
+ newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
newLeaf.values[0] = valueHolder;
}
@@ -897,7 +782,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( values, 0, newLeaf.values, 0, pos );
// Add the new element
- newLeaf.keys[pos] = new KeyHolder<K>( key, btree.getKeySerializer() );
+ newLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
newLeaf.values[pos] = valueHolder;
// And copy the remaining elements
@@ -929,7 +814,7 @@ import org.apache.directory.mavibot.btre
int middle = btree.getPageSize() >> 1;
Leaf<K, V> leftLeaf = null;
Leaf<K, V> rightLeaf = null;
- ElementHolder<V, K, V> valueHolder = btree.createValueHolder( value );
+ ValueHolder<V> valueHolder = btree.createValueHolder( value );
// Determinate where to store the new value
if ( pos <= middle )
@@ -942,7 +827,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( values, 0, leftLeaf.values, 0, pos );
// Add the new element
- leftLeaf.keys[pos] = new KeyHolder<K>( key, btree.getKeySerializer() );
+ leftLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
leftLeaf.values[pos] = valueHolder;
// And copy the remaining elements
@@ -975,7 +860,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
// Add the new element
- rightLeaf.keys[rightPos] = new KeyHolder<K>( key, btree.getKeySerializer() );
+ rightLeaf.keys[rightPos] = new KeyHolder<K>( btree.getKeySerializer(), key );
rightLeaf.values[rightPos] = valueHolder;
// And copy the remaining elements
@@ -1016,19 +901,25 @@ import org.apache.directory.mavibot.btre
*/
public Tuple<K, V> findLeftMost() throws IOException
{
- V val = null;
+ ValueCursor<V> cursor = values[0].getCursor();
- if ( btree.isAllowDuplicates() )
+ try
{
- BTree<V, V> dupTree = ( BTree<V, V> ) values[0].getValue( btree );
- val = dupTree.rootPage.getLeftMostKey();
+ cursor.beforeFirst();
+ if ( cursor.hasNext() )
+ {
+ return new Tuple<K, V>( keys[0].getKey(), cursor.next() );
+ }
+ else
+ {
+ // Null value
+ return new Tuple<K, V>( keys[0].getKey(), null );
+ }
}
- else
+ finally
{
- val = values[0].getValue( btree );
+ cursor.close();
}
-
- return new Tuple<K, V>( keys[0].getKey(), val );
}
@@ -1037,19 +928,26 @@ import org.apache.directory.mavibot.btre
*/
public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
{
- V val = null;
+ ValueCursor<V> cursor = values[0].getCursor();
- if ( btree.isAllowDuplicates() )
+ try
{
- BTree<V, V> dupTree = ( BTree<V, V> ) values[nbElems - 1].getValue( btree );
- val = dupTree.rootPage.getRightMostKey();
+ cursor.afterLast();
+
+ if ( cursor.hasPrev() )
+ {
+ return new Tuple<K, V>( keys[0].getKey(), cursor.prev() );
+ }
+ else
+ {
+ // Null value
+ return new Tuple<K, V>( keys[0].getKey(), null );
+ }
}
- else
+ finally
{
- val = values[nbElems - 1].getValue( btree );
+ cursor.close();
}
-
- return new Tuple<K, V>( keys[nbElems - 1].getKey(), val );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java Sun Oct 27 08:48:07 2013
@@ -26,6 +26,7 @@ import java.util.LinkedList;
import java.util.List;
import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.ValueCursor;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
@@ -90,10 +91,9 @@ import org.apache.directory.mavibot.btre
// Create the keys array and store the pivot into it
// We get the type of array to create from the btree
// Yes, this is an hack...
- Class<?> keyType = btree.getKeyType();
- keys = ( KeyHolder[] ) Array.newInstance( keyType, btree.getPageSize() );
+ keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, btree.getPageSize() );
- keys[0] = new KeyHolder<K>( key, btree.getKeySerializer() );
+ keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
}
@@ -124,7 +124,7 @@ import org.apache.directory.mavibot.btre
// Create the keys array and store the pivot into it
keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, btree.getPageSize() );
- keys[0] = new KeyHolder<K>( key, btree.getKeySerializer() );
+ keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
}
@@ -292,7 +292,7 @@ import org.apache.directory.mavibot.btre
int index = Math.abs( pos );
// Copy the key and children from sibling
- newNode.keys[nbElems - 1] = new KeyHolder<K>( siblingKey, btree.getKeySerializer() ); // 1
+ newNode.keys[nbElems - 1] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey ); // 1
newNode.children[nbElems] = sibling.children[0]; // 8
if ( index < 2 )
@@ -316,8 +316,8 @@ import org.apache.directory.mavibot.btre
}
// Inject the new modified page key
- newNode.keys[index - 2] = new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey(),
- btree.getKeySerializer() ); // 2
+ newNode.keys[index - 2] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ .getLeftMostKey() ); // 2
if ( index < nbElems )
{
@@ -382,8 +382,8 @@ import org.apache.directory.mavibot.btre
if ( index < 2 )
{
- newNode.keys[0] = new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey(),
- btree.getKeySerializer() );
+ newNode.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ .getLeftMostKey() );
System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
@@ -393,8 +393,8 @@ import org.apache.directory.mavibot.btre
else
{
// Set the first key
- newNode.keys[0] = new KeyHolder<K>( children[0].getValue( btree ).getLeftMostKey(),
- btree.getKeySerializer() ); //2
+ newNode.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), children[0].getValue( btree )
+ .getLeftMostKey() ); //2
if ( index > 2 )
{
@@ -403,8 +403,8 @@ import org.apache.directory.mavibot.btre
}
// Inject the modified key
- newNode.keys[index - 1] = new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey(),
- btree.getKeySerializer() ); // 3
+ newNode.keys[index - 1] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ .getLeftMostKey() ); // 3
if ( index < nbElems )
{
@@ -466,8 +466,8 @@ import org.apache.directory.mavibot.btre
// Then copy all the elements up to the deletion point
if ( index < 2 )
{
- newNode.keys[half] = new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey(),
- btree.getKeySerializer() );
+ newNode.keys[half] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ .getLeftMostKey() );
System.arraycopy( keys, 1, newNode.keys, half + 1, half - 1 );
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
@@ -478,8 +478,8 @@ import org.apache.directory.mavibot.btre
{
// Copy the left part of the node keys up to the deletion point
// Insert the new key
- newNode.keys[half] = new KeyHolder<K>( children[0].getValue( btree ).getLeftMostKey(),
- btree.getKeySerializer() ); // 3
+ newNode.keys[half] = new KeyHolder<K>( btree.getKeySerializer(), children[0].getValue( btree )
+ .getLeftMostKey() ); // 3
if ( index > 2 )
{
@@ -487,8 +487,8 @@ import org.apache.directory.mavibot.btre
}
// Inject the new merged key
- newNode.keys[half + index - 1] = new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey(),
- btree.getKeySerializer() ); //5
+ newNode.keys[half + index - 1] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult
+ .getModifiedPage().getLeftMostKey() ); //5
if ( index < half )
{
@@ -532,8 +532,8 @@ import org.apache.directory.mavibot.btre
System.arraycopy( children, 0, newNode.children, 0, index - 1 ); //6
// Inject the modified key
- newNode.keys[index - 2] = new KeyHolder<K>( mergedResult.getModifiedPage().getLeftMostKey(),
- btree.getKeySerializer() ); //2
+ newNode.keys[index - 2] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ .getLeftMostKey() ); //2
// Inject the modified children
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
@@ -550,7 +550,7 @@ import org.apache.directory.mavibot.btre
}
// Inject the new key from sibling
- newNode.keys[half - 1] = new KeyHolder<K>( sibling.findLeftMost().getKey(), btree.getKeySerializer() ); //3
+ newNode.keys[half - 1] = new KeyHolder<K>( btree.getKeySerializer(), sibling.findLeftMost().getKey() ); //3
// Copy the sibling keys
System.arraycopy( sibling.keys, 0, newNode.keys, half, half );
@@ -715,9 +715,9 @@ import org.apache.directory.mavibot.btre
if ( borrowedResult.isFromRight() )
{
// Update the keys
- newPage.keys[pos] = new KeyHolder<K>( modifiedPage.findLeftMost().getKey(), btree.getKeySerializer() );
- newPage.keys[pos + 1] = new KeyHolder<K>( modifiedSibling.findLeftMost().getKey(),
- btree.getKeySerializer() );
+ newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost().getKey() );
+ newPage.keys[pos + 1] = new KeyHolder<K>( btree.getKeySerializer(), modifiedSibling.findLeftMost()
+ .getKey() );
// Update the children
newPage.children[pos + 1] = createHolder( modifiedPage );
@@ -726,7 +726,7 @@ import org.apache.directory.mavibot.btre
else
{
// Update the keys
- newPage.keys[pos] = new KeyHolder<K>( modifiedPage.findLeftMost().getKey(), btree.getKeySerializer() );
+ newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost().getKey() );
// Update the children
newPage.children[pos] = createHolder( modifiedSibling );
@@ -738,7 +738,7 @@ import org.apache.directory.mavibot.btre
if ( borrowedResult.isFromRight() )
{
// Update the keys
- newPage.keys[pos] = new KeyHolder<K>( modifiedSibling.findLeftMost().getKey(), btree.getKeySerializer() );
+ newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedSibling.findLeftMost().getKey() );
// Update the children
newPage.children[pos] = createHolder( modifiedPage );
@@ -747,8 +747,8 @@ import org.apache.directory.mavibot.btre
else
{
// Update the keys
- newPage.keys[pos - 1] = new KeyHolder<K>( modifiedPage.findLeftMost().getKey(),
- btree.getKeySerializer() );
+ newPage.keys[pos - 1] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost()
+ .getKey() );
// Update the children
newPage.children[pos - 1] = createHolder( modifiedSibling );
@@ -800,8 +800,8 @@ import org.apache.directory.mavibot.btre
System.arraycopy( keys, 0, newNode.keys, 0, index );
}
- newNode.keys[index] = new KeyHolder<K>( mergedResult.getModifiedPage().findLeftMost().getKey(),
- btree.getKeySerializer() );
+ newNode.keys[index] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
+ .findLeftMost().getKey() );
if ( index < nbElems - 2 )
{
@@ -854,7 +854,7 @@ import org.apache.directory.mavibot.btre
* {@inheritDoc}
*/
@Override
- public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
{
int pos = findPos( key );
@@ -892,7 +892,6 @@ import org.apache.directory.mavibot.btre
if ( page == null )
{
System.out.println( "Page is null for pos = " + pos + ", children = " + children[pos] );
- System.out.println( "Key = " + key );
}
return page.hasKey( key );
@@ -1058,7 +1057,7 @@ import org.apache.directory.mavibot.btre
}
// Add the new key and children
- newNode.keys[pos] = new KeyHolder<K>( key, btree.getKeySerializer() );
+ newNode.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
// If the BTree is managed, we now have to write the modified page on disk
// and to add this page to the list of modified pages
@@ -1117,7 +1116,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( children, 0, newLeftPage.children, 0, pos );
// Add the new element
- newLeftPage.keys[pos] = new KeyHolder<K>( pivot, btree.getKeySerializer() );
+ newLeftPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), pivot );
newLeftPage.children[pos] = createHolder( leftPage );
newLeftPage.children[pos + 1] = createHolder( rightPage );
@@ -1167,7 +1166,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( children, middle + 1, newRightPage.children, 0, pos - middle - 1 );
// Add the new element
- newRightPage.keys[pos - middle - 1] = new KeyHolder<K>( pivot, btree.getKeySerializer() );
+ newRightPage.keys[pos - middle - 1] = new KeyHolder<K>( btree.getKeySerializer(), pivot );
newRightPage.children[pos - middle - 1] = createHolder( leftPage );
newRightPage.children[pos - middle] = createHolder( rightPage );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java?rev=1536066&r1=1536065&r2=1536066&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java Sun Oct 27 08:48:07 2013
@@ -24,6 +24,7 @@ import java.io.IOException;
import java.util.LinkedList;
import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.ValueCursor;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
@@ -111,7 +112,7 @@ import org.apache.directory.mavibot.btre
* @throws IOException If we have an error while trying to access the page
* @throws IllegalArgumentException If duplicates are not enabled
*/
- DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;
+ ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;
/**