Author: elecharny
Date: Thu Jun 21 21:44:02 2012
New Revision: 1352708
URL: http://svn.apache.org/viewvc?rev=1352708&view=rev
Log:
o Added the brows() method
o Added a very first implementation for the transaction handling
Modified:
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
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
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=1352708&r1=1352707&r2=1352708&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 21 21:44:02 2012
@@ -202,6 +202,44 @@ public class BTree<K, V>
{
return rootPage.find( key );
}
+
+
+ /**
+ * Creates a cursor starting on the given key
+ *
+ * @param key The key which is the starting point. If the key is not found,
+ * then the cursor will always return null.
+ * @return A cursor on the btree
+ * @throws IOException
+ */
+ public Cursor<K, V> browse( K key ) throws IOException
+ {
+ Transaction<K, V> transaction = beginReadTransaction();
+
+ // Fetch the root page for this revision
+ Page<K, V> root = roots.get( transaction.getRevision() );
+ Cursor<K, V> cursor = root.browse( key, transaction );
+
+ return cursor;
+ }
+
+
+ /**
+ * Creates a cursor starting at the beginning of the tree
+ *
+ * @return A cursor on the btree
+ * @throws IOException
+ */
+ public Cursor<K, V> browse() throws IOException
+ {
+ Transaction<K, V> transaction = beginReadTransaction();
+
+ // Fetch the root page for this revision
+ Page<K, V> root = roots.get( transaction.getRevision() );
+ Cursor<K, V> cursor = root.browse( transaction );
+
+ return cursor;
+ }
/**
@@ -280,7 +318,20 @@ public class BTree<K, V>
//releaseWriteLock()
}
}
+
+
+ public Transaction<K, V> beginReadTransaction()
+ {
+ Transaction<K, V> readTransaction = new Transaction<K, V>( this,
revision.get() - 1, System.currentTimeMillis() );
+
+ return readTransaction;
+ }
+
+ public void commitTransaction( Transaction transaction )
+ {
+
+ }
/**
* @return the comparator
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=1352708&r1=1352707&r2=1352708&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 21 21:44:02 2012
@@ -30,7 +30,7 @@ package org.apache.mavibot.btree;
public class Leaf<K, V> extends AbstractPage<K, V>
{
/** Values associated with keys */
- private V[] values;
+ protected V[] values;
/** The page that comes next to this one */
protected Leaf<K, V> nextPage;
@@ -116,7 +116,67 @@ public class Leaf<K, V> extends Abstract
return null;
}
}
-
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Cursor<K, V> browse( K key, Transaction<K, V> transaction )
+ {
+ int pos = findPos( key );
+ Cursor<K, V> cursor = null;
+
+ if ( pos < 0 )
+ {
+ // The first element has been found. Create the cursor
+ cursor = new Cursor<K, V>( transaction, this, - ( pos + 1 ) );
+ }
+ else
+ {
+ // The key has not been found. Select the value just above, if we
have one
+ if ( pos < nbElems )
+ {
+ cursor = new Cursor<K, V>( transaction, this, pos );
+ }
+ else
+ {
+ if ( nextPage != null )
+ {
+ cursor = new Cursor<K, V>( transaction, nextPage, 0 );
+ }
+ else
+ {
+ cursor = new Cursor<K, V>( transaction, null, -1 );
+ }
+ }
+ }
+
+ return cursor;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Cursor<K, V> browse( Transaction<K, V> transaction )
+ {
+ int pos = 0;
+ Cursor<K, V> cursor = null;
+
+ if ( nbElems == 0 )
+ {
+ // The tree is empty, we have nothing to return
+ return new Cursor<K, V>( transaction, null, -1 );
+ }
+ else
+ {
+ // Start at the beginning of the page
+ cursor = new Cursor<K, V>( transaction, this, pos );
+ }
+
+ return cursor;
+ }
+
/**
* Copy the current page and all of the keys, values and children, if it's
not a leaf.
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=1352708&r1=1352707&r2=1352708&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 21 21:44:02 2012
@@ -157,6 +157,35 @@ public class Node<K, V> extends Abstract
/**
+ * {@inheritDoc}
+ */
+ public Cursor<K, V> browse( K key, Transaction<K, V> transaction )
+ {
+ 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 ].browse( key, transaction );
+ }
+ else
+ {
+ return children[pos].browse( key, transaction );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Cursor<K, V> browse( Transaction<K, V> transaction )
+ {
+ return children[0].browse( transaction );
+ }
+
+
+ /**
* 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).
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1352708&r1=1352707&r2=1352708&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Thu Jun 21 21:44:02 2012
@@ -65,6 +65,26 @@ public interface Page<K, V>
/**
+ * browse the tree, looking for the given key, and create a Cursor on top
+ * of the found result.
+ *
+ * @param key The key we are looking for.
+ * @param transaction The started transaction for this operation
+ * @return A Cursor to browse the next elements
+ */
+ Cursor<K, V> browse( K key, Transaction<K, V> transaction );
+
+
+ /**
+ * browse the whole tree, and create a Cursor on top of it.
+ *
+ * @param transaction The started transaction for this operation
+ * @return A Cursor to browse the next elements
+ */
+ Cursor<K, V> browse( Transaction<K, V> transaction );
+
+
+ /**
* @return the revision
*/
long getRevision();
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java?rev=1352708&r1=1352707&r2=1352708&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
Thu Jun 21 21:44:02 2012
@@ -25,8 +25,7 @@ package org.apache.mavibot.btree;
*
* @param <K> The type for the Key
* @param <V> The type for the stored value
-
- * @author <a href="mailto:[email protected]";>Apache Directory
Project</a>
+ * @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
/* No qualifier */ class SplitResult<K, V> implements InsertResult<K, V>
{
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
