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.lang.reflect.Array;
25  
26  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
27  
28  
29  /**
30   * A MVCC abstract Page. It stores the field and the methods shared by the Node and Leaf
31   * classes.
32   * 
33   * @param <K> The type for the Key
34   * @param <V> The type for the stored value
35   *
36   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
37   */
38  /* No qualifier */abstract class AbstractPage<K, V> implements Page<K, V>
39  {
40      /** Parent B+Tree. */
41      protected transient BTree<K, V> btree;
42  
43      /** This BPage's revision */
44      protected long revision;
45  
46      /** Keys of children nodes */
47      protected KeyHolder<K>[] keys;
48  
49      /** The number of current values in the Page */
50      protected int nbElems;
51  
52      /** The first {@link PageIO} storing the serialized Page on disk */
53      private long offset = -1L;
54  
55      /** The last {@link PageIO} storing the serialized Page on disk */
56      private long lastOffset = -1L;
57  
58      /** A static Exception used to avoid creating a new one every time */
59      protected KeyNotFoundException KEY_NOT_FOUND_EXCEPTION = new KeyNotFoundException(
60          "Cannot find an entry associated with this key" );
61  
62  
63      /**
64       * Creates a default empty AbstractPage
65       * 
66       * @param btree The associated BTree
67       */
68      protected AbstractPage( BTree<K, V> btree )
69      {
70          this.btree = btree;
71      }
72  
73  
74      /**
75       * Internal constructor used to create Page instance used when a page is being copied or overflow
76       */
77      @SuppressWarnings("unchecked")
78      // Cannot create an array of generic objects
79      protected AbstractPage( BTree<K, V> btree, long revision, int nbElems )
80      {
81          this.btree = btree;
82          this.revision = revision;
83          this.nbElems = nbElems;
84          this.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, nbElems );
85      }
86  
87  
88      /**
89       * Selects the sibling (the previous or next page with the same parent) which has
90       * the more element assuming it's above N/2
91       * 
92       * @param parent The parent of the current page
93       * @param The position of the current page reference in its parent
94       * @return The position of the sibling, or -1 if we have'nt found any sibling
95       * @throws IOException If we have an error while trying to access the page
96       */
97      protected int selectSibling( Node<K, V> parent, int parentPos ) throws IOException
98      {
99          if ( parentPos == 0 )
100         {
101             // The current page is referenced on the left of its parent's page :
102             // we will not have a previous page with the same parent
103             return 1;
104         }
105 
106         if ( parentPos == parent.getNbElems() )
107         {
108             // The current page is referenced on the right of its parent's page :
109             // we will not have a next page with the same parent
110             return parentPos - 1;
111         }
112 
113         Page<K, V> prevPage = parent.children[parentPos - 1].getValue( btree );
114         Page<K, V> nextPage = parent.children[parentPos + 1].getValue( btree );
115 
116         int prevPageSize = prevPage.getNbElems();
117         int nextPageSize = nextPage.getNbElems();
118 
119         if ( prevPageSize >= nextPageSize )
120         {
121             return parentPos - 1;
122         }
123         else
124         {
125             return parentPos + 1;
126         }
127     }
128 
129 
130     /**
131      * {@inheritDoc}
132      */
133     public int getNbElems()
134     {
135         return nbElems;
136     }
137 
138 
139     /**
140      * Finds the position of the given key in the page. If we have found the key,
141      * we will return its position as a negative value.
142      * <p/>
143      * Assuming that the array is zero-indexed, the returned value will be : <br/>
144      *   position = - ( position + 1)
145      * <br/>
146      * So for the following table of keys : <br/>
147      * <pre>
148      * +---+---+---+---+
149      * | b | d | f | h |
150      * +---+---+---+---+
151      *   0   1   2   3
152      * </pre>
153      * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
154      * Computing the real position is just a matter to get -(position++).
155      * <p/>
156      * If we don't find the key in the table, we will return the position of the key
157      * immediately above the key we are looking for. <br/>
158      * For instance, looking for :
159      * <ul>
160      * <li>'a' will return 0</li>
161      * <li>'b' will return -1</li>
162      * <li>'c' will return 1</li>
163      * <li>'d' will return -2</li>
164      * <li>'e' will return 2</li>
165      * <li>'f' will return -3</li>
166      * <li>'g' will return 3</li>
167      * <li>'h' will return -4</li>
168      * <li>'i' will return 4</li>
169      * </ul>
170      * 
171      * 
172      * @param key The key to find
173      * @return The position in the page.
174      */
175     public int findPos( K key )
176     {
177         // Deal with the special key where we have an empty page
178         if ( nbElems == 0 )
179         {
180             return 0;
181         }
182 
183         int min = 0;
184         int max = nbElems - 1;
185 
186         // binary search
187         while ( min < max )
188         {
189             int middle = ( min + max + 1 ) >> 1;
190 
191             int comp = compare( keys[middle].getKey(), key );
192 
193             if ( comp < 0 )
194             {
195                 min = middle + 1;
196             }
197             else if ( comp > 0 )
198             {
199                 max = middle - 1;
200             }
201             else
202             {
203                 // Special case : the key already exists,
204                 // we can return immediately. The value will be
205                 // negative, and as the index may be 0, we subtract 1
206                 return -( middle + 1 );
207             }
208         }
209 
210         // Special case : we don't know if the key is present
211         int comp = compare( keys[max].getKey(), key );
212 
213         if ( comp == 0 )
214         {
215             return -( max + 1 );
216         }
217         else
218         {
219             if ( comp < 0 )
220             {
221                 return max + 1;
222             }
223             else
224             {
225                 return max;
226             }
227         }
228     }
229 
230 
231     /**
232      * Compares two keys
233      * 
234      * @param key1 The first key
235      * @param key2 The second key
236      * @return -1 if the first key is above the second one, 1 if it's below, and 0
237      * if the two keys are equal
238      */
239     private final int compare( K key1, K key2 )
240     {
241         if ( key1 == key2 )
242         {
243             return 0;
244         }
245 
246         if ( key1 == null )
247         {
248             return 1;
249         }
250 
251         if ( key2 == null )
252         {
253             return -1;
254         }
255 
256         return btree.getComparator().compare( key1, key2 );
257     }
258 
259 
260     /**
261      * {@inheritDoc}
262      */
263     public long getRevision()
264     {
265         return revision;
266     }
267 
268 
269     /**
270      * {@inheritDoc}
271      */
272     public K getKey( int pos )
273     {
274         if ( pos < nbElems )
275         {
276             return keys[pos].getKey();
277         }
278         else
279         {
280             return null;
281         }
282     }
283 
284 
285     /**
286      * Sets the key at a give position
287      * 
288      * @param pos The position in the keys array
289      * @param key the key to inject
290      */
291     /* No qualifier*/void setKey( int pos, K key )
292     {
293         keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
294     }
295 
296 
297     /**
298      * Sets the key at a give position
299      * 
300      * @param pos The position in the keys array
301      * @param buffer the serialized key to inject
302      */
303     /* No qualifier*/void setKey( int pos, byte[] buffer )
304     {
305         keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), buffer );
306     }
307 
308 
309     /**
310      * {@inheritDoc}
311      */
312     public long getOffset()
313     {
314         return offset;
315     }
316 
317 
318     /**
319      * @param offset the offset to set
320      */
321     /* No qualifier */void setOffset( long offset )
322     {
323         this.offset = offset;
324     }
325 
326 
327     /**
328      * {@inheritDoc}
329      */
330     public long getLastOffset()
331     {
332         return lastOffset;
333     }
334 
335 
336     /**
337      * {@inheritDoc}
338      */
339     /* No qualifier */void setLastOffset( long lastOffset )
340     {
341         this.lastOffset = lastOffset;
342     }
343 
344 
345     /**
346      * @see Object#toString()
347      */
348     public String toString()
349     {
350         StringBuilder sb = new StringBuilder();
351 
352         sb.append( "r" ).append( revision );
353         sb.append( ", nbElems:" ).append( nbElems );
354 
355         if ( offset > 0 )
356         {
357             sb.append( ", offset:" ).append( offset );
358         }
359 
360         return sb.toString();
361     }
362 
363 
364     /**
365      * {@inheritDoc}
366      */
367     public String dumpPage( String tabs )
368     {
369         return "";
370     }
371 }