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 2010/05/16 15:10:32 UTC
svn commit: r944824 - in /directory/apacheds/trunk/jdbm/src/main/java/jdbm:
btree/BPage.java btree/BTree.java helper/Tuple.java
Author: elecharny
Date: Sun May 16 13:10:32 2010
New Revision: 944824
URL: http://svn.apache.org/viewvc?rev=944824&view=rev
Log:
o The fin() method is not anymore recursive
o Added some generics
o Removed commented code
o Improved the compare method
o Added some javadoc
o Added a toString() method
o Minor refactoring
Modified:
directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java
directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java
directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/Tuple.java
Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java?rev=944824&r1=944823&r2=944824&view=diff
==============================================================================
--- directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java (original)
+++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java Sun May 16 13:10:32 2010
@@ -240,30 +240,19 @@ public final class BPage<K, V> implement
* @return TupleBrowser positionned just before the given key, or before
* next greater key if key isn't found.
*/
- TupleBrowser find( int height, Object key ) throws IOException
+ TupleBrowser<K, V> find( int height, Object key ) throws IOException
{
- int index = findChildren( key );
-
- /*
- if ( DEBUG ) {
- System.out.println( "BPage.find() current: " + this
- + " height: " + height);
- }
- */
+ int index = this.findChildren( key );
+ BPage<K, V> child = this;
- height -= 1;
-
- if ( height == 0 )
- {
- // leaf BPage
- return new Browser( this, index );
- }
- else
+ while ( !child.isLeaf )
{
// non-leaf BPage
- BPage child = childBPage( index );
- return child.find( height, key );
+ child = child.loadBPage( child.children[index] );
+ index = child.findChildren( key );
}
+
+ return new Browser( child, index );
}
@@ -272,7 +261,7 @@ public final class BPage<K, V> implement
*
* @return TupleBrowser positionned just before the first entry.
*/
- TupleBrowser findFirst() throws IOException
+ TupleBrowser<K, V> findFirst() throws IOException
{
if ( isLeaf )
{
@@ -280,7 +269,7 @@ public final class BPage<K, V> implement
}
else
{
- BPage child = childBPage( first );
+ BPage<K, V> child = childBPage( first );
return child.findFirst();
}
@@ -397,7 +386,7 @@ public final class BPage<K, V> implement
// page is full, we must divide the page
int half = btree.pageSize >> 1;
- BPage newPage = new BPage( btree, isLeaf );
+ BPage<K, V> newPage = new BPage<K, V>( btree, isLeaf );
if ( index < half )
{
@@ -468,7 +457,7 @@ public final class BPage<K, V> implement
if ( previous != 0 )
{
- BPage previousBPage = loadBPage( previous );
+ BPage<K, V> previousBPage = loadBPage( previous );
previousBPage.next = newPage.recid;
btree.recordManager.update( previous, previousBPage, this );
}
@@ -761,7 +750,7 @@ public final class BPage<K, V> implement
// binary search
while ( left < right )
{
- int middle = ( left + right ) / 2;
+ int middle = ( left + right ) >> 1;
if ( compare( keys[middle], key ) < 0 )
{
@@ -834,25 +823,6 @@ public final class BPage<K, V> implement
/**
- * Remove child at given position.
- */
- /*
- private static void removeChild( BPage page, int index )
- {
- Object[] keys = page.keys;
- long[] children = page._children;
- int start = page.first;
- int count = index-page.first;
-
- System.arraycopy( keys, start, keys, start+1, count );
- keys[ start ] = null;
- System.arraycopy( children, start, children, start+1, count );
- children[ start ] = (long) -1;
- page.first++;
- }
- */
-
- /**
* Set the entry at the given index.
*/
private static void setEntry( BPage page, int index, Object key, Object value )
@@ -916,10 +886,16 @@ public final class BPage<K, V> implement
private final int compare( Object value1, Object value2 )
{
+ if ( value1 == value2 )
+ {
+ return 0;
+ }
+
if ( value1 == null )
{
return 1;
}
+
if ( value2 == null )
{
return -1;
@@ -1181,7 +1157,6 @@ public final class BPage<K, V> implement
// note: It is assumed that BPage instance doing the serialization is the parent
// of the BPage object being serialized.
-
bpage = ( BPage<K, V> ) obj;
baos = new ByteArrayOutputStream();
oos = new ObjectOutputStream( baos );
@@ -1254,7 +1229,10 @@ public final class BPage<K, V> implement
}
/** STATIC INNER CLASS
- * Result from insert() method call
+ * Result from insert() method call. If the insertion has created
+ * a new page, it will be contained in the overflow field.
+ * If the inserted element already exist, then we will store
+ * the existing element.
*/
static class InsertResult<K, V>
{
@@ -1268,15 +1246,14 @@ public final class BPage<K, V> implement
* Existing value for the insertion key.
*/
V existing;
-
}
/** STATIC INNER CLASS
- * Result from remove() method call
+ * Result from remove() method call. If we had to removed a BPage,
+ * it will be stored into the underflow field.
*/
static class RemoveResult<V>
{
-
/**
* Set to true if underlying pages underflowed
*/
@@ -1293,11 +1270,8 @@ public final class BPage<K, V> implement
*/
class Browser extends TupleBrowser<K, V>
{
-
- /**
- * Current page.
- */
- private BPage<K, V> bPage;
+ /** Current page. */
+ private BPage<K, V> page;
/**
* Current index in the page. The index positionned on the next
@@ -1314,44 +1288,56 @@ public final class BPage<K, V> implement
*/
Browser( BPage<K, V> page, int index )
{
- this.bPage = page;
+ this.page = page;
this.index = index;
}
+ /**
+ * Get the next Tuple in the current BTree. We have 3 cases to deal with :
+ * 1) we are at the end of the btree. We will return false, the tuple won't be set.
+ * 2) we are in the middle of a page : grab the values and store them into the tuple
+ * 3) we are at the end of the page : grab the next page, and get the tuple from it.
+ *
+ * @return true if we have found a tumple, false otherwise.
+ */
public boolean getNext( Tuple<K, V> tuple ) throws IOException
{
- if ( index < bPage.btree.pageSize )
+ // First, check that we are within a page
+ if ( index < page.btree.pageSize )
{
- if ( bPage.keys[index] == null )
+ // We are. Now check that we have a Tuple
+ if ( page.keys[index] == null )
{
- // reached end of the tree.
+ // no : reached end of the tree.
return false;
}
}
- else if ( bPage.next != 0 )
+ // all the tuple for this page has been read. Move to the
+ // next page, if we have one.
+ else if ( page.next != 0 )
{
// move to next page
- bPage = bPage.loadBPage( bPage.next );
- index = bPage.first;
+ page = page.loadBPage( page.next );
+ index = page.first;
}
- tuple.setKey( bPage.keys[index] );
- tuple.setValue( bPage.values[index] );
+ tuple.setKey( page.keys[index] );
+ tuple.setValue( page.values[index] );
index++;
return true;
}
- public boolean getPrevious( Tuple tuple ) throws IOException
+ public boolean getPrevious( Tuple<K, V> tuple ) throws IOException
{
- if ( index == bPage.first )
+ if ( index == page.first )
{
- if ( bPage.previous != 0 )
+ if ( page.previous != 0 )
{
- bPage = bPage.loadBPage( bPage.previous );
- index = bPage.btree.pageSize;
+ page = page.loadBPage( page.previous );
+ index = page.btree.pageSize;
}
else
{
@@ -1361,8 +1347,8 @@ public final class BPage<K, V> implement
}
index--;
- tuple.setKey( bPage.keys[index] );
- tuple.setValue( bPage.values[index] );
+ tuple.setKey( page.keys[index] );
+ tuple.setValue( page.values[index] );
return true;
}
Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java?rev=944824&r1=944823&r2=944824&view=diff
==============================================================================
--- directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java (original)
+++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java Sun May 16 13:10:32 2010
@@ -401,7 +401,7 @@ public class BTree implements Externaliz
}
Tuple<Object, Object> tuple = new Tuple<Object, Object>( null, null );
- TupleBrowser browser = rootPage.find( bTreeHeight, key );
+ TupleBrowser<Object, Object> browser = rootPage.find( bTreeHeight, key );
if ( browser.getNext( tuple ) )
{
@@ -434,7 +434,7 @@ public class BTree implements Externaliz
public synchronized Tuple<Object, Object> findGreaterOrEqual( Object key ) throws IOException
{
Tuple<Object, Object> tuple;
- TupleBrowser browser;
+ TupleBrowser<Object, Object> browser;
if ( key == null )
{
@@ -460,7 +460,7 @@ public class BTree implements Externaliz
/**
* Get a browser initially positioned at the beginning of the BTree.
* <p><b>
- * WARNING: �If you make structural modifications to the BTree during
+ * WARNING: If you make structural modifications to the BTree during
* browsing, you will get inconsistent browing results.
* </b>
*
@@ -484,16 +484,16 @@ public class BTree implements Externaliz
/**
* Get a browser initially positioned just before the given key.
* <p><b>
- * WARNING: �If you make structural modifications to the BTree during
- * browsing, you will get inconsistent browing results.
+ * WARNING: If you make structural modifications to the BTree during
+ * browsing, you will get inconsistent browsing results.
* </b>
*
* @param key Key used to position the browser. If null, the browser
- * will be positionned after the last entry of the BTree.
+ * will be positioned after the last entry of the BTree.
* (Null is considered to be an "infinite" key)
- * @return Browser positionned just before the given key.
+ * @return Browser positioned just before the given key.
*/
- public synchronized TupleBrowser browse( Object key ) throws IOException
+ public synchronized TupleBrowser<Object, Object> browse( Object key ) throws IOException
{
BPage<Object, Object> rootPage = getRoot();
@@ -502,7 +502,7 @@ public class BTree implements Externaliz
return EmptyBrowser.INSTANCE;
}
- TupleBrowser browser = rootPage.find( bTreeHeight, key );
+ TupleBrowser<Object, Object> browser = rootPage.find( bTreeHeight, key );
return browser;
}
@@ -549,7 +549,7 @@ public class BTree implements Externaliz
*/
public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException
{
- comparator = ( Comparator ) in.readObject();
+ comparator = ( Comparator<?> ) in.readObject();
keySerializer = ( Serializer ) in.readObject();
valueSerializer = ( Serializer ) in.readObject();
bTreeHeight = in.readInt();
@@ -602,7 +602,7 @@ public class BTree implements Externaliz
/**
* @return the comparator
*/
- public Comparator getComparator()
+ public Comparator<?> getComparator()
{
return comparator;
}
Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/Tuple.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/Tuple.java?rev=944824&r1=944823&r2=944824&view=diff
==============================================================================
--- directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/Tuple.java (original)
+++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/Tuple.java Sun May 16 13:10:32 2010
@@ -118,4 +118,10 @@ public final class Tuple<K, V> {
{
this.value = value;
}
+
+
+ public String toString()
+ {
+ return "<" + key + "," + value + ">";
+ }
}