+ * Assuming that the array is zero-indexed, the returned value will be :
+ * position = - ( position + 1) + *
+ * So for the following table of keys :
+ *

```+     * +---+---+---+---+
+     * | b | d | f | h |
+     * +---+---+---+---+
+     *   0   1   2   3
+     * ```
+ * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).
+ * Computing the real position is just a matter to get -(position++). + *

+ * If we don't find the key in the table, we will return the position of the key + * immediately above the key we are looking for.
+ * For instance, looking for : + *

+ *
• 'a' will return 0
• + *
• 'b' will return -1
• + *
• 'c' will return 1
• + *
• 'd' will return -2
• + *
• 'e' will return 2
• + *
• 'f' will return -3
• + *
• 'g' will return 3
• + *
• 'h' will return -4
• + *
• 'i' will return 4
• + *

- * Assuming that the array is zero-indexed, the returned value will be :
- * position = - ( position + 1) - *
- * So for the following table of keys :
- *

```-     * +---+---+---+---+
-     * | b | d | f | h |
-     * +---+---+---+---+
-     *   0   1   2   3
-     * ```
- * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).
- * Computing the real position is just a matter to get -(position++). - *

- * If we don't find the key in the table, we will return the position of the key - * immediately above the key we are looking for.
- * For instance, looking for : - *

- *
• 'a' will return 0
• - *
• 'b' will return -1
• - *
• 'c' will return 1
• - *
• 'd' will return -2
• - *
• 'e' will return 2
• - *
• 'f' will return -3
• - *
• 'g' will return 3
• - *
• 'h' will return -4
• - *
• 'i' will return 4
• - *

- * Assuming that the array is zero-indexed, the returned value will be :
- * position = - ( position + 1) - *
- * So for the following table of keys :
- *

```-     * +---+---+---+---+
-     * | b | d | f | h |
-     * +---+---+---+---+
-     *   0   1   2   3
-     * ```
- * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).
- * Computing the real position is just a matter to get -(position++). - *

- * If we don't find the key in the table, we will return the position of the key - * immediately above the key we are looking for.
- * For instance, looking for : - *

