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;
21  
22  
23  import java.io.IOException;
24  import java.lang.reflect.Array;
25  
26  import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
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      /** Keys of children nodes */
45      protected KeyHolder<K>[] keys;
46  
47      /** Children pages associated with keys. */
48      protected PageHolder<K, V>[] children;
49  
50      /** The number of current values in the Page */
51      protected int nbElems;
52  
53      /** This BPage's revision */
54      protected long revision;
55  
56      /** The first {@link PageIO} storing the serialized Page on disk */
57      protected long offset = -1L;
58  
59      /** The last {@link PageIO} storing the serialized Page on disk */
60      protected long lastOffset = -1L;
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       * {@inheritDoc}
90       */
91      public int getNbElems()
92      {
93          return nbElems;
94      }
95  
96  
97      /**
98       * Sets the number of element in this page
99       * @param nbElems The number of elements
100      */
101     /* no qualifier */void setNbElems( int nbElems )
102     {
103         this.nbElems = nbElems;
104     }
105 
106 
107     /**
108      * {@inheritDoc}
109      */
110     public K getKey( int pos )
111     {
112         if ( ( pos < nbElems ) && ( keys[pos] != null ) )
113         {
114             return keys[pos].getKey();
115         }
116         else
117         {
118             return null;
119         }
120     }
121 
122 
123     /**
124      * {@inheritDoc}
125      */
126     @Override
127     public boolean hasKey( K key ) throws IOException
128     {
129         int pos = findPos( key );
130 
131         if ( pos < 0 )
132         {
133             // Here, if we have found the key in the node, then we must go down into
134             // the right child, not the left one
135             return children[-pos].getValue().hasKey( key );
136         }
137         else
138         {
139             Page<K, V> page = children[pos].getValue();
140 
141             return page.hasKey( key );
142         }
143     }
144 
145 
146     /**
147      * {@inheritDoc}
148      */
149     /* no qualifier */Page<K, V> getReference( int pos ) throws IOException
150     {
151         if ( pos < nbElems + 1 )
152         {
153             if ( children[pos] != null )
154             {
155                 return children[pos].getValue();
156             }
157             else
158             {
159                 return null;
160             }
161         }
162         else
163         {
164             return null;
165         }
166     }
167 
168 
169     /**
170      * {@inheritDoc}
171      */
172     public TupleCursor<K, V> browse( K key, ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
173         throws IOException
174     {
175         int pos = findPos( key );
176 
177         if ( pos < 0 )
178         {
179             pos = -pos;
180         }
181 
182         // We first stack the current page
183         stack[depth++] = new ParentPos<K, V>( this, pos );
184 
185         Page<K, V> page = children[pos].getValue();
186 
187         return page.browse( key, transaction, stack, depth );
188     }
189 
190 
191     /**
192      * {@inheritDoc}
193      */
194     @Override
195     public boolean contains( K key, V value ) throws IOException
196     {
197         int pos = findPos( key );
198 
199         if ( pos < 0 )
200         {
201             // Here, if we have found the key in the node, then we must go down into
202             // the right child, not the left one
203             return children[-pos].getValue().contains( key, value );
204         }
205         else
206         {
207             return children[pos].getValue().contains( key, value );
208         }
209     }
210 
211 
212     /**
213      * {@inheritDoc}
214      */
215     public DeleteResult<K, V> delete( K key, V value, long revision ) throws IOException
216     {
217         return delete( key, value, revision, null, -1 );
218     }
219 
220 
221     /**
222      * The real delete implementation. It can be used for internal deletion in the B-tree.
223      *
224      * @param key The key to delete
225      * @param value The value to delete
226      * @param revision The revision for which we want to delete a tuple
227      * @param parent The parent page
228      * @param parentPos The position of this page in the parent page
229      * @return The result
230      * @throws IOException If we had an issue while processing the deletion
231      */
232     /* no qualifier */abstract DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent,
233         int parentPos )
234         throws IOException;
235 
236 
237     /**
238      * {@inheritDoc}
239      */
240     public V get( K key ) throws IOException, KeyNotFoundException
241     {
242         int pos = findPos( key );
243 
244         if ( pos < 0 )
245         {
246             // Here, if we have found the key in the node, then we must go down into
247             // the right child, not the left one
248             return children[-pos].getValue().get( key );
249         }
250         else
251         {
252             return children[pos].getValue().get( key );
253         }
254     }
255 
256 
257     /**
258      * {@inheritDoc}
259      */
260     /* no qualifier */Page<K, V> getPage( int pos )
261     {
262         if ( ( pos >= 0 ) && ( pos < children.length ) )
263         {
264             if ( children[pos] != null )
265             {
266                 return children[pos].getValue();
267             }
268             else
269             {
270                 return null;
271             }
272         }
273         else
274         {
275             return null;
276         }
277     }
278 
279 
280     /**
281      * Inject a pageHolder into the node, at a given position
282      * 
283      * @param pos The position of the added pageHolder
284      * @param pageHolder The pageHolder to add
285      */
286     /* no qualifier */void setPageHolder( int pos, PageHolder<K, V> pageHolder )
287     {
288         if ( ( pos >= 0 ) && ( pos < children.length ) )
289         {
290             children[pos] = pageHolder;
291         }
292     }
293 
294 
295     /**
296      * {@inheritDoc}
297      */
298     @Override
299     public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
300     {
301         int pos = findPos( key );
302 
303         if ( pos < 0 )
304         {
305             // Here, if we have found the key in the node, then we must go down into
306             // the right child, not the left one
307             return children[-pos].getValue().getValues( key );
308         }
309         else
310         {
311             return children[pos].getValue().getValues( key );
312         }
313     }
314 
315 
316     /**
317      * Sets the value at a give position
318      * @param pos The position in the values array
319      * @param value the value to inject
320      */
321     /* no qualifier */void setValue( int pos, ValueHolder<V> value )
322     {
323         // Implementation in the leaves
324     }
325 
326 
327     /**
328      * {@inheritDoc}
329      */
330     public TupleCursor<K, V> browse( ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
331         throws IOException
332     {
333         stack[depth++] = new ParentPos<K, V>( this, 0 );
334 
335         Page<K, V> page = children[0].getValue();
336 
337         return page.browse( transaction, stack, depth );
338     }
339 
340 
341     /**
342      * {@inheritDoc}
343      */
344     public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
345         throws IOException
346     {
347         stack[depth++] = new ParentPos( this, 0 );
348 
349         Page<K, V> page = children[0].getValue();
350 
351         return page.browseKeys( transaction, stack, depth );
352     }
353 
354 
355     /**
356      * Selects the sibling (the previous or next page with the same parent) which has
357      * the more element assuming it's above N/2
358      *
359      * @param parent The parent of the current page
360      * @param The position of the current page reference in its parent
361      * @return The position of the sibling, or -1 if we have'nt found any sibling
362      * @throws IOException If we have an error while trying to access the page
363      */
364     protected int selectSibling( Page<K, V> parent, int parentPos ) throws IOException
365     {
366         if ( parentPos == 0 )
367         {
368             // The current page is referenced on the left of its parent's page :
369             // we will not have a previous page with the same parent
370             return 1;
371         }
372 
373         if ( parentPos == parent.getNbElems() )
374         {
375             // The current page is referenced on the right of its parent's page :
376             // we will not have a next page with the same parent
377             return parentPos - 1;
378         }
379 
380         Page<K, V> prevPage = ( ( AbstractPage<K, V> ) parent ).getPage( parentPos - 1 );
381         Page<K, V> nextPage = ( ( AbstractPage<K, V> ) parent ).getPage( parentPos + 1 );
382 
383         int prevPageSize = prevPage.getNbElems();
384         int nextPageSize = nextPage.getNbElems();
385 
386         if ( prevPageSize >= nextPageSize )
387         {
388             return parentPos - 1;
389         }
390         else
391         {
392             return parentPos + 1;
393         }
394     }
395 
396 
397     /**
398      * {@inheritDoc}
399      */
400     public K getLeftMostKey()
401     {
402         return keys[0].getKey();
403     }
404 
405 
406     /**
407      * {@inheritDoc}
408      */
409     public K getRightMostKey()
410     {
411         return keys[nbElems - 1].getKey();
412     }
413 
414 
415     /**
416      * @return the offset of the first {@link PageIO} which stores the Page on disk.
417      */
418     /* no qualifier */long getOffset()
419     {
420         return offset;
421     }
422 
423 
424     /**
425      * @param offset the offset to set
426      */
427     /* no qualifier */void setOffset( long offset )
428     {
429         this.offset = offset;
430     }
431 
432 
433     /**
434      * @return the offset of the last {@link PageIO} which stores the Page on disk.
435      */
436     /* no qualifier */long getLastOffset()
437     {
438         return lastOffset;
439     }
440 
441 
442     /**
443      * {@inheritDoc}
444      */
445     /* no qualifier */void setLastOffset( long lastOffset )
446     {
447         this.lastOffset = lastOffset;
448     }
449 
450 
451     /**
452      * @return the keys
453      */
454     /* no qualifier */KeyHolder<K>[] getKeys()
455     {
456         return keys;
457     }
458 
459 
460     /**
461      * Sets the key at a give position
462      *
463      * @param pos The position in the keys array
464      * @param key the key to inject
465      */
466     /* no qualifier */void setKey( int pos, KeyHolder<K> key )
467     {
468         keys[pos] = key;
469     }
470 
471 
472     /**
473      * @param revision the keys to set
474      */
475     /* no qualifier */void setKeys( KeyHolder<K>[] keys )
476     {
477         this.keys = keys;
478     }
479 
480 
481     /**
482      * {@inheritDoc}
483      */
484     /* no qualifier */ValueHolder<V> getValue( int pos )
485     {
486         // Node don't have values. Leaf.getValue() will return the value
487         return null;
488     }
489 
490 
491     /**
492      * @return the revision
493      */
494     public long getRevision()
495     {
496         return revision;
497     }
498 
499 
500     /**
501      * @param revision the revision to set
502      */
503     /* no qualifier */void setRevision( long revision )
504     {
505         this.revision = revision;
506     }
507 
508 
509     /**
510      * Compares two keys
511      *
512      * @param key1 The first key
513      * @param key2 The second key
514      * @return -1 if the first key is above the second one, 1 if it's below, and 0
515      * if the two keys are equal
516      */
517     protected final int compare( K key1, K key2 )
518     {
519         if ( key1 == key2 )
520         {
521             return 0;
522         }
523 
524         if ( key1 == null )
525         {
526             return 1;
527         }
528 
529         if ( key2 == null )
530         {
531             return -1;
532         }
533 
534         return btree.getKeyComparator().compare( key1, key2 );
535     }
536 
537 
538     /**
539      * Finds the position of the given key in the page. If we have found the key,
540      * we will return its position as a negative value.
541      * <p/>
542      * Assuming that the array is zero-indexed, the returned value will be : <br/>
543      *   position = - ( position + 1)
544      * <br/>
545      * So for the following table of keys : <br/>
546      * <pre>
547      * +---+---+---+---+
548      * | b | d | f | h |
549      * +---+---+---+---+
550      *   0   1   2   3
551      * </pre>
552      * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
553      * Computing the real position is just a matter to get -(position++).
554      * <p/>
555      * If we don't find the key in the table, we will return the position of the key
556      * immediately above the key we are looking for. <br/>
557      * For instance, looking for :
558      * <ul>
559      * <li>'a' will return 0</li>
560      * <li>'b' will return -1</li>
561      * <li>'c' will return 1</li>
562      * <li>'d' will return -2</li>
563      * <li>'e' will return 2</li>
564      * <li>'f' will return -3</li>
565      * <li>'g' will return 3</li>
566      * <li>'h' will return -4</li>
567      * <li>'i' will return 4</li>
568      * </ul>
569      *
570      *
571      * @param key The key to find
572      * @return The position in the page.
573      */
574     public int findPos( K key )
575     {
576         // Deal with the special key where we have an empty page
577         if ( nbElems == 0 )
578         {
579             return 0;
580         }
581 
582         int min = 0;
583         int max = nbElems - 1;
584 
585         // binary search
586         while ( min < max )
587         {
588             int middle = ( min + max + 1 ) >> 1;
589 
590             int comp = compare( keys[middle].getKey(), key );
591 
592             if ( comp < 0 )
593             {
594                 min = middle + 1;
595             }
596             else if ( comp > 0 )
597             {
598                 max = middle - 1;
599             }
600             else
601             {
602                 // Special case : the key already exists,
603                 // we can return immediately. The value will be
604                 // negative, and as the index may be 0, we subtract 1
605                 return -( middle + 1 );
606             }
607         }
608 
609         // Special case : we don't know if the key is present
610         int comp = compare( keys[max].getKey(), key );
611 
612         if ( comp == 0 )
613         {
614             return -( max + 1 );
615         }
616         else
617         {
618             if ( comp < 0 )
619             {
620                 return max + 1;
621             }
622             else
623             {
624                 return max;
625             }
626         }
627     }
628 
629 
630     /**
631      * {@inheritDoc}
632      */
633     public Tuple<K, V> findLeftMost() throws EndOfFileExceededException, IOException
634     {
635         return children[0].getValue().findLeftMost();
636     }
637 
638 
639     /**
640      * {@inheritDoc}
641      */
642     public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
643     {
644         return children[nbElems].getValue().findRightMost();
645     }
646 
647 
648     /**
649      * @return the btree
650      */
651     public BTree<K, V> getBtree()
652     {
653         return btree;
654     }
655 
656 
657     /**
658      * {@inheritDoc}
659      */
660     public String dumpPage( String tabs )
661     {
662         StringBuilder sb = new StringBuilder();
663 
664         if ( nbElems > 0 )
665         {
666             // Start with the first child
667             sb.append( children[0].getValue().dumpPage( tabs + "    " ) );
668 
669             for ( int i = 0; i < nbElems; i++ )
670             {
671                 sb.append( tabs );
672                 sb.append( "<" );
673                 sb.append( getKey( i ) ).append( ">\n" );
674                 sb.append( children[i + 1].getValue().dumpPage( tabs + "    " ) );
675             }
676         }
677 
678         return sb.toString();
679     }
680 
681 
682     /**
683      * @see Object#toString()
684      */
685     public String toString()
686     {
687         StringBuilder sb = new StringBuilder();
688 
689         sb.append( "r" ).append( revision );
690         sb.append( ", nbElems:" ).append( nbElems );
691 
692         if ( offset > 0 )
693         {
694             sb.append( ", offset:" ).append( offset );
695         }
696 
697         return sb.toString();
698     }
699 }