| /* |
| * 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 BTree builder that builds a tree from the bottom. |
| * |
| * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> |
| */ |
| public class InMemoryBTreeBuilder<K, V> |
| { |
| /** The Btree configuration */ |
| private InMemoryBTreeConfiguration<K, V> 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<K> keySerializer, |
| ElementSerializer<V> valueSerializer ) |
| { |
| btreeConfiguration = new InMemoryBTreeConfiguration<K, V>(); |
| 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<K, V> btreeConfiguration ) |
| { |
| this.btreeConfiguration = btreeConfiguration; |
| } |
| |
| |
| @SuppressWarnings("unchecked") |
| public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException |
| { |
| BTree<K, V> 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<InMemoryNode<K, V>>[] pageStack = new ArrayList[15]; |
| |
| for ( int i = 0; i < 15; i++ ) |
| { |
| pageStack[i] = new ArrayList<InMemoryNode<K, V>>( maxElements ); |
| } |
| |
| // The number of added elements |
| int nbAdded = 0; |
| |
| // The btree height |
| int btreeHeight = 0; |
| |
| // An array containing the number of elements necessary to fulfill a layer : |
| // pageSize * (pageSize + 1) |
| List<Tuple<K, V>> tuples = new ArrayList<Tuple<K, V>>( maxElements ); |
| |
| // A list of nodes that are going to be created |
| List<InMemoryNode<K, V>> nodes = new ArrayList<InMemoryNode<K, V>>(); |
| |
| // Now, loop on all the elements |
| while ( sortedTupleItr.hasNext() ) |
| { |
| nbAdded++; |
| |
| // Get the tuple to inject |
| Tuple<K, V> tuple = sortedTupleItr.next(); |
| tuples.add( tuple ); |
| |
| if ( tuples.size() == maxElements ) |
| { |
| // We have enough elements to create pageSize leaves, and the upper node |
| InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) 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<K, V> ) btree ).setRootPage( pageStack[level].get( 0 ) ); |
| |
| // Update the btree height |
| if ( btreeHeight < level ) |
| { |
| btreeHeight = level; |
| } |
| } |
| |
| tuples.clear(); |
| } |
| } |
| |
| if ( tuples.size() > 0 ) |
| { |
| // Let's deal with the remaining elements |
| Page<K, V> page = addLeaves( btree, tuples, maxElements ); |
| |
| if ( page instanceof InMemoryNode ) |
| { |
| nodes.add( ( InMemoryNode<K, V> ) page ); |
| |
| // If the node list has enough elements to fulfill a parent node, |
| // then process |
| if ( nodes.size() == maxElements ) |
| { |
| Page<K, V> rootPage = createParentNode( btree, nodes, maxElements ); |
| |
| ( ( AbstractBTree<K, V> ) btree ).setRootPage( rootPage ); |
| } |
| } |
| else |
| { |
| InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) 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. |
| // TODO |
| } |
| else |
| { |
| // Enough elements in the added leaf (at least N/2). We just have to update |
| // the parent's node. |
| // TODO |
| } |
| } |
| } |
| } |
| |
| // Update the number of elements |
| ( ( AbstractBTree<K, V> ) btree ).getBtreeHeader().setNbElems( nbAdded ); |
| |
| return btree; |
| } |
| |
| |
| /** |
| * Creates all the nodes using the provided node pages, and update the upper laye |
| */ |
| private InMemoryNode<K, V> createParentNode( BTree<K, V> btree, List<InMemoryNode<K, V>> nodes, int maxElements ) |
| { |
| // We have enough tuples to fulfill the upper node. |
| // First, create the new node |
| InMemoryNode<K, V> parentNode = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, |
| btreeConfiguration.getPageSize() ); |
| |
| int nodePos = 0; |
| |
| // Then iterate on the tuples, creating the needed pages |
| for ( InMemoryNode<K, V> node : nodes ) |
| { |
| if ( nodePos != 0 ) |
| { |
| K key = node.getLeftMostKey(); |
| BTreeFactory.setKey( btree, parentNode, nodePos - 1, key ); |
| } |
| |
| PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, node ); |
| parentNode.setPageHolder( nodePos, pageHolder ); |
| nodePos++; |
| } |
| |
| // And return the node |
| return parentNode; |
| } |
| |
| |
| /** |
| * Creates all the leaves using the provided tuples, and update the upper layer if needed |
| */ |
| private Page<K, V> addLeaves( BTree<K, V> btree, List<Tuple<K, V>> tuples, int maxElements ) |
| { |
| if ( tuples.size() == 0 ) |
| { |
| // 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<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, |
| btreeConfiguration.getPageSize() ); |
| |
| // Iterate on the tuples |
| for ( Tuple<K, V> tuple : tuples ) |
| { |
| injectTuple( btree, leaf, leafPos, tuple ); |
| leafPos++; |
| } |
| |
| return leaf; |
| } |
| |
| // 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<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, |
| btreeConfiguration.getPageSize() ); |
| |
| // creates a first leaf |
| InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, |
| btreeConfiguration.getPageSize() ); |
| |
| int nodePos = 0; |
| |
| // Then iterate on the tuples, creating the needed pages |
| for ( Tuple<K, V> 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<K, V> pageHolder = new PageHolder<K, V>( btree, leaf ); |
| node.setPageHolder( nodePos, pageHolder ); |
| nodePos++; |
| |
| // When done, we need to create a new leaf |
| leaf = ( InMemoryLeaf<K, V> ) 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<K, V> pageHolder = new PageHolder<K, V>( btree, leaf ); |
| node.setPageHolder( nodePos, pageHolder ); |
| } |
| |
| return node; |
| } |
| else |
| { |
| // We have enough tuples to fulfill the upper node. |
| // First, create the new node |
| InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, |
| btreeConfiguration.getPageSize() ); |
| |
| // creates a first leaf |
| InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, |
| btreeConfiguration.getPageSize() ); |
| |
| int nodePos = 0; |
| |
| // Then iterate on the tuples, creating the needed pages |
| for ( Tuple<K, V> 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<K, V> pageHolder = new PageHolder<K, V>( btree, leaf ); |
| node.setPageHolder( nodePos, pageHolder ); |
| nodePos++; |
| |
| // When done, we need to create a new leaf |
| leaf = ( InMemoryLeaf<K, V> ) 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<K, V> pageHolder = new PageHolder<K, V>( btree, leaf ); |
| node.setPageHolder( nodePos, pageHolder ); |
| } |
| |
| // And return the node |
| return node; |
| } |
| } |
| |
| |
| private void injectTuple( BTree<K, V> btree, InMemoryLeaf<K, V> leaf, int leafPos, Tuple<K, V> tuple ) |
| { |
| BTreeFactory.setKey( btree, leaf, leafPos, tuple.getKey() ); |
| ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() ); |
| BTreeFactory.setValue( btree, leaf, leafPos, valueHolder ); |
| } |
| |
| |
| private int add( BTree<K, V> btree, Page<K, V>[] pageStack, int level, Page<K, V> page, Tuple<K, V> tuple ) |
| { |
| if ( page == null ) |
| { |
| // No existing page at this level, create a new one |
| if ( level == 0 ) |
| { |
| // creates a leaf |
| InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) 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<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() ); |
| BTreeFactory.setValue( btree, leaf, 0, valueHolder ); |
| } |
| else |
| { |
| // Create a node |
| InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, |
| btreeConfiguration.getPageSize() ); |
| |
| // Inject the tuple key in the node |
| BTreeFactory.setKey( btree, node, 0, tuple.getKey() ); |
| PageHolder<K, V> pageHolder = new PageHolder<K, V>( 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 |
| //TODO |
| } |
| 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<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() ); |
| BTreeFactory.setValue( btree, page, page.getNbElems(), valueHolder ); |
| } |
| else |
| { |
| // It's a node |
| BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() ); |
| PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, pageStack[level - 1] ); |
| ( ( InMemoryNode<K, V> ) page ).setPageHolder( page.getNbElems(), pageHolder ); |
| } |
| } |
| } |
| |
| return level; |
| } |
| |
| |
| @SuppressWarnings("unchecked") |
| private Page<K, V> attachNodes( 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<Page<K, V>>(); |
| |
| int numChildren = btreeConfiguration.getPageSize() + 1; |
| |
| InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, |
| btreeConfiguration.getPageSize() ); |
| lstNodes.add( node ); |
| int i = 0; |
| int totalNodes = 0; |
| |
| for ( Page<K, V> p : children ) |
| { |
| if ( i != 0 ) |
| { |
| BTreeFactory.setKey( btree, node, i - 1, p.getLeftMostKey() ); |
| } |
| |
| node.setPageHolder( i, new PageHolder<K, V>( btree, p ) ); |
| |
| i++; |
| totalNodes++; |
| |
| if ( ( totalNodes % numChildren ) == 0 ) |
| { |
| i = 0; |
| node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, btreeConfiguration.getPageSize() ); |
| 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.getNbElems(); j++ ) |
| { |
| if ( lastNode.getKey( j ) == null ) |
| { |
| int n = j; |
| lastNode.setNbElems( n ); |
| KeyHolder<K>[] keys = lastNode.getKeys(); |
| |
| lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) ); |
| System.arraycopy( keys, 0, lastNode.getKeys(), 0, n ); |
| |
| break; |
| } |
| } |
| |
| return attachNodes( lstNodes, btree ); |
| } |
| } |