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