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.managed;
22  
23  
24  import static org.apache.directory.mavibot.btree.managed.BTreeFactory.createLeaf;
25  import static org.apache.directory.mavibot.btree.managed.BTreeFactory.createNode;
26  import static org.apache.directory.mavibot.btree.managed.BTreeFactory.setKey;
27  import static org.apache.directory.mavibot.btree.managed.BTreeFactory.setValue;
28  
29  import java.io.IOException;
30  import java.lang.reflect.Array;
31  import java.util.ArrayList;
32  import java.util.Arrays;
33  import java.util.Iterator;
34  import java.util.List;
35  
36  import org.apache.directory.mavibot.btree.Page;
37  import org.apache.directory.mavibot.btree.Tuple;
38  import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
39  
40  
41  /**
42   * A BTree builder that builds a tree from the bottom.
43   *
44   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
45   */
46  public class ManagedBTreeBuilder<K, V>
47  {
48      private String name;
49  
50      private int numKeysInNode;
51  
52      private ElementSerializer<K> keySerializer;
53  
54      private ElementSerializer<V> valueSerializer;
55  
56      private RecordManager rm;
57  
58      public ManagedBTreeBuilder( RecordManager rm, String name, int numKeysInNode, ElementSerializer<K> keySerializer,
59          ElementSerializer<V> valueSerializer )
60      {
61          this.rm = rm;
62          this.name = name;
63          this.numKeysInNode = numKeysInNode;
64          this.keySerializer = keySerializer;
65          this.valueSerializer = valueSerializer;
66      }
67  
68  
69      @SuppressWarnings("unchecked")
70      public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws Exception
71      {
72          BTree<K, V> btree = new BTree<K, V>( name, keySerializer, valueSerializer );
73          btree.init();
74  
75          rm.manage( btree );
76          
77          List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>();
78  
79          int totalTupleCount = 0;
80  
81          Leaf<K, V> leaf1 = createLeaf( btree, 0, numKeysInNode );
82          lstLeaves.add( leaf1 );
83  
84          int leafIndex = 0;
85  
86          while ( sortedTupleItr.hasNext() )
87          {
88              Tuple<K, V> tuple = sortedTupleItr.next();
89              
90              setKey( leaf1, leafIndex, tuple.getKey() );
91  
92              ValueHolder<V> eh = new ValueHolder<V>( btree, tuple.getValue() );
93  
94              setValue( leaf1, leafIndex, eh );
95  
96              leafIndex++;
97              totalTupleCount++;
98              if ( ( totalTupleCount % numKeysInNode ) == 0 )
99              {
100                 leafIndex = 0;
101                 
102                 PageHolder<K, V> pageHolder = ( PageHolder<K, V> ) rm.writePage( btree, leaf1, 1 );
103                 
104                 leaf1 = createLeaf( btree, 0, numKeysInNode );
105                 lstLeaves.add( leaf1 );
106             }
107             
108             //TODO build the whole tree in chunks rather than processing *all* leaves at first
109         }
110 
111         if ( lstLeaves.isEmpty() )
112         {
113             return btree;
114         }
115 
116         // remove null keys and values from the last leaf and resize
117         Leaf<K, V> lastLeaf = ( Leaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
118         for ( int i = 0; i < lastLeaf.nbElems; i++ )
119         {
120             if ( lastLeaf.keys[i] == null )
121             {
122                 int n = i;
123                 lastLeaf.nbElems = n;
124                 KeyHolder<K>[] keys = lastLeaf.keys;
125 
126                 lastLeaf.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n );
127                 System.arraycopy( keys, 0, lastLeaf.keys, 0, n );
128 
129                 ValueHolder<V>[] values = lastLeaf.values;
130                 lastLeaf.values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, n );
131                 System.arraycopy( values, 0, lastLeaf.values, 0, n );
132 
133                 PageHolder<K, V> pageHolder = ( PageHolder<K, V> ) rm.writePage( btree, lastLeaf, 1 );
134 
135                 break;
136             }
137         }
138 
139         // make sure either one of the root pages is reclaimed, cause when we call rm.manage()
140         // there is already a root page created
141         Page<K, V> rootPage = attachNodes( lstLeaves, btree );
142 
143         //System.out.println("built rootpage : " + rootPage);
144         btree.setNbElems( totalTupleCount );
145         
146         rm.updateBtreeHeader( btree, ( ( AbstractPage<K, V> ) rootPage ).getOffset() );
147         
148         rm.addFreePages( btree, Arrays.asList( btree.rootPage ) );
149         
150         btree.rootPage = rootPage;
151         
152         return btree;
153     }
154 
155 
156     @SuppressWarnings("unchecked")
157     private Page<K, V> attachNodes( List<Page<K, V>> children, BTree<K, V> btree ) throws IOException
158     {
159         if ( children.size() == 1 )
160         {
161             return children.get( 0 );
162         }
163 
164         List<Page<K, V>> lstNodes = new ArrayList<Page<K, V>>();
165 
166         int numChildren = numKeysInNode + 1;
167 
168         Node<K, V> node = createNode( btree, 0, numKeysInNode );
169         lstNodes.add( node );
170         int i = 0;
171         int totalNodes = 0;
172 
173         for ( Page<K, V> p : children )
174         {
175             if ( i != 0 )
176             {
177                 setKey( node, i - 1, p.getLeftMostKey() );
178             }
179 
180             node.children[i] = btree.createPageHolder( p );
181 
182             i++;
183             totalNodes++;
184 
185             if ( ( totalNodes % numChildren ) == 0 )
186             {
187                 i = 0;
188                 
189                 PageHolder<K, V> pageHolder = ( PageHolder<K, V> ) rm.writePage( btree, node, 1 );
190 
191                 node = createNode( btree, 0, numKeysInNode );
192                 lstNodes.add( node );
193             }
194         }
195 
196         // remove null keys and values from the last node and resize
197         AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
198 
199         for ( int j = 0; j < lastNode.nbElems; j++ )
200         {
201             if ( lastNode.keys[j] == null )
202             {
203                 int n = j;
204                 lastNode.nbElems = n;
205                 KeyHolder<K>[] keys = lastNode.keys;
206 
207                 lastNode.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n );
208                 System.arraycopy( keys, 0, lastNode.keys, 0, n );
209 
210                 PageHolder<K, V> pageHolder = ( PageHolder<K, V> ) rm.writePage( btree, lastNode, 1 );
211 
212                 break;
213             }
214         }
215 
216         return attachNodes( lstNodes, btree );
217     }
218 }