Author: elecharny
Date: Thu Jun 14 16:37:35 2012
New Revision: 1350320
URL: http://svn.apache.org/viewvc?rev=1350320&view=rev
Log:
o Added some (empty) methods in the AbstractPage class
o Created a dedicated constructor in the Node class
o Added the modified value in the ModifyResult class
o Added the BTree constructor, the getters/setters and a first drop of insert()
method
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java?rev=1350320&r1=1350319&r2=1350320&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
Thu Jun 14 16:37:35 2012
@@ -44,4 +44,20 @@ public class AbstractPage<K, V> implemen
/** The number of current values in the Page */
protected int nbElems;
+
+ /**
+ * {@inheritDoc}
+ */
+ public long getNbElems()
+ {
+ return nbElems;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public InsertResult<K, V> insert( long revision, K key, V value )
+ {
+ return null;
+ }
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java?rev=1350320&r1=1350319&r2=1350320&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
Thu Jun 14 16:37:35 2012
@@ -19,6 +19,7 @@
*/
package org.apache.mavibot.btree;
+import java.io.IOException;
import java.util.Comparator;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
@@ -52,4 +53,255 @@ public class BTree<K, V>
/** A map containing all the existing revisions */
private Map<Long, Page<K, V>> roots = new ConcurrentHashMap<Long, Page<K,
V>>();
+ /** Number of entries in each Page. */
+ protected int pageSize;
+
+
+ /**
+ * Creates a new BTree with a default page size and a comparator.
+ *
+ * @param comparator The comparator to use
+ */
+ public BTree( Comparator<K> comparator ) throws IOException
+ {
+ this( comparator, DEFAULT_PAGE_SIZE );
+ }
+
+
+ /**
+ * Creates a new BTree with a specific page size and a comparator.
+ *
+ * @param comparator The comparator to use
+ * @param pageSize The number of elements we can store in a page
+ */
+ public BTree( Comparator<K> comparator, int pageSize ) throws IOException
+ {
+ if ( comparator == null )
+ {
+ throw new IllegalArgumentException( "Comparator should not be
null" );
+ }
+
+ this.comparator = comparator;
+ setPageSize( pageSize );
+
+ // Create the map contaning all the revisions
+ roots = new ConcurrentHashMap<Long, Page<K,V>>();
+
+ // Initialize the PageId counter
+ pageRecordIdGenerator = new AtomicLong(0);
+
+ // Initialize the revision counter
+ revision = new AtomicLong(0);
+
+ // Create the first root page, with revision 0L. It wil be empty
+ // and increment the revision at the same time
+ rootPage = new Leaf<K, V>();
+ roots.put( revision.getAndIncrement(), rootPage );
+ }
+
+
+ /**
+ * Gets the number which is a power of 2 immediately above the given
positive number.
+ */
+ private int getPowerOf2( int size )
+ {
+ int newSize = size--;
+ newSize |= newSize >> 1;
+ newSize |= newSize >> 2;
+ newSize |= newSize >> 4;
+ newSize |= newSize >> 8;
+ newSize |= newSize >> 16;
+ newSize++;
+
+ return newSize;
+ }
+
+
+ /**
+ * Set the maximum number of elements we can store in a page. This must be
a
+ * number greater than 1, and a power of 2. The default page size is 16.
+ * <br/>
+ * If the provided size is below 2, we will default to
DEFAULT_PAGE_SIZE.<br/>
+ * If the provided size is not a power of 2, we will select the closest
power of 2
+ * higher than the given number<br/>
+ *
+ * @param pageSize The requested page size
+ */
+ public void setPageSize( int pageSize )
+ {
+ this.pageSize = pageSize;
+
+ if ( pageSize <= 2 )
+ {
+ this.pageSize = DEFAULT_PAGE_SIZE;
+ }
+
+ this.pageSize = getPowerOf2( pageSize );
+ }
+
+
+ /**
+ * @return the pageSize
+ */
+ public int getPageSize()
+ {
+ return pageSize;
+ }
+
+
+ /**
+ * Generates a new RecordId. It's only used by the Page instances.
+ *
+ * @return a new incremental recordId
+ */
+ /** No qualifier */ long generateRecordId()
+ {
+ return pageRecordIdGenerator.getAndIncrement();
+ }
+
+
+ /**
+ * Generates a new revision number. It's only used by the Page instances.
+ *
+ * @return a new incremental revision number
+ */
+ /** No qualifier */ long generateRevision()
+ {
+ return revision.getAndIncrement();
+ }
+
+
+ /**
+ * Insert an entry in the BTree.
+ * <p>
+ * We will replace the value if the provided key already exists in the
+ * btree.
+ *
+ * @param key Inserted key
+ * @param value Inserted value
+ * @return Existing value, if any.
+ */
+ public V insert( K key, V value ) throws IOException
+ {
+ long revision = generateRevision();
+
+ return insert( key, value, revision );
+ }
+
+
+ /**
+ * Insert an entry in the BTree.
+ * <p>
+ * We will replace the value if the provided key already exists in the
+ * btree.
+ * <p>
+ * The revision number is the revision to use to insert the data.
+ *
+ * @param key Inserted key
+ * @param value Inserted value
+ * @param revision The revision to use
+ * @return Existing value, if any.
+ */
+ private V insert( K key, V value, long revision ) throws IOException
+ {
+ if ( key == null )
+ {
+ throw new IllegalArgumentException( "Key must not be null" );
+ }
+
+ if ( value == null )
+ {
+ throw new IllegalArgumentException( "Value must not be null" );
+ }
+
+ // Commented atm, we will have to play around the idea of transactions
laer
+ //acquireWriteLock();
+
+ try
+ {
+ // If the key exists, the existing value will be replaced. We
store it
+ // to return it to the caller.
+ V modifiedValue = null;
+
+ // Try to insert the new value in the tree at the right place,
+ // starting from the root page
+ InsertResult<K, V> result = rootPage.insert( revision, key, value
);
+
+ if ( result instanceof ModifyResult )
+ {
+ ModifyResult<K, V> modifyResult = ((ModifyResult)result);
+
+ // The root has just been modified, we haven't split it
+ // Get it and make it the current root page
+ rootPage = modifyResult.getModifiedPage();
+
+ modifiedValue = modifyResult.getModifiedValue();
+
+ // Save it into the roots.
+ roots.put( revision, rootPage );
+ }
+ else
+ {
+ // We have split the old root, create a new one containing
+ // only the pivotal we got back
+ SplitResult<K, V> splitResult = ((SplitResult)result);
+
+ K pivot = splitResult.getPivot();
+ Page<K, V> leftPage = splitResult.getLeftPage();
+ Page<K, V> rightPage = splitResult.getRightPage();
+
+ // Create the new rootPage
+ rootPage = new Node<K, V>( this, revision, pivot, leftPage,
rightPage );
+ }
+
+
+ // Save the rootPage into the roots with the new revision.
+ roots.put( revision, rootPage );
+
+ // Return the value we have found if it was modified
+ return modifiedValue;
+ }
+ finally
+ {
+ // See above
+ //releaseWriteLock()
+ }
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "BTree" );
+ sb.append( ", pageSize:" ).append( pageSize );
+
+ if ( rootPage != null )
+ {
+ sb.append( ", nbEntries:" ).append( rootPage.getNbElems() );
+ }
+ else
+ {
+ sb.append( ", nbEntries:" ).append( 0 );
+ }
+
+ sb.append( ", comparator:" );
+
+ if ( comparator == null )
+ {
+ sb.append( "null" );
+ }
+ else
+ {
+ sb.append( comparator.getClass().getSimpleName() );
+ }
+
+ sb.append( ") : " );
+ sb.append( rootPage );
+
+ return sb.toString();
+ }
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java?rev=1350320&r1=1350319&r2=1350320&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
Thu Jun 14 16:37:35 2012
@@ -33,13 +33,19 @@ package org.apache.mavibot.btree;
/** The modified page reference */
protected Page<K, V> modifiedPage;
+ /** The modified value if the key was found in the tree*/
+ protected V modifiedValue;
+
/**
* The default constructor for ModifyResult.
- * @param modifiedPage
+ *
+ * @param modifiedPage The modified page
+ * @param modifiedvalue The modified value (can be null if the key wasn't
present in the tree)
*/
- public ModifyResult( Page<K, V> modifiedPage )
+ public ModifyResult( Page<K, V> modifiedPage, V modifiedValue )
{
this.modifiedPage = modifiedPage;
+ this.modifiedValue = modifiedValue;
}
@@ -50,4 +56,13 @@ package org.apache.mavibot.btree;
{
return modifiedPage;
}
+
+
+ /**
+ * @return the modifiedValue
+ */
+ public V getModifiedValue()
+ {
+ return modifiedValue;
+ }
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java?rev=1350320&r1=1350319&r2=1350320&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
Thu Jun 14 16:37:35 2012
@@ -31,5 +31,34 @@ package org.apache.mavibot.btree;
public class Node<K, V> extends AbstractPage<K, V>
{
/** Children pages associated with keys. */
- protected AbstractPage<K, V>[] children;
+ protected Page<K, V>[] children;
+
+
+ /**
+ * Create 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
+ */
+ /* No qualifier */ Node( BTree<K, V> btree, long revision, K key, Page<K,
V> leftPage, Page<K, V> rightPage )
+ {
+ // Store the common values
+ this.btree = btree;
+ this.revision = revision;
+ nbElems = 1;
+
+ // Create the children array, and store the left and right children
+ children = (Page<K, V>[])new Object[btree.getPageSize()];
+ children[0] = leftPage;
+ children[1] = rightPage;
+
+ // Create the keys array and store the pivot into it
+ keys = (K[])new Object[btree.getPageSize()];
+ keys[0] = key;
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
