View Javadoc

1   /*
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *   or more contributor license agreements.  See the NOTICE file
4    *   distributed with this work for additional information
5    *   regarding copyright ownership.  The ASF licenses this file
6    *   to you under the Apache License, Version 2.0 (the
7    *   "License"); you may not use this file except in compliance
8    *   with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *   Unless required by applicable law or agreed to in writing,
13   *   software distributed under the License is distributed on an
14   *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *   KIND, either express or implied.  See the License for the
16   *   specific language governing permissions and limitations
17   *   under the License.
18   *
19   */
20  
21  package org.apache.directory.mavibot.btree.memory;
22  
23  
24  import static org.apache.directory.mavibot.btree.memory.BTreeFactory.createLeaf;
25  import static org.apache.directory.mavibot.btree.memory.BTreeFactory.createNode;
26  import static org.apache.directory.mavibot.btree.memory.BTreeFactory.setKey;
27  import static org.apache.directory.mavibot.btree.memory.BTreeFactory.setValue;
28  
29  import java.io.IOException;
30  import java.lang.reflect.Array;
31  import java.util.ArrayList;
32  import java.util.Iterator;
33  import java.util.List;
34  
35  import org.apache.directory.mavibot.btree.Page;
36  import org.apache.directory.mavibot.btree.Tuple;
37  import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
38  
39  
40  /**
41   * A BTree builder that builds a tree from the bottom.
42   *
43   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
44   */
45  public class BTreeBuilder<K, V>
46  {
47      private String name;
48  
49      private int numKeysInNode;
50  
51      private ElementSerializer<K> keySerializer;
52  
53      private ElementSerializer<V> valueSerializer;
54  
55  
56      public BTreeBuilder( String name, int numKeysInNode, ElementSerializer<K> keySerializer,
57          ElementSerializer<V> valueSerializer )
58      {
59          this.name = name;
60          this.numKeysInNode = numKeysInNode;
61          this.keySerializer = keySerializer;
62          this.valueSerializer = valueSerializer;
63      }
64  
65  
66      @SuppressWarnings("unchecked")
67      public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException
68      {
69          BTree<K, V> btree = new BTree<K, V>( name, keySerializer, valueSerializer );
70          btree.init();
71  
72          List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>();
73  
74          int totalTupleCount = 0;
75  
76          Leaf<K, V> leaf1 = createLeaf( btree, 0, numKeysInNode );
77          lstLeaves.add( leaf1 );
78  
79          int leafIndex = 0;
80          while ( sortedTupleItr.hasNext() )
81          {
82              Tuple<K, V> tuple = sortedTupleItr.next();
83  
84              setKey( leaf1, leafIndex, tuple.getKey() );
85  
86              ValueHolder<V> eh = new ValueHolder<V>( btree, tuple.getValue() );
87  
88              setValue( leaf1, leafIndex, eh );
89  
90              leafIndex++;
91              totalTupleCount++;
92              if ( ( totalTupleCount % numKeysInNode ) == 0 )
93              {
94                  leafIndex = 0;
95                  leaf1 = createLeaf( btree, 0, numKeysInNode );
96                  lstLeaves.add( leaf1 );
97              }
98          }
99  
100         if ( lstLeaves.isEmpty() )
101         {
102             return btree;
103         }
104 
105         // remove null keys and values from the last leaf and resize
106         Leaf<K, V> lastLeaf = ( Leaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
107         for ( int i = 0; i < lastLeaf.nbElems; i++ )
108         {
109             if ( lastLeaf.keys[i] == null )
110             {
111                 int n = i;
112                 lastLeaf.nbElems = n;
113                 K[] keys = lastLeaf.keys;
114 
115                 Class<?> keyType = btree.getKeyType();
116                 lastLeaf.keys = ( K[] ) Array.newInstance( keyType, n );
117                 System.arraycopy( keys, 0, lastLeaf.keys, 0, n );
118 
119                 ValueHolder<V>[] values = lastLeaf.values;
120                 lastLeaf.values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, n );
121                 System.arraycopy( values, 0, lastLeaf.values, 0, n );
122 
123                 break;
124             }
125         }
126 
127         Page<K, V> rootPage = attachNodes( lstLeaves, btree );
128 
129         System.out.println("built rootpage : " + rootPage);
130         
131         btree.rootPage = rootPage;
132 
133         return btree;
134     }
135 
136 
137     @SuppressWarnings("unchecked")
138     private Page<K, V> attachNodes( List<Page<K, V>> children, BTree<K, V> btree ) throws IOException
139     {
140         if ( children.size() == 1 )
141         {
142             return children.get( 0 );
143         }
144 
145         List<Page<K, V>> lstNodes = new ArrayList<Page<K, V>>();
146 
147         int numChildren = numKeysInNode + 1;
148 
149         Node<K, V> node = createNode( btree, 0, numKeysInNode );
150         lstNodes.add( node );
151         int i = 0;
152         int totalNodes = 0;
153 
154         for ( Page<K, V> p : children )
155         {
156             if ( i != 0 )
157             {
158                 setKey( node, i - 1, p.getLeftMostKey() );
159             }
160 
161             node.children[i] = p;
162 
163             i++;
164             totalNodes++;
165 
166             if ( ( totalNodes % numChildren ) == 0 )
167             {
168                 i = 0;
169                 node = createNode( btree, 0, numKeysInNode );
170                 lstNodes.add( node );
171             }
172         }
173 
174         // remove null keys and values from the last node and resize
175         AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
176 
177         for ( int j = 0; j < lastNode.nbElems; j++ )
178         {
179             if ( lastNode.keys[j] == null )
180             {
181                 int n = j;
182                 lastNode.nbElems = n;
183                 K[] keys = lastNode.keys;
184 
185                 Class<?> keyType = btree.getKeyType();
186                 lastNode.keys = ( K[] ) Array.newInstance( keyType, n );
187                 System.arraycopy( keys, 0, lastNode.keys, 0, n );
188 
189                 break;
190             }
191         }
192 
193         return attachNodes( lstNodes, btree );
194     }
195 }