Return-Path: X-Original-To: apmail-directory-commits-archive@www.apache.org Delivered-To: apmail-directory-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id B2C0917EB0 for ; Tue, 24 Feb 2015 13:44:00 +0000 (UTC) Received: (qmail 35777 invoked by uid 500); 24 Feb 2015 13:44:00 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 35707 invoked by uid 500); 24 Feb 2015 13:44:00 -0000 Mailing-List: contact commits-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@directory.apache.org Delivered-To: mailing list commits@directory.apache.org Received: (qmail 35615 invoked by uid 99); 24 Feb 2015 13:44:00 -0000 Received: from eris.apache.org (HELO hades.apache.org) (140.211.11.105) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 24 Feb 2015 13:44:00 +0000 Received: from hades.apache.org (localhost [127.0.0.1]) by hades.apache.org (ASF Mail Server at hades.apache.org) with ESMTP id 53542AC0309 for ; Tue, 24 Feb 2015 13:44:00 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1661949 [3/3] - in /directory/mavibot/trunk/mavibot: img/ src/main/java/org/apache/directory/mavibot/btree/ src/test/java/org/apache/directory/mavibot/btree/ Date: Tue, 24 Feb 2015 13:43:59 -0000 To: commits@directory.apache.org From: elecharny@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20150224134400.53542AC0309@hades.apache.org> Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java Tue Feb 24 13:43:59 2015 @@ -1095,11 +1095,6 @@ import org.apache.directory.mavibot.btre long t1 = System.currentTimeMillis(); - if ( nbTxns > 0 ) - { - System.out.println( "Processing old txn : " + nbTxns + ", " + ( t1 - t0 ) + "ms" ); - } - // Wait until we reach the timeout Thread.sleep( readTimeOut ); } Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java Tue Feb 24 13:43:59 2015 @@ -138,11 +138,6 @@ import org.apache.directory.mavibot.btre { Page page = children[pos].getValue(); - if ( page == null ) - { - System.out.println( "Page is null for pos = " + pos + ", children = " + children[pos] ); - } - return page.hasKey( key ); } } @@ -318,6 +313,17 @@ import org.apache.directory.mavibot.btre } + /** + * Sets the value at a give position + * @param pos The position in the values array + * @param value the value to inject + */ + /* no qualifier */void setValue( int pos, ValueHolder value ) + { + // Implementation in the leaves + } + + /** * {@inheritDoc} */ Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java Tue Feb 24 13:43:59 2015 @@ -23,6 +23,7 @@ package org.apache.directory.mavibot.btr import java.io.IOException; import java.lang.reflect.Array; import java.util.Comparator; +import java.util.Iterator; import org.apache.directory.mavibot.btree.exception.KeyNotFoundException; import org.apache.directory.mavibot.btree.serializer.ElementSerializer; @@ -247,7 +248,8 @@ import org.apache.directory.mavibot.btre } catch ( KeyNotFoundException knfe ) { - knfe.printStackTrace();return false; + knfe.printStackTrace(); + return false; } } @@ -275,9 +277,15 @@ import org.apache.directory.mavibot.btre /** + * Manage a new Sub-BTree . + */ + protected abstract void manageSubTree(); + + + /** * Add the value in an array */ - private void addInArray( V value ) + private void addInArray( final V value ) { // We have to check that we have reached the threshold or not if ( size() >= valueThresholdUp ) @@ -285,27 +293,61 @@ import org.apache.directory.mavibot.btre // Ok, transform the array into a btree createSubTree(); - try + Iterator> valueIterator = new Iterator>() { - for ( V val : valueArray ) + int pos = 0; + + + @Override + public Tuple next() + { + // We can now return the found value + if ( pos == valueArray.length ) + { + // Special case : deal with the added value + pos++; + + return new Tuple( value, value ); + } + else + { + V oldValue = valueArray[pos]; + pos++; + + return new Tuple( oldValue, oldValue ); + } + } + + + @Override + public boolean hasNext() + { + // Check that we have at least one element to read + return pos < valueArray.length + 1; + } + + + @Override + public void remove() { - // Here, we should insert all the values in one shot then - // write the btree on disk only once. - valueBtree.insert( val, null ); } - // We can delete the array now - nbArrayElems = 0; - valueArray = null; + }; - // And inject the new value - valueBtree.insert( value, null ); + try + { + BulkLoader.load( valueBtree, valueIterator, valueArray.length ); } catch ( IOException e ) { // TODO Auto-generated catch block e.printStackTrace(); } + + manageSubTree(); + + // And make the valueArray to be null now + valueArray = null; } else { @@ -375,24 +417,24 @@ import org.apache.directory.mavibot.btre addInBtree( value ); } } - - + + /** * {@inheritDoc} */ @Override public V replaceValueArray( V newValue ) { - if( isSubBtree() ) + if ( isSubBtree() ) { throw new IllegalStateException( "method is not applicable for the duplicate B-Trees" ); } - + V tmp = valueArray[0]; - + nbArrayElems = 1; valueArray[0] = newValue; - + return tmp; } Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java Tue Feb 24 13:43:59 2015 @@ -59,7 +59,7 @@ import java.util.concurrent.atomic.Atomi private long rootPageOffset; /** The position of the B-tree header in the file */ - private long btreeHeaderOffset; + private long btreeHeaderOffset = RecordManager.NO_PAGE; // Those are data which aren't serialized : they are in memory only */ /** A Map containing the rootPage for this tree */ Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BulkLoader.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BulkLoader.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BulkLoader.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BulkLoader.java Tue Feb 24 13:43:59 2015 @@ -65,6 +65,27 @@ public class BulkLoader NODE } + /** + * A private class used to store the temporary sorted file. It's used by + * the bulkLoader + */ + private static class SortedFile + { + /** the file that contains the values */ + private File file; + + /** The number of stored values */ + private int nbValues; + + + /** A constructor for this class */ + /*No Qualifier*/SortedFile( File file, int nbValues ) + { + this.file = file; + this.nbValues = nbValues; + } + } + /** * Process the data, and creates files to store them sorted if necessary, or store them @@ -163,7 +184,7 @@ public class BulkLoader * sorted and merged elements. * @throws IOException */ - private static Tuple>>, Integer> processFiles( BTree btree, + private static Tuple>>, SortedFile> processFiles( BTree btree, Iterator>> dataIterator ) throws IOException { File file = File.createTempFile( "sortedUnique", "data" ); @@ -206,9 +227,10 @@ public class BulkLoader FileInputStream fis = new FileInputStream( file ); Iterator>> uniqueIterator = createUniqueFileIterator( btree, fis ); + SortedFile sortedFile = new SortedFile( file, nbReads ); - Tuple>>, Integer> result = new Tuple>>, Integer>( - uniqueIterator, nbReads ); + Tuple>>, SortedFile> result = new Tuple>>, SortedFile>( + uniqueIterator, sortedFile ); return result; } @@ -222,7 +244,7 @@ public class BulkLoader * @param chunkSize The number of elements we may store in memory at each iteration * @throws IOException If there is a problem while processing the data */ - public static BTree load( PersistedBTree btree, Iterator> iterator, int chunkSize ) + public static BTree load( BTree btree, Iterator> iterator, int chunkSize ) throws IOException { if ( btree == null ) @@ -281,8 +303,9 @@ public class BulkLoader dataIterator = createIterator( btree, streams ); // Process the files, and construct one single file with an iterator - Tuple>>, Integer> result = processFiles( btree, dataIterator ); - resultBTree = bulkLoad( btree, result.key, result.value ); + Tuple>>, SortedFile> result = processFiles( btree, dataIterator ); + resultBTree = bulkLoad( btree, result.key, result.value.nbValues ); + result.value.file.delete(); } // Ok, we have an iterator over sorted elements, we can now load them in the @@ -444,14 +467,18 @@ public class BulkLoader /** * Inject a tuple into a leaf */ - private static void injectInLeaf( BTree btree, Tuple> tuple, LevelInfo leafLevel ) + private static void injectInLeaf( BTree btree, Tuple> tuple, LevelInfo leafLevel ) { PersistedLeaf leaf = ( PersistedLeaf ) leafLevel.getCurrentPage(); KeyHolder keyHolder = new PersistedKeyHolder( btree.getKeySerializer(), tuple.getKey() ); - ValueHolder valueHolder = new PersistedValueHolder( btree, ( V[] ) tuple.getValue().toArray() ); leaf.setKey( leafLevel.getCurrentPos(), keyHolder ); - leaf.setValue( leafLevel.getCurrentPos(), valueHolder ); + + if ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB ) + { + ValueHolder valueHolder = new PersistedValueHolder( btree, ( V[] ) tuple.getValue().toArray() ); + leaf.setValue( leafLevel.getCurrentPos(), valueHolder ); + } leafLevel.incCurrentPos(); } @@ -515,8 +542,8 @@ public class BulkLoader LevelInfo level ) throws IOException { PersistedNode node = ( PersistedNode ) level.getCurrentPage(); - if ( ( level.getCurrentPos() == 0 ) && ( node.getPage( 0 ) == null ) ) + if ( ( level.getCurrentPos() == 0 ) && ( node.getPage( 0 ) == null ) ) { node.setPageHolder( 0, pageHolder ); level.incNbAddedElems(); @@ -759,8 +786,23 @@ public class BulkLoader private static BTree bulkLoadSinglePage( BTree btree, Iterator>> dataIterator, int nbElems ) throws IOException { - // Create a new page - PersistedLeaf rootPage = ( PersistedLeaf ) BTreeFactory.createLeaf( btree, 0L, nbElems ); + // Use the root page + Page rootPage = btree.getRootPage(); + + // Initialize the root page + ( ( AbstractPage ) rootPage ).setNbElems( nbElems ); + KeyHolder[] keys = new KeyHolder[nbElems]; + ValueHolder[] values = new ValueHolder[nbElems]; + + switch ( btree.getType() ) + { + case IN_MEMORY: + ( ( InMemoryLeaf ) rootPage ).values = values; + break; + + default: + ( ( PersistedLeaf ) rootPage ).values = values; + } // We first have to inject data into the page int pos = 0; @@ -771,18 +813,31 @@ public class BulkLoader // Store the current element in the rootPage KeyHolder keyHolder = new PersistedKeyHolder( btree.getKeySerializer(), tuple.getKey() ); - ValueHolder valueHolder = new PersistedValueHolder( btree, ( V[] ) tuple.getValue().toArray() ); - rootPage.setKey( pos, keyHolder ); - rootPage.setValue( pos, valueHolder ); + keys[pos] = keyHolder; + + switch ( btree.getType() ) + { + case IN_MEMORY: + ValueHolder valueHolder = new InMemoryValueHolder( btree, ( V[] ) tuple.getValue() + .toArray() ); + ( ( InMemoryLeaf ) rootPage ).values[pos] = valueHolder; + break; + + default: + valueHolder = new PersistedValueHolder( btree, ( V[] ) tuple.getValue() + .toArray() ); + ( ( PersistedLeaf ) rootPage ).values[pos] = valueHolder; + } + pos++; } - // Now write the page on disk - ( ( PersistedBTree ) btree ).getRecordManager().writePage( btree, rootPage, 0L ); + // Update the rootPage + ( ( AbstractPage ) rootPage ).setKeys( keys ); - // Update the btree with the rootPage and the nb of added elements - ( ( PersistedBTree ) btree ).getBtreeHeader().setRootPage( rootPage ); - ( ( PersistedBTree ) btree ).getBtreeHeader().setNbElems( nbElems ); + // Update the btree with the nb of added elements, and write it$ + BTreeHeader btreeHeader = ( ( AbstractBTree ) btree ).getBtreeHeader(); + btreeHeader.setNbElems( nbElems ); return btree; } @@ -862,7 +917,8 @@ public class BulkLoader } // Now inject the page into the node - injectInNode( btree, leafLevel.getCurrentPage(), levels, 1 ); + Page currentPage = leafLevel.getCurrentPage(); + injectInNode( btree, currentPage, levels, 1 ); // Create a new page for the remaining elements nbToAdd = pageSize / 2; @@ -880,7 +936,8 @@ public class BulkLoader } // And update the parent node - injectInNode( btree, leafLevel.getCurrentPage(), levels, 1 ); + Page levelCurrentPage = leafLevel.getCurrentPage(); + injectInNode( btree, levelCurrentPage, levels, 1 ); // We are done break; @@ -910,6 +967,10 @@ public class BulkLoader } } + // Update the btree with the nb of added elements, and write it$ + BTreeHeader btreeHeader = ( ( AbstractBTree ) btree ).getBtreeHeader(); + btreeHeader.setNbElems( nbElems ); + return btree; } Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java Tue Feb 24 13:43:59 2015 @@ -134,6 +134,15 @@ import org.apache.directory.mavibot.btre /** + * Manage a new Sub-BTree + */ + protected void manageSubTree() + { + // Nothing to do + } + + + /** * Set the subBtree in the ValueHolder */ /* No qualifier*/void setSubBtree( BTree subBtree ) Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java Tue Feb 24 13:43:59 2015 @@ -67,7 +67,7 @@ public class PersistedBTree extend /*No qualifier*/static int valueThresholdLow = DEFAULT_VALUE_THRESHOLD_LOW; /** The BtreeInfo offset */ - private long btreeInfoOffset; + private long btreeInfoOffset = RecordManager.NO_PAGE; /** The internal recordManager */ private RecordManager recordManager; Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedKeyHolder.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedKeyHolder.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedKeyHolder.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedKeyHolder.java Tue Feb 24 13:43:59 2015 @@ -121,6 +121,11 @@ import org.apache.directory.mavibot.btre sb.append( key ); sb.append( ", " ); } + else if ( raw != null ) + { + K key = getKey(); + sb.append( ":" ).append( key ).append( ":," ); + } else { sb.append( "null," ); Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java Tue Feb 24 13:43:59 2015 @@ -1113,11 +1113,6 @@ import org.apache.directory.mavibot.btre */ public K getLeftMostKey() { - if ( keys.length == 0 ) - { - System.out.println( "" ); - } - return keys[0].getKey(); } @@ -1250,7 +1245,18 @@ import org.apache.directory.mavibot.btre sb.append( ", " ); } - sb.append( "<" ).append( keys[i] ).append( "," ).append( values[i] ).append( ">" ); + sb.append( "<" ).append( keys[i] ).append( "," ); + + if ( values != null ) + { + sb.append( values[i] ); + } + else + { + sb.append( "null" ); + } + + sb.append( ">" ); } } @@ -1422,7 +1428,18 @@ import org.apache.directory.mavibot.btre sb.append( ", " ); } - sb.append( "<" ).append( keys[i] ).append( "," ).append( values[i] ).append( ">" ); + sb.append( "<" ).append( keys[i] ).append( "," ); + + if ( values != null ) + { + sb.append( values[i] ); + } + else + { + sb.append( "null" ); + } + + sb.append( ">" ); } } Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java Tue Feb 24 13:43:59 2015 @@ -20,16 +20,10 @@ package org.apache.directory.mavibot.btree; -import static org.apache.directory.mavibot.btree.BTreeFactory.createLeaf; -import static org.apache.directory.mavibot.btree.BTreeFactory.createNode; -import static org.apache.directory.mavibot.btree.BTreeFactory.setKey; - import java.io.IOException; import java.lang.reflect.Array; -import java.util.ArrayList; -import java.util.Arrays; import java.util.Comparator; -import java.util.List; +import java.util.Iterator; import java.util.UUID; import org.apache.directory.mavibot.btree.exception.BTreeAlreadyCreatedException; @@ -139,6 +133,8 @@ import org.slf4j.LoggerFactory; { throw new RuntimeException( e ); } + + manageSubTree(); } } else @@ -249,29 +245,33 @@ import org.slf4j.LoggerFactory; */ protected void createSubTree() { - try - { - PersistedBTreeConfiguration configuration = new PersistedBTreeConfiguration(); - configuration.setAllowDuplicates( false ); - configuration.setKeySerializer( valueSerializer ); - configuration.setName( UUID.randomUUID().toString() ); - configuration.setValueSerializer( valueSerializer ); - configuration.setParentBTree( parentBtree ); - configuration.setBtreeType( BTreeTypeEnum.PERSISTED_SUB ); + PersistedBTreeConfiguration configuration = new PersistedBTreeConfiguration(); + 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 ); + valueBtree = BTreeFactory.createPersistedBTree( configuration ); + ( ( PersistedBTree ) valueBtree ).setRecordManager( parentBtree.getRecordManager() ); + } - try - { - // The sub-btree will not be added into the BOB. - parentBtree.getRecordManager().manage( valueBtree, RecordManager.INTERNAL_BTREE ); - raw = null; - } - catch ( BTreeAlreadyManagedException e ) - { - // should never happen - throw new BTreeAlreadyCreatedException( e ); - } + + /** + * Push the sub-BTree into the RecordManager + */ + protected void manageSubTree() + { + try + { + parentBtree.getRecordManager().manageSubBtree( valueBtree ); + raw = null; + } + catch ( BTreeAlreadyManagedException e ) + { + // should never happen + throw new BTreeAlreadyCreatedException( e ); } catch ( IOException e ) { @@ -712,159 +712,42 @@ import org.slf4j.LoggerFactory; * @return The created BTree * @throws Exception */ - private BTree build( PersistedBTree btree, V[] dupKeyValues ) throws Exception + private BTree build( PersistedBTree btree, final V[] dupKeyValues ) throws Exception { - long newRevision = btree.getRevision() + 1; - int numKeysInNode = btree.getPageSize(); - RecordManager rm = btree.getRecordManager(); - List> lstLeaves = new ArrayList>(); - int totalTupleCount = 0; - int nbKeyPage = Math.min( dupKeyValues.length, numKeysInNode ); - - Page newLeaf = BTreeFactory.createLeaf( btree, newRevision, nbKeyPage ); - lstLeaves.add( newLeaf ); - - int leafIndex = 0; - - // Iterate on all the values - for ( V v : dupKeyValues ) + Iterator> valueIterator = new Iterator>() { - // Inject the key in the leaf - setKey( btree, newLeaf, leafIndex, v ); + int pos = 0; - leafIndex++; - totalTupleCount++; - if ( ( totalTupleCount % numKeysInNode ) == 0 ) + @Override + public Tuple next() { - // The page has been completed, create a new one or - // if it was the last value, we are done - if ( totalTupleCount == dupKeyValues.length ) - { - // We are done with the values, exit - break; - } - else - { - // Create a new leaf - leafIndex = 0; - nbKeyPage = Math.min( dupKeyValues.length - totalTupleCount, numKeysInNode ); + // We can now return the found value + V value = dupKeyValues[pos]; + pos++; - newLeaf = createLeaf( btree, newRevision, nbKeyPage ); - lstLeaves.add( newLeaf ); - } + return new Tuple( value, value ); } - //TODO build the whole tree in chunks rather than processing *all* leaves at first - } - - if ( lstLeaves.isEmpty() ) - { - return btree; - } - - // make sure either one of the root pages is reclaimed, cause when we call rm.manage() - // there is already a root page created - Page rootPage = attachNodes( lstLeaves, btree, numKeysInNode, rm ); - rm.writePage( btree, rootPage, rootPage.getRevision() ); - - Page oldRoot = btree.getRootPage(); - - long newRootPageOffset = ( ( AbstractPage ) rootPage ).getOffset(); - LOG.debug( "replacing old offset {} of the BTree {} with {}", - btree.getRootPageOffset(), btree.getName(), newRootPageOffset ); - BTreeHeader header = btree.getBtreeHeader(); - - header.setRootPage( rootPage ); - header.setRevision( newRevision ); - header.setNbElems( totalTupleCount ); - - long newBtreeHeaderOffset = rm.writeBtreeHeader( btree, header ); - - header.setBTreeHeaderOffset( newBtreeHeaderOffset ); - rm.writeBtreeHeader( btree, header ); - - rm.freePages( ( BTree ) btree, btree.getRevision(), ( List ) Arrays.asList( oldRoot ) ); - - return btree; - } - - - /** - * Attaches the Nodes together - * - * @param children the leaves - * @param btree the sub-BTree - * @param numKeysInNode number of keys per each node - * @param rm the RecordManager - * @return the new root page of the sub-BTree after attaching all the nodes - * @throws IOException - */ - private Page attachNodes( List> children, BTree btree, int numKeysInNode, RecordManager rm ) - throws IOException - { - if ( children.size() == 1 ) - { - return children.get( 0 ); - } - - List> lstNodes = new ArrayList>(); - - int numChildren = numKeysInNode + 1; - - PersistedNode node = ( PersistedNode ) createNode( btree, btree.getRevision(), numKeysInNode ); - lstNodes.add( node ); - int i = 0; - int totalNodes = 0; - - for ( Page p : children ) - { - if ( i != 0 ) + @Override + public boolean hasNext() { - setKey( btree, node, i - 1, p.getLeftMostKey() ); + // Check that we have at least one element to read + return pos < dupKeyValues.length; } - node.children[i] = new PersistedPageHolder( btree, p ); - i++; - totalNodes++; - - if ( ( totalNodes % numChildren ) == 0 ) + @Override + public void remove() { - i = 0; - - PageHolder pageHolder = ( PageHolder ) rm.writePage( btree, node, 1 ); - - node = ( PersistedNode ) createNode( btree, btree.getRevision(), numKeysInNode ); - lstNodes.add( node ); } - } - // 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++ ) - { - if ( lastNode.keys[j] == null ) - { - int n = j; - lastNode.nbElems = n; - KeyHolder[] keys = lastNode.keys; + BulkLoader.load( btree, valueIterator, dupKeyValues.length ); - lastNode.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ); - System.arraycopy( keys, 0, lastNode.keys, 0, n ); - - break; - } - } - - if ( lastNode.keys.length == 0 ) - { - lstNodes.remove( lastNode ); - } - - return attachNodes( lstNodes, btree, numKeysInNode, rm ); + return btree; } Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java (original) +++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java Tue Feb 24 13:43:59 2015 @@ -23,6 +23,7 @@ package org.apache.directory.mavibot.btr import java.io.File; import java.io.IOException; import java.io.RandomAccessFile; +import java.nio.BufferUnderflowException; import java.nio.ByteBuffer; import java.nio.channels.FileChannel; import java.util.ArrayList; @@ -376,7 +377,7 @@ public class RecordManager extends Abstr // Create a new Header nbBtree = 0; firstFreePage = NO_PAGE; - currentBtreeOfBtreesOffset = 0L; + currentBtreeOfBtreesOffset = NO_PAGE; updateRecordManagerHeader(); @@ -389,7 +390,7 @@ public class RecordManager extends Abstr // Inject these B-trees into the RecordManager. They are internal B-trees. try { - manage( btreeOfBtrees, INTERNAL_BTREE ); + manageSubBtree( btreeOfBtrees ); currentBtreeOfBtreesOffset = ( ( PersistedBTree ) btreeOfBtrees ).getBtreeHeader() .getBTreeHeaderOffset(); @@ -1407,18 +1408,81 @@ public class RecordManager extends Abstr * Manage a B-tree. The btree will be added and managed by this RecordManager. We will create a * new RootPage for this added B-tree, which will contain no data.
* This method is threadsafe. + * Managing a btree is a matter of storing an reference to the managed B-tree in the B-tree Of B-trees. + * We store a tuple of NameRevision (where revision is 0L) and a offset to the B-tree header. + * At the same time, we keep a track of the managed B-trees in a Map. * * @param btree The new B-tree to manage. - * @throws BTreeAlreadyManagedException if the B-tree is already managed + * @param treeType flag indicating if this is an internal tree + * + * @throws BTreeAlreadyManagedException If the B-tree is already managed * @throws IOException if there was a problem while accessing the file */ public synchronized void manage( BTree btree ) throws BTreeAlreadyManagedException, IOException { beginTransaction(); - manage( ( BTree ) btree, NORMAL_BTREE ); + try + { + LOG.debug( "Managing the btree {}", btree.getName() ); + BTreeFactory.setRecordManager( btree, this ); + + String name = btree.getName(); + + if ( managedBtrees.containsKey( name ) ) + { + // There is already a B-tree with this name in the recordManager... + LOG.error( "There is already a B-tree named '{}' managed by this recordManager", name ); + rollback(); + throw new BTreeAlreadyManagedException( name ); + } + + // Now, write the B-tree informations + long btreeInfoOffset = writeBtreeInfo( btree ); + BTreeHeader btreeHeader = ( ( AbstractBTree ) btree ).getBtreeHeader(); + ( ( PersistedBTree ) btree ).setBtreeInfoOffset( btreeInfoOffset ); + + // Serialize the B-tree root page + Page rootPage = btreeHeader.getRootPage(); + + PageIO[] rootPageIos = serializePage( btree, btreeHeader.getRevision(), rootPage ); + + // Get the reference on the first page + long rootPageOffset = rootPageIos[0].getOffset(); + + // Store the rootPageOffset into the Btree header and into the rootPage + btreeHeader.setRootPageOffset( rootPageOffset ); + ( ( PersistedLeaf ) rootPage ).setOffset( rootPageOffset ); + + LOG.debug( "Flushing the newly managed '{}' btree rootpage", btree.getName() ); + flushPages( rootPageIos ); + + // And the B-tree header + long btreeHeaderOffset = writeBtreeHeader( btree, btreeHeader ); - commit(); + // Now, if this is a new B-tree, add it to the B-tree of B-trees + // Add the btree into the map of managed B-trees + managedBtrees.put( name, ( BTree ) btree ); + + // And in the Map of currentBtreeHeaders and newBtreeHeaders + currentBTreeHeaders.put( name, btreeHeader ); + newBTreeHeaders.put( name, btreeHeader ); + + // We can safely increment the number of managed B-trees + nbBtree++; + + // Create the new NameRevision + NameRevision nameRevision = new NameRevision( name, 0L ); + + // Inject it into the B-tree of B-tree + btreeOfBtrees.insert( nameRevision, btreeHeaderOffset ); + commit(); + } + catch ( IOException ioe ) + { + rollback(); + throw ioe; + } } @@ -1433,22 +1497,22 @@ public class RecordManager extends Abstr * @throws BTreeAlreadyManagedException If the B-tree is already managed * @throws IOException */ - public synchronized void manage( BTree btree, boolean treeType ) + public synchronized void manageSubBtree( BTree btree ) throws BTreeAlreadyManagedException, IOException { - LOG.debug( "Managing the btree {} which is an internam tree : {}", btree.getName(), treeType ); + LOG.debug( "Managing the sub-btree {}", btree.getName() ); BTreeFactory.setRecordManager( btree, this ); String name = btree.getName(); if ( managedBtrees.containsKey( name ) ) { - // There is already a B-tree with this name in the recordManager... - LOG.error( "There is already a B-tree named '{}' managed by this recordManager", name ); + // There is already a subB-tree with this name in the recordManager... + LOG.error( "There is already a sub-B-tree named '{}' managed by this recordManager", name ); throw new BTreeAlreadyManagedException( name ); } - // Now, write the B-tree informations + // Now, write the subB-tree informations long btreeInfoOffset = writeBtreeInfo( btree ); BTreeHeader btreeHeader = ( ( AbstractBTree ) btree ).getBtreeHeader(); ( ( PersistedBTree ) btree ).setBtreeInfoOffset( btreeInfoOffset ); @@ -1463,7 +1527,8 @@ public class RecordManager extends Abstr // Store the rootPageOffset into the Btree header and into the rootPage btreeHeader.setRootPageOffset( rootPageOffset ); - ( ( PersistedLeaf ) rootPage ).setOffset( rootPageOffset ); + + ( ( AbstractPage ) rootPage ).setOffset( rootPageOffset ); LOG.debug( "Flushing the newly managed '{}' btree rootpage", btree.getName() ); flushPages( rootPageIos ); @@ -1472,24 +1537,29 @@ public class RecordManager extends Abstr long btreeHeaderOffset = writeBtreeHeader( btree, btreeHeader ); // Now, if this is a new B-tree, add it to the B-tree of B-trees - if ( treeType != INTERNAL_BTREE ) + // Add the btree into the map of managed B-trees + if ( ( btree.getType() != BTreeTypeEnum.BTREE_OF_BTREES ) && ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB ) ) { - // Add the btree into the map of managed B-trees managedBtrees.put( name, ( BTree ) btree ); + } - // And in the Map of currentBtreeHeaders and newBtreeHeaders - currentBTreeHeaders.put( name, btreeHeader ); - newBTreeHeaders.put( name, btreeHeader ); + // And in the Map of currentBtreeHeaders and newBtreeHeaders + currentBTreeHeaders.put( name, btreeHeader ); + newBTreeHeaders.put( name, btreeHeader ); + + // Create the new NameRevision + NameRevision nameRevision = new NameRevision( name, 0L ); + // Inject it into the B-tree of B-tree + if ( ( btree.getType() != BTreeTypeEnum.BTREE_OF_BTREES ) && ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB ) ) + { // We can safely increment the number of managed B-trees nbBtree++; - // Create the new NameRevision - NameRevision nameRevision = new NameRevision( name, 0L ); - - // Inject it into the B-tree of B-tree btreeOfBtrees.insert( nameRevision, btreeHeaderOffset ); } + + updateRecordManagerHeader(); } @@ -1692,6 +1762,15 @@ public class RecordManager extends Abstr int dataSize = 0; int nbValues = valueHolder.size(); + if ( nbValues == 0 ) + { + // No value. + byte[] buffer = IntSerializer.serialize( nbValues ); + serializedData.add( buffer ); + + return buffer.length; + } + if ( !valueHolder.isSubBtree() ) { // Write the nb elements first @@ -1716,47 +1795,15 @@ public class RecordManager extends Abstr } else { - if ( nbValues == 0 ) - { - // No value. - byte[] buffer = IntSerializer.serialize( nbValues ); - serializedData.add( buffer ); - - return buffer.length; - } - - if ( valueHolder.isSubBtree() ) - { - // Store the nbVlues as a negative number. We add 1 so that 0 is not confused with an Array value - byte[] buffer = IntSerializer.serialize( -( nbValues + 1 ) ); - serializedData.add( buffer ); - dataSize += buffer.length; - - // the B-tree offset - buffer = LongSerializer.serialize( ( ( PersistedValueHolder ) valueHolder ).getOffset() ); - serializedData.add( buffer ); - dataSize += buffer.length; - } - else - { - // This is an array, store the nb of values as a positive number - byte[] buffer = IntSerializer.serialize( nbValues ); - serializedData.add( buffer ); - dataSize += buffer.length; - - // Now store each value - byte[] data = ( ( PersistedValueHolder ) valueHolder ).getRaw(); - buffer = IntSerializer.serialize( data.length ); - serializedData.add( buffer ); - dataSize += buffer.length; - - if ( data.length > 0 ) - { - serializedData.add( data ); - } + // Store the nbVlues as a negative number. We add 1 so that 0 is not confused with an Array value + byte[] buffer = IntSerializer.serialize( -( nbValues + 1 ) ); + serializedData.add( buffer ); + dataSize += buffer.length; - dataSize += data.length; - } + // the B-tree offset + buffer = LongSerializer.serialize( ( ( PersistedValueHolder ) valueHolder ).getOffset() ); + serializedData.add( buffer ); + dataSize += buffer.length; } return dataSize; @@ -2926,8 +2973,6 @@ public class RecordManager extends Abstr */ private PageIO fetchNewPage() throws IOException { - //dumpFreePages( firstFreePage ); - if ( firstFreePage == NO_PAGE ) { nbCreatedPages.incrementAndGet(); Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BulkLoaderTest.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BulkLoaderTest.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BulkLoaderTest.java (original) +++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BulkLoaderTest.java Tue Feb 24 13:43:59 2015 @@ -150,7 +150,7 @@ public class BulkLoaderTest public void testPersistedBulkLoad1000Elements() throws IOException, KeyNotFoundException, BTreeAlreadyManagedException { - for ( int i = 0; i < 1001; i++ ) + for ( int i = 1000000; i < 1000001; i++ ) { Random random = new Random( System.currentTimeMillis() ); File file = File.createTempFile( "managedbtreebuilder", ".data" ); @@ -161,6 +161,7 @@ public class BulkLoaderTest RecordManager rm = new RecordManager( file.getAbsolutePath() ); PersistedBTree btree = ( PersistedBTree ) rm.addBTree( "test", LongSerializer.INSTANCE, StringSerializer.INSTANCE, false ); + btree.setPageSize( 64 ); int nbElems = i; int addedElems = 0; @@ -193,12 +194,8 @@ public class BulkLoaderTest expectedTuple.value.add( value ); expected.put( key, expectedTuple ); addedElems++; - - if ( addedElems % 100 == 0 ) - { - //System.out.println( "Nb added elements = " + addedElems ); - } } + long t01 = System.currentTimeMillis(); // System.out.println( "Time to create the " + nbElems + " elements " + ( ( t01 - t00 ) / 1 ) ); @@ -229,10 +226,10 @@ public class BulkLoaderTest }; long t0 = System.currentTimeMillis(); - BTree result = BulkLoader.load( btree, tupleIterator, 128 ); + BTree result = BulkLoader.load( btree, tupleIterator, 1024000 ); long t1 = System.currentTimeMillis(); - if ( i % 100 == 0 ) + if ( ( i % 100 ) == 0 ) { System.out.println( "== Btree #" + i + ", Time to bulkoad the " + nbElems + " elements " + ( t1 - t0 ) + "ms" ); @@ -451,10 +448,6 @@ public class BulkLoaderTest for ( int i = 0; i < 49; i++ ) { - System.out.println( "=======================================" ); - System.out.println( "== Iteration n#" + i ); - System.out.println( "=======================================" ); - LevelInfo leafInfo = BulkLoader.computeLevel( btree, i, LevelEnum.LEAF ); assertEquals( expectedNbPages[i], leafInfo.getNbPages() ); @@ -510,10 +503,6 @@ public class BulkLoaderTest for ( int i = 2; i < 52; i++ ) { - System.out.println( "=======================================" ); - System.out.println( "== Iteration n#" + i ); - System.out.println( "=======================================" ); - LevelInfo nodeInfo = BulkLoader.computeLevel( btree, i, LevelEnum.NODE ); assertEquals( expectedNbPages[i], nodeInfo.getNbPages() ); @@ -569,10 +558,6 @@ public class BulkLoaderTest for ( int i = 2599; i <= 2599; i++ ) { - System.out.println( "=======================================" ); - System.out.println( "== Iteration #" + i ); - System.out.println( "=======================================" ); - List> levels = BulkLoader.computeLevels( btree, i ); for ( LevelInfo level : levels ) @@ -592,7 +577,7 @@ public class BulkLoaderTest * Test that we can load 100 BTrees with 0 to 1000 elements, each one of them having multiple values * @throws BTreeAlreadyManagedException */ - @Ignore("The test is failing atm due to the sub-btree construction which is not working correctly when we have too many elements") + //@Ignore("The test is failing atm due to the sub-btree construction which is not working correctly when we have too many elements") @Test public void testPersistedBulkLoad1000ElementsMultipleValues() throws IOException, KeyNotFoundException, BTreeAlreadyManagedException @@ -672,24 +657,11 @@ public class BulkLoaderTest }; long t0 = System.currentTimeMillis(); - BTree result = null; - - try - { - result = BulkLoader.load( btree, tupleIterator, 128 ); - } - catch ( NullPointerException npe ) - { - System.out.println( "Error with : " ); - for ( int j = 0; j < i; j++ ) - { - System.out.println( elems[j] ); - } - } + BTree result = BulkLoader.load( btree, tupleIterator, 128 ); long t1 = System.currentTimeMillis(); - System.out.println( "== Btree #" + i + ", Time to bulkoad the " + nbElems + " elements " - + ( t1 - t0 ) + "ms" ); + //System.out.println( "== Btree #" + i + ", Time to bulkoad the " + nbElems + " elements " + // + ( t1 - t0 ) + "ms" ); TupleCursor cursor = result.browse(); int nbFetched = 0; @@ -793,19 +765,8 @@ public class BulkLoaderTest long t0 = System.currentTimeMillis(); BTree result = null; - try - { - result = BulkLoader.load( btree, tupleIterator, 128 ); - } - catch ( NullPointerException npe ) - { - npe.printStackTrace(); - System.out.println( "Error with : " ); - for ( int j = 0; j < 4; j++ ) - { - System.out.println( elems[j] ); - } - } + + result = BulkLoader.load( btree, tupleIterator, 128 ); long t1 = System.currentTimeMillis(); System.out.println( "== Btree #" + 4 + ", Time to bulkoad the " + nbElems + " elements " @@ -819,10 +780,6 @@ public class BulkLoaderTest while ( cursor.hasNext() ) { Tuple elem = cursor.next(); - - assertTrue( expected.containsKey( elem.key ) ); - Tuple> tuple = expected.get( elem.key ); - assertNotNull( tuple ); nbFetched++; } @@ -856,7 +813,7 @@ public class BulkLoaderTest listTuples.add( new Tuple( 32L, "V8" ) ); listTuples.add( new Tuple( -21L, "V9" ) ); listTuples.add( new Tuple( 9L, "V10" ) ); - //listTuples.add( new Tuple( 0L, "V11" ) ); + listTuples.add( new Tuple( 0L, "V11" ) ); listTuples.add( new Tuple( -7L, "V12" ) ); listTuples.add( new Tuple( -13L, "V13" ) ); listTuples.add( new Tuple( 23L, "V14" ) ); @@ -1222,6 +1179,7 @@ public class BulkLoaderTest prev = elem; elem = cursor.next(); nbFetched++; + System.out.println( elem ); } } catch ( Exception e ) @@ -1234,7 +1192,7 @@ public class BulkLoaderTest } catch ( Exception e ) { - + e.printStackTrace(); } } } Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java (original) +++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java Tue Feb 24 13:43:59 2015 @@ -1193,7 +1193,8 @@ public class InMemoryBTreeTest * @param element The removed element * @param expected The expected set of elements */ - private void checkRemoval( BTree btree, int element, Set expected ) throws IOException, KeyNotFoundException + private void checkRemoval( BTree btree, int element, Set expected ) throws IOException, + KeyNotFoundException { Tuple removed = btree.delete( element ); assertEquals( element, removed.getKey().intValue() ); @@ -1983,7 +1984,7 @@ public class InMemoryBTreeTest btree.close(); } - + /** * Test the overwriting of elements */ @@ -1999,7 +2000,7 @@ public class InMemoryBTreeTest assertTrue( btree.hasKey( 1 ) ); assertEquals( Integer.valueOf( 1 ), btree.get( 1 ) ); - + btree.insert( 1, 10 ); assertTrue( btree.hasKey( 1 ) ); Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java?rev=1661949&r1=1661948&r2=1661949&view=diff ============================================================================== --- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java (original) +++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java Tue Feb 24 13:43:59 2015 @@ -19,6 +19,7 @@ */ package org.apache.directory.mavibot.btree; + import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; @@ -35,6 +36,7 @@ import org.junit.Rule; import org.junit.Test; import org.junit.rules.TemporaryFolder; + /** * Tests for KeyCursor of a persisted sub-Btree. * @@ -71,7 +73,7 @@ public class PersistedSubBtreeKeyCursorT btree = BTreeFactory.createPersistedBTree( configuration ); - recordManager.manage( btree, RecordManager.INTERNAL_BTREE ); + recordManager.manage( btree ); } catch ( Exception e ) { @@ -91,33 +93,34 @@ public class PersistedSubBtreeKeyCursorT { FileUtils.deleteDirectory( dataDir ); } - + recordManager.close(); assertTrue( recordManager.isContextOk() ); } + @Test public void testBrowseKeys() throws Exception { - for( int i=0; i< 10; i++ ) + for ( int i = 0; i < 10; i++ ) { // only the keys are stored, values are ignored btree.insert( i, i ); } - + KeyCursor cursor = btree.browseKeys(); - - for( int i=0; i< 10; i++ ) + + for ( int i = 0; i < 10; i++ ) { assertTrue( cursor.hasNext() ); assertEquals( String.valueOf( i ), String.valueOf( cursor.next() ) ); } - + assertFalse( cursor.hasNext() ); cursor.afterLast(); - - for( int i=9; i>= 0; i-- ) + + for ( int i = 9; i >= 0; i-- ) { assertTrue( cursor.hasPrev() ); assertEquals( String.valueOf( i ), String.valueOf( cursor.prev() ) );