View Javadoc

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