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