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 9544B10C4B for ; Sun, 7 Dec 2014 03:28:59 +0000 (UTC) Received: (qmail 51780 invoked by uid 500); 7 Dec 2014 03:28:59 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 51736 invoked by uid 500); 7 Dec 2014 03:28:59 -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 51726 invoked by uid 99); 7 Dec 2014 03:28:59 -0000 Received: from hades.apache.org (HELO hades.apache.org) (140.211.11.105) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 07 Dec 2014 03:28:59 +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 7AC9AAC0957; Sun, 7 Dec 2014 03:28:55 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1643645 [1/2] - in /directory/mavibot/branches/free-page-mgmt: ./ distribution/ mavibot/ mavibot/src/main/java/org/apache/directory/mavibot/btree/ mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/ mavibot/src/test/java/o... Date: Sun, 07 Dec 2014 03:28:54 -0000 To: commits@directory.apache.org From: kayyagari@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20141207032856.7AC9AAC0957@hades.apache.org> Author: kayyagari Date: Sun Dec 7 03:28:54 2014 New Revision: 1643645 URL: http://svn.apache.org/r1643645 Log: merged with trunk revision 1642979 (stashing a lot of untested code as well) Modified: directory/mavibot/branches/free-page-mgmt/distribution/pom.xml directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBuilderTest.java directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeDuplicateKeyTest.java directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerTest.java directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerWithDuplicatesTest.java directory/mavibot/branches/free-page-mgmt/pom.xml Modified: directory/mavibot/branches/free-page-mgmt/distribution/pom.xml URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/distribution/pom.xml?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/distribution/pom.xml (original) +++ directory/mavibot/branches/free-page-mgmt/distribution/pom.xml Sun Dec 7 03:28:54 2014 @@ -24,7 +24,7 @@ org.apache.directory.mavibot mavibot-parent - 1.0.0-M6-SNAPSHOT + 1.0.0-M7-SNAPSHOT distribution Modified: directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml Sun Dec 7 03:28:54 2014 @@ -23,12 +23,12 @@ org.apache.directory.mavibot mavibot-parent - 1.0.0-M6-SNAPSHOT + 1.0.0-M7-SNAPSHOT mavibot ApacheDS MVCC BTree implementation - jar + bundle A MVCC BTree Implementation @@ -65,12 +65,44 @@ slf4j-log4j12 ${slf4j.log4j12.version} + + + + + + org.apache.maven.plugins + maven-jar-plugin + + + META-INF/MANIFEST.MF + false + + + + + + org.apache.felix + maven-bundle-plugin + true + true + + META-INF + + ${project.groupId}.mavibot + + org.apache.directory.mavibot.btree;version=${project.version};-noimport:=true, + org.apache.directory.mavibot.btree.comparator;version=${project.version};-noimport:=true, + org.apache.directory.mavibot.btree.exception;version=${project.version};-noimport:=true, + org.apache.directory.mavibot.btree.memory;version=${project.version};-noimport:=true, + org.apache.directory.mavibot.btree.persisted;version=${project.version};-noimport:=true, + org.apache.directory.mavibot.btree.serializer;version=${project.version};-noimport:=true, + org.apache.directory.mavibot.btree.util;version=${project.version};-noimport:=true + + + + - - log4j - log4j - ${log4j.version} - - + + Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java Sun Dec 7 03:28:54 2014 @@ -93,10 +93,11 @@ import org.apache.directory.mavibot.btre /** The current revision */ protected AtomicLong currentRevision = new AtomicLong( 0L ); - + /** The TransactionManager used for this BTree */ protected TransactionManager transactionManager; + /** * Starts a Read Only transaction. If the transaction is not closed, it will be * automatically closed after the timeout @@ -125,7 +126,7 @@ import org.apache.directory.mavibot.btre { throw new BTreeCreationException( "We don't have a transactionLManager" ); } - + ReadTransaction transaction = beginReadTransaction(); if ( transaction == null ) @@ -134,7 +135,7 @@ import org.apache.directory.mavibot.btre } else { - ParentPos[] stack = (ParentPos[]) Array.newInstance( ParentPos.class, 32 ); + ParentPos[] stack = ( ParentPos[] ) Array.newInstance( ParentPos.class, 32 ); TupleCursor cursor = getRootPage().browse( transaction, stack, 0 ); @@ -165,7 +166,7 @@ import org.apache.directory.mavibot.btre } else { - ParentPos[] stack = (ParentPos[]) Array.newInstance( ParentPos.class, 32 ); + ParentPos[] stack = ( ParentPos[] ) Array.newInstance( ParentPos.class, 32 ); // And get the cursor TupleCursor cursor = getRootPage( transaction.getRevision() ).browse( transaction, stack, 0 ); @@ -188,13 +189,13 @@ import org.apache.directory.mavibot.btre ReadTransaction transaction = beginReadTransaction(); - ParentPos[] stack = (ParentPos[]) Array.newInstance( ParentPos.class, 32 ); + ParentPos[] stack = ( ParentPos[] ) Array.newInstance( ParentPos.class, 32 ); TupleCursor cursor; try { cursor = getRootPage( transaction.getRevision() ).browse( key, transaction, stack, 0 ); - + return cursor; } catch ( KeyNotFoundException e ) @@ -223,7 +224,7 @@ import org.apache.directory.mavibot.btre } else { - ParentPos[] stack = (ParentPos[]) Array.newInstance( ParentPos.class, 32 ); + ParentPos[] stack = ( ParentPos[] ) Array.newInstance( ParentPos.class, 32 ); // And get the cursor TupleCursor cursor = getRootPage( transaction.getRevision() ).browse( key, transaction, stack, 0 ); @@ -316,22 +317,33 @@ import org.apache.directory.mavibot.btre throw new IllegalArgumentException( "Key must not be null" ); } - // Take the lock if it's not already taken by another thread - transactionManager.beginTransaction(); + boolean txnAllowed = ( ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) && ( btreeType != BTreeTypeEnum.BTREE_OF_BTREES ) ); + + if ( txnAllowed ) + { + // Take the lock if it's not already taken by another thread + transactionManager.beginTransaction(); + } try { Tuple deleted = delete( key, currentRevision.get() + 1 ); - // Commit now - transactionManager.commit(); + if ( txnAllowed ) + { + // Commit now + transactionManager.commit(); + } return deleted; } catch ( IOException ioe ) { - // We have had an exception, we must rollback the transaction - transactionManager.rollback(); + if ( txnAllowed ) + { + // We have had an exception, we must rollback the transaction + transactionManager.rollback(); + } return null; } @@ -359,19 +371,30 @@ import org.apache.directory.mavibot.btre throw new IllegalArgumentException( "Value must not be null" ); } - transactionManager.beginTransaction(); - + boolean txnAllowed = ( ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) && ( btreeType != BTreeTypeEnum.BTREE_OF_BTREES ) ); + + if ( txnAllowed ) + { + transactionManager.beginTransaction(); + } + try { Tuple deleted = delete( key, value, currentRevision.get() + 1 ); - - transactionManager.commit(); + + if ( txnAllowed ) + { + transactionManager.commit(); + } return deleted; } catch ( IOException ioe ) { - transactionManager.rollback(); + if ( txnAllowed ) + { + transactionManager.rollback(); + } throw ioe; } @@ -412,9 +435,11 @@ import org.apache.directory.mavibot.btre throw new IllegalArgumentException( "Key must not be null" ); } + boolean txnAllowed = ( ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) && ( btreeType != BTreeTypeEnum.BTREE_OF_BTREES ) ); + // Take the lock if it's not already taken by another thread and if we // aren't on a sub-btree - if ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) + if ( txnAllowed ) { transactionManager.beginTransaction(); } @@ -433,7 +458,7 @@ import org.apache.directory.mavibot.btre } // Commit now if it's not a sub-btree - if ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) + if ( txnAllowed ) { //FIXME when result type is ExistsResult then we should avoid writing the headers transactionManager.commit(); @@ -445,7 +470,7 @@ import org.apache.directory.mavibot.btre { // We have had an exception, we must rollback the transaction // if it's not a sub-btree - if ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) + if ( txnAllowed ) { transactionManager.rollback(); } @@ -456,7 +481,7 @@ import org.apache.directory.mavibot.btre { // We have had an exception, we must rollback the transaction // if it's not a sub-btree - if ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) + if ( txnAllowed ) { transactionManager.rollback(); } @@ -771,7 +796,7 @@ import org.apache.directory.mavibot.btre currentRevision.set( revision ); currentBtreeHeader = btreeHeader; - + // And update the newBTreeHeaders map if ( btreeHeader.getBtree().getType() != BTreeTypeEnum.PERSISTED_SUB ) { @@ -794,7 +819,7 @@ import org.apache.directory.mavibot.btre currentRevision.set( revision ); currentBtreeHeader = btreeHeader; - + // And update the newBTreeHeaders map if ( btreeHeader.getBtree().getType() != BTreeTypeEnum.PERSISTED_SUB ) { @@ -907,7 +932,7 @@ import org.apache.directory.mavibot.btre /** * {@inheritDoc} */ - public Comparator getComparator() + public Comparator getKeyComparator() { return keySerializer.getComparator(); } @@ -916,6 +941,15 @@ import org.apache.directory.mavibot.btre /** * {@inheritDoc} */ + public Comparator getValueComparator() + { + return valueSerializer.getComparator(); + } + + + /** + * {@inheritDoc} + */ public int getWriteBufferSize() { return writeBufferSize; @@ -1012,7 +1046,7 @@ import org.apache.directory.mavibot.btre { throw new BTreeCreationException( "We don't have a Transaction Manager" ); } - + ReadTransaction transaction = beginReadTransaction(); if ( transaction == null ) @@ -1021,7 +1055,7 @@ import org.apache.directory.mavibot.btre } else { - ParentPos[] stack = (ParentPos[]) Array.newInstance( ParentPos.class, 32 ); + ParentPos[] stack = ( ParentPos[] ) Array.newInstance( ParentPos.class, 32 ); KeyCursor cursor = getRootPage().browseKeys( transaction, stack, 0 ); @@ -1032,7 +1066,7 @@ import org.apache.directory.mavibot.btre } } - + /** * Create a thread that is responsible of cleaning the transactions when * they hit the timeout Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java Sun Dec 7 03:28:54 2014 @@ -59,6 +59,7 @@ import org.apache.directory.mavibot.btre /** The last {@link PageIO} storing the serialized Page on disk */ protected long lastOffset = -1L; + /** * Creates a default empty AbstractPage * @@ -155,7 +156,14 @@ import org.apache.directory.mavibot.btre { if ( pos < nbElems + 1 ) { - return children[pos].getValue(); + if ( children[pos] != null ) + { + return children[pos].getValue(); + } + else + { + return null; + } } else { @@ -227,7 +235,8 @@ import org.apache.directory.mavibot.btre * @return The result * @throws IOException If we had an issue while processing the deletion */ - /* no qualifier */abstract DeleteResult delete( K key, V value, long revision, Page parent, int parentPos ) + /* no qualifier */abstract DeleteResult delete( K key, V value, long revision, Page parent, + int parentPos ) throws IOException; @@ -258,7 +267,14 @@ import org.apache.directory.mavibot.btre { if ( ( pos >= 0 ) && ( pos < children.length ) ) { - return children[pos].getValue(); + if ( children[pos] != null ) + { + return children[pos].getValue(); + } + else + { + return null; + } } else { @@ -268,7 +284,10 @@ import org.apache.directory.mavibot.btre /** - * {@inheritDoc} + * Inject a pageHolder into the node, at a given position + * + * @param pos The position of the added pageHolder + * @param pageHolder The pageHolder to add */ /* no qualifier */void setPageHolder( int pos, PageHolder pageHolder ) { @@ -327,7 +346,7 @@ import org.apache.directory.mavibot.btre return page.browseKeys( transaction, stack, depth ); } - + /** * Selects the sibling (the previous or next page with the same parent) which has * the more element assuming it's above N/2 @@ -507,7 +526,7 @@ import org.apache.directory.mavibot.btre return -1; } - return btree.getComparator().compare( key1, key2 ); + return btree.getKeyComparator().compare( key1, key2 ); } Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java Sun Dec 7 03:28:54 2014 @@ -73,7 +73,7 @@ public interface BTree /** - * @return the pageSize + * @return the number of elements per page */ int getPageSize(); @@ -264,11 +264,17 @@ public interface BTree */ KeyCursor browseKeys() throws IOException, KeyNotFoundException; - + + /** + * @return the key comparator + */ + Comparator getKeyComparator(); + + /** - * @return the comparator + * @return the value comparator */ - Comparator getComparator(); + Comparator getValueComparator(); /** Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java Sun Dec 7 03:28:54 2014 @@ -62,7 +62,7 @@ public class BTreeFactory public static BTree createPersistedBTree( BTreeTypeEnum type ) { BTree btree = new PersistedBTree(); - ((AbstractBTree)btree).setType( type ); + ( ( AbstractBTree ) btree ).setType( type ); return btree; } @@ -79,6 +79,7 @@ public class BTreeFactory btree.setBtreeHeaderOffset( btreeHeaderOffset ); } + /** * Creates a new persisted B-tree using the BTreeConfiguration to initialize the * B-tree @@ -514,6 +515,7 @@ public class BTreeFactory { if ( btree.getType() != BTreeTypeEnum.IN_MEMORY ) { + //System.out.println( "Creating a node with nbElems : " + nbElems ); return new PersistedNode( btree, revision, nbElems ); } else @@ -609,7 +611,8 @@ public class BTreeFactory * @throws IllegalArgumentException */ /* no qualifier*/static void setKeySerializer( BTree btree, String keySerializerFqcn ) - throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, SecurityException, NoSuchFieldException + throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, + SecurityException, NoSuchFieldException { Class keySerializer = Class.forName( keySerializerFqcn ); @SuppressWarnings("unchecked") @@ -618,7 +621,7 @@ public class BTreeFactory { instance = ( ElementSerializer ) keySerializer.getDeclaredField( "INSTANCE" ).get( null ); } - catch( NoSuchFieldException e ) + catch ( NoSuchFieldException e ) { // ignore } @@ -645,7 +648,8 @@ public class BTreeFactory * @throws IllegalArgumentException */ /* no qualifier*/static void setValueSerializer( BTree btree, String valueSerializerFqcn ) - throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, SecurityException, NoSuchFieldException + throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, + SecurityException, NoSuchFieldException { Class valueSerializer = Class.forName( valueSerializerFqcn ); @SuppressWarnings("unchecked") @@ -654,16 +658,16 @@ public class BTreeFactory { instance = ( ElementSerializer ) valueSerializer.getDeclaredField( "INSTANCE" ).get( null ); } - catch( NoSuchFieldException e ) + catch ( NoSuchFieldException e ) { // ignore } - + if ( instance == null ) { instance = ( ElementSerializer ) valueSerializer.newInstance(); } - + btree.setValueSerializer( instance ); } Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java Sun Dec 7 03:28:54 2014 @@ -77,6 +77,7 @@ import org.slf4j.LoggerFactory; /** The Journal channel */ private FileChannel journalChannel = null; + /** * Creates a new BTree, with no initialization. */ @@ -137,7 +138,7 @@ import org.slf4j.LoggerFactory; newBtreeHeader.setRootPage( new InMemoryLeaf( this ) ); newBtreeHeader.setRootPageOffset( 0L ); - btreeRevisions.put( 0L, newBtreeHeader ); + btreeRevisions.put( 0L, newBtreeHeader ); currentBtreeHeader = newBtreeHeader; // Now, initialize the BTree @@ -180,7 +181,7 @@ import org.slf4j.LoggerFactory; // Create the queue containing the pending read transactions readTransactions = new ConcurrentLinkedQueue>(); - + // Create the transaction manager transactionManager = new InMemoryTransactionManager(); @@ -236,8 +237,8 @@ import org.slf4j.LoggerFactory; return readTransaction; } - - + + /** * {@inheritDoc} */ @@ -247,7 +248,7 @@ import org.slf4j.LoggerFactory; if ( btreeHeader != null ) { - ReadTransaction readTransaction = new ReadTransaction( btreeHeader, readTransactions ); + ReadTransaction readTransaction = new ReadTransaction( btreeHeader, readTransactions ); readTransactions.add( readTransaction ); @@ -520,40 +521,40 @@ import org.slf4j.LoggerFactory; try { TupleCursor cursor = browse(); - + if ( keySerializer == null ) { throw new MissingSerializerException( "Cannot flush the btree without a Key serializer" ); } - + if ( valueSerializer == null ) { throw new MissingSerializerException( "Cannot flush the btree without a Value serializer" ); } - + // Write the number of elements first bb.putLong( getBtreeHeader().getNbElems() ); - + while ( cursor.hasNext() ) { Tuple tuple = cursor.next(); - + byte[] keyBuffer = keySerializer.serialize( tuple.getKey() ); - + writeBuffer( ch, bb, keyBuffer ); - + byte[] valueBuffer = valueSerializer.serialize( tuple.getValue() ); - + writeBuffer( ch, bb, valueBuffer ); } - + // Write the buffer if needed if ( bb.position() > 0 ) { bb.flip(); ch.write( bb ); } - + // Flush to the disk for real ch.force( true ); ch.close(); @@ -741,6 +742,20 @@ import org.slf4j.LoggerFactory; /** + * Set the file path where the journal will be stored + * + * @param filePath The file path + */ + public void setFilePath( String filePath ) + { + if ( filePath != null ) + { + envDir = new File( filePath ); + } + } + + + /** * @return the journal */ public File getJournal() @@ -836,8 +851,8 @@ import org.slf4j.LoggerFactory; case BACKED_ON_DISK: sb.append( "Persistent " ); break; - - default : + + default: sb.append( "Wrong type... " ); break; } Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java Sun Dec 7 03:28:54 2014 @@ -37,94 +37,415 @@ import org.apache.directory.mavibot.btre */ public class InMemoryBTreeBuilder { - private String name; - - private int numKeysInNode; - - private ElementSerializer keySerializer; - - private ElementSerializer valueSerializer; + /** The Btree configuration */ + private InMemoryBTreeConfiguration btreeConfiguration; + /** + * Creates a new instance of InMemoryBTreeBuilder. + * + * @param name The BTree name + * @param numKeysInNode The number of keys per node + * @param keySerializer The key serializer + * @param valueSerializer The value serializer + */ public InMemoryBTreeBuilder( String name, int numKeysInNode, ElementSerializer keySerializer, ElementSerializer valueSerializer ) { - this.name = name; - this.numKeysInNode = numKeysInNode; - this.keySerializer = keySerializer; - this.valueSerializer = valueSerializer; + btreeConfiguration = new InMemoryBTreeConfiguration(); + btreeConfiguration.setName( name ); + btreeConfiguration.setPageSize( numKeysInNode ); + btreeConfiguration.setKeySerializer( keySerializer ); + btreeConfiguration.setValueSerializer( valueSerializer ); + } + + + /** + * Creates a new instance of InMemoryBTreeBuilder. + * + * @param btreeConfiguration The Btree configuration + */ + public InMemoryBTreeBuilder( InMemoryBTreeConfiguration btreeConfiguration ) + { + this.btreeConfiguration = btreeConfiguration; } @SuppressWarnings("unchecked") public BTree build( Iterator> sortedTupleItr ) throws IOException { - BTree btree = BTreeFactory.createInMemoryBTree( name, keySerializer, valueSerializer ); + BTree btree = BTreeFactory.createInMemoryBTree( btreeConfiguration ); + int pageSize = btree.getPageSize(); + int maxElements = ( pageSize + 1 ) * pageSize; + + // The stack used to store all the levels. No need to have more than 16 levels, + // it will allow the storage of 2^64 elements with pages containing 4 elements each. + List>[] pageStack = new ArrayList[15]; + + for ( int i = 0; i < 15; i++ ) + { + pageStack[i] = new ArrayList>( maxElements ); + } - List> lstLeaves = new ArrayList>(); + // The number of added elements + int nbAdded = 0; - int totalTupleCount = 0; + // The btree height + int btreeHeight = 0; - InMemoryLeaf leaf1 = ( InMemoryLeaf ) BTreeFactory.createLeaf( btree, 0, numKeysInNode ); - lstLeaves.add( leaf1 ); + // An array containing the number of elements necessary to fulfill a layer : + // pageSize * (pageSize + 1) + List> tuples = new ArrayList>( maxElements ); - int leafIndex = 0; + // A list of nodes that are going to be created + List> nodes = new ArrayList>(); + // Now, loop on all the elements while ( sortedTupleItr.hasNext() ) { + nbAdded++; + + // Get the tuple to inject Tuple tuple = sortedTupleItr.next(); + tuples.add( tuple ); + + if ( tuples.size() == maxElements ) + { + // We have enough elements to create pageSize leaves, and the upper node + InMemoryNode node = ( InMemoryNode ) addLeaves( btree, tuples, maxElements ); + int level = 0; + + if ( node != null ) + { + while ( true ) + { + pageStack[level].add( node ); + + // If the node list has enough elements to fulfill a parent node, + // then process + if ( pageStack[level].size() > btree.getPageSize() ) + { + node = createParentNode( btree, pageStack[level], btree.getPageSize() ); + pageStack[level].clear(); + level++; + } + else + { + break; + } + } + + ( ( AbstractBTree ) btree ).setRootPage( pageStack[level].get( 0 ) ); + + // Update the btree height + if ( btreeHeight < level ) + { + btreeHeight = level; + } + } - BTreeFactory.setKey( btree, leaf1, leafIndex, tuple.getKey() ); + tuples.clear(); + } + } - InMemoryValueHolder eh = new InMemoryValueHolder( btree, tuple.getValue() ); + if ( tuples.size() > 0 ) + { + // Let's deal with the remaining elements + Page page = addLeaves( btree, tuples, maxElements ); - BTreeFactory.setValue( btree, leaf1, leafIndex, eh ); + if ( page instanceof InMemoryNode ) + { + nodes.add( ( InMemoryNode ) page ); - leafIndex++; - totalTupleCount++; + // If the node list has enough elements to fulfill a parent node, + // then process + if ( nodes.size() == maxElements ) + { + Page rootPage = createParentNode( btree, nodes, maxElements ); - if ( ( totalTupleCount % numKeysInNode ) == 0 ) + ( ( AbstractBTree ) btree ).setRootPage( rootPage ); + } + } + else { - leafIndex = 0; - leaf1 = ( InMemoryLeaf ) BTreeFactory.createLeaf( btree, 0, numKeysInNode ); - lstLeaves.add( leaf1 ); + InMemoryLeaf leaf = ( InMemoryLeaf ) page; + + // Its a leaf. That means we may have to balance the btree + if ( pageStack[0].size() != 0 ) + { + // We have some leaves in level 0, which means we just have to add the new leaf + // there, after having check we don't have to borrow some elements from the last leaf + if ( leaf.getNbElems() < btree.getPageSize() / 2 ) + { + // Not enough elements in the added leaf. Borrow some from the left. + } + else + { + // Enough elements in the added leaf (at least N/2). We just have to update + // the parent's node. + } + } } } - if ( lstLeaves.isEmpty() ) + // Update the number of elements + ( ( AbstractBTree ) btree ).getBtreeHeader().setNbElems( nbAdded ); + + return btree; + } + + + /** + * Creates all the nodes using the provided node pages, and update the upper laye + */ + private InMemoryNode createParentNode( BTree btree, List> nodes, int maxElements ) + { + // We have enough tuples to fulfill the upper node. + // First, create the new node + InMemoryNode parentNode = ( InMemoryNode ) BTreeFactory.createNode( btree, 0, + btreeConfiguration.getPageSize() ); + + int nodePos = 0; + + // Then iterate on the tuples, creating the needed pages + for ( InMemoryNode node : nodes ) { - return btree; + if ( nodePos == 0 ) + { + PageHolder pageHolder = new PageHolder( btree, node ); + parentNode.setPageHolder( nodePos, pageHolder ); + } + else if ( nodePos == btree.getPageSize() ) + { + K key = node.getLeftMostKey(); + BTreeFactory.setKey( btree, parentNode, nodePos - 1, key ); + PageHolder pageHolder = new PageHolder( btree, node ); + parentNode.setPageHolder( nodePos, pageHolder ); + } + else + { + K key = node.getLeftMostKey(); + BTreeFactory.setKey( btree, parentNode, nodePos - 1, key ); + PageHolder pageHolder = new PageHolder( btree, node ); + parentNode.setPageHolder( nodePos, pageHolder ); + } + + nodePos++; } - // remove null keys and values from the last leaf and resize - InMemoryLeaf lastLeaf = ( InMemoryLeaf ) lstLeaves.get( lstLeaves.size() - 1 ); + // And return the node + return parentNode; + } + - for ( int i = 0; i < lastLeaf.getNbElems(); i++ ) + /** + * Creates all the leaves using the provided tuples, and update the upper layer if needed + */ + private Page addLeaves( BTree btree, List> tuples, int maxElements ) + { + if ( tuples.size() == 0 ) { - if ( lastLeaf.getKeys()[i] == null ) + // No element to inject in the BTree + return null; + } + + // The insertion position in the leaf + int leafPos = 0; + + // Deal with special cases : + // First, everything will fit in a single page + if ( tuples.size() < btree.getPageSize() ) + { + // The leaf will be the rootPage + // creates a first leaf + InMemoryLeaf leaf = ( InMemoryLeaf ) BTreeFactory.createLeaf( btree, 0, + btreeConfiguration.getPageSize() ); + + // Iterate on the tuples + for ( Tuple tuple : tuples ) { - int n = i; - lastLeaf.setNbElems( n ); - KeyHolder[] keys = lastLeaf.getKeys(); + injectTuple( btree, leaf, leafPos, tuple ); + leafPos++; + } + + return leaf; + } - lastLeaf.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) ); - System.arraycopy( keys, 0, lastLeaf.getKeys(), 0, n ); + // Second, the data will fit into a 2 level tree + if ( tuples.size() < maxElements ) + { + // We will just create the necessary leaves and the upper node if needed + // We have enough tuples to fulfill the uper node. + // First, create the new node + InMemoryNode node = ( InMemoryNode ) BTreeFactory.createNode( btree, 0, + btreeConfiguration.getPageSize() ); + + // creates a first leaf + InMemoryLeaf leaf = ( InMemoryLeaf ) BTreeFactory.createLeaf( btree, 0, + btreeConfiguration.getPageSize() ); - ValueHolder[] values = lastLeaf.values; - lastLeaf.values = ( InMemoryValueHolder[] ) Array.newInstance( InMemoryValueHolder.class, n ); - System.arraycopy( values, 0, lastLeaf.values, 0, n ); + int nodePos = 0; - break; + // Then iterate on the tuples, creating the needed pages + for ( Tuple tuple : tuples ) + { + if ( leafPos == btree.getPageSize() ) + { + // The leaf is full, we need to attach it to its parent's node + // and to create a new leaf + BTreeFactory.setKey( btree, node, nodePos, tuple.getKey() ); + PageHolder pageHolder = new PageHolder( btree, leaf ); + node.setPageHolder( nodePos, pageHolder ); + nodePos++; + + // When done, we need to create a new leaf + leaf = ( InMemoryLeaf ) BTreeFactory.createLeaf( btree, 0, + btree.getPageSize() ); + + // and inject the tuple in the leaf + injectTuple( btree, leaf, 0, tuple ); + leafPos = 1; + } + else + { + // Inject the tuple in the leaf + injectTuple( btree, leaf, leafPos, tuple ); + leafPos++; + } + } + + // Last, not least, deal with the last created leaf, which has to be injected in its parent's node + if ( leafPos > 0 ) + { + PageHolder pageHolder = new PageHolder( btree, leaf ); + node.setPageHolder( nodePos, pageHolder ); } + + return node; } + else + { + // We have enough tuples to fulfill the upper node. + // First, create the new node + InMemoryNode node = ( InMemoryNode ) BTreeFactory.createNode( btree, 0, + btreeConfiguration.getPageSize() ); + + // creates a first leaf + InMemoryLeaf leaf = ( InMemoryLeaf ) BTreeFactory.createLeaf( btree, 0, + btreeConfiguration.getPageSize() ); + + int nodePos = 0; - Page rootPage = attachNodes( lstLeaves, btree ); + // Then iterate on the tuples, creating the needed pages + for ( Tuple tuple : tuples ) + { + if ( leafPos == btree.getPageSize() ) + { + // The leaf is full, we need to attach it to its parent's node + // and to create a new node + BTreeFactory.setKey( btree, node, nodePos, tuple.getKey() ); + PageHolder pageHolder = new PageHolder( btree, leaf ); + node.setPageHolder( nodePos, pageHolder ); + nodePos++; + + // When done, we need to create a new leaf + leaf = ( InMemoryLeaf ) BTreeFactory.createLeaf( btree, 0, + btree.getPageSize() ); + + // and inject the tuple in the leaf + injectTuple( btree, leaf, 0, tuple ); + leafPos = 1; + } + else + { + // Inject the tuple in the leaf + injectTuple( btree, leaf, leafPos, tuple ); + leafPos++; + } + } - System.out.println( "built rootpage : " + rootPage ); + // Last, not least, deal with the last created leaf, which has to be injected in its parent's node + if ( leafPos > 0 ) + { + PageHolder pageHolder = new PageHolder( btree, leaf ); + node.setPageHolder( nodePos, pageHolder ); + } - ( ( AbstractBTree ) btree ).setRootPage( rootPage ); + // And return the node + return node; + } + } - return btree; + + private void injectTuple( BTree btree, InMemoryLeaf leaf, int leafPos, Tuple tuple ) + { + BTreeFactory.setKey( btree, leaf, leafPos, tuple.getKey() ); + ValueHolder valueHolder = new InMemoryValueHolder( btree, tuple.getValue() ); + BTreeFactory.setValue( btree, leaf, leafPos, valueHolder ); + } + + + private int add( BTree btree, Page[] pageStack, int level, Page page, Tuple tuple ) + { + if ( page == null ) + { + // No existing page at this level, create a new one + if ( level == 0 ) + { + // creates a leaf + InMemoryLeaf leaf = ( InMemoryLeaf ) BTreeFactory.createLeaf( btree, 0, + btreeConfiguration.getPageSize() ); + + // Store the new leaf in the stack + pageStack[level] = leaf; + + // Inject the tuple in the leaf + BTreeFactory.setKey( btree, leaf, 0, tuple.getKey() ); + ValueHolder valueHolder = new InMemoryValueHolder( btree, tuple.getValue() ); + BTreeFactory.setValue( btree, leaf, 0, valueHolder ); + } + else + { + // Create a node + InMemoryNode node = ( InMemoryNode ) BTreeFactory.createNode( btree, 0, + btreeConfiguration.getPageSize() ); + + // Inject the tuple key in the node + BTreeFactory.setKey( btree, node, 0, tuple.getKey() ); + PageHolder pageHolder = new PageHolder( btree, pageStack[level - 1] ); + node.setPageHolder( 0, pageHolder ); + } + } + else + { + // Check first if the current page is full + if ( page.getNbElems() == btree.getPageSize() ) + { + // Ok, it's full. We need to create a new page and to propagate the + // added element to the upper level + } + else + { + // We just have to inject the tuple in the current page + // be it a leaf or a node + if ( page.isLeaf() ) + { + // It's a leaf + BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() ); + ValueHolder valueHolder = new InMemoryValueHolder( btree, tuple.getValue() ); + BTreeFactory.setValue( btree, page, page.getNbElems(), valueHolder ); + } + else + { + // It's a node + BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() ); + PageHolder pageHolder = new PageHolder( btree, pageStack[level - 1] ); + ( ( InMemoryNode ) page ).setPageHolder( page.getNbElems(), pageHolder ); + } + } + } + + return level; } @@ -138,9 +459,10 @@ public class InMemoryBTreeBuilder List> lstNodes = new ArrayList>(); - int numChildren = numKeysInNode + 1; + int numChildren = btreeConfiguration.getPageSize() + 1; - InMemoryNode node = ( InMemoryNode ) BTreeFactory.createNode( btree, 0, numKeysInNode ); + InMemoryNode node = ( InMemoryNode ) BTreeFactory.createNode( btree, 0, + btreeConfiguration.getPageSize() ); lstNodes.add( node ); int i = 0; int totalNodes = 0; @@ -160,7 +482,7 @@ public class InMemoryBTreeBuilder if ( ( totalNodes % numChildren ) == 0 ) { i = 0; - node = ( InMemoryNode ) BTreeFactory.createNode( btree, 0, numKeysInNode ); + node = ( InMemoryNode ) BTreeFactory.createNode( btree, 0, btreeConfiguration.getPageSize() ); lstNodes.add( node ); } } Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java Sun Dec 7 03:28:54 2014 @@ -60,4 +60,13 @@ package org.apache.directory.mavibot.btr { return key; } + + + /** + * @see Object#toString() + */ + public String toString() + { + return key.toString(); + } } Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java Sun Dec 7 03:28:54 2014 @@ -68,10 +68,11 @@ public class PersistedBTree extend /** The BtreeInfo offset */ private long btreeInfoOffset; - + /** The internal recordManager */ private RecordManager recordManager; + /** * Creates a new BTree, with no initialization. */ @@ -130,13 +131,13 @@ public class PersistedBTree extend currentBtreeHeader = btreeHeader; break; - case PERSISTED_SUB : + case PERSISTED_SUB: init( ( PersistedBTree ) configuration.getParentBTree() ); btreeRevisions.put( 0L, btreeHeader ); currentBtreeHeader = btreeHeader; break; - - default : + + default: // We will create a new cache and a new readTransactions map init( null ); btreeRevisions.put( 0L, btreeHeader ); @@ -164,13 +165,13 @@ public class PersistedBTree extend { cacheSize = 1; } - + cache = new LRUMap( cacheSize ); } else { - this.cache = ((PersistedBTree)parentBTree).getCache(); - this.readTransactions = ((PersistedBTree)parentBTree).getReadTransactions(); + this.cache = ( ( PersistedBTree ) parentBTree ).getCache(); + this.readTransactions = ( ( PersistedBTree ) parentBTree ).getReadTransactions(); } // Initialize the txnManager thread @@ -274,7 +275,7 @@ public class PersistedBTree extend * @return * @throws IOException */ - /* no qualifier */ Tuple delete( K key, V value, long revision ) throws IOException + /* no qualifier */Tuple delete( K key, V value, long revision ) throws IOException { // We have to start a new transaction, which will be committed or rollbacked // locally. This will duplicate the current BtreeHeader during this phase. @@ -327,7 +328,7 @@ public class PersistedBTree extend // Try to delete the entry starting from the root page. Here, the root // page may be either a Node or a Leaf - DeleteResult result = btreeHeader.getRootPage().delete( key, value, revision); + DeleteResult result = btreeHeader.getRootPage().delete( key, value, revision ); if ( result instanceof NotPresentResult ) { @@ -369,11 +370,10 @@ public class PersistedBTree extend // Write down the data on disk long newBtreeHeaderOffset = recordManager.writeBtreeHeader( this, newBtreeHeader ); - // Update the B-tree of B-trees with this new offset, if we are not already doing so switch ( btreeType ) { - case PERSISTED : + case PERSISTED: // We have a new B-tree header to inject into the B-tree of btrees recordManager.addInBtreeOfBtrees( getName(), revision, newBtreeHeaderOffset ); @@ -383,19 +383,18 @@ public class PersistedBTree extend storeRevision( newBtreeHeader, recordManager.isKeepRevisions() ); break; - - case PERSISTED_SUB : + + case PERSISTED_SUB: // Sub-B-trees are only updating the CopiedPage B-tree recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() ); - + //btreeRevisions.put( revision, newBtreeHeader ); currentRevision.set( revision ); - break; - case BTREE_OF_BTREES : + case BTREE_OF_BTREES: // The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L ); @@ -471,20 +470,20 @@ public class PersistedBTree extend } } - + private BTreeHeader getNewBTreeHeader( String name ) { if ( btreeType == BTreeTypeEnum.PERSISTED_SUB ) { return getBtreeHeader(); } - + BTreeHeader btreeHeader = recordManager.getNewBTreeHeader( getName() ); return btreeHeader; } - + /** * Insert the tuple into the B-tree rootPage, get back the new rootPage */ @@ -565,7 +564,7 @@ public class PersistedBTree extend // Update the B-tree of B-trees with this new offset, if we are not already doing so switch ( btreeType ) { - case PERSISTED : + case PERSISTED: // We have a new B-tree header to inject into the B-tree of btrees recordManager.addInBtreeOfBtrees( getName(), revision, newBtreeHeaderOffset ); @@ -576,10 +575,10 @@ public class PersistedBTree extend break; - case PERSISTED_SUB : + case PERSISTED_SUB: // Sub-B-trees are only updating the CopiedPage B-tree recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() ); - + // Store the new revision storeRevision( newBtreeHeader, recordManager.isKeepRevisions() ); @@ -587,7 +586,7 @@ public class PersistedBTree extend break; - case BTREE_OF_BTREES : + case BTREE_OF_BTREES: // The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L ); @@ -608,6 +607,7 @@ public class PersistedBTree extend return result; } + /** * Write the data in the ByteBuffer, and eventually on disk if needed. * @@ -660,6 +660,7 @@ public class PersistedBTree extend return pageHolder; } + /** * Get the rootPzge associated to a give revision. * @@ -722,8 +723,8 @@ public class PersistedBTree extend return readTransaction; } - - + + /** * {@inheritDoc} */ @@ -733,7 +734,8 @@ public class PersistedBTree extend if ( btreeHeader != null ) { - ReadTransaction readTransaction = new ReadTransaction( recordManager, btreeHeader, readTransactions ); + ReadTransaction readTransaction = new ReadTransaction( recordManager, btreeHeader, + readTransactions ); readTransactions.add( readTransaction ); @@ -744,7 +746,7 @@ public class PersistedBTree extend return null; } } - + /** * @see Object#toString() Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java Sun Dec 7 03:28:54 2014 @@ -946,6 +946,7 @@ import static org.apache.directory.mavib PersistedLeaf newLeaf = new PersistedLeaf( btree, revision, nbElems + 1 ); // Create the value holder + //System.out.println("( addElement ) creating sub-btree for key " + key + " value " + value ); ValueHolder valueHolder = new PersistedValueHolder( btree, value ); // Deal with the special case of an empty page @@ -994,6 +995,8 @@ import static org.apache.directory.mavib int middle = btree.getPageSize() >> 1; PersistedLeaf leftLeaf = null; PersistedLeaf rightLeaf = null; + + //System.out.println("(addAndSplit) creating sub-btree for key " + key + " value " + value ); ValueHolder valueHolder = new PersistedValueHolder( btree, value ); // Determinate where to store the new value Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java Sun Dec 7 03:28:54 2014 @@ -20,6 +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; @@ -34,7 +38,9 @@ import org.apache.directory.mavibot.btre import org.apache.directory.mavibot.btree.exception.KeyNotFoundException; import org.apache.directory.mavibot.btree.serializer.IntSerializer; import org.apache.directory.mavibot.btree.serializer.LongSerializer; -import static org.apache.directory.mavibot.btree.BTreeFactory.*; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + /** * A holder to store the Values @@ -44,6 +50,9 @@ import static org.apache.directory.mavib */ /* No qualifier */class PersistedValueHolder extends AbstractValueHolder { + /** The LoggerFactory used by this class */ + protected static final Logger LOG = LoggerFactory.getLogger( PersistedValueHolder.class ); + /** The parent BTree */ protected PersistedBTree parentBtree; @@ -132,7 +141,7 @@ import static org.apache.directory.mavib buildSubBTree( ( PersistedBTree ) valueBtree, values ); } } - catch( Exception e ) + catch ( Exception e ) { throw new RuntimeException( e ); } @@ -405,7 +414,7 @@ import static org.apache.directory.mavib } cursor.close(); - + return returnedValue; } else @@ -638,7 +647,7 @@ import static org.apache.directory.mavib V val = super.replaceValueArray( newValue ); // The raw value is not anymore up to date with the content isRawUpToDate = false; - + return val; } @@ -702,7 +711,12 @@ import static org.apache.directory.mavib /** - * {@inheritDoc} + * Constructs the sub-BTree using bulkload instead of performing sequential inserts. + * + * @param btree the sub-BTtree to be constructed + * @param dupKeyValues the array of values to be inserted as keys + * @return + * @throws Exception */ protected BTree buildSubBTree( BTree givenBTree, V[] dupKeyValues ) throws Exception { @@ -805,7 +819,8 @@ import static org.apache.directory.mavib * @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 + private Page attachNodes( List> children, BTree btree, int numKeysInNode, RecordManager rm ) + throws IOException { if ( children.size() == 1 ) { @@ -864,15 +879,15 @@ import static org.apache.directory.mavib } } - if( lastNode.keys.length == 0 ) + if ( lastNode.keys.length == 0 ) { lstNodes.remove( lastNode ); } return attachNodes( lstNodes, btree, numKeysInNode, rm ); } - - + + /** * @see Object#toString() */ Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java Sun Dec 7 03:28:54 2014 @@ -219,7 +219,7 @@ public class RecordManager extends Abstr private int commitCount = 0; /** the threshold at which the SpaceReclaimer will be run to free the copied pages */ - private int spaceReclaimerThreshold = 200; + private int spaceReclaimerThreshold = 0; /** * Create a Record manager which will either create the underlying file @@ -579,6 +579,14 @@ public class RecordManager extends Abstr return; case 1 : + + commitCount++; + + if( commitCount >= spaceReclaimerThreshold ) + { + runReclaimer(); + } + // We are done with the transaction, we can update the RMHeader and swap the BTreeHeaders // First update the RMHeader to be sure that we have a way to restore from a crash updateRecordManagerHeader(); @@ -610,19 +618,20 @@ public class RecordManager extends Abstr // And decrement the number of started transactions decrementTxnLevel(); - commitCount++; - - if( commitCount >= spaceReclaimerThreshold ) - { - runReclaimer(); - } - // Finally, release the global lock transactionLock.unlock(); return; default : + + commitCount++; + + if( commitCount >= spaceReclaimerThreshold ) + { + runReclaimer(); + } + // We are inner an existing transaction. Just update the necessary elements // Update the RMHeader to be sure that we have a way to restore from a crash updateRecordManagerHeader(); @@ -654,13 +663,6 @@ public class RecordManager extends Abstr // And decrement the number of started transactions decrementTxnLevel(); - commitCount++; - - if( commitCount >= spaceReclaimerThreshold ) - { - runReclaimer(); - } - // Finally, release the global lock transactionLock.unlock(); @@ -771,7 +773,7 @@ public class RecordManager extends Abstr if( firstPage.isFree() ) { - System.out.println("------------- NOT freeing free page ---------------"); + //System.out.println("------------- NOT freeing free page ---------------"); return new PageIO[]{}; } else @@ -3931,6 +3933,8 @@ public class RecordManager extends Abstr @SuppressWarnings("all") /* No qualifier */boolean chopTree( PersistedBTree tree, Object key) { + beginTransaction(); + AbstractPage root = ( AbstractPage ) tree.getRootPage(); try @@ -3975,7 +3979,7 @@ public class RecordManager extends Abstr Object leftKey = null; - long revision = tree.getRevision(); + long revision = tree.getRevision() + 1; while( !stack.isEmpty() ) { @@ -4114,15 +4118,21 @@ public class RecordManager extends Abstr BTreeHeader header = tree.getBtreeHeader(); header.setRootPage( pageHolder.getValue() ); - header.setRevision( tree.getRevision() ); + header.setRevision( revision ); // compute header.setNbElems( tree.getNbElems() - keysToRemove ); - writeBtreeHeader( tree, header ); + long newBtreeHeaderOffset = writeBtreeHeader( tree, header ); + + // We have a new B-tree header to inject into the B-tree of btrees + addInBtreeOfBtrees( tree.name, revision, newBtreeHeaderOffset ); + + commit(); } catch( IOException e ) { + rollback(); LOG.warn( "Failed to free the pages of the tree {}", tree.getName() ); LOG.warn( "", e ); return false; Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java Sun Dec 7 03:28:54 2014 @@ -28,6 +28,7 @@ import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.OutputStream; import java.util.ArrayList; +import java.util.Arrays; import java.util.Collections; import java.util.Iterator; import java.util.List; @@ -36,6 +37,7 @@ import java.util.Set; import java.util.TreeSet; import java.util.concurrent.ConcurrentHashMap; +import org.apache.directory.mavibot.btree.exception.KeyNotFoundException; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -162,6 +164,7 @@ public class SpaceReclaimer return map; } + //void reclaim(){} /** * relcaims the copied pages @@ -191,6 +194,8 @@ public class SpaceReclaimer List copiedRevisions = getRevisions( name ); + long lastRev = -1L; + for ( RevisionOffset ro : copiedRevisions ) { long rv = ro.getRevision(); @@ -207,7 +212,39 @@ public class SpaceReclaimer rm.free( offsets ); RevisionName key = new RevisionName( rv, name ); + rm.copiedPageMap.remove( key ); + + if( rv > lastRev ) + { + lastRev = rv; + } + } + + if( lastRev != -1 ) + { + System.out.println( "===================== start ======================= " + name ); + System.out.println( "BoB root offset " + ( ( AbstractPage ) rm.btreeOfBtrees.getRootPage() ).getOffset() ); + System.out.println( "deleting revisions from BoB upto and including " + lastRev ); + ValueCursor values = rm.btreeOfBtrees.getValues( name ); + RevisionAndHeaderOffset prevRho = null; + while( values.hasNext() ) + { + RevisionAndHeaderOffset rho = values.next(); + if( rho.getRevision() > lastRev ) + { + System.out.println( "stopped after deleting revision " + prevRho.getRevision() ); + break; + } + prevRho = rho; + rm.btreeOfBtrees.delete( name, rho ); + System.out.println( "------- deleted " + rho.getRevision() + " , " + rho.getOffset() ); + } + + + values.close(); + System.out.println( "BoB root offset " + ( ( AbstractPage ) rm.btreeOfBtrees.getRootPage() ).getOffset() ); + System.out.println( "===================== end ======================= " + name ); } } } Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java Sun Dec 7 03:28:54 2014 @@ -20,6 +20,9 @@ package org.apache.directory.mavibot.btree; +import java.util.Comparator; + + /** * The Tuple class is used when we browse a btree, it will contain the results * fetched from the btree. @@ -29,7 +32,7 @@ package org.apache.directory.mavibot.btr * @param The type for the Key * @param The type for the stored value */ -public class Tuple +public class Tuple implements Comparable> { /** The key */ protected K key; @@ -37,6 +40,9 @@ public class Tuple /** The value */ protected V value; + /** The key comparator */ + protected Comparator keyComparator; + /** * Creates a Tuple with no content @@ -59,6 +65,19 @@ public class Tuple /** + * Creates a Tuple containing a key and its associated value. + * @param key The key + * @param value The associated value + */ + public Tuple( K key, V value, Comparator keyComparator ) + { + this.key = key; + this.value = value; + this.keyComparator = keyComparator; + } + + + /** * @return the key */ public K getKey() @@ -94,6 +113,77 @@ public class Tuple } + /** + * @see Object#hashCode() + */ + @Override + public int hashCode() + { + return key.hashCode(); + } + + + /** + * @see Object#equals() + */ + @SuppressWarnings("unchecked") + @Override + public boolean equals( Object obj ) + { + if ( this == obj ) + { + return true; + } + + if ( !( obj instanceof Tuple ) ) + { + return false; + } + + if ( this.key == null ) + { + return ( ( Tuple ) obj ).key == null; + } + + return this.key.equals( ( ( Tuple ) obj ).key ); + } + + + /** + * @see java.lang.Comparable#compareTo(java.lang.Object) + */ + @Override + public int compareTo( Tuple t ) + { + if ( keyComparator != null ) + { + return keyComparator.compare( key, t.key ); + } + else + { + return 0; + } + } + + + /** + * @return the keyComparator + */ + public Comparator getKeyComparator() + { + return keyComparator; + } + + + /** + * @param keyComparator the keyComparator to set + */ + public void setKeyComparator( Comparator keyComparator ) + { + this.keyComparator = keyComparator; + } + + /** * @see Object#toString() */ Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java Sun Dec 7 03:28:54 2014 @@ -54,9 +54,6 @@ public class TupleCursor /** The transaction used for this cursor */ protected ReadTransaction transaction; - /** The Tuple used to return the results */ - protected Tuple tuple = new Tuple(); - /** * Creates a new instance of Cursor. @@ -322,8 +319,7 @@ public class TupleCursor } AbstractPage leaf = ( AbstractPage ) ( parentPos.page ); - tuple.setKey( leaf.getKey( parentPos.pos ) ); - tuple.setValue( value ); + Tuple tuple = new Tuple( leaf.getKey( parentPos.pos ), value ); return tuple; } @@ -396,6 +392,7 @@ public class TupleCursor // The key AbstractPage leaf = ( AbstractPage ) ( parentPos.page ); + Tuple tuple = new Tuple(); tuple.setKey( leaf.getKey( parentPos.pos ) ); // The value @@ -595,8 +592,7 @@ public class TupleCursor } AbstractPage leaf = ( AbstractPage ) ( parentPos.page ); - tuple.setKey( leaf.getKey( parentPos.pos ) ); - tuple.setValue( value ); + Tuple tuple = new Tuple( leaf.getKey( parentPos.pos ), value ); return tuple; } @@ -665,6 +661,7 @@ public class TupleCursor AbstractPage leaf = ( AbstractPage ) ( parentPos.page ); // The key + Tuple tuple = new Tuple(); tuple.setKey( leaf.getKey( parentPos.pos ) ); // The value @@ -703,16 +700,16 @@ public class TupleCursor switch ( parentPos.pos ) { - case 0 : + case 0: // Beginning of the leaf. We have to go back into the stack up to the // parent, and down to the leaf return hasPrevParentPos(); - - case -1 : + + case -1: // no previous key return false; - - default : + + default: // we have a previous key return true; } Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java Sun Dec 7 03:28:54 2014 @@ -50,9 +50,9 @@ public abstract class AbstractElementSer { this.comparator = comparator; - // We will extract the Type to use for values, using the serializer for that - Class valueSerializerClass = comparator.getClass(); - Type[] types = valueSerializerClass.getGenericInterfaces(); + // We will extract the Type to use for values, using the comparator for that + Class comparatorClass = comparator.getClass(); + Type[] types = comparatorClass.getGenericInterfaces(); if ( types[0] instanceof Class ) { Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java Sun Dec 7 03:28:54 2014 @@ -29,6 +29,7 @@ import java.util.List; import org.apache.directory.mavibot.btree.exception.KeyNotFoundException; import org.apache.directory.mavibot.btree.serializer.IntSerializer; +import org.junit.Ignore; import org.junit.Test; @@ -40,6 +41,7 @@ import org.junit.Test; public class InMemoryBTreeBuilderTest { @Test + @Ignore public void testIntegerTree() throws IOException, KeyNotFoundException { List> sortedTuple = new ArrayList>(); Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java?rev=1643645&r1=1643644&r2=1643645&view=diff ============================================================================== --- directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java (original) +++ directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java Sun Dec 7 03:28:54 2014 @@ -36,7 +36,6 @@ import org.apache.commons.io.FileUtils; import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException; import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException; import org.apache.directory.mavibot.btree.exception.KeyNotFoundException; -import org.apache.directory.mavibot.btree.serializer.IntSerializer; import org.apache.directory.mavibot.btree.serializer.LongSerializer; import org.apache.directory.mavibot.btree.serializer.StringSerializer; import org.junit.After; @@ -52,6 +51,7 @@ import org.junit.rules.TemporaryFolder; * * @author Apache Directory Project */ +@Ignore public class PersistedBTreeBrowseTest { private BTree btree = null; @@ -98,7 +98,7 @@ public class PersistedBTreeBrowseTest { FileUtils.deleteDirectory( dataDir ); } - + recordManager1.close(); assertTrue( recordManager1.isContextOk() ); } @@ -416,12 +416,12 @@ public class PersistedBTreeBrowseTest assertEquals( "3", tuple.getValue() ); // Now, move to the prev value - cursor.prev(); + tuple = cursor.prev(); assertEquals( 2L, ( long ) tuple.getKey() ); assertEquals( "2", tuple.getValue() ); // And to the next value - cursor.next(); + tuple = cursor.next(); assertEquals( 3L, ( long ) tuple.getKey() ); assertEquals( "3", tuple.getValue() ); } @@ -633,7 +633,7 @@ public class PersistedBTreeBrowseTest btree.insert( i, Long.toString( j ) ); } } - +System.out.println("inserted"); // Create the cursor TupleCursor cursor = btree.browse(); @@ -716,7 +716,8 @@ public class PersistedBTreeBrowseTest * stored into a sub btree */ @Test - public void testBrowseBTreeLeafNextDupsSubBTree1() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException + public void testBrowseBTreeLeafNextDupsSubBTree1() throws IOException, BTreeAlreadyManagedException, + KeyNotFoundException { // Inject some duplicate data which will be stored into a sub btree for ( long i = 1L; i < 32L; i++ ) @@ -748,7 +749,8 @@ public class PersistedBTreeBrowseTest * Test the browse methods on a btree containing just a leaf with duplicate values */ @Test - public void testBrowseBTreeLeafPrevDupsSubBTree1() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException + public void testBrowseBTreeLeafPrevDupsSubBTree1() throws IOException, BTreeAlreadyManagedException, + KeyNotFoundException { // Inject some duplicate data which will be stored into a sub btree for ( long i = 1L; i < 32L; i++ ) @@ -911,7 +913,7 @@ public class PersistedBTreeBrowseTest // Create the cursor TupleCursor cursor = btree.browseFrom( 1500L ); - + assertFalse( cursor.hasNext() ); assertTrue( cursor.hasPrev() ); assertEquals( 1000L, cursor.prev().getKey().longValue() ); @@ -1009,55 +1011,55 @@ public class PersistedBTreeBrowseTest } } - + /** * Test the TupleCursor.nextKey method on a btree containing nodes * with duplicate values. */ - @Test - @Ignore - public void testNextKeyDups() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException - { - // Inject some data - //for ( long i = 1; i < 3; i++ ) - { - for ( long j = 1; j < 9; j++ ) - { - btree.insert( 1L, Long.toString( j ) ); - } - } - - btree.insert( 1L, "10" ); - - // Create the cursor - TupleCursor cursor = btree.browse(); - - // Move forward - cursor.beforeFirst(); - - assertFalse( cursor.hasPrevKey() ); - assertTrue( cursor.hasNextKey() ); - - Tuple tuple = cursor.nextKey(); - - checkTuple( tuple, 1L, "1" ); - - cursor.beforeFirst(); - long val = 1L; - - while ( cursor.hasNext() ) - { - tuple = cursor.next(); - - assertEquals( Long.valueOf( 1L ), tuple.getKey() ); - assertEquals( Long.toString( val ), tuple.getValue() ); - - val++; - } - - assertFalse( cursor.hasNextKey() ); - assertFalse( cursor.hasPrevKey() ); - } + @Test + @Ignore + public void testNextKeyDups() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException + { + // Inject some data + //for ( long i = 1; i < 3; i++ ) + { + for ( long j = 1; j < 9; j++ ) + { + btree.insert( 1L, Long.toString( j ) ); + } + } + + btree.insert( 1L, "10" ); + + // Create the cursor + TupleCursor cursor = btree.browse(); + + // Move forward + cursor.beforeFirst(); + + assertFalse( cursor.hasPrevKey() ); + assertTrue( cursor.hasNextKey() ); + + Tuple tuple = cursor.nextKey(); + + checkTuple( tuple, 1L, "1" ); + + cursor.beforeFirst(); + long val = 1L; + + while ( cursor.hasNext() ) + { + tuple = cursor.next(); + + assertEquals( Long.valueOf( 1L ), tuple.getKey() ); + assertEquals( Long.toString( val ), tuple.getValue() ); + + val++; + } + + assertFalse( cursor.hasNextKey() ); + assertFalse( cursor.hasPrevKey() ); + } /** @@ -1106,8 +1108,8 @@ public class PersistedBTreeBrowseTest } } } - - + + /** * Test the overwriting of elements */ @@ -1115,14 +1117,14 @@ public class PersistedBTreeBrowseTest public void testOverwrite() throws Exception { btree.setAllowDuplicates( false ); - + // Adding an element with a null value btree.insert( 1L, "1" ); assertTrue( btree.hasKey( 1L ) ); assertEquals( "1", btree.get( 1L ) ); - + btree.insert( 1L, "10" ); assertTrue( btree.hasKey( 1L ) ); @@ -1131,17 +1133,17 @@ public class PersistedBTreeBrowseTest btree.close(); } - + @Ignore("test used for debugging") @Test public void testAdd20Random() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException { - long [] values = new long[] - { - 14, 7, 43, 37, 49, 3, 20, 26, 17, 29, - 40, 33, 21, 18, 9, 30, 45, 36, 12, 8 - }; - + long[] values = new long[] + { + 14, 7, 43, 37, 49, 3, 20, 26, 17, 29, + 40, 33, 21, 18, 9, 30, 45, 36, 12, 8 + }; + btree.setPageSize( 4 ); // Inject some data for ( long value : values ) @@ -1150,16 +1152,45 @@ public class PersistedBTreeBrowseTest System.out.println( btree ); } - Map copiedPagesBtree = recordManager1.copiedPageMap; - + System.out.println( copiedPagesBtree ); - + TupleCursor cursor = btree.browse(); - + while ( cursor.hasNext() ) { System.out.println( cursor.nextKey() ); } } -} \ No newline at end of file + + + /** + * Test the overwriting of elements + */ + @Test + public void testDelete() throws Exception + { + btree.setAllowDuplicates( false ); + + btree.setPageSize( 4 ); + + for(long i = 0; i < 8; i++ ) + { + btree.insert( i, String.valueOf( i ) ); + } + + for( long i =7; i > 1; i-- ) + { + btree.delete( i ); + System.out.println("======================= deleted " + i + " ======================="); + System.out.println( btree ); + System.out.println("================================================================="); + } + + System.out.println( btree ); + + btree.close(); + } + +}