in mavibot/src/main/java/org/apache/directory/mavibot/btree/BulkLoader.java [577:783]
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 );
PersistedNode<K, V> node = ( PersistedNode<K, V> ) level.getCurrentPage();
// We first have to write the page on disk
PageHolder<K, V> pageHolder = ( ( PersistedBTree<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 PersistedKeyHolder<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 PersistedKeyHolder<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 PersistedKeyHolder<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.getNbElems() + 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 PersistedKeyHolder<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.getNbElems() + 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;
}
}
}