You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2013/09/30 08:32:28 UTC
svn commit: r1527458 [5/14] - in /directory/mavibot/trunk/mavibot: img/
src/main/java/org/apache/directory/mavibot/btree/
src/main/java/org/apache/directory/mavibot/btree/managed/
src/main/java/org/apache/directory/mavibot/btree/memory/ src/main/java/o...
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,1322 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.managed;
+
+
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+
+
+/**
+ * A MVCC Node. It stores the keys and references to its children page. It does not
+ * contain any value.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class Node<K, V> extends AbstractPage<K, V>
+{
+ /** Children pages associated with keys. */
+ protected ElementHolder<Page<K, V>, K, V>[] children;
+
+
+ /**
+ * Creates a new Node which will contain only one key, with references to
+ * a left and right page. This is a specific constructor used by the btree
+ * when the root was full when we added a new value.
+ *
+ * @param btree the parent BTree
+ * @param revision the Node revision
+ * @param nbElems The number of elements in this Node
+ */
+ @SuppressWarnings("unchecked")
+ /* No qualifier */Node( BTree<K, V> btree, long revision, int nbElems )
+ {
+ super( btree, revision, nbElems );
+
+ // Create the children array
+ children = ( ElementHolder<Page<K, V>, K, V>[] ) Array.newInstance( ElementHolder.class, nbElems + 1 );
+ }
+
+
+ /**
+ * Creates a new Node which will contain only one key, with references to
+ * a left and right page. This is a specific constructor used by the btree
+ * when the root was full when we added a new value.
+ *
+ * @param btree the parent BTree
+ * @param revision the Node revision
+ * @param key The new key
+ * @param leftPage The left page
+ * @param rightPage The right page
+ */
+ @SuppressWarnings("unchecked")
+ /* No qualifier */Node( BTree<K, V> btree, long revision, K key, Page<K, V> leftPage, Page<K, V> rightPage )
+ {
+ super( btree, revision, 1 );
+
+ // Create the children array, and store the left and right children
+ children = ( CacheHolder<Page<K, V>, K, V>[] ) Array.newInstance( CacheHolder.class,
+ btree.getPageSize() + 1 );
+
+ children[0] = btree.createPageHolder( leftPage );
+ children[1] = btree.createPageHolder( rightPage );
+
+ // Create the keys array and store the pivot into it
+ // We get the type of array to create from the btree
+ // Yes, this is an hack...
+ Class<?> keyType = btree.getKeyType();
+ keys = ( K[] ) Array.newInstance( keyType, btree.getPageSize() );
+
+ keys[0] = key;
+ }
+
+
+ /**
+ * Creates a new Node which will contain only one key, with references to
+ * a left and right page. This is a specific constructor used by the btree
+ * when the root was full when we added a new value.
+ *
+ * @param btree the parent BTree
+ * @param revision the Node revision
+ * @param key The new key
+ * @param leftPage The left page
+ * @param rightPage The right page
+ */
+ @SuppressWarnings("unchecked")
+ /* No qualifier */Node( BTree<K, V> btree, long revision, K key, ElementHolder<Page<K, V>, K, V> leftPage,
+ ElementHolder<Page<K, V>, K, V> rightPage )
+ {
+ super( btree, revision, 1 );
+
+ // Create the children array, and store the left and right children
+ children = ( CacheHolder<Page<K, V>, K, V>[] ) Array.newInstance( CacheHolder.class,
+ btree.getPageSize() + 1 );
+
+ children[0] = leftPage;
+ children[1] = rightPage;
+
+ // Create the keys array and store the pivot into it
+ // We get the type of array to create from the btree
+ // Yes, this is an hack...
+ Class<?> keyType = btree.getKeyType();
+ keys = ( K[] ) Array.newInstance( keyType, btree.getPageSize() );
+
+ keys[0] = key;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public InsertResult<K, V> insert( long revision, K key, V value ) throws IOException
+ {
+ // Find the key into this leaf
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // The key has been found in the page. As it's a Node, that means
+ // we must go down in the right child to insert the value
+ pos = -( pos++ );
+ }
+
+ // Get the child page into which we will insert the <K, V> tuple
+ Page<K, V> child = children[pos].getValue( btree );
+
+ // and insert the <K, V> into this child
+ InsertResult<K, V> result = child.insert( revision, key, value );
+
+ // Ok, now, we have injected the <K, V> tuple down the tree. Let's check
+ // the result to see if we have to split the current page
+ if ( result instanceof ModifyResult )
+ {
+ // The child has been modified.
+ return replaceChild( revision, ( ModifyResult<K, V> ) result, pos );
+ }
+ else
+ {
+ // The child has been split. We have to insert the new pivot in the
+ // current page, and to reference the two new pages
+ SplitResult<K, V> splitResult = ( SplitResult<K, V> ) result;
+ K pivot = splitResult.getPivot();
+ Page<K, V> leftPage = splitResult.getLeftPage();
+ Page<K, V> rightPage = splitResult.getRightPage();
+
+ // We have to deal with the two cases :
+ // - the current page is full, we have to split it
+ // - the current page is not full, we insert the new pivot
+ if ( nbElems == btree.getPageSize() )
+ {
+ // The page is full
+ result = addAndSplit( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
+ }
+ else
+ {
+ // The page can contain the new pivot, let's insert it
+ result = insertChild( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
+ }
+
+ return result;
+ }
+ }
+
+
+ /**
+ * Modifies the current node after a remove has been done in one of its children.
+ * The node won't be merged with another node.
+ *
+ * @param removeResult The result of a remove operation
+ * @param index the position of the key, not transformed
+ * @param pos The position of the key, as a positive value
+ * @param found If the key has been found in the page
+ * @return The new result
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private RemoveResult<K, V> handleRemoveResult( RemoveResult<K, V> removeResult, int index, int pos, boolean found )
+ throws IOException
+ {
+ // Simplest case : the element has been removed from the underlying page,
+ // we just have to copy the current page an modify the reference to link to
+ // the modified page.
+ Node<K, V> newPage = copy( revision );
+
+ Page<K, V> modifiedPage = removeResult.getModifiedPage();
+
+ if ( found )
+ {
+ newPage.children[index + 1] = createHolder( modifiedPage );
+ }
+ else
+ {
+ newPage.children[index] = createHolder( modifiedPage );
+ }
+
+ if ( pos < 0 )
+ {
+ newPage.keys[index] = removeResult.getModifiedPage().getLeftMostKey();
+ }
+
+ // Modify the result and return
+ removeResult.setModifiedPage( newPage );
+ removeResult.addCopiedPage( this );
+
+ return removeResult;
+ }
+
+
+ /**
+ * Handles the removal of an element from the root page, when two of its children
+ * have been merged.
+ *
+ * @param mergedResult The merge result
+ * @param pos The position in the current root
+ * @param found Tells if the removed key is present in the root page
+ * @return The resulting root page
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private RemoveResult<K, V> handleRootRemove( MergedWithSiblingResult<K, V> mergedResult, int pos, boolean found )
+ throws IOException
+ {
+ RemoveResult<K, V> removeResult = null;
+
+ // If the current node contains only one key, then the merged result will be
+ // the new root. Deal with this case
+ if ( nbElems == 1 )
+ {
+ removeResult = new RemoveResult<K, V>( mergedResult.getCopiedPages(), mergedResult.getModifiedPage(),
+ mergedResult.getRemovedElement() );
+
+ removeResult.addCopiedPage( this );
+ }
+ else
+ {
+ // Remove the element and update the reference to the changed pages
+ removeResult = removeKey( mergedResult, revision, pos );
+ }
+
+ return removeResult;
+ }
+
+
+ /**
+ * Borrows an element from the right sibling, creating a new sibling with one
+ * less element and creating a new page where the element to remove has been
+ * deleted and the borrowed element added on the right.
+ *
+ * @param revision The new revision for all the pages
+ * @param sibling The right sibling
+ * @param pos The position of the element to remove
+ * @return The resulting pages
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> borrowFromRight( long revision, MergedWithSiblingResult<K, V> mergedResult,
+ Node<K, V> sibling, int pos ) throws IOException
+ {
+ // Create the new sibling, with one less element at the beginning
+ Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
+
+ K siblingKey = sibling.children[0].getValue( btree ).getLeftMostKey();
+
+ // Copy the keys and children of the old sibling in the new sibling
+ System.arraycopy( sibling.keys, 1, newSibling.keys, 0, newSibling.getNbElems() );
+ System.arraycopy( sibling.children, 1, newSibling.children, 0, newSibling.getNbElems() + 1 );
+
+ // Create the new page and add the new element at the end
+ // First copy the current node, with the same size
+ Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
+
+ // Copy the keys and the values up to the insertion position
+ int index = Math.abs( pos );
+
+ // Copy the key and children from sibling
+ newNode.keys[nbElems - 1] = siblingKey; // 1
+ newNode.children[nbElems] = sibling.children[0]; // 8
+
+ if ( index < 2 )
+ {
+ // Copy the keys
+ System.arraycopy( keys, 1, newNode.keys, 0, nbElems - 1 );
+
+ // Inject the modified page
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[0] = createHolder( modifiedPage );
+
+ // Copy the children
+ System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
+ }
+ else
+ {
+ if ( index > 2 )
+ {
+ // Copy the keys before the deletion point
+ System.arraycopy( keys, 0, newNode.keys, 0, index - 2 ); // 4
+ }
+
+ // Inject the new modified page key
+ newNode.keys[index - 2] = mergedResult.getModifiedPage().getLeftMostKey(); // 2
+
+ if ( index < nbElems )
+ {
+ // Copy the remaining keys after the deletion point
+ System.arraycopy( keys, index, newNode.keys, index - 1, nbElems - index ); // 3
+
+ // Copy the remaining children after the deletion point
+ System.arraycopy( children, index + 1, newNode.children, index, nbElems - index ); // 7
+ }
+
+ // Copy the children before the deletion point
+ System.arraycopy( children, 0, newNode.children, 0, index - 1 ); // 5
+
+ // Inject the modified page
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[index - 1] = createHolder( modifiedPage ); // 6
+ }
+
+ // Create the result
+ DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( mergedResult.getCopiedPages(), newNode,
+ newSibling, mergedResult.getRemovedElement() );
+
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * Borrows an element from the left sibling, creating a new sibling with one
+ * less element and creating a new page where the element to remove has been
+ * deleted and the borrowed element added on the left.
+ *
+ * @param revision The new revision for all the pages
+ * @param sibling The left sibling
+ * @param pos The position of the element to remove
+ * @return The resulting pages
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> borrowFromLeft( long revision, MergedWithSiblingResult<K, V> mergedResult,
+ Node<K, V> sibling, int pos ) throws IOException
+ {
+ // The sibling is on the left, borrow the rightmost element
+ Page<K, V> siblingChild = sibling.children[sibling.nbElems].getValue( btree );
+
+ // Create the new sibling, with one less element at the end
+ Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
+
+ // Copy the keys and children of the old sibling in the new sibling
+ System.arraycopy( sibling.keys, 0, newSibling.keys, 0, newSibling.getNbElems() );
+ System.arraycopy( sibling.children, 0, newSibling.children, 0, newSibling.getNbElems() + 1 );
+
+ // Create the new page and add the new element at the beginning
+ // First copy the current node, with the same size
+ Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
+
+ // Sets the first children
+ newNode.children[0] = createHolder( siblingChild ); //1
+
+ int index = Math.abs( pos );
+
+ if ( index < 2 )
+ {
+ newNode.keys[0] = mergedResult.getModifiedPage().getLeftMostKey();
+ System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
+
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[1] = createHolder( modifiedPage );
+ System.arraycopy( children, 2, newNode.children, 2, nbElems - 1 );
+ }
+ else
+ {
+ // Set the first key
+ newNode.keys[0] = children[0].getValue( btree ).getLeftMostKey(); //2
+
+ if ( index > 2 )
+ {
+ // Copy the keys before the deletion point
+ System.arraycopy( keys, 0, newNode.keys, 1, index - 2 ); // 4
+ }
+
+ // Inject the modified key
+ newNode.keys[index - 1] = mergedResult.getModifiedPage().getLeftMostKey(); // 3
+
+ if ( index < nbElems )
+ {
+ // Add copy the remaining keys after the deletion point
+ System.arraycopy( keys, index, newNode.keys, index, nbElems - index ); // 5
+
+ // Copy the remaining children after the insertion point
+ System.arraycopy( children, index + 1, newNode.children, index + 1, nbElems - index ); // 8
+ }
+
+ // Copy the children before the insertion point
+ System.arraycopy( children, 0, newNode.children, 1, index - 1 ); // 6
+
+ // Insert the modified page
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[index] = createHolder( modifiedPage ); // 7
+ }
+
+ // Create the result
+ DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( mergedResult.getCopiedPages(), newNode,
+ newSibling,
+ mergedResult.getRemovedElement() );
+
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * We have to merge the node with its sibling, both have N/2 elements before the element
+ * removal.
+ *
+ * @param revision The revision
+ * @param mergedResult The result of the merge
+ * @param sibling The Page we will merge the current page with
+ * @param isLeft Tells if the sibling is on the left
+ * @param pos The position of the key that has been removed
+ * @return The page resulting of the merge
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> mergeWithSibling( long revision, MergedWithSiblingResult<K, V> mergedResult,
+ Node<K, V> sibling, boolean isLeft, int pos ) throws IOException
+ {
+ // Create the new node. It will contain N - 1 elements (the maximum number)
+ // as we merge two nodes that contain N/2 elements minus the one we remove
+ Node<K, V> newNode = new Node<K, V>( btree, revision, btree.getPageSize() );
+ Tuple<K, V> removedElement = mergedResult.getRemovedElement();
+ int half = btree.getPageSize() / 2;
+ int index = Math.abs( pos );
+
+ if ( isLeft )
+ {
+ // The sibling is on the left. Copy all of its elements in the new node first
+ System.arraycopy( sibling.keys, 0, newNode.keys, 0, half ); //1
+ System.arraycopy( sibling.children, 0, newNode.children, 0, half + 1 ); //2
+
+ // Then copy all the elements up to the deletion point
+ if ( index < 2 )
+ {
+ newNode.keys[half] = mergedResult.getModifiedPage().getLeftMostKey();
+ System.arraycopy( keys, 1, newNode.keys, half + 1, half - 1 );
+
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[half + 1] = createHolder( modifiedPage );
+ System.arraycopy( children, 2, newNode.children, half + 2, half - 1 );
+ }
+ else
+ {
+ // Copy the left part of the node keys up to the deletion point
+ // Insert the new key
+ newNode.keys[half] = children[0].getValue( btree ).getLeftMostKey(); // 3
+
+ if ( index > 2 )
+ {
+ System.arraycopy( keys, 0, newNode.keys, half + 1, index - 2 ); //4
+ }
+
+ // Inject the new merged key
+ newNode.keys[half + index - 1] = mergedResult.getModifiedPage().getLeftMostKey(); //5
+
+ if ( index < half )
+ {
+ System.arraycopy( keys, index, newNode.keys, half + index, half - index ); //6
+ System.arraycopy( children, index + 1, newNode.children, half + index + 1, half - index ); //9
+ }
+
+ // Copy the children before the deletion point
+ System.arraycopy( children, 0, newNode.children, half + 1, index - 1 ); // 7
+
+ // Inject the new merged child
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[half + index] = createHolder( modifiedPage ); //8
+ }
+ }
+ else
+ {
+ // The sibling is on the right.
+ if ( index < 2 )
+ {
+ // Copy the keys
+ System.arraycopy( keys, 1, newNode.keys, 0, half - 1 );
+
+ // Insert the first child
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[0] = createHolder( modifiedPage );
+
+ // Copy the node children
+ System.arraycopy( children, 2, newNode.children, 1, half - 1 );
+ }
+ else
+ {
+ // Copy the keys and children before the deletion point
+ if ( index > 2 )
+ {
+ // Copy the first keys
+ System.arraycopy( keys, 0, newNode.keys, 0, index - 2 ); //1
+ }
+
+ // Copy the first children
+ System.arraycopy( children, 0, newNode.children, 0, index - 1 ); //6
+
+ // Inject the modified key
+ newNode.keys[index - 2] = mergedResult.getModifiedPage().getLeftMostKey(); //2
+
+ // Inject the modified children
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[index - 1] = createHolder( modifiedPage ); // 7
+
+ // Add the remaining node's key if needed
+ if ( index < half )
+ {
+ System.arraycopy( keys, index, newNode.keys, index - 1, half - index ); //5
+
+ // Add the remining children if below half
+ System.arraycopy( children, index + 1, newNode.children, index, half - index ); // 8
+ }
+ }
+
+ // Inject the new key from sibling
+ newNode.keys[half - 1] = sibling.findLeftMost().getKey(); //3
+
+ // Copy the sibling keys
+ System.arraycopy( sibling.keys, 0, newNode.keys, half, half );
+
+ // Add the sibling children
+ System.arraycopy( sibling.children, 0, newNode.children, half, half + 1 ); // 9
+ }
+
+ // And create the result
+ DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( mergedResult.getCopiedPages(), newNode,
+ removedElement );
+
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos )
+ throws IOException
+ {
+ // We first try to delete the element from the child it belongs to
+ // Find the key in the page
+ int pos = findPos( key );
+ boolean found = pos < 0;
+ int index = pos;
+ Page<K, V> child = null;
+ DeleteResult<K, V> deleteResult = null;
+
+ if ( found )
+ {
+ index = -( pos + 1 );
+ child = children[-pos].getValue( btree );
+ deleteResult = child.delete( revision, key, value, this, -pos );
+ }
+ else
+ {
+ child = children[pos].getValue( btree );
+ deleteResult = child.delete( revision, key, value, this, pos );
+ }
+
+ // If the key is not present in the tree, we simply return
+ if ( deleteResult instanceof NotPresentResult )
+ {
+ // Nothing to do...
+ return deleteResult;
+ }
+
+ // If we just modified the child, return a modified page
+ if ( deleteResult instanceof RemoveResult )
+ {
+ RemoveResult<K, V> removeResult = handleRemoveResult( ( RemoveResult<K, V> ) deleteResult, index, pos,
+ found );
+
+ return removeResult;
+ }
+
+ // If we had to borrow an element in the child, then have to update
+ // the current page
+ if ( deleteResult instanceof BorrowedFromSiblingResult )
+ {
+ RemoveResult<K, V> removeResult = handleBorrowedResult( ( BorrowedFromSiblingResult<K, V> ) deleteResult,
+ pos );
+
+ return removeResult;
+ }
+
+ // Last, not least, we have merged two child pages. We now have to remove
+ // an element from the local page, and to deal with the result.
+ if ( deleteResult instanceof MergedWithSiblingResult )
+ {
+ MergedWithSiblingResult<K, V> mergedResult = ( MergedWithSiblingResult<K, V> ) deleteResult;
+
+ // If the parent is null, then this page is the root page.
+ if ( parent == null )
+ {
+ RemoveResult<K, V> result = handleRootRemove( mergedResult, pos, found );
+
+ return result;
+ }
+
+ // We have some parent. Check if the current page is not half full
+ int halfSize = btree.getPageSize() / 2;
+
+ if ( nbElems > halfSize )
+ {
+ // The page has more than N/2 elements.
+ // We simply remove the element from the page, and if it was the leftmost,
+ // we return the new pivot (it will replace any instance of the removed
+ // key in its parents)
+ RemoveResult<K, V> result = removeKey( mergedResult, revision, pos );
+
+ return result;
+ }
+ else
+ {
+ // We will remove one element from a page that will have less than N/2 elements,
+ // which will lead to some reorganization : either we can borrow an element from
+ // a sibling, or we will have to merge two pages
+ int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
+
+ Node<K, V> sibling = ( Node<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue( btree ) );
+
+ if ( sibling.getNbElems() > halfSize )
+ {
+ // The sibling contains enough elements
+ // We can borrow the element from the sibling
+ if ( siblingPos < parentPos )
+ {
+ DeleteResult<K, V> result = borrowFromLeft( revision, mergedResult, sibling, pos );
+
+ return result;
+ }
+ else
+ {
+ // Borrow from the right
+ DeleteResult<K, V> result = borrowFromRight( revision, mergedResult, sibling, pos );
+
+ return result;
+ }
+ }
+ else
+ {
+ // We need to merge the sibling with the current page
+ DeleteResult<K, V> result = mergeWithSibling( revision, mergedResult, sibling,
+ ( siblingPos < parentPos ), pos );
+
+ return result;
+ }
+ }
+ }
+
+ // We should never reach this point
+ return null;
+ }
+
+
+ /**
+ * The deletion in a children has moved an element from one of its sibling. The key
+ * is present in the current node.
+ * @param borrowedResult The result of the deletion from the children
+ * @param pos The position the key was found in the current node
+ * @return The result
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private RemoveResult<K, V> handleBorrowedResult( BorrowedFromSiblingResult<K, V> borrowedResult, int pos )
+ throws IOException
+ {
+ Page<K, V> modifiedPage = borrowedResult.getModifiedPage();
+ Page<K, V> modifiedSibling = borrowedResult.getModifiedSibling();
+
+ Node<K, V> newPage = copy( revision );
+
+ if ( pos < 0 )
+ {
+ pos = -( pos + 1 );
+
+ if ( borrowedResult.isFromRight() )
+ {
+ // Update the keys
+ newPage.keys[pos] = modifiedPage.findLeftMost().getKey();
+ newPage.keys[pos + 1] = modifiedSibling.findLeftMost().getKey();
+
+ // Update the children
+ newPage.children[pos + 1] = createHolder( modifiedPage );
+ newPage.children[pos + 2] = createHolder( modifiedSibling );
+ }
+ else
+ {
+ // Update the keys
+ newPage.keys[pos] = modifiedPage.findLeftMost().getKey();
+
+ // Update the children
+ newPage.children[pos] = createHolder( modifiedSibling );
+ newPage.children[pos + 1] = createHolder( modifiedPage );
+ }
+ }
+ else
+ {
+ if ( borrowedResult.isFromRight() )
+ {
+ // Update the keys
+ newPage.keys[pos] = modifiedSibling.findLeftMost().getKey();
+
+ // Update the children
+ newPage.children[pos] = createHolder( modifiedPage );
+ newPage.children[pos + 1] = createHolder( modifiedSibling );
+ }
+ else
+ {
+ // Update the keys
+ newPage.keys[pos - 1] = modifiedPage.findLeftMost().getKey();
+
+ // Update the children
+ newPage.children[pos - 1] = createHolder( modifiedSibling );
+ newPage.children[pos] = createHolder( modifiedPage );
+ }
+ }
+
+ // Modify the result and return
+ RemoveResult<K, V> removeResult = new RemoveResult<K, V>( borrowedResult.getCopiedPages(), newPage,
+ borrowedResult.getRemovedElement() );
+
+ removeResult.addCopiedPage( this );
+
+ return removeResult;
+ }
+
+
+ /**
+ * Remove the key at a given position.
+ *
+ * @param mergedResult The page we will remove a key from
+ * @param revision The revision of the modified page
+ * @param pos The position into the page of the element to remove
+ * @return The modified page with the <K,V> element added
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private RemoveResult<K, V> removeKey( MergedWithSiblingResult<K, V> mergedResult, long revision, int pos )
+ throws IOException
+ {
+ // First copy the current page, but remove one element in the copied page
+ Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems - 1 );
+
+ int index = Math.abs( pos ) - 2;
+
+ //
+ if ( index < 0 )
+ {
+ // Copy the keys and the children
+ System.arraycopy( keys, 1, newNode.keys, 0, newNode.nbElems );
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[0] = createHolder( modifiedPage );
+ System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
+ }
+ else
+ {
+ // Copy the keys
+ if ( index > 0 )
+ {
+ System.arraycopy( keys, 0, newNode.keys, 0, index );
+ }
+
+ newNode.keys[index] = mergedResult.getModifiedPage().findLeftMost().getKey();
+
+ if ( index < nbElems - 2 )
+ {
+ System.arraycopy( keys, index + 2, newNode.keys, index + 1, nbElems - index - 2 );
+ }
+
+ // Copy the children
+ System.arraycopy( children, 0, newNode.children, 0, index + 1 );
+
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[index + 1] = createHolder( modifiedPage );
+
+ if ( index < nbElems - 2 )
+ {
+ System.arraycopy( children, index + 3, newNode.children, index + 2, nbElems - index - 2 );
+ }
+ }
+
+ // Create the result
+ RemoveResult<K, V> result = new RemoveResult<K, V>( mergedResult.getCopiedPages(), newNode,
+ mergedResult.getRemovedElement() );
+
+ result.addCopiedPage( this );
+
+ return result;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public V get( K key ) throws IOException, KeyNotFoundException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // Here, if we have found the key in the node, then we must go down into
+ // the right child, not the left one
+ return children[-pos].getValue( btree ).get( key );
+ }
+ else
+ {
+ return children[pos].getValue( btree ).get( key );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // Here, if we have found the key in the node, then we must go down into
+ // the right child, not the left one
+ return children[-pos].getValue( btree ).getValues( key );
+ }
+ else
+ {
+ return children[pos].getValue( btree ).getValues( key );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean hasKey( K key ) throws IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // Here, if we have found the key in the node, then we must go down into
+ // the right child, not the left one
+ return children[-pos].getValue( btree ).hasKey( key );
+ }
+ else
+ {
+ Page<K, V> page = children[pos].getValue( btree );
+
+ if ( page == null )
+ {
+ System.out.println( "Page is null for pos = " + pos + ", children = " + children[pos] );
+ System.out.println( "Key = " + key );
+ }
+
+ return page.hasKey( key );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean contains( K key, V value ) throws IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // Here, if we have found the key in the node, then we must go down into
+ // the right child, not the left one
+ return children[-pos].getValue( btree ).contains( key, value );
+ }
+ else
+ {
+ return children[pos].getValue( btree ).contains( key, value );
+ }
+ }
+
+
+ /**
+ * Set the value at a give position
+ *
+ * @param pos The position in the values array
+ * @param value the value to inject
+ */
+ public void setValue( int pos, ElementHolder<Page<K, V>, K, V> value )
+ {
+ children[pos] = value;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Page<K, V> getReference( int pos ) throws IOException
+ {
+ if ( pos < nbElems + 1 )
+ {
+ return children[pos].getValue( btree );
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public CursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ throws IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ pos = -pos;
+ }
+
+ // We first stack the current page
+ stack.push( new ParentPos<K, V>( this, pos ) );
+
+ return children[pos].getValue( btree ).browse( key, transaction, stack );
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public CursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ throws IOException
+ {
+ stack.push( new ParentPos<K, V>( this, 0 ) );
+
+ return children[0].getValue( btree ).browse( transaction, stack );
+ }
+
+
+ /**
+ * This method is used when we have to replace a child in a page when we have
+ * found the key in the tree (the value will be changed, so we have made
+ * copies of the existing pages).
+ *
+ * @param revision The current revision
+ * @param result The modified page
+ * @param pos The position of the found key
+ * @return A modified page
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private InsertResult<K, V> replaceChild( long revision, ModifyResult<K, V> result, int pos ) throws IOException
+ {
+ // Just copy the current page and update its revision
+ Page<K, V> newPage = copy( revision );
+
+ // Last, we update the children table of the newly created page
+ // to point on the modified child
+ Page<K, V> modifiedPage = result.getModifiedPage();
+
+ ( ( Node<K, V> ) newPage ).children[pos] = createHolder( modifiedPage );
+
+ // We can return the result, where we update the modifiedPage,
+ // to avoid the creation of a new object
+ result.modifiedPage = newPage;
+
+ result.addCopiedPage( this );
+
+ return result;
+ }
+
+
+ /**
+ * Creates a new holder contaning a reference to a Page
+ *
+ * @param page The page we will refer to
+ * @return A holder contaning a reference to the child page
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private ElementHolder<Page<K, V>, K, V> createHolder( Page<K, V> page ) throws IOException
+ {
+ ElementHolder<Page<K, V>, K, V> holder = btree.getRecordManager().writePage( btree,
+ page,
+ revision );
+
+ return holder;
+ }
+
+
+ /**
+ * Adds a new key into a copy of the current page at a given position. We return the
+ * modified page. The new page will have one more key than the current page.
+ *
+ * @param copiedPages the list of copied pages
+ * @param revision The revision of the modified page
+ * @param key The key to insert
+ * @param leftPage The left child
+ * @param rightPage The right child
+ * @param pos The position into the page
+ * @return The modified page with the <K,V> element added
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private InsertResult<K, V> insertChild( List<Page<K, V>> copiedPages, long revision, K key, Page<K, V> leftPage,
+ Page<K, V> rightPage, int pos )
+ throws IOException
+ {
+ // First copy the current page, but add one element in the copied page
+ Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems + 1 );
+
+ // Copy the keys and the children up to the insertion position
+ if ( nbElems > 0 )
+ {
+ System.arraycopy( keys, 0, newNode.keys, 0, pos );
+ System.arraycopy( children, 0, newNode.children, 0, pos );
+ }
+
+ // Add the new key and children
+ newNode.keys[pos] = key;
+
+ // If the BTree is managed, we now have to write the modified page on disk
+ // and to add this page to the list of modified pages
+ newNode.children[pos] = createHolder( leftPage );
+ newNode.children[pos + 1] = createHolder( rightPage );
+
+ // And copy the remaining keys and children
+ if ( nbElems > 0 )
+ {
+ System.arraycopy( keys, pos, newNode.keys, pos + 1, keys.length - pos );
+ System.arraycopy( children, pos + 1, newNode.children, pos + 2, children.length - pos - 1 );
+ }
+
+ // Create the result
+ InsertResult<K, V> result = new ModifyResult<K, V>( copiedPages, newNode, null );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+
+
+ /**
+ * Splits a full page into two new pages, a left, a right and a pivot element. The new pages will
+ * each contains half of the original elements. <br/>
+ * The pivot will be computed, depending on the place
+ * we will inject the newly added element. <br/>
+ * If the newly added element is in the middle, we will use it
+ * as a pivot. Otherwise, we will use either the last element in the left page if the element is added
+ * on the left, or the first element in the right page if it's added on the right.
+ *
+ * @param copiedPages the list of copied pages
+ * @param revision The new revision for all the created pages
+ * @param pivot The key that will be move up after the split
+ * @param leftPage The left child
+ * @param rightPage The right child
+ * @param pos The position of the insertion of the new element
+ * @return An OverflowPage containing the pivot, and the new left and right pages
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private InsertResult<K, V> addAndSplit( List<Page<K, V>> copiedPages, long revision, K pivot, Page<K, V> leftPage,
+ Page<K, V> rightPage, int pos ) throws IOException
+ {
+ int middle = btree.getPageSize() >> 1;
+
+ // Create two new pages
+ Node<K, V> newLeftPage = new Node<K, V>( btree, revision, middle );
+ Node<K, V> newRightPage = new Node<K, V>( btree, revision, middle );
+
+ // Determinate where to store the new value
+ // If it's before the middle, insert the value on the left,
+ // the key in the middle will become the new pivot
+ if ( pos < middle )
+ {
+ // Copy the keys and the children up to the insertion position
+ System.arraycopy( keys, 0, newLeftPage.keys, 0, pos );
+ System.arraycopy( children, 0, newLeftPage.children, 0, pos );
+
+ // Add the new element
+ newLeftPage.keys[pos] = pivot;
+ newLeftPage.children[pos] = createHolder( leftPage );
+ newLeftPage.children[pos + 1] = createHolder( rightPage );
+
+ // And copy the remaining elements minus the new pivot
+ System.arraycopy( keys, pos, newLeftPage.keys, pos + 1, middle - pos - 1 );
+ System.arraycopy( children, pos + 1, newLeftPage.children, pos + 2, middle - pos - 1 );
+
+ // Copy the keys and the children in the right page
+ System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
+ System.arraycopy( children, middle, newRightPage.children, 0, middle + 1 );
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, keys[middle - 1], newLeftPage, newRightPage );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+ else if ( pos == middle )
+ {
+ // A special case : the pivot will be propagated up in the tree
+ // The left and right pages will be spread on the two new pages
+ // Copy the keys and the children up to the insertion position (here, middle)
+ System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
+ System.arraycopy( children, 0, newLeftPage.children, 0, middle );
+ newLeftPage.children[middle] = createHolder( leftPage );
+
+ // And process the right page now
+ System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
+ System.arraycopy( children, middle + 1, newRightPage.children, 1, middle );
+ newRightPage.children[0] = createHolder( rightPage );
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage, newRightPage );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+ else
+ {
+ // Copy the keys and the children up to the middle
+ System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
+ System.arraycopy( children, 0, newLeftPage.children, 0, middle + 1 );
+
+ // Copy the keys and the children in the right page up to the pos
+ System.arraycopy( keys, middle + 1, newRightPage.keys, 0, pos - middle - 1 );
+ System.arraycopy( children, middle + 1, newRightPage.children, 0, pos - middle - 1 );
+
+ // Add the new element
+ newRightPage.keys[pos - middle - 1] = pivot;
+ newRightPage.children[pos - middle - 1] = createHolder( leftPage );
+ newRightPage.children[pos - middle] = createHolder( rightPage );
+
+ // And copy the remaining elements minus the new pivot
+ System.arraycopy( keys, pos, newRightPage.keys, pos - middle, nbElems - pos );
+ System.arraycopy( children, pos + 1, newRightPage.children, pos + 1 - middle, nbElems - pos );
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, keys[middle], newLeftPage, newRightPage );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+ }
+
+
+ /**
+ * Copies the current page and all its keys, with a new revision.
+ *
+ * @param revision The new revision
+ * @return The copied page
+ */
+ protected Node<K, V> copy( long revision )
+ {
+ Node<K, V> newPage = new Node<K, V>( btree, revision, nbElems );
+
+ // Copy the keys
+ System.arraycopy( keys, 0, newPage.keys, 0, nbElems );
+
+ // Copy the children
+ System.arraycopy( children, 0, newPage.children, 0, nbElems + 1 );
+
+ return newPage;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getLeftMostKey() throws EndOfFileExceededException, IOException
+ {
+ return children[0].getValue( btree ).getLeftMostKey();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getRightMostKey() throws EndOfFileExceededException, IOException
+ {
+ int index = ( nbElems + 1 ) - 1;
+
+ if ( children[index] != null )
+ {
+ return children[index].getValue( btree ).getRightMostKey();
+ }
+
+ return children[nbElems - 1].getValue( btree ).getRightMostKey();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Tuple<K, V> findLeftMost() throws EndOfFileExceededException, IOException
+ {
+ return children[0].getValue( btree ).findLeftMost();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
+ {
+ return children[nbElems].getValue( btree ).findRightMost();
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "Node[" );
+ sb.append( super.toString() );
+ sb.append( "] -> {" );
+
+ try
+ {
+ if ( nbElems > 0 )
+ {
+ // Start with the first child
+ if ( children[0] == null )
+ {
+ sb.append( "null" );
+ }
+ else
+ {
+ sb.append( 'r' ).append( children[0].getValue( btree ).getRevision() );
+ }
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ sb.append( "|<" ).append( keys[i] ).append( ">|" );
+
+ if ( children[i + 1] == null )
+ {
+ sb.append( "null" );
+ }
+ else
+ {
+ sb.append( 'r' ).append( children[i + 1].getValue( btree ).getRevision() );
+ }
+ }
+ }
+ }
+ catch ( IOException ioe )
+ {
+ // Do nothing
+ }
+
+ sb.append( "}" );
+
+ return sb.toString();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public String dumpPage( String tabs )
+ {
+ StringBuilder sb = new StringBuilder();
+
+ if ( nbElems > 0 )
+ {
+ try
+ {
+ // Start with the first child
+ sb.append( children[0].getValue( btree ).dumpPage( tabs + " " ) );
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ sb.append( tabs );
+ sb.append( "<" );
+ sb.append( keys[i] ).append( ">\n" );
+ sb.append( children[i + 1].getValue( btree ).dumpPage( tabs + " " ) );
+ }
+ }
+ catch ( IOException ioe )
+ {
+ // Do nothing
+ }
+ }
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/NotPresentResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/NotPresentResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/NotPresentResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/NotPresentResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,75 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.managed;
+
+
+import org.apache.directory.mavibot.btree.Tuple;
+
+
+/**
+ * The result of an delete operation, when the key to delete is not present in the tree.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class NotPresentResult<K, V> extends AbstractResult<K, V> implements DeleteResult<K, V>
+{
+ /** The unique instance for this class */
+ @SuppressWarnings("rawtypes")
+ /* No qualifier */static final NotPresentResult NOT_PRESENT = new NotPresentResult();
+
+
+ /**
+ * A private void constructor, as we won't have any other instance.
+ */
+ private NotPresentResult()
+ {
+ // Do nothing
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Page<K, V> getModifiedPage()
+ {
+ return null;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Tuple<K, V> getRemovedElement()
+ {
+ return null;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getNewLeftMost()
+ {
+ return null;
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,275 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.managed;
+
+
+import java.io.IOException;
+import java.util.LinkedList;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+
+
+/**
+ * A MVCC Page interface. A Page can be either a Leaf (containing keys and values) or a Node
+ * (containing keys and references to child pages).<br/>
+ * A Page can be stored on disk. If so, we store the serialized value of this Page into
+ * one or more {@link PageIO} (they will be linked)
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */interface Page<K, V>
+{
+ /**
+ * @return The number of keys present in this page
+ */
+ int getNbElems();
+
+
+ /**
+ * Inserts the given key and value into this page. We first find the place were to
+ * inject the <K,V> into the tree, by recursively browsing the pages :<br/>
+ * <ul>
+ * <li>If the index is below zero, the key is present in the Page : we modify the
+ * value and return</li>
+ * <li>If the page is a node, we have to go down to the right child page</li>
+ * <li>If the page is a leaf, we insert the new <K,V> element into the page, and if
+ * the Page is full, we split it and propagate the new pivot up into the tree</li>
+ * </ul>
+ * <p>
+ *
+ * @param revision The new revision for the modified pages
+ * @param key Inserted key
+ * @param value Inserted value
+ * @return Either a modified Page or an Overflow element if the Page was full
+ * @throws IOException If we have an error while trying to access the page
+ */
+ InsertResult<K, V> insert( long revision, K key, V value ) throws IOException;
+
+
+ /**
+ * Deletes the value from an entry associated with the given key in this page. We first find
+ * the place were to remove the <K,V> into the tree, by recursively browsing the pages.
+ * If the value is present, it will be deleted first, later if there are no other values associated with
+ * this key(which can happen when duplicates are enabled), we will remove the key from the tree.
+ *
+ * @param revision The new revision for the modified pages
+ * @param key The key to delete
+ * @param value The value to delete (can be null)
+ * @param parent The parent page
+ * @param parentPos The position of the current page in it's parent
+ * @return Either a modified Page if the key has been removed from the page, or a NotPresentResult.
+ * @throws IOException If we have an error while trying to access the page
+ */
+ DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos ) throws IOException;
+
+
+ /**
+ * Gets the value associated with the given key, if any. If we don't have
+ * one, this method will throw a KeyNotFoundException.<br/>
+ * Note that we may get back null if a null value has been associated
+ * with the key.
+ *
+ * @param key The key we are looking for
+ * @return The associated value, which can be null
+ * @throws KeyNotFoundException If no entry with the given key can be found
+ * @throws IOException If we have an error while trying to access the page
+ */
+ V get( K key ) throws KeyNotFoundException, IOException;
+
+
+ /**
+ * Gets the values associated with the given key, if any. If we don't have
+ * the key, this method will throw a KeyNotFoundException.<br/>
+ * Note that we may get back null if a null value has been associated
+ * with the key.
+ *
+ * @param key The key we are looking for
+ * @return The associated value, which can be null
+ * @throws KeyNotFoundException If no entry with the given key can be found
+ * @throws IOException If we have an error while trying to access the page
+ * @throws IllegalArgumentException If duplicates are not enabled
+ */
+ DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;
+
+
+ /**
+ * Checks if the page contains the given key with the given value.
+ *
+ * @param key The key we are looking for
+ * @param value The value associated with the given key
+ * @return true if the key and value are associated with each other, false otherwise
+ */
+ boolean contains( K key, V value ) throws IOException;
+
+
+ /**
+ * Browses the tree, looking for the given key, and creates a Cursor on top
+ * of the found result.
+ *
+ * @param key The key we are looking for.
+ * @param transaction The started transaction for this operation
+ * @param stack The stack of parents we go through to get to this page
+ * @return A Cursor to browse the next elements
+ * @throws IOException If we have an error while trying to access the page
+ */
+ CursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ throws IOException;
+
+
+ /**
+ * Browses the whole tree, and creates a Cursor on top of it.
+ *
+ * @param transaction The started transaction for this operation
+ * @param stack The stack of parents we go through to get to this page
+ * @return A Cursor to browse the next elements
+ * @throws IOException If we have an error while trying to access the page
+ */
+ CursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * @return the revision
+ */
+ long getRevision();
+
+
+ /**
+ * Returns the key at a given position
+ *
+ * @param pos The position of the key we want to retrieve
+ * @return The key found at the given position
+ */
+ K getKey( int pos );
+
+
+ /**
+ * Finds the leftmost key in this page. If the page is a node, it will go
+ * down in the leftmost children to recursively find the leftmost key.
+ *
+ * @return The leftmost key in the tree
+ * @throws IOException If we have an error while trying to access the page
+ */
+ K getLeftMostKey() throws IOException;
+
+
+ /**
+ * Finds the rightmost key in this page. If the page is a node, it will go
+ * down in the rightmost children to recursively find the rightmost key.
+ *
+ * @return The rightmost key in the tree
+ * @throws IOException If we have an error while trying to access the page
+ */
+ K getRightMostKey() throws IOException;
+
+
+ /**
+ * Finds the leftmost element in this page. If the page is a node, it will go
+ * down in the leftmost children to recursively find the leftmost element.
+ *
+ * @return The leftmost element in the tree
+ * @throws IOException If we have an error while trying to access the page
+ */
+ Tuple<K, V> findLeftMost() throws IOException;
+
+
+ /**
+ * Finds the rightmost element in this page. If the page is a node, it will go
+ * down in the rightmost children to recursively find the rightmost element.
+ *
+ * @return The rightmost element in the tree
+ * @throws IOException If we have an error while trying to access the page
+ */
+ Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * Pretty-prints the tree with tabs
+ * @param tabs The tabs to add in front of each node
+ * @return A pretty-print dump of the tree
+ */
+ String dumpPage( String tabs );
+
+
+ /**
+ * Find the position of the given key in the page. If we have found the key,
+ * we will return its position as a negative value.
+ * <p/>
+ * Assuming that the array is zero-indexed, the returned value will be : <br/>
+ * position = - ( position + 1)
+ * <br/>
+ * So for the following table of keys : <br/>
+ * <pre>
+ * +---+---+---+---+
+ * | b | d | f | h |
+ * +---+---+---+---+
+ * 0 1 2 3
+ * </pre>
+ * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
+ * Computing the real position is just a matter to get -(position++).
+ * <p/>
+ * If we don't find the key in the table, we will return the position of the key
+ * immediately above the key we are looking for. <br/>
+ * For instance, looking for :
+ * <ul>
+ * <li>'a' will return 0</li>
+ * <li>'b' will return -1</li>
+ * <li>'c' will return 1</li>
+ * <li>'d' will return -2</li>
+ * <li>'e' will return 2</li>
+ * <li>'f' will return -3</li>
+ * <li>'g' will return 3</li>
+ * <li>'h' will return -4</li>
+ * <li>'i' will return 4</li>
+ * </ul>
+ *
+ *
+ * @param key The key to find
+ * @return The position in the page.
+ */
+ int findPos( K key );
+
+
+ /**
+ * Checks if the given key exists.
+ *
+ * @param key The key we are looking at
+ * @return true if the key is present, false otherwise
+ * @throws IOException If we have an error while trying to access the page
+ */
+ boolean hasKey( K key ) throws IOException;
+
+
+ /**
+ * @return the offset of the first {@link PageIO} which stores the Page on disk.
+ */
+ long getOffset();
+
+
+ /**
+ * @return the offset of the last {@link PageIO} which stores the Page on disk.
+ */
+ long getLastOffset();
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageIO.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageIO.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageIO.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/PageIO.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,234 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.managed;
+
+
+import java.nio.ByteBuffer;
+
+import org.apache.directory.mavibot.btree.util.Strings;
+
+
+/**
+ * A structure containing a Page on disk. It's a byte[PageSize] plus a few more details like
+ * the page offset on disk and a link to the next page.</br>
+ * As we may need more than one Page to store some data, the PageIO are linked so that
+ * the list of all the PageIO contain the full data.</br>
+ * The first PageIO contains the size of the data.</br>
+ * Here is the logical structure of a PageIO :
+ * <pre>
+ * For a first page :
+ *
+ * +----------+------+----------------------+
+ * | nextPage | size | XXXXXXXXXXXXXXXXXXXX |
+ * +----------+------+----------------------+
+ *
+ * for any page but the first :
+ *
+ * +----------+-----------------------------+
+ * | nextPage | XXXXXXXXXXXXXXXXXXXXXXXXXXX |
+ * +----------+-----------------------------+
+ *
+ * for the last page :
+ * +----------+-----------------------------+
+ * | -1 | XXXXXXXXXXXXXXXXXXXXXXXXXXX |
+ * +----------+-----------------------------+
+ *
+ * In any case, the page length is always PageSize.
+ * </pre>
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier*/class PageIO
+{
+ /** The contain data */
+ private ByteBuffer data;
+
+ /** A pointer to the next pageIO */
+ private long nextPage;
+
+ /** The offset on disk */
+ private int size;
+
+ /** The position of the page on disk */
+ private long offset;
+
+
+ /**
+ * A default constructor for a PageIO
+ */
+ public PageIO()
+ {
+ nextPage = -2L;
+ size = -1;
+ offset = -1L;
+ }
+
+
+ /**
+ * A constructor for a PageIO when we know the offset of this page on disk
+ */
+ public PageIO( long offset )
+ {
+ nextPage = -2L;
+ size = -1;
+ this.offset = offset;
+ }
+
+
+ /**
+ * @return the data
+ */
+ public ByteBuffer getData()
+ {
+ return data;
+ }
+
+
+ /**
+ * @param data the data to set
+ */
+ public void setData( ByteBuffer data )
+ {
+ this.data = data;
+ nextPage = data.getLong( 0 );
+ }
+
+
+ /**
+ * Get the NextPage value from the PageIO. If it's -1, there is no next page<br/>
+ * @return the nextPage
+ */
+ public long getNextPage()
+ {
+ return nextPage;
+ }
+
+
+ /**
+ * @param nextPage the nextPage to set
+ */
+ public void setNextPage( long nextPage )
+ {
+ this.nextPage = nextPage;
+
+ data.putLong( 0, nextPage );
+ }
+
+
+ /**
+ * @return the size
+ */
+ public long getSize()
+ {
+ return size;
+ }
+
+
+ /**
+ * @param size the size to set
+ */
+ public void setSize( int size )
+ {
+ data.putInt( 8, size );
+
+ this.size = size;
+ }
+
+
+ /**
+ * @param size the size to set
+ */
+ public void setSize()
+ {
+ size = data.getInt( 8 );
+ }
+
+
+ /**
+ * @return the offset
+ */
+ public long getOffset()
+ {
+ return offset;
+ }
+
+
+ /**
+ * @param offset the offset to set
+ */
+ public void setOffset( long offset )
+ {
+ this.offset = offset;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "PageIO[offset:" ).append( offset );
+
+ if ( size != -1 )
+ {
+ sb.append( ", size:" ).append( size );
+ }
+
+ if ( nextPage != -1L )
+ {
+ sb.append( ", next:" ).append( nextPage );
+ }
+
+ sb.append( "]" );
+
+ int start = 0;
+
+ byte[] array = null;
+
+ data.mark();
+ data.position( 0 );
+
+ if ( data.isDirect() )
+ {
+ array = new byte[data.capacity()];
+ data.get( array );
+ }
+ else
+ {
+ array = data.array();
+ }
+
+ data.reset();
+
+ for ( int i = start; i < array.length; i++ )
+ {
+ if ( ( ( i - start ) % 16 ) == 0 )
+ {
+ sb.append( "\n " );
+ }
+
+ sb.append( Strings.dumpByte( array[i] ) ).append( " " );
+ }
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,66 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.managed;
+
+
+/**
+ * This class is used to store the parent page and the position in it during
+ * a browse operation. We have as many ParentPos instance than the depth of the tree.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier*/class ParentPos<K, V>
+{
+ /** The page we are browsing */
+ /* No qualifier*/Page<K, V> page;
+
+ /** The current position in the page */
+ /* No qualifier*/int pos;
+
+ /** The current position of the duplicate container in the page */
+ /* No qualifier*/int dupPos;
+
+ /** the container of duplicate key's values. The tuples will be stored as <V,null>*/
+ /* No qualifier*/BTree<V, V> dupsContainer;
+
+
+ /**
+ * Creates a new instance of ParentPos
+ * @param page The current Page
+ * @param pos The current position in the page
+ */
+ /* No qualifier*/ParentPos( Page<K, V> page, int pos )
+ {
+ this.page = page;
+ this.pos = pos;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ return "<" + pos + "," + page + ">";
+ }
+}
\ No newline at end of file