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