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