You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2018/01/02 22:43:36 UTC
[directory-mavibot] branch single-value updated: Removed classes
that are unused atm
This is an automated email from the ASF dual-hosted git repository.
elecharny pushed a commit to branch single-value
in repository https://gitbox.apache.org/repos/asf/directory-mavibot.git
The following commit(s) were added to refs/heads/single-value by this push:
new d7fb116 Removed classes that are unused atm
d7fb116 is described below
commit d7fb11613fc8f731fdb303209e11ff19c446f426
Author: Emmanuel Lécharny <el...@symas.com>
AuthorDate: Tue Jan 2 23:43:34 2018 +0100
Removed classes that are unused atm
---
.../directory/mavibot/btree/BTreeBuilder.java | 212 ---
.../apache/directory/mavibot/btree/BulkLoader.java | 1413 --------------------
.../directory/mavibot/btree/BulkLoaderTest.java | 996 --------------
3 files changed, 2621 deletions(-)
diff --git a/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeBuilder.java b/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeBuilder.java
deleted file mode 100644
index 3ee6ad7..0000000
--- a/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeBuilder.java
+++ /dev/null
@@ -1,212 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- *
- */
-
-package org.apache.directory.mavibot.btree;
-
-
-import java.io.IOException;
-import java.lang.reflect.Array;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-
-import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
-
-
-/**
- * A B-tree builder that builds a tree from the bottom.
- *
- * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
- */
-public class BTreeBuilder<K, V>
-{
- private String name;
-
- private int numKeysInNode;
-
- private ElementSerializer<K> keySerializer;
-
- private ElementSerializer<V> valueSerializer;
-
- private RecordManager rm;
-
-
- public BTreeBuilder( RecordManager rm, String name, int numKeysInNode, ElementSerializer<K> keySerializer,
- ElementSerializer<V> valueSerializer )
- {
- this.rm = rm;
- this.name = name;
- this.numKeysInNode = numKeysInNode;
- this.keySerializer = keySerializer;
- this.valueSerializer = valueSerializer;
- }
-
-
- @SuppressWarnings("unchecked")
- public BTree<K, V> build( WriteTransaction transaction, Iterator<Tuple<K, V>> sortedTupleItr ) throws Exception
- {
- BTree<K, V> btree = BTreeFactory.createBTree( transaction, name, keySerializer, valueSerializer );
-
- rm.manage( transaction, btree );
-
- List<Page<K, V>> lstLeaves = new ArrayList<>();
-
- int totalTupleCount = 0;
-
- Leaf<K, V> leaf1 = ( Leaf<K, V> ) BTreeFactory.createLeaf( btree, transaction.getRevision(), numKeysInNode );
- lstLeaves.add( leaf1 );
-
- int leafIndex = 0;
-
- while ( sortedTupleItr.hasNext() )
- {
- Tuple<K, V> tuple = sortedTupleItr.next();
-
- BTreeFactory.setKey( btree, leaf1, leafIndex, tuple.getKey() );
-
- ValueHolder<V> eh = new ValueHolder<>( btree, tuple.getValue() );
-
- BTreeFactory.setValue( btree, leaf1, leafIndex, eh );
-
- leafIndex++;
- totalTupleCount++;
-
- if ( ( totalTupleCount % numKeysInNode ) == 0 )
- {
- leafIndex = 0;
-
- PageHolder<K, V> pageHolder = rm.writePage( transaction, btree, leaf1, 1 );
-
- leaf1 = ( Leaf<K, V> ) BTreeFactory.createLeaf( btree, transaction.getRevision(), numKeysInNode );
- lstLeaves.add( leaf1 );
- }
-
- //TODO build the whole tree in chunks rather than processing *all* leaves at first
- }
-
- if ( lstLeaves.isEmpty() )
- {
- return btree;
- }
-
- // remove null keys and values from the last leaf and resize
- Leaf<K, V> lastLeaf = ( Leaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
-
- for ( int i = 0; i < lastLeaf.getPageNbElems(); i++ )
- {
- if ( lastLeaf.getKey( i ) == null )
- {
- int n = i;
- lastLeaf.setPageNbElems( n );
- KeyHolder<K>[] keys = lastLeaf.getKeys();
-
- lastLeaf.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) );
- System.arraycopy( keys, 0, lastLeaf.getKeys(), 0, n );
-
- ValueHolder<V>[] values = lastLeaf.getValues();
- lastLeaf.setValues( ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, n ) );
- System.arraycopy( values, 0, lastLeaf.getValues(), 0, n );
-
- PageHolder<K, V> pageHolder = rm.writePage( transaction, btree, lastLeaf, 1 );
-
- break;
- }
- }
-
- // make sure either one of the root pages is reclaimed, cause when we call rm.manage()
- // there is already a root page created
- Page<K, V> rootPage = attachNodes( transaction, lstLeaves, btree );
-
- //System.out.println("built rootpage : " + rootPage);
- ( ( BTree<K, V> ) btree ).setNbElems( totalTupleCount );
-
- //rm.updateBtreeHeader( btree, ( ( AbstractPage<K, V> ) rootPage ).getOffset() );
-
- //rm.freePages( transaction, btree, btree.getRootPage( transaction ).getRevision(), Arrays.asList( btree.getRootPage( transaction ) ) );
-
- ( ( BTree<K, V> ) btree ).setRootPage( rootPage );
-
- return btree;
- }
-
-
- @SuppressWarnings("unchecked")
- private Page<K, V> attachNodes( WriteTransaction transaction, List<Page<K, V>> children, BTree<K, V> btree ) throws IOException
- {
- if ( children.size() == 1 )
- {
- return children.get( 0 );
- }
-
- List<Page<K, V>> lstNodes = new ArrayList<>();
-
- int numChildren = numKeysInNode + 1;
-
- Node<K, V> node = ( Node<K, V> ) BTreeFactory.createNode( btree, transaction.getRevision(), numKeysInNode );
- lstNodes.add( node );
- int i = 0;
- int totalNodes = 0;
-
- for ( Page<K, V> page : children )
- {
- if ( i != 0 )
- {
- BTreeFactory.setKey( btree, node, i - 1, page.getLeftMostKey() );
- }
-
- BTreeFactory.setPage( btree, node, i, page );
-
- i++;
- totalNodes++;
-
- if ( ( totalNodes % numChildren ) == 0 )
- {
- i = 0;
-
- rm.writePage( transaction, btree, node, 1 );
-
- node = ( Node<K, V> ) BTreeFactory.createNode( btree, transaction.getRevision(), numKeysInNode );
- lstNodes.add( node );
- }
- }
-
- // remove null keys and values from the last node and resize
- AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
-
- for ( int j = 0; j < lastNode.getPageNbElems(); j++ )
- {
- if ( lastNode.getKey( j ) == null )
- {
- int n = j;
- lastNode.setPageNbElems( n );
- KeyHolder<K>[] keys = lastNode.getKeys();
-
- lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) );
- System.arraycopy( keys, 0, lastNode.getKeys(), 0, n );
-
- rm.writePage( transaction, btree, lastNode, 1 );
-
- break;
- }
- }
-
- return attachNodes( transaction, lstNodes, btree );
- }
-}
diff --git a/mavibot/src/main/java/org/apache/directory/mavibot/btree/BulkLoader.java b/mavibot/src/main/java/org/apache/directory/mavibot/btree/BulkLoader.java
deleted file mode 100644
index b6f818c..0000000
--- a/mavibot/src/main/java/org/apache/directory/mavibot/btree/BulkLoader.java
+++ /dev/null
@@ -1,1413 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- *
- */
-
-package org.apache.directory.mavibot.btree;
-
-
-import java.io.File;
-import java.io.FileInputStream;
-import java.io.FileNotFoundException;
-import java.io.FileOutputStream;
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-import java.util.TreeMap;
-import java.util.TreeSet;
-
-import org.apache.directory.mavibot.btree.comparator.IntComparator;
-import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
-import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
-import org.apache.directory.mavibot.btree.serializer.IntSerializer;
-
-
-/**
- * A class used to bulk load a BTree. It will allow the load of N elements in
- * a given BTree without to have to inject one by one, saving a lot of time.
- * The second advantage is that the btree will be dense (the leaves will be
- * complete, except the last one).
- * This class can also be used to compact a BTree.
- *
- * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
- */
-public class BulkLoader<K, V>
-{
- private BulkLoader()
- {
- }
-
- enum LevelEnum
- {
- LEAF,
- 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
- * TODO readElements.
- *
- * @param btree
- * @param iterator
- * @param sortedFiles
- * @param tuples
- * @param chunkSize
- * @return
- * @throws IOException
- */
- private static <K, V> int readElements( BTree<K, V> btree, Iterator<Tuple<K, V>> iterator, List<File> sortedFiles,
- List<Tuple<K, V>> tuples, int chunkSize ) throws IOException
- {
- int nbRead = 0;
- int nbIteration = 0;
- int nbElems = 0;
- boolean inMemory = true;
- Set<K> keys = new HashSet<>();
-
- while ( true )
- {
- nbIteration++;
- tuples.clear();
- keys.clear();
-
- // Read up to chukSize elements
- while ( iterator.hasNext() && ( nbRead < chunkSize ) )
- {
- Tuple<K, V> tuple = iterator.next();
- tuples.add( tuple );
-
- if ( !keys.contains( tuple.getKey() ) )
- {
- keys.add( tuple.getKey() );
- nbRead++;
- }
- }
-
- if ( nbRead < chunkSize )
- {
- if ( nbIteration != 1 )
- {
- // Flush the sorted data on disk and exit
- inMemory = false;
-
- sortedFiles.add( flushToDisk( nbIteration, tuples, btree ) );
- }
-
- // Update the number of read elements
- nbElems += nbRead;
-
- break;
- }
- else
- {
- if ( !iterator.hasNext() )
- {
- // special case : we have exactly chunkSize elements in the incoming data
- if ( nbIteration > 1 )
- {
- // Flush the sorted data on disk and exit
- inMemory = false;
- sortedFiles.add( flushToDisk( nbIteration, tuples, btree ) );
- }
-
- // We have read all the data in one round trip, let's get out, no need
- // to store the data on disk
-
- // Update the number of read elements
- nbElems += nbRead;
-
- break;
- }
-
- // We have read chunkSize elements, we have to sort them on disk
- nbElems += nbRead;
- nbRead = 0;
- sortedFiles.add( flushToDisk( nbIteration, tuples, btree ) );
- }
- }
-
- if ( !inMemory )
- {
- tuples.clear();
- }
-
- return nbElems;
- }
-
-
- /**
- * Read all the sorted files, and inject them into one single big file containing all the
- * sorted and merged elements.
- * @throws IOException
- */
- private static <K, V> Tuple<Iterator<Tuple<K, V>>, SortedFile> processFiles( BTree<K, V> btree,
- Iterator<Tuple<K, V>> dataIterator ) throws IOException
- {
- File file = File.createTempFile( "sortedUnique", "data" );
- file.deleteOnExit();
- // Number of read elements
- int nbReads = 0;
-
- try ( FileOutputStream fos = new FileOutputStream( file ) )
- {
-
- // Flush the tuples on disk
- while ( dataIterator.hasNext() )
- {
- nbReads++;
-
- // grab a tuple
- Tuple<K, V> tuple = dataIterator.next();
-
- // Serialize the key
- byte[] bytesKey = btree.getKeySerializer().serialize( tuple.key );
- fos.write( IntSerializer.serialize( bytesKey.length ) );
- fos.write( bytesKey );
-
- // Serialize the values
- V value = tuple.getValue();
-
- byte[] bytesValue = btree.getValueSerializer().serialize( value );
-
- // Serialize the value
- fos.write( IntSerializer.serialize( bytesValue.length ) );
- fos.write( bytesValue );
- }
-
- fos.flush();
- }
-
- FileInputStream fis = new FileInputStream( file );
- Iterator<Tuple<K, V>> uniqueIterator = createUniqueFileIterator( btree, fis );
- SortedFile sortedFile = new SortedFile( file, nbReads );
-
- return new Tuple<>( uniqueIterator, sortedFile );
- }
-
-
- /**
- * Bulk Load data into a persisted BTree
- *
- * @param btree The persisted BTree in which we want to load the data
- * @param iterator The iterator over the data to bulkload
- * @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 <K, V> BTree<K, V> load( BTree<K, V> btree, Iterator<Tuple<K, V>> iterator, int chunkSize )
- throws IOException
- {
- if ( btree == null )
- {
- throw new RuntimeException( "Invalid BTree : it's null" );
- }
-
- if ( iterator == null )
- {
- // Nothing to do...
- return null;
- }
-
- // Iterate through the elements by chunk
- boolean inMemory = true;
-
- // The list of files we will use to store the sorted chunks
- List<File> sortedFiles = new ArrayList<>();
-
- // An array of chunkSize tuple max
- List<Tuple<K, V>> tuples = new ArrayList<>( chunkSize );
-
- // Now, start to read all the tuples to sort them. We may use intermediate files
- // for that purpose if we hit the threshold.
- int nbElems = readElements( btree, iterator, sortedFiles, tuples, chunkSize );
-
- // If the tuple list is empty, we have to process the load based on files, not in memory
- if ( nbElems > 0 )
- {
- inMemory = !tuples.isEmpty();
- }
-
- // Now that we have processed all the data, we can start storing them in the btree
- Iterator<Tuple<K, V>> dataIterator = null;
- FileInputStream[] streams = null;
- BTree<K, V> resultBTree = null;
-
- if ( inMemory )
- {
- // Here, we have all the data in memory, no need to merge files
- // We will build a simple iterator over the data
- dataIterator = createTupleIterator( btree, tuples );
- resultBTree = bulkLoad( btree, dataIterator, nbElems );
- }
- else
- {
- // We first have to build an iterator over the files
- int nbFiles = sortedFiles.size();
- streams = new FileInputStream[nbFiles];
-
- for ( int i = 0; i < nbFiles; i++ )
- {
- streams[i] = new FileInputStream( sortedFiles.get( i ) );
- }
-
- dataIterator = createIterator( btree, streams );
-
- // Process the files, and construct one single file with an iterator
- Tuple<Iterator<Tuple<K, V>>, 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
- // target btree.
- // Now, close the FileInputStream, and delete them if we have some
- if ( !inMemory )
- {
- int nbFiles = sortedFiles.size();
-
- for ( int i = 0; i < nbFiles; i++ )
- {
- streams[i].close();
- sortedFiles.get( i ).delete();
- }
- }
-
- return resultBTree;
- }
-
-
- /**
- * Creates a node leaf LevelInfo based on the number of elements in the lower level. We can store
- * up to PageSize + 1 references to pages in a node.
- */
- /* no qualifier*/static <K, V> LevelInfo<K, V> computeLevel( BTree<K, V> btree, int nbElems, LevelEnum levelType )
- {
- BTreeInfo<K, V> btreeInfo = btree.getBtreeInfo();
- int pageSize = btree.getPageNbElem();
- int incrementNode = 0;
-
- if ( levelType == LevelEnum.NODE )
- {
- incrementNode = 1;
- }
-
- LevelInfo<K, V> level = new LevelInfo<>();
- level.setType( ( levelType == LevelEnum.NODE ) );
- level.setNbElems( nbElems );
- level.setNbPages( nbElems / ( pageSize + incrementNode ) );
- level.setLevelNumber( 0 );
- level.setNbAddedElems( 0 );
- level.setCurrentPos( 0 );
-
- // Create the first level page
- if ( nbElems <= pageSize + incrementNode )
- {
- if ( nbElems % ( pageSize + incrementNode ) != 0 )
- {
- level.setNbPages( 1 );
- }
-
- level.setNbElemsLimit( nbElems );
-
- if ( level.isNode() )
- {
- level.setCurrentPage( BTreeFactory.createNode( btreeInfo, 0L, nbElems - 1 ) );
- }
- else
- {
- level.setCurrentPage( BTreeFactory.createLeaf( btreeInfo, 0L, nbElems ) );
- }
- }
- else
- {
- int remaining = nbElems % ( pageSize + incrementNode );
-
- if ( remaining == 0 )
- {
- level.setNbElemsLimit( nbElems );
-
- if ( level.isNode() )
- {
- level.setCurrentPage( BTreeFactory.createNode( btreeInfo, 0L, pageSize ) );
- }
- else
- {
- level.setCurrentPage( BTreeFactory.createLeaf( btreeInfo, 0L, pageSize ) );
- }
- }
- else
- {
- level.incNbPages();
-
- if ( remaining < ( pageSize / 2 ) + incrementNode )
- {
- level.setNbElemsLimit( nbElems - remaining - ( pageSize + incrementNode ) );
-
- if ( level.getNbElemsLimit() > 0 )
- {
- if ( level.isNode() )
- {
- level.setCurrentPage( BTreeFactory.createNode( btreeInfo, 0L, pageSize ) );
- }
- else
- {
- level.setCurrentPage( BTreeFactory.createLeaf( btreeInfo, 0L, pageSize ) );
- }
- }
- else
- {
- if ( level.isNode() )
- {
- level
- .setCurrentPage( BTreeFactory.createNode( btreeInfo, 0L, ( pageSize / 2 ) + remaining - 1 ) );
- }
- else
- {
- level.setCurrentPage( BTreeFactory.createLeaf( btreeInfo, 0L, ( pageSize / 2 ) + remaining ) );
- }
- }
- }
- else
- {
- level.setNbElemsLimit( nbElems - remaining );
-
- if ( level.isNode() )
- {
- level.setCurrentPage( BTreeFactory.createNode( btreeInfo, 0L, pageSize ) );
- }
- else
- {
- level.setCurrentPage( BTreeFactory.createLeaf( btreeInfo, 0L, pageSize ) );
- }
- }
- }
- }
-
- return level;
- }
-
-
- /**
- * Compute the number of pages necessary to store all the elements per level. The resulting list is
- * reversed ( ie the leaves are on the left, the root page on the right.
- */
- /* No Qualifier */static <K, V> List<LevelInfo<K, V>> computeLevels( BTree<K, V> btree, int nbElems )
- {
- List<LevelInfo<K, V>> levelList = new ArrayList<LevelInfo<K, V>>();
-
- // Compute the leaves info
- LevelInfo<K, V> leafLevel = computeLevel( btree, nbElems, LevelEnum.LEAF );
-
- levelList.add( leafLevel );
- int nbPages = leafLevel.getNbPages();
- int levelNumber = 1;
-
- while ( nbPages > 1 )
- {
- // Compute the Nodes info
- LevelInfo<K, V> nodeLevel = computeLevel( btree, nbPages, LevelEnum.NODE );
- nodeLevel.setLevelNumber( levelNumber++ );
- levelList.add( nodeLevel );
- nbPages = nodeLevel.getNbPages();
- }
-
- return levelList;
- }
-
-
- /**
- * Inject a tuple into a leaf
- */
- private static <K, V> void injectInLeaf( BTree<K, V> btree, Tuple<K, V> tuple, LevelInfo<K, V> leafLevel )
- {
- Leaf<K, V> leaf = ( Leaf<K, V> ) leafLevel.getCurrentPage();
-
- KeyHolder<K> keyHolder = new KeyHolder<K>( btree.getKeySerializer(), tuple.getKey() );
- leaf.setKey( leafLevel.getCurrentPos(), keyHolder );
-
- leafLevel.incCurrentPos();
- }
-
-
- private static <K, V> int computeNbElemsLeaf( BTree<K, V> btree, LevelInfo<K, V> levelInfo )
- {
- int pageSize = btree.getPageNbElem();
- int remaining = levelInfo.getNbElemsLimit() - levelInfo.getNbAddedElems();
-
- if ( remaining < pageSize )
- {
- return remaining;
- }
- else if ( remaining == pageSize )
- {
- return pageSize;
- }
- else if ( remaining > levelInfo.getNbElemsLimit() - levelInfo.getNbElemsLimit() )
- {
- return pageSize;
- }
- else
- {
- return remaining - pageSize / 2;
- }
- }
-
-
- /**
- * Compute the number of nodes necessary to store all the elements.
- */
- /* No qualifier */int computeNbElemsNode( BTree<K, V> btree, LevelInfo<K, V> levelInfo )
- {
- int pageSize = btree.getPageNbElem();
- int remaining = levelInfo.getNbElemsLimit() - levelInfo.getNbAddedElems();
-
- if ( remaining < pageSize + 1 )
- {
- return remaining;
- }
- else if ( remaining == pageSize + 1 )
- {
- return pageSize + 1;
- }
- else if ( remaining > levelInfo.getNbElemsLimit() - levelInfo.getNbElemsLimit() )
- {
- return pageSize + 1;
- }
- else
- {
- return remaining - pageSize / 2;
- }
- }
-
-
- /**
- * Inject a page reference into the root page.
- */
- private static <K, V> void injectInRoot( BTree<K, V> btree, Page<K, V> page, long child,
- LevelInfo<K, V> level ) throws IOException
- {
- Node<K, V> node = ( Node<K, V> ) level.getCurrentPage();
-
- if ( ( level.getCurrentPos() == 0 ) && ( node.getPage( 0 ) == null ) )
- {
- node.setPageHolder( 0, pageHolder );
- level.incNbAddedElems();
- }
- else
- {
- // Inject the pageHolder and the page leftmost key
- node.setPageHolder( level.getCurrentPos() + 1, pageHolder );
- KeyHolder<K> keyHolder = new KeyHolder<K>( btree.getKeySerializer(), page.getLeftMostKey() );
- node.setKey( level.getCurrentPos(), keyHolder );
- level.incCurrentPos();
- level.incNbAddedElems();
-
- // Check that we haven't added the last element. If so,
- // we have to write the page on disk and update the btree
- if ( level.getNbAddedElems() == level.getNbElems() )
- {
- PageHolder<K, V> rootHolder = ( ( BTree<K, V> ) btree ).getRecordManager().writePage(
- btree, node, 0L );
- ( ( BTree<K, V> ) btree ).setRootPage( rootHolder.getValue() );
- }
- }
-
- return;
- }
-
-
- /**
- * Inject a page reference into a Node. This method will recurse if needed.
- */
- private static <K, V> void injectInNode( BTree<K, V> btree, Page<K, V> page, List<LevelInfo<K, V>> levels,
- int levelIndex )
- throws IOException
- {
- int pageSize = btree.getPageSize();
- LevelInfo<K, V> level = levels.get( levelIndex );
- Node<K, V> node = ( Node<K, V> ) level.getCurrentPage();
-
- // We first have to write the page on disk
- PageHolder<K, V> pageHolder = ( ( BTree<K, V> ) btree ).getRecordManager().writePage( btree, page, 0L );
-
- // First deal with a node that has less than PageSize elements at this level.
- // It will become the root node.
- if ( level.getNbElems() <= pageSize + 1 )
- {
- injectInRoot( btree, page, pageHolder, level );
-
- return;
- }
-
- // Now, we have some parent node. We process the 3 different use case :
- // o Full node before the limit
- // o Node over the limit but with at least N/2 elements
- // o Node over the limit but with elements spread into 2 nodes
- if ( level.getNbAddedElems() < level.getNbElemsLimit() )
- {
- // Ok, we haven't yet reached the incomplete pages (if any).
- // Let's add the page reference into the node
- // There is one special case : when we are adding the very first page
- // reference into a node. In this case, we don't store the key
- if ( ( level.getCurrentPos() == 0 ) && ( node.getKey( 0 ) == null ) )
- {
- node.setPageHolder( 0, pageHolder );
- }
- else
- {
- // Inject the pageHolder and the page leftmost key
- node.setPageHolder( level.getCurrentPos(), pageHolder );
- KeyHolder<K> keyHolder = new KeyHolder<K>( btree.getKeySerializer(), page.getLeftMostKey() );
- node.setKey( level.getCurrentPos() - 1, keyHolder );
- }
-
- // Now, increment this level nb of added elements
- level.incCurrentPos();
- level.incNbAddedElems();
-
- // Check that we haven't added the last element. If so,
- // we have to write the page on disk and update the parent's node
- if ( level.getNbAddedElems() == level.getNbElems() )
- {
- //PageHolder<K, V> rootHolder = ( ( PersistedBTree<K, V> ) btree ).getRecordManager().writePage(
- // btree, node, 0L );
- //( ( PersistedBTree<K, V> ) btree ).setRootPage( rootHolder.getValue() );
- injectInNode( btree, node, levels, levelIndex + 1 );
-
- return;
- }
- else
- {
- // Check that we haven't completed the current node, and that this is not the root node.
- if ( ( level.getCurrentPos() == pageSize + 1 ) && ( level.getLevelNumber() < levels.size() - 1 ) )
- {
- // yes. We have to write the node on disk, update its parent
- // and create a new current node
- injectInNode( btree, node, levels, levelIndex + 1 );
-
- // The page is full, we have to create a new one, with a size depending on the remaining elements
- if ( level.getNbAddedElems() < level.getNbElemsLimit() )
- {
- // We haven't reached the limit, create a new full node
- level.setCurrentPage( BTreeFactory.createNode( btree, 0L, pageSize ) );
- }
- else if ( level.getNbElems() - level.getNbAddedElems() <= pageSize )
- {
- level.setCurrentPage( BTreeFactory.createNode( btree, 0L,
- level.getNbElems() - level.getNbAddedElems() - 1 ) );
- }
- else
- {
- level.setCurrentPage( BTreeFactory.createNode( btree, 0L, ( level.getNbElems() - 1 )
- - ( level.getNbAddedElems() + 1 ) - pageSize / 2 ) );
- }
-
- level.setCurrentPos( 0 );
- }
- }
-
- return;
- }
- else
- {
- // We are dealing with the last page or the last two pages
- // We can have either one single pages which can contain up to pageSize-1 elements
- // or with two pages, the first one containing ( nbElems - limit ) - pageSize/2 elements
- // and the second one will contain pageSize/2 elements.
- if ( level.getNbElems() - level.getNbElemsLimit() > pageSize )
- {
- // As the remaining elements are above a page size, they will be spread across
- // two pages. We have two cases here, depending on the page we are filling
- if ( level.getNbElems() - level.getNbAddedElems() <= pageSize / 2 + 1 )
- {
- // As we have less than PageSize/2 elements to write, we are on the second page
- if ( ( level.getCurrentPos() == 0 ) && ( node.getKey( 0 ) == null ) )
- {
- node.setPageHolder( 0, pageHolder );
- }
- else
- {
- // Inject the pageHolder and the page leftmost key
- node.setPageHolder( level.getCurrentPos(), pageHolder );
- KeyHolder<K> keyHolder = new KeyHolder<K>( btree.getKeySerializer(),
- page.getLeftMostKey() );
- node.setKey( level.getCurrentPos() - 1, keyHolder );
- }
-
- // Now, increment this level nb of added elements
- level.incCurrentPos();
- level.incNbAddedElems();
-
- // Check if we are done with the page
- if ( level.getNbAddedElems() == level.getNbElems() )
- {
- // Yes, we have to update the parent
- injectInNode( btree, node, levels, levelIndex + 1 );
- }
- }
- else
- {
- // This is the first page
- if ( ( level.getCurrentPos() == 0 ) && ( node.getKey( 0 ) == null ) )
- {
- // First element of the page
- node.setPageHolder( 0, pageHolder );
- }
- else
- {
- // Any other following elements
- // Inject the pageHolder and the page leftmost key
- node.setPageHolder( level.getCurrentPos(), pageHolder );
- KeyHolder<K> keyHolder = new KeyHolder<K>( btree.getKeySerializer(),
- page.getLeftMostKey() );
- node.setKey( level.getCurrentPos() - 1, keyHolder );
- }
-
- // Now, increment this level nb of added elements
- level.incCurrentPos();
- level.incNbAddedElems();
-
- // Check if we are done with the page
- if ( level.getCurrentPos() == node.getPageNbElems() + 1 )
- {
- // Yes, we have to update the parent
- injectInNode( btree, node, levels, levelIndex + 1 );
-
- // An create a new one
- level.setCurrentPage( BTreeFactory.createNode( btree, 0L, pageSize / 2 ) );
- level.setCurrentPos( 0 );
- }
- }
- }
- else
- {
- // Two cases : we don't have anything else to write, or this is a single page
- if ( level.getNbAddedElems() == level.getNbElems() )
- {
- // We are done with the page
- injectInNode( btree, node, levels, levelIndex + 1 );
- }
- else
- {
- // We have some more elements to add in the page
- // This is the first page
- if ( ( level.getCurrentPos() == 0 ) && ( node.getKey( 0 ) == null ) )
- {
- // First element of the page
- node.setPageHolder( 0, pageHolder );
- }
- else
- {
- // Any other following elements
- // Inject the pageHolder and the page leftmost key
- node.setPageHolder( level.getCurrentPos(), pageHolder );
- KeyHolder<K> keyHolder = new KeyHolder<K>( btree.getKeySerializer(),
- page.getLeftMostKey() );
- node.setKey( level.getCurrentPos() - 1, keyHolder );
- }
-
- // Now, increment this level nb of added elements
- level.incCurrentPos();
- level.incNbAddedElems();
-
- // Check if we are done with the page
- if ( level.getCurrentPos() == node.getPageNbElems() + 1 )
- {
- // Yes, we have to update the parent
- injectInNode( btree, node, levels, levelIndex + 1 );
-
- // An create a new one
- level.setCurrentPage( BTreeFactory.createNode( btree, 0L, pageSize / 2 ) );
- level.setCurrentPos( 0 );
- }
- }
-
- return;
- }
- }
- }
-
-
- private static <K, V> BTree<K, V> bulkLoadSinglePage( WriteTransaction writeTransaction, BTree<K, V> btree, Iterator<Tuple<K, V>> dataIterator,
- int nbElems ) throws IOException
- {
- // Use the root page
- Page<K, V> rootPage = btree.getRootPage();
-
- // Initialize the root page
- ( ( AbstractPage<K, V> ) rootPage ).setPageNbElems( nbElems );
- KeyHolder<K>[] keys = new KeyHolder[nbElems];
- ValueHolder<V>[] values = new ValueHolder[nbElems];
-
- switch ( btree.getType() )
- {
- default:
- ( ( Leaf<K, V> ) rootPage ).setValues( values );
- }
-
- // We first have to inject data into the page
- int pos = 0;
-
- while ( dataIterator.hasNext() )
- {
- Tuple<K, V> tuple = dataIterator.next();
-
- // Store the current element in the rootPage
- KeyHolder<K> keyHolder = new KeyHolder<K>( btree.getKeySerializer(), tuple.getKey() );
- keys[pos] = keyHolder;
-
- ValueHolder<V>valueHolder = new ValueHolder<V>( btree, ( V )tuple.getValue() );
- ( ( Leaf<K, V> ) rootPage ).values[pos] = valueHolder;
-
- pos++;
- }
-
- // Update the rootPage
- ( ( AbstractPage<K, V> ) rootPage ).setKeys( keys );
-
- // Update the btree with the nb of added elements, and write it$
- BTreeHeader<K, V> btreeHeader = ( ( BTree<K, V> ) btree ).getBtreeHeader();
- btreeHeader.setNbElems( nbElems );
-
- return btree;
- }
-
-
- /**
- * Construct the target BTree from the sorted data. We will use the nb of elements
- * to determinate the structure of the BTree, as it must be balanced
- */
- private static <K, V> BTree<K, V> bulkLoad( WriteTransaction writeTransaction, BTree<K, V> btree, Iterator<Tuple<K, V>> dataIterator, int nbElems )
- throws IOException
- {
- int pageSize = btree.getBtreeInfo().getPageNbElem();
-
- // Special case : we can store all the elements in a single page
- if ( nbElems <= pageSize )
- {
- return bulkLoadSinglePage( writeTransaction, btree, dataIterator, nbElems );
- }
-
- // Ok, we will need more than one page to store the elements, which
- // means we also will need more than one level.
- // First, compute the needed number of levels.
- List<LevelInfo<K, V>> levels = computeLevels( btree, nbElems );
-
- // Now, let's fill the levels
- LevelInfo<K, V> leafLevel = levels.get( 0 );
-
- while ( dataIterator.hasNext() )
- {
- // let's fill page up to the point all the complete pages have been filled
- if ( leafLevel.getNbAddedElems() < leafLevel.getNbElemsLimit() )
- {
- // grab a tuple
- Tuple<K, V> tuple = dataIterator.next();
-
- injectInLeaf( btree, tuple, leafLevel );
- leafLevel.incNbAddedElems();
-
- // The page is completed, update the parent's node and create a new current page
- if ( leafLevel.getCurrentPos() == pageSize )
- {
- injectInNode( btree, leafLevel.getCurrentPage(), levels, 1 );
-
- // The page is full, we have to create a new one
- leafLevel.setCurrentPage( BTreeFactory
- .createLeaf( btree, 0L, computeNbElemsLeaf( btree, leafLevel ) ) );
- leafLevel.setCurrentPos( 0 );
- }
- }
- else
- {
- // We have to deal with uncompleted pages now (if we have any)
- if ( leafLevel.getNbAddedElems() == nbElems )
- {
- // First use case : we have injected all the elements in the btree : get out
- break;
- }
-
- if ( nbElems - leafLevel.getNbElemsLimit() > pageSize )
- {
- // Second use case : the number of elements after the limit does not
- // fit in a page, that means we have to split it into
- // two pages
-
- // First page will contain nbElems - leafLevel.nbElemsLimit - PageSize/2 elements
- int nbToAdd = nbElems - leafLevel.getNbElemsLimit() - pageSize / 2;
-
- while ( nbToAdd > 0 )
- {
- // grab a tuple
- Tuple<K, V> tuple = dataIterator.next();
-
- injectInLeaf( btree, tuple, leafLevel );
- leafLevel.incNbAddedElems();
- nbToAdd--;
- }
-
- // Now inject the page into the node
- Page<K, V> currentPage = leafLevel.getCurrentPage();
- injectInNode( btree, currentPage, levels, 1 );
-
- // Create a new page for the remaining elements
- nbToAdd = pageSize / 2;
- leafLevel.setCurrentPage( BTreeFactory.createLeaf( btree, 0L, nbToAdd ) );
- leafLevel.setCurrentPos( 0 );
-
- while ( nbToAdd > 0 )
- {
- // grab a tuple
- Tuple<K, V> tuple = dataIterator.next();
-
- injectInLeaf( btree, tuple, leafLevel );
- leafLevel.incNbAddedElems();
- nbToAdd--;
- }
-
- // And update the parent node
- Page<K, V> levelCurrentPage = leafLevel.getCurrentPage();
- injectInNode( btree, levelCurrentPage, levels, 1 );
-
- // We are done
- break;
- }
- else
- {
- // Third use case : we can push all the elements in the last page.
- // Let's do it
- int nbToAdd = nbElems - leafLevel.getNbElemsLimit();
-
- while ( nbToAdd > 0 )
- {
- // grab a tuple
- Tuple<K, V> tuple = dataIterator.next();
-
- injectInLeaf( btree, tuple, leafLevel );
- leafLevel.incNbAddedElems();
- nbToAdd--;
- }
-
- // Now inject the page into the node
- injectInNode( btree, leafLevel.getCurrentPage(), levels, 1 );
-
- // and we are done
- break;
- }
- }
- }
-
- // Update the btree with the nb of added elements, and write it$
- BTreeHeader<K, V> btreeHeader = ( ( BTree<K, V> ) btree ).getBtreeHeader();
- btreeHeader.setNbElems( nbElems );
-
- return btree;
- }
-
-
- /**
- * Flush a list of tuples to disk after having sorted them. In the process, we may have to gather the values
- * for the tuples having the same keys.
- * @throws IOException
- */
- private static <K, V> File flushToDisk( int fileNb, List<Tuple<K, V>> tuples, BTree<K, V> btree )
- throws IOException
- {
- // Sort the tuples.
- Tuple<K, V>[] sortedTuples = sort( btree, tuples );
-
- File file = File.createTempFile( "sorted", Integer.toString( fileNb ) );
- file.deleteOnExit();
- FileOutputStream fos = new FileOutputStream( file );
-
- // Flush the tuples on disk
- for ( Tuple<K, V> tuple : sortedTuples )
- {
- // Serialize the key
- byte[] bytesKey = btree.getKeySerializer().serialize( tuple.key );
- fos.write( IntSerializer.serialize( bytesKey.length ) );
- fos.write( bytesKey );
-
- // Serialize the values
- V value = tuple.getValue();
- byte[] bytesValue = btree.getValueSerializer().serialize( value );
-
- // Serialize the value
- fos.write( IntSerializer.serialize( bytesValue.length ) );
- fos.write( bytesValue );
- }
-
- fos.flush();
- fos.close();
-
- return file;
- }
-
-
- /**
- * Sort a list of tuples, eliminating the duplicate keys and storing the values in a set when we
- * have a duplicate key
- */
- private static <K, V> Tuple<K, V>[] sort( BTree<K, V> btree, List<Tuple<K, V>> tuples )
- {
- Comparator<Tuple<K, V>> tupleComparator = new TupleComparator( btree.getKeyComparator(), btree
- .getValueComparator() );
-
- // Sort the list
- Tuple<K, V>[] tuplesArray = ( Tuple<K, V>[] ) tuples.toArray( new Tuple[]
- {} );
-
- // First, eliminate the equals keys. We use a map for that
- Map<K, V> mapTuples = new HashMap<>();
-
- for ( Tuple<K, V> tuple : tuplesArray )
- {
- // Is the key present in the map ?
- V foundSet = mapTuples.get( tuple.key );
-
- if ( foundSet != null )
- {
- // We already have had such a key, add the value to the existing key
- foundSet = tuple.value;
- }
- else
- {
- // No such key present in the map : create a new set to store the values,
- // and add it in the map associated with the new key
- V set = new TreeMap<>( );
- set.add( tuple.value );
- mapTuples.put( tuple.key, set );
- }
- }
-
- // Now, sort the map, by extracting all the key/values from the map
- int size = mapTuples.size();
- Tuple<K, V>[] sortedTuples = new Tuple[size];
- int pos = 0;
-
- // We create an array containing all the elements
- for ( Map.Entry<K, V> entry : mapTuples.entrySet() )
- {
- sortedTuples[pos] = new Tuple<K, V>();
- sortedTuples[pos].key = entry.getKey();
- sortedTuples[pos].value = entry.getValue();
- pos++;
- }
-
- // And we sort the array
- Arrays.sort( sortedTuples, tupleComparator );
-
- return sortedTuples;
- }
-
-
- /**
- * Build an iterator over an array of sorted tuples, in memory
- */
- private static <K, V> Iterator<Tuple<K, V>> createTupleIterator( BTree<K, V> btree, List<Tuple<K, V>> tuples )
- {
- final Tuple<K, V>[] sortedTuples = sort( btree, tuples );
-
- Iterator<Tuple<K, V>> tupleIterator = new Iterator<Tuple<K, V>>()
- {
- private int pos = 0;
-
-
- @Override
- public Tuple<K, V> next()
- {
- // Return the current tuple, if any
- if ( pos < sortedTuples.length )
- {
- Tuple<K, V> tuple = sortedTuples[pos];
- pos++;
-
- return tuple;
- }
-
- return null;
- }
-
-
- @Override
- public boolean hasNext()
- {
- return pos < sortedTuples.length;
- }
-
-
- @Override
- public void remove()
- {
- }
- };
-
- return tupleIterator;
- }
-
-
- private static <K, V> Tuple<K, V> fetchTuple( BTree<K, V> btree, FileInputStream fis )
- {
- try
- {
- if ( fis.available() == 0 )
- {
- return null;
- }
-
- Tuple<K, V> tuple = new Tuple<K, V>();
- tuple.value = new TreeV();
-
- byte[] intBytes = new byte[4];
-
- // Read the key length
- fis.read( intBytes );
- int keyLength = IntSerializer.deserialize( intBytes );
-
- // Read the key
- byte[] keyBytes = new byte[keyLength];
- fis.read( keyBytes );
- K key = btree.getKeySerializer().fromBytes( keyBytes );
- tuple.key = key;
-
- // get the number of values
- fis.read( intBytes );
- int nbValues = IntSerializer.deserialize( intBytes );
-
- // Serialize the values
- for ( int i = 0; i < nbValues; i++ )
- {
- // Read the value length
- fis.read( intBytes );
- int valueLength = IntSerializer.deserialize( intBytes );
-
- // Read the value
- byte[] valueBytes = new byte[valueLength];
- fis.read( valueBytes );
- V value = btree.getValueSerializer().fromBytes( valueBytes );
- tuple.value.add( value );
- }
-
- return tuple;
- }
- catch ( IOException ioe )
- {
- return null;
- }
- }
-
-
- /**
- * Build an iterator over an array of sorted tuples, from files on the disk
- * @throws FileNotFoundException
- */
- private static <K, V> Iterator<Tuple<K, V>> createIterator( final BTree<K, V> btree,
- final FileInputStream[] streams )
- throws FileNotFoundException
- {
- // The number of files we have to read from
- final int nbFiles = streams.length;
-
- // We will read only one element at a time from each file
- final Tuple<K, V>[] readTuples = new Tuple[nbFiles];
- final TreeMap<Tuple<K, Integer>, V> candidates =
- new TreeMap<Tuple<K, Integer>, V>(
- new TupleComparator<K, Integer>( btree.getKeyComparator(), IntComparator.INSTANCE ) );
-
- // Read the tuple from each files
- for ( int i = 0; i < nbFiles; i++ )
- {
- while ( true )
- {
- readTuples[i] = fetchTuple( btree, streams[i] );
-
- if ( readTuples[i] != null )
- {
- Tuple<K, Integer> candidate = new Tuple<K, Integer>( readTuples[i].key, i, btree.getKeySerializer()
- .getComparator() );
-
- if ( !candidates.containsKey( candidate ) )
- {
- candidates.put( candidate, readTuples[i].getValue() );
- break;
- }
- else
- {
- // We have to merge the pulled tuple with the existing one, and read one more tuple
- V oldValues = candidates.get( candidate );
- oldValues.addAll( readTuples[i].getValue() );
- }
- }
- else
- {
- break;
- }
- }
- }
-
- Iterator<Tuple<K, V>> tupleIterator = new Iterator<Tuple<K, V>>()
- {
- @Override
- public Tuple<K, V> next()
- {
- // Get the first candidate
- Tuple<K, Integer> tupleCandidate = candidates.firstKey();
-
- // Remove it from the set
- candidates.remove( tupleCandidate );
-
- // Get the the next tuple from the stream we just got the tuple from
- Tuple<K, V> tuple = readTuples[tupleCandidate.value];
-
- // fetch the next tuple from the file we just read teh candidate from
- while ( true )
- {
- // fetch it from the disk and store it into its reader
- readTuples[tupleCandidate.value] = fetchTuple( btree, streams[tupleCandidate.value] );
-
- if ( readTuples[tupleCandidate.value] == null )
- {
- // No more tuple for this file
- break;
- }
-
- if ( readTuples[tupleCandidate.value] != null )
- {
- // And store it into the candidate set
- V oldValues = candidates.get( readTuples[tupleCandidate.value] );
-
- if ( oldValues != null )
- {
- // We already have another element with the same key, merge them
- oldValues.addAll( readTuples[tupleCandidate.value].value );
- }
- else
- {
- Tuple<K, Integer> newTuple = new Tuple<K, Integer>( readTuples[tupleCandidate.value].key,
- tupleCandidate.value );
- candidates.put( newTuple, readTuples[tupleCandidate.value].getValue() );
-
- // and exit the loop
- break;
- }
- }
- }
-
- // We can now return the found value
- return tuple;
- }
-
-
- @Override
- public boolean hasNext()
- {
- // Check that we have at least one element to read
- return !candidates.isEmpty();
- }
-
-
- @Override
- public void remove()
- {
- }
-
- };
-
- return tupleIterator;
- }
-
-
- /**
- * Build an iterator over an array of sorted tuples, from files on the disk
- * @throws FileNotFoundException
- */
- private static <K, V> Iterator<Tuple<K, V>> createUniqueFileIterator( final BTree<K, V> btree,
- final FileInputStream stream )
- throws FileNotFoundException
- {
- Iterator<Tuple<K, V>> tupleIterator = new Iterator<Tuple<K, V>>()
- {
- boolean hasNext = true;
-
-
- @Override
- public Tuple<K, V> next()
- {
- // Get the tuple from the stream
- Tuple<K, V> tuple = fetchTuple( btree, stream );
-
- // We can now return the found value
- return tuple;
- }
-
-
- @Override
- public boolean hasNext()
- {
- // Check that we have at least one element to read
- try
- {
- return stream.available() > 0;
- }
- catch ( IOException e )
- {
- return false;
- }
- }
-
-
- @Override
- public void remove()
- {
- }
-
- };
-
- return tupleIterator;
- }
-
-
- /**
- * Compact a given persisted BTree, making it dense. All the values will be stored
- * in newly created pages, each one of them containing as much elements
- * as it's size.
- * </br>
- * The RecordManager will be stopped and restarted, do not use this method
- * on a running BTree.
- *
- * @param recordManager The associated recordManager
- * @param btree The BTree to compact
- */
- public static void compact( RecordManager recordManager, BTree<?, ?> btree )
- {
-
- }
-
-
- /**
- * Compact a given in-memory BTree, making it dense. All the values will be stored
- * in newly created pages, each one of them containing as much elements
- * as it's size.
- * </br>
- *
- * @param btree The BTree to compact
- * @throws KeyNotFoundException
- * @throws IOException
- */
- public static BTree<?, ?> compact( BTree<?, ?> btree ) throws IOException, KeyNotFoundException
- {
- // First, create a new BTree which will contain all the elements
- InMemoryBTreeConfiguration configuration = new InMemoryBTreeConfiguration();
- configuration.setName( btree.getName() );
- configuration.setPageSize( btree.getPageSize() );
- configuration.setKeySerializer( btree.getKeySerializer() );
- configuration.setValueSerializer( btree.getValueSerializer() );
- configuration.setAllowDuplicates( btree.isAllowDuplicates() );
- configuration.setReadTimeOut( btree.getReadTimeOut() );
- configuration.setWriteBufferSize( btree.getWriteBufferSize() );
-
- File file = ( ( InMemoryBTree ) btree ).getFile();
-
- if ( file != null )
- {
- configuration.setFilePath( file.getPath() );
- }
-
- // Create a new Btree Builder
- InMemoryBTreeBuilder btreeBuilder = new InMemoryBTreeBuilder( configuration );
-
- // Create a cursor over the existing btree
- final TupleCursor cursor = btree.browse();
-
- // Create an iterator that will iterate the existing btree
- Iterator<Tuple> tupleItr = new Iterator<Tuple>()
- {
- @Override
- public Tuple next()
- {
- try
- {
- return cursor.next();
- }
- catch ( EndOfFileExceededException e )
- {
- return null;
- }
- catch ( IOException e )
- {
- return null;
- }
- }
-
-
- @Override
- public boolean hasNext()
- {
- try
- {
- return cursor.hasNext();
- }
- catch ( EndOfFileExceededException e )
- {
- return false;
- }
- catch ( IOException e )
- {
- return false;
- }
- }
-
-
- @Override
- public void remove()
- {
- }
- };
-
- // And finally, compact the btree
- return btreeBuilder.build( tupleItr );
- }
-}
diff --git a/mavibot/src/test/java/org/apache/directory/mavibot/btree/BulkLoaderTest.java b/mavibot/src/test/java/org/apache/directory/mavibot/btree/BulkLoaderTest.java
deleted file mode 100644
index f2078ef..0000000
--- a/mavibot/src/test/java/org/apache/directory/mavibot/btree/BulkLoaderTest.java
+++ /dev/null
@@ -1,996 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- *
- */
-
-package org.apache.directory.mavibot.btree;
-
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertNotNull;
-import static org.junit.Assert.assertTrue;
-
-import java.io.File;
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Random;
-import java.util.Set;
-import java.util.TreeSet;
-
-import org.apache.directory.mavibot.btree.BulkLoader.LevelEnum;
-import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
-import org.apache.directory.mavibot.btree.exception.CursorException;
-import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
-import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
-import org.apache.directory.mavibot.btree.serializer.LongSerializer;
-import org.apache.directory.mavibot.btree.serializer.StringSerializer;
-import org.junit.Ignore;
-import org.junit.Test;
-
-
-/**
- * Test the BulkLoader class.
- *
- * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
- */
-public class BulkLoaderTest
-{
- private void checkBtree( BTree<Long, String> oldBtree, BTree<Long, String> newBtree )
- throws EndOfFileExceededException, IOException, KeyNotFoundException, CursorException
- {
- assertEquals( oldBtree.getNbElems(), newBtree.getNbElems() );
-
- try ( Transaction transaction = oldBtree.getRecordManager().beginReadTransaction() )
- {
- TupleCursor<Long, String> cursorOld = oldBtree.browse( transaction );
- TupleCursor<Long, String> cursorNew = newBtree.browse( transaction );
-
- while ( cursorOld.hasNext() && cursorNew.hasNext() )
- {
- Tuple<Long, String> tupleOld = cursorOld.next();
- Tuple<Long, String> tupleNew = cursorNew.next();
-
- assertEquals( tupleOld.getKey(), tupleNew.getKey() );
- assertEquals( tupleOld.getValue(), tupleNew.getValue() );
- }
-
- assertEquals( cursorOld.hasNext(), cursorNew.hasNext() );
- }
- }
-
-
- /**
- * Test that we can load 100 BTrees with 0 to 1000 elements
- * @throws BTreeAlreadyManagedException
- */
- @Test
- public void testBulkLoad1000Elements() throws IOException, KeyNotFoundException,
- BTreeAlreadyManagedException, CursorException
- {
- for ( int i = 0; i < 1000001; i++ )
- {
- Random random = new Random( System.currentTimeMillis() );
- File file = File.createTempFile( "managedbtreebuilder", ".data" );
- file.deleteOnExit();
-
- try
- {
- RecordManager rm = new RecordManager( file.getAbsolutePath() );
-
- try ( WriteTransaction writeTransaction = rm.beginWriteTransaction() )
- {
- BTree<Long, String> btree = ( BTree<Long, String> ) rm.addBTree( writeTransaction, "test",
- LongSerializer.INSTANCE, StringSerializer.INSTANCE );
- btree.setPageNbElem( 64 );
-
- int nbElems = i;
- int addedElems = 0;
-
- final Tuple<Long, String>[] elems = new Tuple[nbElems];
- Map<Long, Tuple<Long, Set<String>>> expected = new HashMap<>();
-
- long t00 = System.currentTimeMillis();
-
- while ( addedElems < nbElems )
- {
- long key = random.nextLong() % 3333333L;
-
- if ( expected.containsKey( key ) )
- {
- continue;
- }
-
- long w = random.nextLong() % 3333333L;
- String value = "V" + w;
- elems[addedElems] = new Tuple<Long, String>( key, value );
-
- Tuple<Long, Set<String>> expectedTuple = expected.get( key );
-
- if ( expectedTuple == null )
- {
- expectedTuple = new Tuple<Long, Set<String>>( key, new TreeSet<String>() );
- }
-
- expectedTuple.value.add( value );
- expected.put( key, expectedTuple );
- addedElems++;
- }
-
- long t01 = System.currentTimeMillis();
-
- // System.out.println( "Time to create the " + nbElems + " elements " + ( ( t01 - t00 ) / 1 ) );
-
- Iterator<Tuple<Long, String>> tupleIterator = new Iterator<Tuple<Long, String>>()
- {
- private int pos = 0;
-
-
- @Override
- public Tuple<Long, String> next()
- {
- return elems[pos++];
- }
-
-
- @Override
- public boolean hasNext()
- {
- return pos < elems.length;
- }
-
-
- @Override
- public void remove()
- {
- }
- };
-
- long t0 = System.currentTimeMillis();
- BTree<Long, String> result = BulkLoader.load( btree, tupleIterator, 1024000 );
- long t1 = System.currentTimeMillis();
-
- if ( ( i % 100 ) == 0 )
- {
- System.out.println( "== Btree #" + i + ", Time to bulkoad the " + nbElems + " elements "
- + ( t1 - t0 ) + "ms" );
- }
-
- TupleCursor<Long, String> cursor = result.browse( writeTransaction );
- int nbFetched = 0;
-
- long t2 = System.currentTimeMillis();
-
- while ( cursor.hasNext() )
- {
- Tuple<Long, String> elem = cursor.next();
-
- assertTrue( expected.containsKey( elem.key ) );
- Tuple<Long, Set<String>> tuple = expected.get( elem.key );
- assertNotNull( tuple );
- nbFetched++;
- }
-
- long t3 = System.currentTimeMillis();
-
- //System.out.println( "Time to read the " + nbElems + " elements " + ( t3 - t2 ) );
- assertEquals( nbElems, nbFetched );
-
- checkBtree( btree, result );
- }
- }
- finally
- {
- file.delete();
- }
- }
- }
-
-
- /**
- * test the computeLeafLevel method
- */
- @Test
- public void testPersistedBulkLoadComputeLeafLevel() throws IOException, KeyNotFoundException,
- BTreeAlreadyManagedException
- {
- Random random = new Random( System.currentTimeMillis() );
- File file = File.createTempFile( "managedbtreebuilder", ".data" );
- file.deleteOnExit();
-
- try
- {
- RecordManager rm = new RecordManager( file.getAbsolutePath() );
- BTree<Long, String> btree = ( BTree<Long, String> ) rm.addBTree( "test",
- LongSerializer.INSTANCE, StringSerializer.INSTANCE );
-
- int[] expectedNbPages = new int[]
- {
- 0,
- 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
- };
-
- int[] expectedLimit = new int[]
- {
- 0,
- 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
- 0, 0, 0, 0, 0, 0, 0, 16, 16, 16, 16, 16, 16, 16, 16, 32,
- 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 48
- };
-
- int[] expectedKeys = new int[]
- {
- 0,
- 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
- 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16,
- 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16
- };
-
- for ( int i = 0; i < 49; i++ )
- {
- LevelInfo<Long, String> leafInfo = BulkLoader.computeLevel( btree, i, LevelEnum.LEAF );
-
- assertEquals( expectedNbPages[i], leafInfo.getNbPages() );
- assertEquals( expectedLimit[i], leafInfo.getNbElemsLimit() );
- assertEquals( expectedKeys[i], leafInfo.getCurrentPage().getNbElems() );
- }
- }
- finally
- {
- file.delete();
- }
- }
-
-
- /**
- * test the computeNodeLevel method
- */
- @Test
- public void testPersistedBulkLoadComputeNodeLevel() throws IOException, KeyNotFoundException,
- BTreeAlreadyManagedException
- {
- Random random = new Random( System.currentTimeMillis() );
- File file = File.createTempFile( "managedbtreebuilder", ".data" );
- file.deleteOnExit();
-
- try
- {
- RecordManager rm = new RecordManager( file.getAbsolutePath() );
- BTree<Long, String> btree = ( BTree<Long, String> ) rm.addBTree( "test",
- LongSerializer.INSTANCE, StringSerializer.INSTANCE );
-
- int[] expectedNbPages = new int[]
- {
- -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
- };
-
- int[] expectedLimit = new int[]
- {
- -1,
- -1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
- 0, 0, 0, 0, 0, 0, 0, 0, 17, 17, 17, 17, 17, 17, 17, 17, 34,
- 17, 17, 17, 17, 17, 17, 17, 17, 34, 34, 34, 34, 34, 34, 34, 34, 51
- };
-
- int[] expectedKeys = new int[]
- {
- -1, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
- 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16,
- 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16
- };
-
- for ( int i = 2; i < 52; i++ )
- {
- LevelInfo<Long, String> nodeInfo = BulkLoader.computeLevel( btree, i, LevelEnum.NODE );
-
- assertEquals( expectedNbPages[i], nodeInfo.getNbPages() );
- assertEquals( expectedLimit[i], nodeInfo.getNbElemsLimit() );
- assertEquals( expectedKeys[i], nodeInfo.getCurrentPage().getNbElems() );
- }
- }
- finally
- {
- file.delete();
- }
- }
-
-
- /**
- * test the computeNodeLevel method
- */
- @Test
- public void testPersistedBulkLoadComputeLevels() throws IOException, KeyNotFoundException,
- BTreeAlreadyManagedException
- {
- Random random = new Random( System.currentTimeMillis() );
- File file = File.createTempFile( "managedbtreebuilder", ".data" );
- file.deleteOnExit();
-
- try
- {
- RecordManager rm = new RecordManager( file.getAbsolutePath() );
- BTree<Long, String> btree = ( BTree<Long, String> ) rm.addBTree( "test",
- LongSerializer.INSTANCE, StringSerializer.INSTANCE );
-
- int[] expectedNbPages = new int[]
- {
- -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
- };
-
- int[] expectedLimit = new int[]
- {
- -1,
- -1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
- 0, 0, 0, 0, 0, 0, 0, 0, 17, 17, 17, 17, 17, 17, 17, 17, 34,
- 17, 17, 17, 17, 17, 17, 17, 17, 34, 34, 34, 34, 34, 34, 34, 34, 51
- };
-
- int[] expectedKeys = new int[]
- {
- -1, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
- 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16,
- 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16
- };
-
- for ( int i = 2599; i <= 2599; i++ )
- {
- List<LevelInfo<Long, String>> levels = BulkLoader.computeLevels( btree, i );
- }
- }
- finally
- {
- file.delete();
- }
- }
-
-
- /**
- * 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")
- @Test
- public void testPersistedBulkLoad1000ElementsMultipleValues() throws IOException, KeyNotFoundException,
- BTreeAlreadyManagedException, CursorException
- {
- for ( int i = 1; i < 1001; i++ )
- {
- Random random = new Random( System.currentTimeMillis() );
- File file = File.createTempFile( "managedbtreebuilder", ".data" );
- file.deleteOnExit();
-
- try
- {
- RecordManager rm = new RecordManager( file.getAbsolutePath() );
- BTree<Long, String> btree = ( BTree<Long, String> ) rm.addBTree( "test",
- LongSerializer.INSTANCE, StringSerializer.INSTANCE );
-
- int nbElems = i;
- int addedElems = 0;
-
- final Tuple<Long, String>[] elems = new Tuple[nbElems];
- Map<Long, Tuple<Long, Set<String>>> expected = new HashMap<Long, Tuple<Long, Set<String>>>();
- long valueNumber = 0;
-
- long t00 = System.currentTimeMillis();
-
- while ( addedElems < nbElems )
- {
- long key = random.nextLong() % 33L;
- String value = "V" + valueNumber++;
-
- elems[addedElems] = new Tuple<Long, String>( key, value );
-
- Tuple<Long, Set<String>> expectedTuple = expected.get( key );
-
- if ( expectedTuple == null )
- {
- expectedTuple = new Tuple<Long, Set<String>>( key, new TreeSet<String>() );
- }
-
- 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 ) );
-
- Iterator<Tuple<Long, String>> tupleIterator = new Iterator<Tuple<Long, String>>()
- {
- private int pos = 0;
-
-
- @Override
- public Tuple<Long, String> next()
- {
- return elems[pos++];
- }
-
-
- @Override
- public boolean hasNext()
- {
- return pos < elems.length;
- }
-
-
- @Override
- public void remove()
- {
- }
- };
-
- long t0 = System.currentTimeMillis();
- BTree<Long, String> result = BulkLoader.load( btree, tupleIterator, 128 );
- long t1 = System.currentTimeMillis();
-
- //System.out.println( "== Btree #" + i + ", Time to bulkoad the " + nbElems + " elements "
- // + ( t1 - t0 ) + "ms" );
-
- TupleCursor<Long, String> cursor = result.browse();
- int nbFetched = 0;
-
- long t2 = System.currentTimeMillis();
-
- try
- {
- while ( cursor.hasNext() )
- {
- Tuple<Long, String> elem = cursor.next();
-
- assertTrue( expected.containsKey( elem.key ) );
- Tuple<Long, Set<String>> tuple = expected.get( elem.key );
- assertNotNull( tuple );
- nbFetched++;
- }
- }
- catch ( Exception e )
- {
- for ( Tuple<Long, String> tuple : elems )
- {
- System.out
- .println( "listTuples.add( new Tuple<Long, String>( " + tuple.getKey() + "L, \""
- + tuple.getValue() + "\" ) );" );
- }
-
- e.printStackTrace();
- break;
- }
-
- long t3 = System.currentTimeMillis();
-
- //System.out.println( "Time to read the " + nbElems + " elements " + ( t3 - t2 ) );
- assertEquals( nbElems, nbFetched );
-
- checkBtree( btree, result );
- }
- finally
- {
- file.delete();
- }
- }
- }
-
-
- /**
- * Test that we can load 100 BTrees with 0 to 1000 elements, each one of them having multiple values
- * @throws BTreeAlreadyManagedException
- */
- @Test
- public void testPersistedBulkLoad1000ElementsMultipleValuesDebug() throws IOException, KeyNotFoundException,
- BTreeAlreadyManagedException, CursorException
- {
- Random random = new Random( System.currentTimeMillis() );
- File file = File.createTempFile( "managedbtreebuilder", ".data" );
- file.deleteOnExit();
-
- try
- {
- RecordManager rm = new RecordManager( file.getAbsolutePath() );
- BTree<Long, String> btree = ( BTree<Long, String> ) rm.addBTree( "test",
- LongSerializer.INSTANCE, StringSerializer.INSTANCE );
-
- int nbElems = 4;
- int addedElems = 0;
-
- final Tuple<Long, String>[] elems = new Tuple[nbElems];
- Map<Long, Tuple<Long, Set<String>>> expected = new HashMap<Long, Tuple<Long, Set<String>>>();
- long valueNumber = 0;
-
- elems[0] = new Tuple<Long, String>( 26L, "V0" );
- elems[1] = new Tuple<Long, String>( 26L, "V1" );
- elems[2] = new Tuple<Long, String>( -22L, "V2" );
- elems[3] = new Tuple<Long, String>( 5L, "V3" );
-
- Iterator<Tuple<Long, String>> tupleIterator = new Iterator<Tuple<Long, String>>()
- {
- private int pos = 0;
-
-
- @Override
- public Tuple<Long, String> next()
- {
- return elems[pos++];
- }
-
-
- @Override
- public boolean hasNext()
- {
- return pos < elems.length;
- }
-
-
- @Override
- public void remove()
- {
- }
- };
-
- long t0 = System.currentTimeMillis();
- BTree<Long, String> result = null;
-
- result = BulkLoader.load( btree, tupleIterator, 128 );
- long t1 = System.currentTimeMillis();
-
- TupleCursor<Long, String> cursor = result.browse();
- int nbFetched = 0;
-
- long t2 = System.currentTimeMillis();
-
- while ( cursor.hasNext() )
- {
- Tuple<Long, String> elem = cursor.next();
- nbFetched++;
- }
-
- long t3 = System.currentTimeMillis();
-
- //System.out.println( "Time to read the " + nbElems + " elements " + ( t3 - t2 ) );
- assertEquals( nbElems, nbFetched );
-
- checkBtree( btree, result );
- }
- finally
- {
- file.delete();
- }
- }
-
-
- @Test
- public void testDebug() throws IOException
- {
- final List<Tuple<Long, String>> listTuples = new ArrayList<Tuple<Long, String>>();
-
- listTuples.add( new Tuple<Long, String>( 0L, "V0" ) );
- listTuples.add( new Tuple<Long, String>( -14L, "V1" ) );
- listTuples.add( new Tuple<Long, String>( 7L, "V2" ) );
- listTuples.add( new Tuple<Long, String>( 6L, "V3" ) );
- listTuples.add( new Tuple<Long, String>( -12L, "V4" ) );
- listTuples.add( new Tuple<Long, String>( 17L, "V5" ) );
- listTuples.add( new Tuple<Long, String>( -18L, "V6" ) );
- listTuples.add( new Tuple<Long, String>( 7L, "V7" ) );
- listTuples.add( new Tuple<Long, String>( 32L, "V8" ) );
- listTuples.add( new Tuple<Long, String>( -21L, "V9" ) );
- listTuples.add( new Tuple<Long, String>( 9L, "V10" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V11" ) );
- listTuples.add( new Tuple<Long, String>( -7L, "V12" ) );
- listTuples.add( new Tuple<Long, String>( -13L, "V13" ) );
- listTuples.add( new Tuple<Long, String>( 23L, "V14" ) );
- listTuples.add( new Tuple<Long, String>( -1L, "V15" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V16" ) );
- listTuples.add( new Tuple<Long, String>( -13L, "V17" ) );
- listTuples.add( new Tuple<Long, String>( 9L, "V18" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V19" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V20" ) );
- listTuples.add( new Tuple<Long, String>( 7L, "V21" ) );
- listTuples.add( new Tuple<Long, String>( 28L, "V22" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V23" ) );
- listTuples.add( new Tuple<Long, String>( 3L, "V24" ) );
- listTuples.add( new Tuple<Long, String>( -31L, "V25" ) );
- listTuples.add( new Tuple<Long, String>( -14L, "V26" ) );
- listTuples.add( new Tuple<Long, String>( -1L, "V27" ) );
- listTuples.add( new Tuple<Long, String>( 5L, "V28" ) );
- listTuples.add( new Tuple<Long, String>( 29L, "V29" ) );
- listTuples.add( new Tuple<Long, String>( -24L, "V30" ) );
- listTuples.add( new Tuple<Long, String>( 8L, "V31" ) );
- listTuples.add( new Tuple<Long, String>( -1L, "V32" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V33" ) );
- listTuples.add( new Tuple<Long, String>( -24L, "V34" ) );
- listTuples.add( new Tuple<Long, String>( -7L, "V35" ) );
- listTuples.add( new Tuple<Long, String>( -3L, "V36" ) );
- listTuples.add( new Tuple<Long, String>( -7L, "V37" ) );
- listTuples.add( new Tuple<Long, String>( -9L, "V38" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V39" ) );
- listTuples.add( new Tuple<Long, String>( -27L, "V40" ) );
- listTuples.add( new Tuple<Long, String>( 19L, "V41" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V42" ) );
- listTuples.add( new Tuple<Long, String>( -14L, "V43" ) );
- listTuples.add( new Tuple<Long, String>( -4L, "V44" ) );
- listTuples.add( new Tuple<Long, String>( -2L, "V45" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V46" ) );
- listTuples.add( new Tuple<Long, String>( -21L, "V47" ) );
- listTuples.add( new Tuple<Long, String>( 17L, "V48" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V49" ) );
- listTuples.add( new Tuple<Long, String>( -11L, "V50" ) );
- listTuples.add( new Tuple<Long, String>( -23L, "V51" ) );
- listTuples.add( new Tuple<Long, String>( 3L, "V52" ) );
- listTuples.add( new Tuple<Long, String>( 4L, "V53" ) );
- listTuples.add( new Tuple<Long, String>( -28L, "V54" ) );
- listTuples.add( new Tuple<Long, String>( 24L, "V55" ) );
- listTuples.add( new Tuple<Long, String>( 12L, "V56" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V57" ) );
- listTuples.add( new Tuple<Long, String>( -2L, "V58" ) );
- listTuples.add( new Tuple<Long, String>( -3L, "V59" ) );
- listTuples.add( new Tuple<Long, String>( 14L, "V60" ) );
- listTuples.add( new Tuple<Long, String>( -6L, "V61" ) );
- listTuples.add( new Tuple<Long, String>( -9L, "V62" ) );
- listTuples.add( new Tuple<Long, String>( 16L, "V63" ) );
- listTuples.add( new Tuple<Long, String>( -15L, "V64" ) );
- listTuples.add( new Tuple<Long, String>( -25L, "V65" ) );
- listTuples.add( new Tuple<Long, String>( 17L, "V66" ) );
- listTuples.add( new Tuple<Long, String>( -12L, "V67" ) );
- listTuples.add( new Tuple<Long, String>( -13L, "V68" ) );
- listTuples.add( new Tuple<Long, String>( -21L, "V69" ) );
- listTuples.add( new Tuple<Long, String>( -27L, "V70" ) );
- listTuples.add( new Tuple<Long, String>( -8L, "V71" ) );
- listTuples.add( new Tuple<Long, String>( -14L, "V72" ) );
- listTuples.add( new Tuple<Long, String>( -24L, "V73" ) );
- listTuples.add( new Tuple<Long, String>( 12L, "V74" ) );
- listTuples.add( new Tuple<Long, String>( 1L, "V75" ) );
- listTuples.add( new Tuple<Long, String>( -6L, "V76" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V77" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V78" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V79" ) );
- listTuples.add( new Tuple<Long, String>( 12L, "V80" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V81" ) );
- listTuples.add( new Tuple<Long, String>( 10L, "V82" ) );
- listTuples.add( new Tuple<Long, String>( 28L, "V83" ) );
- listTuples.add( new Tuple<Long, String>( 23L, "V84" ) );
- listTuples.add( new Tuple<Long, String>( -20L, "V85" ) );
- listTuples.add( new Tuple<Long, String>( 22L, "V86" ) );
- listTuples.add( new Tuple<Long, String>( -2L, "V87" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V88" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V89" ) );
- listTuples.add( new Tuple<Long, String>( -7L, "V90" ) );
- listTuples.add( new Tuple<Long, String>( 20L, "V91" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V92" ) );
- listTuples.add( new Tuple<Long, String>( 12L, "V93" ) );
- listTuples.add( new Tuple<Long, String>( 24L, "V94" ) );
- listTuples.add( new Tuple<Long, String>( 5L, "V95" ) );
- listTuples.add( new Tuple<Long, String>( 1L, "V96" ) );
- listTuples.add( new Tuple<Long, String>( 11L, "V97" ) );
- listTuples.add( new Tuple<Long, String>( 3L, "V98" ) );
- listTuples.add( new Tuple<Long, String>( -4L, "V99" ) );
- listTuples.add( new Tuple<Long, String>( 6L, "V100" ) );
- listTuples.add( new Tuple<Long, String>( 27L, "V101" ) );
- listTuples.add( new Tuple<Long, String>( -23L, "V102" ) );
- listTuples.add( new Tuple<Long, String>( 18L, "V103" ) );
- listTuples.add( new Tuple<Long, String>( 30L, "V104" ) );
- listTuples.add( new Tuple<Long, String>( -29L, "V105" ) );
- listTuples.add( new Tuple<Long, String>( 13L, "V106" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V107" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V108" ) );
- listTuples.add( new Tuple<Long, String>( 1L, "V109" ) );
- listTuples.add( new Tuple<Long, String>( 10L, "V110" ) );
- listTuples.add( new Tuple<Long, String>( -11L, "V111" ) );
- listTuples.add( new Tuple<Long, String>( 29L, "V112" ) );
- listTuples.add( new Tuple<Long, String>( -21L, "V113" ) );
- listTuples.add( new Tuple<Long, String>( -30L, "V114" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V115" ) );
- listTuples.add( new Tuple<Long, String>( 9L, "V116" ) );
- listTuples.add( new Tuple<Long, String>( 5L, "V117" ) );
- listTuples.add( new Tuple<Long, String>( 12L, "V118" ) );
- listTuples.add( new Tuple<Long, String>( -32L, "V119" ) );
- listTuples.add( new Tuple<Long, String>( -1L, "V120" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V121" ) );
- listTuples.add( new Tuple<Long, String>( -22L, "V122" ) );
- listTuples.add( new Tuple<Long, String>( -32L, "V123" ) );
- listTuples.add( new Tuple<Long, String>( -23L, "V124" ) );
- listTuples.add( new Tuple<Long, String>( -25L, "V125" ) );
- listTuples.add( new Tuple<Long, String>( -24L, "V126" ) );
- listTuples.add( new Tuple<Long, String>( 9L, "V127" ) );
- listTuples.add( new Tuple<Long, String>( -27L, "V128" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V129" ) );
- listTuples.add( new Tuple<Long, String>( 12L, "V130" ) );
- listTuples.add( new Tuple<Long, String>( -17L, "V131" ) );
- listTuples.add( new Tuple<Long, String>( -6L, "V132" ) );
- listTuples.add( new Tuple<Long, String>( 14L, "V133" ) );
- listTuples.add( new Tuple<Long, String>( -16L, "V134" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V135" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V136" ) );
- listTuples.add( new Tuple<Long, String>( 20L, "V137" ) );
- listTuples.add( new Tuple<Long, String>( -2L, "V138" ) );
- listTuples.add( new Tuple<Long, String>( 14L, "V139" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V140" ) );
- listTuples.add( new Tuple<Long, String>( 13L, "V141" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V142" ) );
- listTuples.add( new Tuple<Long, String>( -29L, "V143" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V144" ) );
- listTuples.add( new Tuple<Long, String>( 6L, "V145" ) );
- listTuples.add( new Tuple<Long, String>( -22L, "V146" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V147" ) );
- listTuples.add( new Tuple<Long, String>( -4L, "V148" ) );
- listTuples.add( new Tuple<Long, String>( 27L, "V149" ) );
- listTuples.add( new Tuple<Long, String>( 31L, "V150" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V151" ) );
- listTuples.add( new Tuple<Long, String>( 30L, "V152" ) );
- listTuples.add( new Tuple<Long, String>( -31L, "V153" ) );
- listTuples.add( new Tuple<Long, String>( -6L, "V154" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V155" ) );
- listTuples.add( new Tuple<Long, String>( -22L, "V156" ) );
- listTuples.add( new Tuple<Long, String>( 15L, "V157" ) );
- listTuples.add( new Tuple<Long, String>( 25L, "V158" ) );
- listTuples.add( new Tuple<Long, String>( -26L, "V159" ) );
- listTuples.add( new Tuple<Long, String>( 22L, "V160" ) );
- listTuples.add( new Tuple<Long, String>( 32L, "V161" ) );
- listTuples.add( new Tuple<Long, String>( 16L, "V162" ) );
- listTuples.add( new Tuple<Long, String>( -27L, "V163" ) );
- listTuples.add( new Tuple<Long, String>( 11L, "V164" ) );
- listTuples.add( new Tuple<Long, String>( -9L, "V165" ) );
- listTuples.add( new Tuple<Long, String>( -11L, "V166" ) );
- listTuples.add( new Tuple<Long, String>( -14L, "V167" ) );
- listTuples.add( new Tuple<Long, String>( 19L, "V168" ) );
- listTuples.add( new Tuple<Long, String>( -21L, "V169" ) );
- listTuples.add( new Tuple<Long, String>( -21L, "V170" ) );
- listTuples.add( new Tuple<Long, String>( 10L, "V171" ) );
- listTuples.add( new Tuple<Long, String>( 17L, "V172" ) );
- listTuples.add( new Tuple<Long, String>( 30L, "V173" ) );
- listTuples.add( new Tuple<Long, String>( -12L, "V174" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V175" ) );
- listTuples.add( new Tuple<Long, String>( 14L, "V176" ) );
- listTuples.add( new Tuple<Long, String>( 9L, "V177" ) );
- listTuples.add( new Tuple<Long, String>( -14L, "V178" ) );
- listTuples.add( new Tuple<Long, String>( 5L, "V179" ) );
- listTuples.add( new Tuple<Long, String>( 8L, "V180" ) );
- listTuples.add( new Tuple<Long, String>( -32L, "V181" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V182" ) );
- listTuples.add( new Tuple<Long, String>( -17L, "V183" ) );
- listTuples.add( new Tuple<Long, String>( -26L, "V184" ) );
- listTuples.add( new Tuple<Long, String>( -26L, "V185" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V186" ) );
- listTuples.add( new Tuple<Long, String>( -12L, "V187" ) );
- listTuples.add( new Tuple<Long, String>( 7L, "V188" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V189" ) );
- listTuples.add( new Tuple<Long, String>( 16L, "V190" ) );
- listTuples.add( new Tuple<Long, String>( -26L, "V191" ) );
- listTuples.add( new Tuple<Long, String>( -26L, "V192" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V193" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V194" ) );
- listTuples.add( new Tuple<Long, String>( -24L, "V195" ) );
- listTuples.add( new Tuple<Long, String>( 32L, "V196" ) );
- listTuples.add( new Tuple<Long, String>( 9L, "V197" ) );
- listTuples.add( new Tuple<Long, String>( 13L, "V198" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V199" ) );
- listTuples.add( new Tuple<Long, String>( 32L, "V200" ) );
- listTuples.add( new Tuple<Long, String>( -29L, "V201" ) );
- listTuples.add( new Tuple<Long, String>( -16L, "V202" ) );
- listTuples.add( new Tuple<Long, String>( 9L, "V203" ) );
- listTuples.add( new Tuple<Long, String>( 25L, "V204" ) );
- listTuples.add( new Tuple<Long, String>( 18L, "V205" ) );
- listTuples.add( new Tuple<Long, String>( 4L, "V206" ) );
- listTuples.add( new Tuple<Long, String>( -4L, "V207" ) );
- listTuples.add( new Tuple<Long, String>( 4L, "V208" ) );
- listTuples.add( new Tuple<Long, String>( 23L, "V209" ) );
- listTuples.add( new Tuple<Long, String>( 31L, "V210" ) );
- listTuples.add( new Tuple<Long, String>( 17L, "V211" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V212" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V213" ) );
- listTuples.add( new Tuple<Long, String>( 18L, "V214" ) );
- listTuples.add( new Tuple<Long, String>( 8L, "V215" ) );
- listTuples.add( new Tuple<Long, String>( -5L, "V216" ) );
- listTuples.add( new Tuple<Long, String>( 13L, "V217" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V218" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V219" ) );
- listTuples.add( new Tuple<Long, String>( 22L, "V220" ) );
- listTuples.add( new Tuple<Long, String>( -2L, "V221" ) );
- listTuples.add( new Tuple<Long, String>( -3L, "V222" ) );
- listTuples.add( new Tuple<Long, String>( -9L, "V223" ) );
- listTuples.add( new Tuple<Long, String>( -4L, "V224" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V225" ) );
- listTuples.add( new Tuple<Long, String>( 18L, "V226" ) );
- listTuples.add( new Tuple<Long, String>( -8L, "V227" ) );
- listTuples.add( new Tuple<Long, String>( 1L, "V228" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V229" ) );
- listTuples.add( new Tuple<Long, String>( 25L, "V230" ) );
- listTuples.add( new Tuple<Long, String>( 22L, "V231" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V232" ) );
- listTuples.add( new Tuple<Long, String>( -27L, "V233" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V234" ) );
- listTuples.add( new Tuple<Long, String>( -27L, "V235" ) );
- listTuples.add( new Tuple<Long, String>( 17L, "V236" ) );
- listTuples.add( new Tuple<Long, String>( -15L, "V237" ) );
- listTuples.add( new Tuple<Long, String>( 3L, "V238" ) );
- listTuples.add( new Tuple<Long, String>( -1L, "V239" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V240" ) );
- listTuples.add( new Tuple<Long, String>( -17L, "V241" ) );
- listTuples.add( new Tuple<Long, String>( -18L, "V242" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V243" ) );
- listTuples.add( new Tuple<Long, String>( 7L, "V244" ) );
- listTuples.add( new Tuple<Long, String>( 18L, "V245" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V246" ) );
- listTuples.add( new Tuple<Long, String>( -31L, "V247" ) );
- listTuples.add( new Tuple<Long, String>( 18L, "V248" ) );
- listTuples.add( new Tuple<Long, String>( -28L, "V249" ) );
- listTuples.add( new Tuple<Long, String>( 7L, "V250" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V251" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V252" ) );
- listTuples.add( new Tuple<Long, String>( -15L, "V253" ) );
- listTuples.add( new Tuple<Long, String>( -4L, "V254" ) );
- listTuples.add( new Tuple<Long, String>( 11L, "V255" ) );
- listTuples.add( new Tuple<Long, String>( 30L, "V256" ) );
- listTuples.add( new Tuple<Long, String>( -27L, "V257" ) );
- listTuples.add( new Tuple<Long, String>( 30L, "V258" ) );
- listTuples.add( new Tuple<Long, String>( -6L, "V259" ) );
- listTuples.add( new Tuple<Long, String>( -4L, "V260" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V261" ) );
- listTuples.add( new Tuple<Long, String>( 7L, "V262" ) );
- listTuples.add( new Tuple<Long, String>( -6L, "V263" ) );
- listTuples.add( new Tuple<Long, String>( -4L, "V264" ) );
- listTuples.add( new Tuple<Long, String>( 29L, "V265" ) );
- listTuples.add( new Tuple<Long, String>( 26L, "V266" ) );
- listTuples.add( new Tuple<Long, String>( -7L, "V267" ) );
- listTuples.add( new Tuple<Long, String>( -24L, "V268" ) );
- listTuples.add( new Tuple<Long, String>( 4L, "V269" ) );
- listTuples.add( new Tuple<Long, String>( -9L, "V270" ) );
- listTuples.add( new Tuple<Long, String>( -18L, "V271" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V272" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V273" ) );
- listTuples.add( new Tuple<Long, String>( 24L, "V274" ) );
- listTuples.add( new Tuple<Long, String>( -13L, "V275" ) );
- listTuples.add( new Tuple<Long, String>( 31L, "V276" ) );
- listTuples.add( new Tuple<Long, String>( -21L, "V277" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V278" ) );
- listTuples.add( new Tuple<Long, String>( -5L, "V279" ) );
- listTuples.add( new Tuple<Long, String>( -6L, "V280" ) );
- listTuples.add( new Tuple<Long, String>( -17L, "V281" ) );
- listTuples.add( new Tuple<Long, String>( -1L, "V282" ) );
- listTuples.add( new Tuple<Long, String>( -1L, "V283" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V284" ) );
- listTuples.add( new Tuple<Long, String>( -29L, "V285" ) );
- listTuples.add( new Tuple<Long, String>( 1L, "V286" ) );
- listTuples.add( new Tuple<Long, String>( -15L, "V287" ) );
- listTuples.add( new Tuple<Long, String>( 14L, "V288" ) );
- listTuples.add( new Tuple<Long, String>( -15L, "V289" ) );
- listTuples.add( new Tuple<Long, String>( -6L, "V290" ) );
- listTuples.add( new Tuple<Long, String>( -26L, "V291" ) );
- listTuples.add( new Tuple<Long, String>( 24L, "V292" ) );
- listTuples.add( new Tuple<Long, String>( -22L, "V293" ) );
- listTuples.add( new Tuple<Long, String>( 2L, "V294" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V295" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V296" ) );
- listTuples.add( new Tuple<Long, String>( 11L, "V297" ) );
- listTuples.add( new Tuple<Long, String>( 28L, "V298" ) );
- listTuples.add( new Tuple<Long, String>( 15L, "V299" ) );
- listTuples.add( new Tuple<Long, String>( 17L, "V300" ) );
- listTuples.add( new Tuple<Long, String>( -25L, "V301" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V302" ) );
- listTuples.add( new Tuple<Long, String>( -20L, "V303" ) );
- listTuples.add( new Tuple<Long, String>( -12L, "V304" ) );
- listTuples.add( new Tuple<Long, String>( -10L, "V305" ) );
- listTuples.add( new Tuple<Long, String>( -9L, "V306" ) );
- listTuples.add( new Tuple<Long, String>( 16L, "V307" ) );
- listTuples.add( new Tuple<Long, String>( -25L, "V308" ) );
- listTuples.add( new Tuple<Long, String>( 6L, "V309" ) );
- listTuples.add( new Tuple<Long, String>( 20L, "V310" ) );
- listTuples.add( new Tuple<Long, String>( -31L, "V311" ) );
- listTuples.add( new Tuple<Long, String>( -17L, "V312" ) );
- listTuples.add( new Tuple<Long, String>( -19L, "V313" ) );
- listTuples.add( new Tuple<Long, String>( 0L, "V314" ) );
- listTuples.add( new Tuple<Long, String>( -32L, "V315" ) );
- listTuples.add( new Tuple<Long, String>( 21L, "V316" ) );
- listTuples.add( new Tuple<Long, String>( 19L, "V317" ) );
- listTuples.add( new Tuple<Long, String>( -31L, "V318" ) );
-
- File file = File.createTempFile( "managedbtreebuilder", ".data" );
- file.deleteOnExit();
-
- try
- {
- RecordManager rm = new RecordManager( file.getAbsolutePath() );
-
- try ( WriteTransaction writeTransaction = rm.beginWriteTransaction() )
- {
- BTree<Long, String> btree = ( BTree<Long, String> ) rm.addBTree( writeTransaction, "test",
- LongSerializer.INSTANCE, StringSerializer.INSTANCE );
- }
-
- Iterator<Tuple<Long, String>> tupleIterator = new Iterator<Tuple<Long, String>>()
- {
- private int pos = 0;
-
-
- @Override
- public Tuple<Long, String> next()
- {
- Tuple<Long, String> tuple = listTuples.get( pos++ );
-
- return tuple;
- }
-
-
- @Override
- public boolean hasNext()
- {
- return pos < listTuples.size();
- }
-
-
- @Override
- public void remove()
- {
- }
- };
-
- long t0 = System.currentTimeMillis();
- BTree<Long, String> result = null;
-
- result = BulkLoader.load( result, tupleIterator, 128 );
-
- try ( Transaction transaction = rm.beginReadTransaction() )
- {
- BTree<Long, String> btree = rm.getBtree( transaction, "test" );
- TupleCursor<Long, String> cursor = result.browse( transaction );
- int nbFetched = 0;
- Tuple<Long, String> prev = null;
- Tuple<Long, String> elem = null;
-
- long t2 = System.currentTimeMillis();
-
- try
- {
- while ( cursor.hasNext() )
- {
- prev = elem;
- elem = cursor.next();
- nbFetched++;
- }
- }
- catch ( Exception e )
- {
- System.out.println( "--->" + prev );
- e.printStackTrace();
- }
- }
-
- long t3 = System.currentTimeMillis();
- }
- catch ( Exception e )
- {
- e.printStackTrace();
- }
- }
-}
--
To stop receiving notification emails like this one, please contact
['"commits@directory.apache.org" <co...@directory.apache.org>'].