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