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  package org.apache.directory.mavibot.btree.managed;
21  
22  
23  import java.io.IOException;
24  import java.util.LinkedList;
25  
26  import org.apache.directory.mavibot.btree.Page;
27  import org.apache.directory.mavibot.btree.ParentPos;
28  import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
29  
30  
31  /**
32   * This class construct a BTree from a serialized version of a BTree. We need it
33   * to avoid exposing all the methods of the BTree class.<br>
34   * 
35   * All its methods are static.
36   *  
37   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
38   */
39  public class BTreeFactory
40  {
41      /**
42       * Create a new BTree.
43       * 
44       * @return The created BTree
45       */
46      public static <K, V> BTree<K, V> createBTree()
47      {
48          BTree<K, V> btree = new BTree<K, V>();
49  
50          return btree;
51      }
52  
53  
54      /**
55       * Create a new Node for the give BTree.
56       * 
57       * @param btree The BTree which will contain this node
58       * @param revision The Node's revision
59       * @param nbElems The number or elements in this node
60       * @return A Node instance
61       */
62      public static <K, V> Node<K, V> createNode( BTree<K, V> btree, long revision, int nbElems )
63      {
64          Node<K, V> node = new Node<K, V>( btree, revision, nbElems );
65  
66          return node;
67      }
68  
69  
70      /**
71       * Create a new Leaf for the give BTree.
72       * 
73       * @param btree The BTree which will contain this leaf
74       * @param revision The Leaf's revision
75       * @param nbElems The number or elements in this leaf
76       * @return A Leaf instance
77       */
78      public static <K, V> Leaf<K, V> createLeaf( BTree<K, V> btree, long revision, int nbElems )
79      {
80          Leaf<K, V> leaf = new Leaf<K, V>( btree, revision, nbElems );
81  
82          return leaf;
83      }
84  
85  
86      /**
87       * Set the new root page for this tree. Used for debug purpose only. The revision
88       * will always be 0;
89       * 
90       * @param root the new root page.
91       */
92      public static <K, V> void setRoot( BTree<K, V> btree, Page<K, V> root )
93      {
94          btree.setRoot( root );
95      }
96  
97  
98      /**
99       * Return the BTree root page
100      * 
101      * @param btree The Btree we want to root page from
102      * @return The root page
103      */
104     public static <K, V> Page<K, V> getRoot( BTree<K, V> btree )
105     {
106         return btree.rootPage;
107     }
108 
109 
110     /**
111      * @param nbElems the nbElems to set
112      */
113     public static <K, V> void setNbElems( BTree<K, V> btree, long nbElems )
114     {
115         btree.setNbElems( nbElems );
116     }
117 
118 
119     /**
120      * @param revision the revision to set
121      */
122     public static <K, V> void setRevision( BTree<K, V> btree, long revision )
123     {
124         btree.setRevision( revision );
125     }
126 
127 
128     /**
129      * @param rootPageOffset the rootPageOffset to set
130      */
131     public static <K, V> void setRootPageOffset( BTree<K, V> btree, long rootPageOffset )
132     {
133         btree.setRootPageOffset( rootPageOffset );
134     }
135 
136 
137     /**
138      * @param nextBTreeOffset the nextBTreeOffset to set
139      */
140     public static <K, V> void setNextBTreeOffset( BTree<K, V> btree, long nextBTreeOffset )
141     {
142         btree.setNextBTreeOffset( nextBTreeOffset );
143     }
144 
145 
146     /**
147      * @param name the name to set
148      */
149     public static <K, V> void setName( BTree<K, V> btree, String name )
150     {
151         btree.setName( name );
152     }
153 
154 
155     /**
156      * Sets the KeySerializer into the BTree
157      *  
158      * @param btree The BTree to update
159      * @param keySerializerFqcn the Key serializer FQCN to set
160      * @throws ClassNotFoundException
161      * @throws InstantiationException 
162      * @throws IllegalAccessException
163      */
164     public static <K, V> void setKeySerializer( BTree<K, V> btree, String keySerializerFqcn )
165         throws ClassNotFoundException, IllegalAccessException, InstantiationException
166     {
167         Class<?> keySerializer = Class.forName( keySerializerFqcn );
168         @SuppressWarnings("unchecked")
169         ElementSerializer<K> instance = ( ElementSerializer<K> ) keySerializer.newInstance();
170         btree.setKeySerializer( instance );
171     }
172 
173 
174     /**
175      * Sets the ValueSerializer into the BTree
176      *  
177      * @param btree The BTree to update
178      * @param valueSerializerFqcn the Value serializer FQCN to set
179      * @throws ClassNotFoundException
180      * @throws InstantiationException 
181      * @throws IllegalAccessException
182      */
183     public static <K, V> void setValueSerializer( BTree<K, V> btree, String valueSerializerFqcn )
184         throws ClassNotFoundException, IllegalAccessException, InstantiationException
185     {
186         Class<?> valueSerializer = Class.forName( valueSerializerFqcn );
187         @SuppressWarnings("unchecked")
188         ElementSerializer<V> instance = ( ElementSerializer<V> ) valueSerializer.newInstance();
189         btree.setValueSerializer( instance );
190     }
191 
192 
193     /**
194      * Set the maximum number of elements we can store in a page.
195      * 
196      * @param pageSize The requested page size
197      */
198     public static <K, V> void setPageSize( BTree<K, V> btree, int pageSize )
199     {
200         btree.setPageSize( pageSize );
201     }
202 
203 
204     /**
205      * Set the RecordManager
206      * 
207      * @param recordManager The injected RecordManager
208      */
209     public static <K, V> void setRecordManager( BTree<K, V> btree, RecordManager recordManager )
210     {
211         btree.setRecordManager( recordManager );
212     }
213 
214 
215     /**
216      * Set the key at a give position
217      * @param pos The position in the keys array
218      * @param key the key to inject
219      */
220     public static <K, V> void setKey( Page<K, V> page, int pos, K key )
221     {
222         ( ( AbstractPage<K, V> ) page ).setKey( pos, key );
223     }
224 
225 
226     /**
227      * Set the key at a give position
228      * @param pos The position in the keys array
229      * @param pos the position of this key in the page
230      * @param buffer the byte[] containing the serialized key
231      */
232     public static <K, V> void setKey( Page<K, V> page, int pos, byte[] buffer )
233     {
234         ( ( AbstractPage<K, V> ) page ).setKey( pos, buffer );
235     }
236 
237 
238     /**
239      * Set the value at a give position
240      * @param pos The position in the values array
241      * @param value the value to inject
242      */
243     public static <K, V> void setValue( Leaf<K, V> page, int pos, ValueHolder<V> value )
244     {
245         page.setValue( pos, value );
246     }
247 
248 
249     /**
250      * Set the value at a give position
251      * @param pos The position in the values array
252      * @param value the value to inject
253      */
254     public static <K, V> void setValue( Node<K, V> page, int pos, PageHolder<K, V> value )
255     {
256         page.setValue( pos, value );
257     }
258 
259 
260     /**
261      * Includes the intermediate nodes in the path up to and including the right most leaf of the tree
262      * 
263      * @param btree the btree
264      * @return a LinkedList of all the nodes and the final leaf
265      * @throws IOException
266      */
267     public static <K, V> LinkedList<ParentPos<K, V>> getPathToRightMostLeaf( BTree<K, V> btree ) throws IOException
268     {
269         LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
270 
271         ParentPos<K, V> last = new ParentPos<K, V>( btree.rootPage, btree.rootPage.getNbElems() );
272         stack.push( last );
273 
274         if ( btree.rootPage instanceof Leaf )
275         {
276             Leaf<K, V> leaf = ( Leaf<K, V> ) ( btree.rootPage );
277             ValueHolder<V> valueHolder = leaf.values[last.pos];
278             last.valueCursor = valueHolder.getCursor();
279         }
280         else
281         {
282             Node<K, V> node = ( Node<K, V> ) btree.rootPage;
283 
284             while ( true )
285             {
286                 Page<K, V> p = node.children[node.getNbElems()].getValue( btree );
287 
288                 last = new ParentPos<K, V>( p, p.getNbElems() );
289                 stack.push( last );
290 
291                 if ( p instanceof Leaf )
292                 {
293                     Leaf<K, V> leaf = ( Leaf<K, V> ) ( last.page );
294                     ValueHolder<V> valueHolder = leaf.values[last.pos];
295                     last.valueCursor = valueHolder.getCursor();
296                     break;
297                 }
298             }
299         }
300 
301         return stack;
302     }
303 
304 
305     /**
306      * Includes the intermediate nodes in the path up to and including the left most leaf of the tree
307      * 
308      * @param btree the btree
309      * @return a LinkedList of all the nodes and the final leaf
310      * @throws IOException
311      */
312     public static <K, V> LinkedList<ParentPos<K, V>> getPathToLeftMostLeaf( BTree<K, V> btree ) throws IOException
313     {
314         LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
315 
316         ParentPos<K, V> first = new ParentPos<K, V>( btree.rootPage, 0 );
317         stack.push( first );
318 
319         if ( btree.rootPage instanceof Leaf )
320         {
321             Leaf<K, V> leaf = ( Leaf<K, V> ) ( btree.rootPage );
322             ValueHolder<V> valueHolder = leaf.values[first.pos];
323             first.valueCursor = valueHolder.getCursor();
324         }
325         else
326         {
327             Node<K, V> node = ( Node<K, V> ) btree.rootPage;
328 
329             while ( true )
330             {
331                 Page<K, V> page = node.children[0].getValue( btree );
332 
333                 first = new ParentPos<K, V>( page, 0 );
334                 stack.push( first );
335 
336                 if ( page instanceof Leaf )
337                 {
338                     Leaf<K, V> leaf = ( Leaf<K, V> ) ( page );
339                     ValueHolder<V> valueHolder = leaf.values[first.pos];
340                     first.valueCursor = valueHolder.getCursor();
341                     break;
342                 }
343             }
344         }
345 
346         return stack;
347     }
348 }