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