- *
• 'a' will return 0
• - *
• 'b' will return -1
• - *
• 'c' will return 1
• - *
• 'd' will return -2
• - *
• 'e' will return 2
• - *
• 'f' will return -3
• - *
• 'g' will return 3
• - *
• 'h' will return -4
• - *
• 'i' will return 4
• - *
- * - * - * @param key The key to find - * @return The position in the page. - */ - public int findPos( K key ) - { - // Deal with the special key where we have an empty page - if ( nbElems == 0 ) - { - return 0; - } - - int min = 0; - int max = nbElems - 1; - - // binary search - while ( min < max ) - { - int middle = ( min + max + 1 ) >> 1; - - int comp = compare( keys[middle], key ); - - if ( comp < 0 ) - { - min = middle + 1; - } - else if ( comp > 0 ) - { - max = middle - 1; - } - else - { - // Special case : the key already exists, - // we can return immediately. The value will be - // negative, and as the index may be 0, we subtract 1 - return -( middle + 1 ); - } - } - - // Special case : we don't know if the key is present - int comp = compare( keys[max], key ); - - if ( comp == 0 ) - { - return -( max + 1 ); - } - else - { - if ( comp < 0 ) - { - return max + 1; - } - else - { - return max; - } - } - } - - - /** - * Compares two keys - * - * @param key1 The first key - * @param key2 The second key - * @return -1 if the first key is above the second one, 1 if it's below, and 0 - * if the two keys are equal - */ - private final int compare( K key1, K key2 ) - { - if ( key1 == key2 ) - { - return 0; - } - - if ( key1 == null ) - { - return 1; - } - - if ( key2 == null ) - { - return -1; - } - - return btree.getComparator().compare( key1, key2 ); - } - - - /** - * {@inheritDoc} - */ - public long getRevision() - { - return revision; - } - - - /** - * {@inheritDoc} - */ - public K getKey( int pos ) - { - if ( pos < nbElems ) - { - return keys[pos]; - } - else - { - return null; - } - } - - - /** * Sets the key at a give position * * @param pos The position in the keys array @@ -296,70 +118,6 @@ import org.apache.directory.mavibot.btre */ /* No qualifier*/void setKey( int pos, K key ) { - keys[pos] = key; - } - - - /** - * {@inheritDoc} - */ - public long getOffset() - { - return offset; - } - - - /** - * @param offset the offset to set - */ - /* No qualifier */void setOffset( long offset ) - { - this.offset = offset; - } - - - /** - * {@inheritDoc} - */ - public long getLastOffset() - { - return lastOffset; - } - - - /** - * {@inheritDoc} - */ - /* No qualifier */void setLastOffset( long lastOffset ) - { - this.lastOffset = lastOffset; - } - - - /** - * @see Object#toString() - */ - public String toString() - { - StringBuilder sb = new StringBuilder(); - - sb.append( "r" ).append( revision ); - sb.append( ", nbElems:" ).append( nbElems ); - - if ( offset > 0 ) - { - sb.append( ", offset:" ).append( offset ); - } - - return sb.toString(); - } - - - /** - * {@inheritDoc} - */ - public String dumpPage( String tabs ) - { - return ""; + keys[pos] = new KeyHolder( key ); } } Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java?rev=1550673&r1=1550672&r2=1550673&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java Fri Dec 13 10:13:21 2013 @@ -191,7 +191,7 @@ public class BTreeFactory */ public static void setKey( Page page, int pos, K key ) { - ( ( AbstractPage ) page ).setKey( pos, key ); + ( ( AbstractInMemoryPage ) page ).setKey( pos, key ); } Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java?rev=1550673&r1=1550672&r2=1550673&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTree.java Fri Dec 13 10:13:21 2013 @@ -26,11 +26,8 @@ import java.io.File; import java.io.FileOutputStream; import java.io.IOException; import java.io.RandomAccessFile; -import java.lang.reflect.ParameterizedType; -import java.lang.reflect.Type; import java.nio.ByteBuffer; import java.nio.channels.FileChannel; -import java.util.Comparator; import java.util.concurrent.ConcurrentLinkedQueue; import java.util.concurrent.locks.ReentrantLock; @@ -47,13 +44,11 @@ import org.apache.directory.mavibot.btre import org.apache.directory.mavibot.btree.ModifyResult; import org.apache.directory.mavibot.btree.NotPresentResult; import org.apache.directory.mavibot.btree.Page; -import org.apache.directory.mavibot.btree.ParentPos; import org.apache.directory.mavibot.btree.RemoveResult; import org.apache.directory.mavibot.btree.SplitResult; import org.apache.directory.mavibot.btree.Transaction; 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.BufferHandler; import org.apache.directory.mavibot.btree.serializer.ElementSerializer; @@ -85,8 +80,6 @@ public class InMemoryBTree extends public static final String JOURNAL_SUFFIX = ".log"; /** The type to use to create the keys */ - protected Class keyType; - /** The associated file. If null, this is an in-memory btree */ private File file; @@ -307,24 +300,6 @@ public class InMemoryBTree extends // Create the queue containing the pending read transactions readTransactions = new ConcurrentLinkedQueue>(); - // We will extract the Type to use for keys, using the comparator for that - Class comparatorClass = keySerializer.getComparator().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(); // Check the files and create them if missing @@ -548,15 +523,6 @@ public class InMemoryBTree extends /** - * @return the type for the keys - */ - public Class getKeyType() - { - return keyType; - } - - - /** * Write the data in the ByteBuffer, and eventually on disk if needed. * * @param channel The channel we want to write to Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java?rev=1550673&r1=1550672&r2=1550673&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeBuilder.java Fri Dec 13 10:13:21 2013 @@ -32,7 +32,9 @@ import java.util.ArrayList; import java.util.Iterator; import java.util.List; +import org.apache.directory.mavibot.btree.AbstractPage; import org.apache.directory.mavibot.btree.BTree; +import org.apache.directory.mavibot.btree.KeyHolder; import org.apache.directory.mavibot.btree.Page; import org.apache.directory.mavibot.btree.Tuple; import org.apache.directory.mavibot.btree.serializer.ElementSerializer; @@ -105,17 +107,16 @@ public class InMemoryBTreeBuilder // remove null keys and values from the last leaf and resize Leaf lastLeaf = ( Leaf ) lstLeaves.get( lstLeaves.size() - 1 ); - for ( int i = 0; i < lastLeaf.nbElems; i++ ) + for ( int i = 0; i < lastLeaf.getNbElems(); i++ ) { - if ( lastLeaf.keys[i] == null ) + if ( lastLeaf.getKeys()[i] == null ) { int n = i; - lastLeaf.nbElems = n; - K[] keys = lastLeaf.keys; + lastLeaf.setNbElems( n ); + KeyHolder[] keys = lastLeaf.getKeys(); - Class keyType = btree.getKeyType(); - lastLeaf.keys = ( K[] ) Array.newInstance( keyType, n ); - System.arraycopy( keys, 0, lastLeaf.keys, 0, n ); + lastLeaf.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) ); + System.arraycopy( keys, 0, lastLeaf.getKeys(), 0, n ); ValueHolder[] values = lastLeaf.values; lastLeaf.values = ( ValueHolder[] ) Array.newInstance( ValueHolder.class, n ); @@ -175,17 +176,16 @@ public class InMemoryBTreeBuilder // remove null keys and values from the last node and resize AbstractPage lastNode = ( AbstractPage ) lstNodes.get( lstNodes.size() - 1 ); - for ( int j = 0; j < lastNode.nbElems; j++ ) + for ( int j = 0; j < lastNode.getNbElems(); j++ ) { - if ( lastNode.keys[j] == null ) + if ( lastNode.getKey( j ) == null ) { int n = j; - lastNode.nbElems = n; - K[] keys = lastNode.keys; + lastNode.setNbElems( n ); + KeyHolder[] keys = lastNode.getKeys(); - Class keyType = btree.getKeyType(); - lastNode.keys = ( K[] ) Array.newInstance( keyType, n ); - System.arraycopy( keys, 0, lastNode.keys, 0, n ); + lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) ); + System.arraycopy( keys, 0, lastNode.getKeys(), 0, n ); break; }