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