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.BorrowedFromLeftResult;
27  import org.apache.directory.mavibot.btree.BorrowedFromRightResult;
28  import org.apache.directory.mavibot.btree.DeleteResult;
29  import org.apache.directory.mavibot.btree.InsertResult;
30  import org.apache.directory.mavibot.btree.ModifyResult;
31  import org.apache.directory.mavibot.btree.NotPresentResult;
32  import org.apache.directory.mavibot.btree.Page;
33  import org.apache.directory.mavibot.btree.ParentPos;
34  import org.apache.directory.mavibot.btree.RemoveResult;
35  import org.apache.directory.mavibot.btree.SplitResult;
36  import org.apache.directory.mavibot.btree.Transaction;
37  import org.apache.directory.mavibot.btree.Tuple;
38  import org.apache.directory.mavibot.btree.TupleCursor;
39  import org.apache.directory.mavibot.btree.ValueCursor;
40  import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
41  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
42  
43  
44  /**
45   * A MVCC Leaf. It stores the keys and values. It does not have any children.
46   * 
47   * @param <K> The type for the Key
48   * @param <V> The type for the stored value
49   *
50   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
51   */
52  /* No qualifier */class Leaf<K, V> extends AbstractPage<K, V>
53  {
54      /** Values associated with keys */
55      protected ValueHolder<V>[] values;
56  
57  
58      /**
59       * Constructor used to create a new Leaf when we read it from a file.
60       * 
61       * @param btree The BTree this page belongs to.
62       */
63      /* No qualifier */Leaf( BTree<K, V> btree )
64      {
65          super( btree );
66      }
67  
68  
69      /**
70       * Internal constructor used to create Page instance used when a page is being copied or overflow
71       * 
72       * @param btree The BTree this page belongs to.
73       * @param revision The page revision
74       * @param nbElems The number of elements this page will contain
75       */
76      @SuppressWarnings("unchecked")
77      // Cannot create an array of generic objects
78      /* No qualifier */Leaf( BTree<K, V> btree, long revision, int nbElems )
79      {
80          super( btree, revision, nbElems );
81          values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, nbElems );
82      }
83  
84  
85      /**
86       * {@inheritDoc}
87       */
88      public InsertResult<K, V> insert( long revision, K key, V value ) throws IOException
89      {
90          // Find the key into this leaf
91          int pos = findPos( key );
92  
93          if ( pos < 0 )
94          {
95              // We already have the key in the page : replace the value
96              // into a copy of this page, unless the page has already be copied
97              int index = -( pos + 1 );
98  
99              // Replace the existing value in a copy of the current page
100             InsertResult<K, V> result = replaceElement( revision, key, value, index );
101 
102             return result;
103         }
104 
105         // The key is not present in the leaf. We have to add it in the page
106         if ( nbElems < btree.getPageSize() )
107         {
108             // The current page is not full, it can contain the added element.
109             // We insert it into a copied page and return the result
110             Page<K, V> modifiedPage = addElement( revision, key, value, pos );
111 
112             InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
113             result.addCopiedPage( this );
114 
115             return result;
116         }
117         else
118         {
119             // The Page is already full : we split it and return the overflow element,
120             // after having created two pages.
121             InsertResult<K, V> result = addAndSplit( revision, key, value, pos );
122             result.addCopiedPage( this );
123 
124             return result;
125         }
126     }
127 
128 
129     /**
130      * {@inheritDoc}
131      */
132     @SuppressWarnings("unchecked")
133     public DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos )
134         throws IOException
135     {
136         // Check that the leaf is not empty
137         if ( nbElems == 0 )
138         {
139             // Empty leaf
140             return NotPresentResult.NOT_PRESENT;
141         }
142 
143         // Find the key in the page
144         int pos = findPos( key );
145 
146         if ( pos >= 0 )
147         {
148             // Not found : return the not present result.
149             return NotPresentResult.NOT_PRESENT;
150         }
151 
152         // Get the removed element
153         Tuple<K, V> removedElement = null;
154 
155         // flag to detect if a key was completely removed
156         boolean keyRemoved = false;
157 
158         int index = -( pos + 1 );
159 
160         ValueHolder<V> valueHolder = values[index];
161 
162         if ( value == null )
163         {
164             // we have to delete the whole value
165             removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // the entire value was removed
166             keyRemoved = true;
167         }
168         else
169         {
170             if ( valueHolder.contains( value ) )
171             {
172                 keyRemoved = ( valueHolder.size() == 1 );
173 
174                 removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // only one value was removed
175             }
176             else
177             {
178                 return NotPresentResult.NOT_PRESENT;
179             }
180         }
181 
182         Leaf<K, V> newLeaf = null;
183 
184         if ( keyRemoved )
185         {
186             // No value, we can remove the key
187             newLeaf = new Leaf<K, V>( btree, revision, nbElems - 1 );
188         }
189         else
190         {
191             // Copy the page as we will delete a value from a ValueHolder
192             newLeaf = new Leaf<K, V>( btree, revision, nbElems );
193         }
194 
195         // Create the result
196         DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );
197 
198         // If the parent is null, then this page is the root page.
199         if ( parent == null )
200         {
201             // Just remove the entry if it's present, or replace it if we have more than one value in the ValueHolder
202             copyAfterRemovingElement( keyRemoved, value, newLeaf, index );
203 
204             // The current page is added in the copied page list
205             defaultResult.addCopiedPage( this );
206 
207             return defaultResult;
208         }
209         else if ( keyRemoved )
210         {
211             // The current page is not the root. Check if the leaf has more than N/2
212             // elements
213             int halfSize = btree.getPageSize() / 2;
214 
215             if ( nbElems == halfSize )
216             {
217                 // We have to find a sibling now, and either borrow an entry from it
218                 // if it has more than N/2 elements, or to merge the two pages.
219                 // Check in both next and previous page, if they have the same parent
220                 // and select the biggest page with the same parent to borrow an element.
221                 int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
222                 Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue( btree ) );
223 
224                 if ( sibling.getNbElems() == halfSize )
225                 {
226                     // We will merge the current page with its sibling
227                     DeleteResult<K, V> result = mergeWithSibling( removedElement, revision, sibling,
228                         ( siblingPos < parentPos ), index );
229 
230                     return result;
231                 }
232                 else
233                 {
234                     // We can borrow the element from the left sibling
235                     if ( siblingPos < parentPos )
236                     {
237                         DeleteResult<K, V> result = borrowFromLeft( removedElement, revision, sibling, index );
238 
239                         return result;
240                     }
241                     else
242                     {
243                         // Borrow from the right sibling
244                         DeleteResult<K, V> result = borrowFromRight( removedElement, revision, sibling, index );
245 
246                         return result;
247                     }
248                 }
249             }
250             else
251             {
252                 // The page has more than N/2 elements.
253                 // We simply remove the element from the page, and if it was the leftmost,
254                 // we return the new pivot (it will replace any instance of the removed
255                 // key in its parents)
256                 copyAfterRemovingElement( true, value, newLeaf, index );
257 
258                 // The current page is added in the copied page list
259                 defaultResult.addCopiedPage( this );
260 
261                 return defaultResult;
262             }
263         }
264         else
265         {
266             // Last, not least : we can copy the full page
267             // Copy the keys and the values
268             System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
269             System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
270             
271             // Replace the ValueHolder now
272             try
273             {
274                 ValueHolder<V> newValueHolder = (ValueHolder<V>)valueHolder.clone();
275                 newValueHolder.remove( value );
276                 
277                 newLeaf.values[pos] = newValueHolder;
278             }
279             catch ( CloneNotSupportedException e )
280             {
281                 // TODO Auto-generated catch block
282                 e.printStackTrace();
283             }
284 
285             // The current page is added in the copied page list
286             defaultResult.addCopiedPage( this );
287 
288             return defaultResult;
289         }
290     }
291 
292 
293     /**
294      * Merges the sibling with the current leaf, after having removed the element in the page.
295      * 
296      * @param revision The new revision
297      * @param sibling The sibling we will merge with
298      * @param isLeft Tells if the sibling is on the left or on the right
299      * @param pos The position of the removed element
300      * @return The new created leaf containing the sibling and the old page.
301      * @throws IOException If we have an error while trying to access the page
302      */
303     private DeleteResult<K, V> mergeWithSibling( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling,
304         boolean isLeft, int pos )
305         throws EndOfFileExceededException, IOException
306     {
307         // Create the new page. It will contain N - 1 elements (the maximum number)
308         // as we merge two pages that contain N/2 elements minus the one we remove
309         Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, btree.getPageSize() - 1 );
310 
311         if ( isLeft )
312         {
313             // The sibling is on the left
314             // Copy all the elements from the sibling first
315             System.arraycopy( sibling.keys, 0, newLeaf.keys, 0, sibling.nbElems );
316             System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
317 
318             // Copy all the elements from the page up to the deletion position
319             System.arraycopy( keys, 0, newLeaf.keys, sibling.nbElems, pos );
320             System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos );
321 
322             // And copy the remaining elements after the deletion point
323             System.arraycopy( keys, pos + 1, newLeaf.keys, sibling.nbElems + pos, nbElems - pos - 1 );
324             System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
325         }
326         else
327         {
328             // The sibling is on the right
329             // Copy all the elements from the page up to the deletion position
330             System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
331             System.arraycopy( values, 0, newLeaf.values, 0, pos );
332 
333             // Then copy the remaining elements after the deletion point
334             System.arraycopy( keys, pos + 1, newLeaf.keys, pos, nbElems - pos - 1 );
335             System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - pos - 1 );
336 
337             // And copy all the elements from the sibling
338             System.arraycopy( sibling.keys, 0, newLeaf.keys, nbElems - 1, sibling.nbElems );
339             System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
340         }
341 
342         // And create the result
343         DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( newLeaf,
344             removedElement );
345 
346         result.addCopiedPage( this );
347         result.addCopiedPage( sibling );
348 
349         return result;
350     }
351 
352 
353     /**
354      * Borrows an element from the left sibling, creating a new sibling with one
355      * less element and creating a new page where the element to remove has been
356      * deleted and the borrowed element added on the left.
357      * 
358      * @param revision The new revision for all the pages
359      * @param sibling The left sibling
360      * @param pos The position of the element to remove
361      * @return The resulting pages
362      * @throws IOException If we have an error while trying to access the page 
363      */
364     private DeleteResult<K, V> borrowFromLeft( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling, int pos )
365         throws IOException
366     {
367         // The sibling is on the left, borrow the rightmost element
368         K siblingKey = sibling.keys[sibling.getNbElems() - 1].getKey();
369         ValueHolder<V> siblingValue = sibling.values[sibling.getNbElems() - 1];
370 
371         // Create the new sibling, with one less element at the end
372         Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
373 
374         // Create the new page and add the new element at the beginning
375         // First copy the current page, with the same size
376         Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
377 
378         // Insert the borrowed element
379         newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
380         newLeaf.values[0] = siblingValue;
381 
382         // Copy the keys and the values up to the insertion position,
383         System.arraycopy( keys, 0, newLeaf.keys, 1, pos );
384         System.arraycopy( values, 0, newLeaf.values, 1, pos );
385 
386         // And copy the remaining elements
387         System.arraycopy( keys, pos + 1, newLeaf.keys, pos + 1, keys.length - pos - 1 );
388         System.arraycopy( values, pos + 1, newLeaf.values, pos + 1, values.length - pos - 1 );
389 
390         DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf, newSibling, removedElement );
391 
392         // Add the copied pages to the list
393         result.addCopiedPage( this );
394         result.addCopiedPage( sibling );
395 
396         return result;
397     }
398 
399 
400     /**
401      * Borrows an element from the right sibling, creating a new sibling with one
402      * less element and creating a new page where the element to remove has been
403      * deleted and the borrowed element added on the right.
404      * 
405      * @param revision The new revision for all the pages
406      * @param sibling The right sibling
407      * @param pos The position of the element to remove
408      * @return The resulting pages
409      * @throws IOException If we have an error while trying to access the page 
410      */
411     private DeleteResult<K, V> borrowFromRight( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling, int pos )
412         throws IOException
413     {
414         // The sibling is on the left, borrow the rightmost element
415         K siblingKey = sibling.keys[0].getKey();
416         ValueHolder<V> siblingHolder = sibling.values[0];
417 
418         // Create the new sibling
419         Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
420 
421         // Copy the keys and the values from 1 to N in the new sibling
422         System.arraycopy( sibling.keys, 1, newSibling.keys, 0, sibling.nbElems - 1 );
423         System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
424 
425         // Create the new page and add the new element at the end
426         // First copy the current page, with the same size
427         Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
428 
429         // Insert the borrowed element at the end
430         newLeaf.keys[nbElems - 1] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
431         newLeaf.values[nbElems - 1] = siblingHolder;
432 
433         // Copy the keys and the values up to the deletion position,
434         System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
435         System.arraycopy( values, 0, newLeaf.values, 0, pos );
436 
437         // And copy the remaining elements
438         System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
439         System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
440 
441         DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newLeaf, newSibling, removedElement );
442 
443         // Add the copied pages to the list
444         result.addCopiedPage( this );
445         result.addCopiedPage( sibling );
446 
447         return result;
448     }
449 
450 
451     /**
452      * Copies the elements of the current page to a new page
453      *
454      * @param keyRemoved a flag stating if the key was removed
455      * @param newLeaf The new page into which the remaining keys and values will be copied
456      * @param pos The position into the page of the element to remove
457      * @throws IOException If we have an error while trying to access the page
458      */
459     private void copyAfterRemovingElement( boolean keyRemoved, V removedValue, Leaf<K, V> newLeaf, int pos ) throws IOException
460     {
461         if ( keyRemoved )
462         {
463             // Deal with the special case of a page with only one element by skipping
464             // the copy, as we won't have any remaining  element in the page
465             if ( nbElems == 1 )
466             {
467                 return;
468             }
469 
470             // Copy the keys and the values up to the insertion position
471             System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
472             System.arraycopy( values, 0, newLeaf.values, 0, pos );
473 
474             // And copy the elements after the position
475             System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
476             System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
477         }
478         else
479         // one of the many values of the same key was removed, no change in the number of keys
480         {
481             System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
482             System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
483             
484             // We still have to clone the modified value holder
485             ValueHolder<V> valueHolder = newLeaf.values[pos];
486             
487             try
488             {
489                 ValueHolder<V> newValueHolder = (ValueHolder<V>)valueHolder.clone();
490                 
491                 newValueHolder.remove( removedValue );
492                 
493                 newLeaf.values[pos] = newValueHolder;
494             }
495             catch ( CloneNotSupportedException e )
496             {
497                 // TODO Auto-generated catch block
498                 e.printStackTrace();
499             }
500         }
501     }
502 
503 
504     /**
505      * {@inheritDoc}
506      */
507     public V get( K key ) throws KeyNotFoundException, IOException
508     {
509         int pos = findPos( key );
510 
511         if ( pos < 0 )
512         {
513             ValueHolder<V> valueHolder = values[-( pos + 1 )];
514 
515             ValueCursor<V> cursor = valueHolder.getCursor();
516 
517             cursor.beforeFirst();
518 
519             if ( cursor.hasNext() )
520             {
521                 V value = cursor.next();
522 
523                 return value;
524             }
525             else
526             {
527                 return null;
528             }
529         }
530         else
531         {
532             throw KEY_NOT_FOUND_EXCEPTION;
533         }
534     }
535 
536 
537     /**
538      * {@inheritDoc}
539      */
540     /* No qualifier */KeyHolder<K> getKeyHolder( int pos )
541     {
542         if ( pos < nbElems )
543         {
544             return keys[pos];
545         }
546         else
547         {
548             return null;
549         }
550     }
551 
552 
553     /**
554      * {@inheritDoc}
555      */
556     @Override
557     public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
558     {
559         if ( !btree.isAllowDuplicates() )
560         {
561             throw new IllegalArgumentException( "Duplicates are not allowed in this tree" );
562         }
563 
564         int pos = findPos( key );
565 
566         if ( pos < 0 )
567         {
568             ValueHolder<V> valueHolder = values[-( pos + 1 )];
569 
570             return valueHolder.getCursor();
571         }
572         else
573         {
574             throw KEY_NOT_FOUND_EXCEPTION;
575         }
576     }
577 
578 
579     /**
580      * {@inheritDoc}
581      */
582     public boolean hasKey( K key )
583     {
584         int pos = findPos( key );
585 
586         if ( pos < 0 )
587         {
588             return true;
589         }
590 
591         return false;
592     }
593 
594 
595     @Override
596     public boolean contains( K key, V value ) throws IOException
597     {
598         int pos = findPos( key );
599 
600         if ( pos < 0 )
601         {
602             ValueHolder<V> valueHolder = values[-( pos + 1 )];
603 
604             return valueHolder.contains( value );
605         }
606         else
607         {
608             return false;
609         }
610     }
611 
612 
613     /**
614      * {@inheritDoc}
615      */
616     public ValueHolder<V> getValue( int pos )
617     {
618         if ( pos < nbElems )
619         {
620             return values[pos];
621         }
622         else
623         {
624             return null;
625         }
626     }
627 
628 
629     /**
630      * Sets the value at a give position
631      * @param pos The position in the values array
632      * @param value the value to inject
633      */
634     public void setValue( int pos, ValueHolder<V> value )
635     {
636         values[pos] = value;
637     }
638 
639 
640     /**
641      * {@inheritDoc}
642      */
643     public TupleCursor<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
644     {
645         int pos = findPos( key );
646         TupleCursor<K, V> cursor = null;
647 
648         if ( pos < 0 )
649         {
650             pos = -( pos + 1 );
651 
652             // Start at the beginning of the page
653             ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
654             
655             // Create the value cursor
656             parentPos.valueCursor = values[pos].getCursor();
657 
658             stack[depth] = parentPos;
659 
660             cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
661         }
662         else
663         {
664             // The key has not been found. Select the value just above, if we have one
665             if ( pos < nbElems )
666             {
667                 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
668 
669                 // Create the value cursor
670                 parentPos.valueCursor = values[pos].getCursor();
671 
672                 stack[depth] = parentPos;
673 
674                 cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
675             }
676             else if ( nbElems > 0 )
677             {
678                 // after the last element
679                 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, nbElems - 1 );
680 
681                 // Create the value cursor
682                 parentPos.valueCursor = values[nbElems - 1].getCursor();
683                 
684                 stack[depth] = parentPos;
685 
686                 cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
687                 
688                 try
689                 {
690                     cursor.afterLast();
691                 }
692                 catch ( IOException e )
693                 {
694                     // TODO Auto-generated catch block
695                     e.printStackTrace();
696                 }
697             }
698             else
699             {
700                 // Not found, because there are no elements : return a null cursor
701                 stack[depth] = null;
702 
703                 cursor = new TupleCursorImpl<K, V>( btree, transaction, null, 0 );
704             }
705         }
706 
707         return cursor;
708     }
709 
710 
711     /**
712      * {@inheritDoc}
713      */
714     public TupleCursor<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
715     {
716         int pos = 0;
717         TupleCursor<K, V> cursor = null;
718 
719         if ( nbElems == 0 )
720         {
721             // The tree is empty, it's the root, we have nothing to return
722             stack[depth] = new ParentPos<K, V>( null, -1 );
723 
724             return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
725         }
726         else
727         {
728             // Start at the beginning of the page
729             ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
730             
731             // Create the value cursor
732             parentPos.valueCursor = values[0].getCursor();
733 
734             stack[depth] = parentPos;
735 
736             cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
737         }
738 
739         return cursor;
740     }
741 
742 
743     /**
744      * Copy the current page and all of the keys, values and children, if it's not a leaf.
745      * 
746      * @param revision The new revision
747      * @param nbElems The number of elements to copy
748      * @return The copied page
749      */
750     private Page<K, V> copy( long revision, int nbElems )
751     {
752         Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
753 
754         // Copy the keys and the values
755         System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
756 
757         // It' not enough to copy the ValueHolder, we have to clone them
758         // as ValueHolders are mutable
759         int pos = 0;
760 
761         for ( ValueHolder<V> valueHolder : values )
762         {
763             try
764             {
765                 newLeaf.values[pos++] = valueHolder.clone();
766             }
767             catch ( CloneNotSupportedException e )
768             {
769                 // TODO Auto-generated catch block
770                 e.printStackTrace();
771             }
772             
773             // Stop when we have copied nbElems values
774             if ( pos == nbElems )
775             {
776                 break;
777             }
778         }
779 
780         return newLeaf;
781     }
782 
783 
784     /**
785      * Copy the current page if needed, and replace the value at the position we have found the key.
786      * 
787      * @param revision The new page revision
788      * @param key The new key
789      * @param value the new value
790      * @param pos The position of the key in the page
791      * @return The copied page
792      * @throws IOException If we have an error while trying to access the page
793      */
794     private InsertResult<K, V> replaceElement( long revision, K key, V value, int pos )
795         throws IOException
796     {
797         Leaf<K, V> newLeaf = this;
798 
799         if ( this.revision != revision )
800         {
801             // The page hasn't been modified yet, we need to copy it first
802             newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
803         }
804 
805         // Get the previous value from the leaf (it's a copy)
806         ValueHolder<V> valueHolder = newLeaf.values[pos];
807         V replacedValue = null;
808 
809         if ( !valueHolder.contains( value ) )
810         {
811             valueHolder.add( value );
812             newLeaf.values[pos] = valueHolder;
813         }
814         else
815         {
816             // As strange as it sounds, we need to remove the value to reinject it.
817             // There are cases where the value retrieval just use one part of the
818             // value only (typically for LDAP Entries, where we use the DN)
819             replacedValue = valueHolder.remove( value );
820             valueHolder.add( value );
821         }
822 
823         // Create the result
824         InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue );
825         result.addCopiedPage( this );
826 
827         return result;
828     }
829 
830 
831     /**
832      * Adds a new <K, V> into a copy of the current page at a given position. We return the
833      * modified page. The new page will have one more element than the current page.
834      * 
835      * @param revision The revision of the modified page
836      * @param key The key to insert
837      * @param value The value to insert
838      * @param pos The position into the page
839      * @return The modified page with the <K,V> element added
840      */
841     private Page<K, V> addElement( long revision, K key, V value, int pos )
842     {
843         // First copy the current page, but add one element in the copied page
844         Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
845 
846         // Create the value holder
847         ValueHolder<V> valueHolder = btree.createValueHolder( value );
848 
849         // Deal with the special case of an empty page
850         if ( nbElems == 0 )
851         {
852             newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
853 
854             newLeaf.values[0] = valueHolder;
855         }
856         else
857         {
858             // Copy the keys and the values up to the insertion position
859             System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
860             System.arraycopy( values, 0, newLeaf.values, 0, pos );
861 
862             // Add the new element
863             newLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
864             newLeaf.values[pos] = valueHolder;
865 
866             // And copy the remaining elements
867             System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length - pos );
868             System.arraycopy( values, pos, newLeaf.values, pos + 1, values.length - pos );
869         }
870 
871         return newLeaf;
872     }
873 
874 
875     /**
876      * Split a full page into two new pages, a left, a right and a pivot element. The new pages will
877      * each contains half of the original elements. <br/>
878      * The pivot will be computed, depending on the place
879      * we will inject the newly added element. <br/>
880      * If the newly added element is in the middle, we will use it
881      * as a pivot. Otherwise, we will use either the last element in the left page if the element is added
882      * on the left, or the first element in the right page if it's added on the right.
883      * 
884      * @param revision The new revision for all the created pages
885      * @param key The key to add
886      * @param value The value to add
887      * @param pos The position of the insertion of the new element
888      * @return An OverflowPage containing the pivot, and the new left and right pages
889      */
890     private InsertResult<K, V> addAndSplit( long revision, K key, V value, int pos )
891     {
892         int middle = btree.getPageSize() >> 1;
893         Leaf<K, V> leftLeaf = null;
894         Leaf<K, V> rightLeaf = null;
895         ValueHolder<V> valueHolder = btree.createValueHolder( value );
896 
897         // Determinate where to store the new value
898         if ( pos <= middle )
899         {
900             // The left page will contain the new value
901             leftLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
902 
903             // Copy the keys and the values up to the insertion position
904             System.arraycopy( keys, 0, leftLeaf.keys, 0, pos );
905             System.arraycopy( values, 0, leftLeaf.values, 0, pos );
906 
907             // Add the new element
908             leftLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
909             leftLeaf.values[pos] = valueHolder;
910 
911             // And copy the remaining elements
912             System.arraycopy( keys, pos, leftLeaf.keys, pos + 1, middle - pos );
913             System.arraycopy( values, pos, leftLeaf.values, pos + 1, middle - pos );
914 
915             // Now, create the right page
916             rightLeaf = new Leaf<K, V>( btree, revision, middle );
917 
918             // Copy the keys and the values in the right page
919             System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
920             System.arraycopy( values, middle, rightLeaf.values, 0, middle );
921         }
922         else
923         {
924             // Create the left page
925             leftLeaf = new Leaf<K, V>( btree, revision, middle );
926 
927             // Copy all the element into the left page
928             System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
929             System.arraycopy( values, 0, leftLeaf.values, 0, middle );
930 
931             // Now, create the right page
932             rightLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
933 
934             int rightPos = pos - middle;
935 
936             // Copy the keys and the values up to the insertion position
937             System.arraycopy( keys, middle, rightLeaf.keys, 0, rightPos );
938             System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
939 
940             // Add the new element
941             rightLeaf.keys[rightPos] = new KeyHolder<K>( btree.getKeySerializer(), key );
942             rightLeaf.values[rightPos] = valueHolder;
943 
944             // And copy the remaining elements
945             System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems - pos );
946             System.arraycopy( values, pos, rightLeaf.values, rightPos + 1, nbElems - pos );
947         }
948 
949         // Get the pivot
950         K pivot = rightLeaf.keys[0].getKey();
951 
952         if ( pivot == null )
953         {
954             pivot = rightLeaf.keys[0].getKey();
955         }
956 
957         // Create the result
958         InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
959 
960         return result;
961     }
962 
963 
964     /**
965      * {@inheritDoc}
966      */
967     public K getLeftMostKey()
968     {
969         return keys[0].getKey();
970     }
971 
972 
973     /**
974      * {@inheritDoc}
975      */
976     public K getRightMostKey()
977     {
978         return keys[nbElems - 1].getKey();
979     }
980 
981 
982     /**
983      * {@inheritDoc}
984      */
985     public Tuple<K, V> findLeftMost() throws IOException
986     {
987         ValueCursor<V> cursor = values[0].getCursor();
988 
989         try
990         {
991             cursor.beforeFirst();
992             if ( cursor.hasNext() )
993             {
994                 return new Tuple<K, V>( keys[0].getKey(), cursor.next() );
995             }
996             else
997             {
998                 // Null value
999                 return new Tuple<K, V>( keys[0].getKey(), null );
1000             }
1001         }
1002         finally
1003         {
1004             cursor.close();
1005         }
1006     }
1007 
1008 
1009     /**
1010      * {@inheritDoc}
1011      */
1012     public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
1013     {
1014         ValueCursor<V> cursor = values[nbElems - 1].getCursor();
1015 
1016         try
1017         {
1018             cursor.afterLast();
1019 
1020             if ( cursor.hasPrev() )
1021             {
1022                 return new Tuple<K, V>( keys[nbElems - 1].getKey(), cursor.prev() );
1023             }
1024             else
1025             {
1026                 // Null value
1027                 return new Tuple<K, V>( keys[nbElems - 1].getKey(), null );
1028             }
1029         }
1030         finally
1031         {
1032             cursor.close();
1033         }
1034     }
1035 
1036 
1037     /**
1038      * @see Object#toString()
1039      */
1040     public String toString()
1041     {
1042         StringBuilder sb = new StringBuilder();
1043 
1044         sb.append( "Leaf[" );
1045         sb.append( super.toString() );
1046 
1047         sb.append( "] -> {" );
1048 
1049         if ( nbElems > 0 )
1050         {
1051             boolean isFirst = true;
1052 
1053             for ( int i = 0; i < nbElems; i++ )
1054             {
1055                 if ( isFirst )
1056                 {
1057                     isFirst = false;
1058                 }
1059                 else
1060                 {
1061                     sb.append( ", " );
1062                 }
1063 
1064                 sb.append( "<" ).append( keys[i] ).append( "," ).append( values[i] ).append( ">" );
1065             }
1066         }
1067 
1068         sb.append( "}" );
1069 
1070         return sb.toString();
1071     }
1072 
1073 
1074     /**
1075      * {@inheritDoc}
1076      */
1077     public String dumpPage( String tabs )
1078     {
1079         StringBuilder sb = new StringBuilder();
1080 
1081         sb.append( tabs );
1082 
1083         if ( nbElems > 0 )
1084         {
1085             boolean isFirst = true;
1086 
1087             for ( int i = 0; i < nbElems; i++ )
1088             {
1089                 if ( isFirst )
1090                 {
1091                     isFirst = false;
1092                 }
1093                 else
1094                 {
1095                     sb.append( ", " );
1096                 }
1097 
1098                 sb.append( "<" ).append( keys[i] ).append( "," ).append( values[i] ).append( ">" );
1099             }
1100         }
1101 
1102         sb.append( "\n" );
1103 
1104         return sb.toString();
1105     }
1106 }