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.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 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  
86          // We get the type of array to create from the btree
87          // Yes, this is an hack...
88          Class<?> keyType = btree.getKeyType();
89          this.keys = ( K[] ) Array.newInstance( keyType, nbElems );
90      }
91  
92  
93      /**
94       * Selects the sibling (the previous or next page with the same parent) which has
95       * the more element assuming it's above N/2
96       * 
97       * @param parent The parent of the current page
98       * @param The position of the current page reference in its parent
99       * @return The position of the sibling, or -1 if we have'nt found any sibling
100      * @throws IOException If we have an error while trying to access the page
101      */
102     protected int selectSibling( Node<K, V> parent, int parentPos ) throws IOException
103     {
104         if ( parentPos == 0 )
105         {
106             // The current page is referenced on the left of its parent's page :
107             // we will not have a previous page with the same parent
108             return 1;
109         }
110 
111         if ( parentPos == parent.getNbElems() )
112         {
113             // The current page is referenced on the right of its parent's page :
114             // we will not have a next page with the same parent
115             return parentPos - 1;
116         }
117 
118         Page<K, V> prevPage = parent.children[parentPos - 1];
119         Page<K, V> nextPage = parent.children[parentPos + 1];
120 
121         int prevPageSize = prevPage.getNbElems();
122         int nextPageSize = nextPage.getNbElems();
123 
124         if ( prevPageSize >= nextPageSize )
125         {
126             return parentPos - 1;
127         }
128         else
129         {
130             return parentPos + 1;
131         }
132     }
133 
134 
135     /**
136      * {@inheritDoc}
137      */
138     public int getNbElems()
139     {
140         return nbElems;
141     }
142 
143 
144     /**
145      * Finds the position of the given key in the page. If we have found the key,
146      * we will return its position as a negative value.
147      * <p/>
148      * Assuming that the array is zero-indexed, the returned value will be : <br/>
149      *   position = - ( position + 1)
150      * <br/>
151      * So for the following table of keys : <br/>
152      * <pre>
153      * +---+---+---+---+
154      * | b | d | f | h |
155      * +---+---+---+---+
156      *   0   1   2   3
157      * </pre>
158      * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
159      * Computing the real position is just a matter to get -(position++).
160      * <p/>
161      * If we don't find the key in the table, we will return the position of the key
162      * immediately above the key we are looking for. <br/>
163      * For instance, looking for :
164      * <ul>
165      * <li>'a' will return 0</li>
166      * <li>'b' will return -1</li>
167      * <li>'c' will return 1</li>
168      * <li>'d' will return -2</li>
169      * <li>'e' will return 2</li>
170      * <li>'f' will return -3</li>
171      * <li>'g' will return 3</li>
172      * <li>'h' will return -4</li>
173      * <li>'i' will return 4</li>
174      * </ul>
175      * 
176      * 
177      * @param key The key to find
178      * @return The position in the page.
179      */
180     public int findPos( K key )
181     {
182         // Deal with the special key where we have an empty page
183         if ( nbElems == 0 )
184         {
185             return 0;
186         }
187 
188         int min = 0;
189         int max = nbElems - 1;
190 
191         // binary search
192         while ( min < max )
193         {
194             int middle = ( min + max + 1 ) >> 1;
195 
196             int comp = compare( keys[middle], key );
197 
198             if ( comp < 0 )
199             {
200                 min = middle + 1;
201             }
202             else if ( comp > 0 )
203             {
204                 max = middle - 1;
205             }
206             else
207             {
208                 // Special case : the key already exists,
209                 // we can return immediately. The value will be
210                 // negative, and as the index may be 0, we subtract 1
211                 return -( middle + 1 );
212             }
213         }
214 
215         // Special case : we don't know if the key is present
216         int comp = compare( keys[max], key );
217 
218         if ( comp == 0 )
219         {
220             return -( max + 1 );
221         }
222         else
223         {
224             if ( comp < 0 )
225             {
226                 return max + 1;
227             }
228             else
229             {
230                 return max;
231             }
232         }
233     }
234 
235 
236     /**
237      * Compares two keys
238      * 
239      * @param key1 The first key
240      * @param key2 The second key
241      * @return -1 if the first key is above the second one, 1 if it's below, and 0
242      * if the two keys are equal
243      */
244     private final int compare( K key1, K key2 )
245     {
246         if ( key1 == key2 )
247         {
248             return 0;
249         }
250 
251         if ( key1 == null )
252         {
253             return 1;
254         }
255 
256         if ( key2 == null )
257         {
258             return -1;
259         }
260 
261         return btree.getComparator().compare( key1, key2 );
262     }
263 
264 
265     /**
266      * {@inheritDoc}
267      */
268     public long getRevision()
269     {
270         return revision;
271     }
272 
273 
274     /**
275      * {@inheritDoc}
276      */
277     public K getKey( int pos )
278     {
279         if ( pos < nbElems )
280         {
281             return keys[pos];
282         }
283         else
284         {
285             return null;
286         }
287     }
288 
289 
290     /**
291      * Sets the key at a give position
292      * 
293      * @param pos The position in the keys array
294      * @param key the key to inject
295      */
296     /* No qualifier*/void setKey( int pos, K key )
297     {
298         keys[pos] = key;
299     }
300 
301 
302     /**
303      * {@inheritDoc}
304      */
305     public long getOffset()
306     {
307         return offset;
308     }
309 
310 
311     /**
312      * @param offset the offset to set
313      */
314     /* No qualifier */void setOffset( long offset )
315     {
316         this.offset = offset;
317     }
318 
319 
320     /**
321      * {@inheritDoc}
322      */
323     public long getLastOffset()
324     {
325         return lastOffset;
326     }
327 
328 
329     /**
330      * {@inheritDoc}
331      */
332     /* No qualifier */void setLastOffset( long lastOffset )
333     {
334         this.lastOffset = lastOffset;
335     }
336 
337 
338     /**
339      * @see Object#toString()
340      */
341     public String toString()
342     {
343         StringBuilder sb = new StringBuilder();
344 
345         sb.append( "r" ).append( revision );
346         sb.append( ", nbElems:" ).append( nbElems );
347 
348         if ( offset > 0 )
349         {
350             sb.append( ", offset:" ).append( offset );
351         }
352 
353         return sb.toString();
354     }
355 
356 
357     /**
358      * {@inheritDoc}
359      */
360     public String dumpPage( String tabs )
361     {
362         return "";
363     }
364 }