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.memory;
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 key at a give position
206      * @param pos The position in the keys array
207      * @param key the key to inject
208      */
209     public static <K, V> void setKey( Page<K, V> page, int pos, K key )
210     {
211         ( ( AbstractPage<K, V> ) page ).setKey( pos, key );
212     }
213 
214 
215     /**
216      * Set the value at a give position
217      * @param pos The position in the values array
218      * @param value the value to inject
219      */
220     public static <K, V> void setValue( Leaf<K, V> page, int pos, ValueHolder<V> value )
221     {
222         page.setValue( pos, value );
223     }
224 
225 
226     /**
227      * Set the value at a give position
228      * @param pos The position in the values array
229      * @param value the value to inject
230      */
231     public static <K, V> void setValue( Node<K, V> page, int pos, Page<K, V> value )
232     {
233         page.children[pos] = value;
234     }
235 
236 
237     /**
238      * Includes the intermediate nodes in the path up to and including the right most leaf of the tree
239      * 
240      * @param btree the btree
241      * @return a LinkedList of all the nodes and the final leaf
242      * @throws IOException
243      */
244     public static <K, V> LinkedList<ParentPos<K, V>> getPathToRightMostLeaf( BTree<K, V> btree ) throws IOException
245     {
246         LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
247 
248         ParentPos<K, V> last = new ParentPos<K, V>( btree.rootPage, btree.rootPage.getNbElems() );
249         stack.push( last );
250 
251         if ( btree.rootPage instanceof Leaf )
252         {
253             Leaf<K, V> leaf = ( Leaf<K, V> ) ( btree.rootPage );
254             ValueHolder<V> valueHolder = leaf.values[last.pos];
255             last.valueCursor = valueHolder.getCursor();
256         }
257         else
258         {
259             Node<K, V> node = ( Node<K, V> ) btree.rootPage;
260 
261             while ( true )
262             {
263                 Page<K, V> p = node.children[node.getNbElems()];
264 
265                 last = new ParentPos<K, V>( p, p.getNbElems() );
266                 stack.push( last );
267 
268                 if ( p instanceof Leaf )
269                 {
270                     Leaf<K, V> leaf = ( Leaf<K, V> ) ( last.page );
271                     ValueHolder<V> valueHolder = leaf.values[last.pos];
272                     last.valueCursor = valueHolder.getCursor();
273                     break;
274                 }
275             }
276         }
277 
278         return stack;
279     }
280 }