Author: elecharny
Date: Thu Jun 14 17:22:51 2012
New Revision: 1350346
URL: http://svn.apache.org/viewvc?rev=1350346&view=rev
Log:
o Added the AbstractPage.findKeyInPage() and compare() methods
o Added some missing getters/setters in BTree
o Added place holder methods for the insert operation in the Leaf class
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/Leaf.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=1350346&r1=1350345&r2=1350346&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 17:22:51 2012
@@ -60,4 +60,108 @@ public class AbstractPage<K, V> implemen
{
return null;
}
+
+
+ /**
+ * 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>
+ * +---+---+---+---+
+ * | a | b | c | d |
+ * +---+---+---+---+
+ * 0 1 2 3
+ * </pre>
+ * looking for 'a' will return -1 (-(0+1)) and looking for 'c' will return
-3 (-(2+1)).<br/>
+ * Computing the real position is just a matter to get -(position++).
+ *
+ * @param key The key to find
+ * @return The position in the page.
+ */
+ protected int findKeyInPage( K key )
+ {
+ int left = 0;
+ int right = nbElems - 1;
+
+ // binary search
+ while ( left < right )
+ {
+ int middle = ( left + right ) >>> 1;
+
+ int comp = compare( keys[middle], key );
+
+ if ( comp < 0 )
+ {
+ left = middle + 1;
+ }
+ else if ( comp > 0 )
+ {
+ if ( middle == left )
+ {
+ return left;
+ }
+
+ right = middle - 1;
+ }
+ else
+ {
+ // Special case : the key already exists,
+ // we can return immediately. The value will be
+ // negative, and as the index may be 0, we subtract 1
+ return - ( middle + 1 );
+ }
+ }
+
+ // Special case : we don't know if the key is present
+ int comp = compare( keys[left], key );
+
+ if ( comp == 0 )
+ {
+ return - ( left + 1 );
+ }
+ else
+ {
+ if ( comp < 0 )
+ {
+ return left + 1;
+ }
+ else
+ {
+ return left;
+ }
+ }
+ }
+
+
+ /**
+ * Compare two keys
+ *
+ * @param key1 The first key
+ * @param key2 The second key
+ * @return -1 if the first key is above the second one, 1 if it's below,
and 0
+ * if the two keys are equal
+ */
+ private final int compare( K key1, K key2 )
+ {
+ if ( key1 == key2 )
+ {
+ return 0;
+ }
+
+ if ( key1 == null )
+ {
+ return 1;
+ }
+
+ if ( key2 == null )
+ {
+ return -1;
+ }
+
+ return btree.getComparator().compare( key1, key2 );
+ }
}
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=1350346&r1=1350345&r2=1350346&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 17:22:51 2012
@@ -45,7 +45,7 @@ public class BTree<K, V>
private transient AtomicLong pageRecordIdGenerator;
/** Comparator used to index entries. */
- Comparator<K> comparator;
+ private Comparator<K> comparator;
/** The current rootPage */
protected Page<K, V> rootPage;
@@ -214,7 +214,7 @@ public class BTree<K, V>
throw new IllegalArgumentException( "Value must not be null" );
}
- // Commented atm, we will have to play around the idea of transactions
laer
+ // Commented atm, we will have to play around the idea of transactions
later
//acquireWriteLock();
try
@@ -267,7 +267,25 @@ public class BTree<K, V>
//releaseWriteLock()
}
}
-
+
+
+ /**
+ * @return the comparator
+ */
+ public Comparator<K> getComparator()
+ {
+ return comparator;
+ }
+
+
+ /**
+ * @param comparator the comparator to set
+ */
+ public void setComparator( Comparator<K> comparator )
+ {
+ this.comparator = comparator;
+ }
+
/**
* @see Object#toString()
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java?rev=1350346&r1=1350345&r2=1350346&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
Thu Jun 14 17:22:51 2012
@@ -37,4 +37,96 @@ public class Leaf<K, V> extends Abstract
/** The page that comes previous to this one */
protected Leaf<K, V> prevPage;
+
+ /**
+ * {@inheritDoc}
+ */
+ public InsertResult<K, V> insert( long revision, K key, V value )
+ {
+ // Find the key into this leaf
+ int index = findKeyInPage( key );
+
+ if ( index < 0 )
+ {
+ // We already have the key in the page : replace the value
+ // into a copy of this page, unless the page has already be copied
+ index = - ( index++ );
+
+ // Replace the existing value in a copy of the current page
+ InsertResult<K, V> result = replaceValue( revision, index, value );
+
+ return result;
+ }
+
+ // The key is not present in the leaf. We have to add it in the page
+ if ( nbElems < btree.pageSize )
+ {
+ // The current page is not full, it can contain the added element.
+ // We insert it into a copied page and return the result
+ InsertResult<K, V> result = addElement( revision, index, key,
value );
+
+ return result;
+ }
+ else
+ {
+ // The Page is already full : we split it and return the overflow
element,
+ // after having created two pages.
+ InsertResult<K, V> result = addAndSplit( revision, key, value,
null, null, index );
+
+ return result;
+ }
+ }
+
+
+ /**
+ * Copy the current page if needed, and replace the value at the position
we have found the key.
+ *
+ * @param revision The new page revision
+ * @param index The position of the key in the page
+ * @param value the new value
+ * @return The copied page
+ */
+ private InsertResult<K, V> replaceValue( long revision, int index, V value
)
+ {
+ return null;
+ }
+
+
+ /**
+ * Add a new <K, V> into a copy of the current page at a given position.
We return the
+ * modified page. The new page will have one more element than the current
page.
+ *
+ * @param revision The revision of the modified page
+ * @param index The position into the page
+ * @param key The key to insert
+ * @param value The value to insert
+ * @return The modified page with the <K,V> element added
+ */
+ private InsertResult<K, V> addElement( long revision, int index, K key, V
value )
+ {
+ return null;
+ }
+
+
+ /**
+ * Split 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 revision The new revision for all the created pages
+ * @param index The position of the insertion of the new element
+ * @param key The key to add
+ * @param value The value to add
+ * @param left The left child of the added element
+ * @param right The right child of the added element
+ * @return An OverflowPage containing the pivor, and the new left and
right pages
+ */
+ private InsertResult<K, V> addAndSplit( long revision, K key, V value,
AbstractPage<K, V> left, AbstractPage<K, V> right, int index )
+ {
+ return null;
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
