View Javadoc

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