You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ka...@apache.org on 2010/03/21 19:22:26 UTC
svn commit: r925852 - in
/directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree: BPage.java
BTree.java
Author: kayyagari
Date: Sun Mar 21 18:22:25 2010
New Revision: 925852
URL: http://svn.apache.org/viewvc?rev=925852&view=rev
Log:
formatting
Modified:
directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java
directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.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=925852&r1=925851&r2=925852&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 Mar 21 18:22:25 2010
@@ -46,6 +46,7 @@
package jdbm.btree;
+
import jdbm.helper.Serializer;
import jdbm.helper.Tuple;
import jdbm.helper.TupleBrowser;
@@ -60,6 +61,7 @@ import java.io.ObjectOutputStream;
import org.apache.directory.server.i18n.I18n;
+
/**
* Page of a Btree.
* <p>
@@ -78,67 +80,56 @@ import org.apache.directory.server.i18n.
* @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
* @version $Id: BPage.java,v 1.6 2003/09/21 15:46:59 boisvert Exp $
*/
-public final class BPage
- implements Serializer
+public final class BPage implements Serializer
{
private static final boolean DEBUG = false;
-
/**
* Version id for serialization.
*/
final static long serialVersionUID = 1L;
-
/**
* Parent B+Tree.
*/
transient BTree _btree;
-
/**
* This BPage's record ID in the PageManager.
*/
protected transient long _recid;
-
/**
* Flag indicating if this is a leaf BPage.
*/
protected boolean _isLeaf;
-
/**
* Keys of children nodes
*/
protected Object[] _keys;
-
/**
* Values associated with keys. (Only valid if leaf BPage)
*/
protected Object[] _values;
-
/**
* Children pages (recids) associated with keys. (Only valid if non-leaf BPage)
*/
protected long[] _children;
-
/**
* Index of first used item at the page
*/
protected int _first;
-
/**
* Previous leaf BPage (only if this BPage is a leaf)
*/
protected long _previous;
-
/**
* Next leaf BPage (only if this BPage is a leaf)
*/
@@ -157,22 +148,21 @@ public final class BPage
/**
* Root page overflow constructor
*/
- BPage( BTree btree, BPage root, BPage overflow )
- throws IOException
+ BPage( BTree btree, BPage root, BPage overflow ) throws IOException
{
_btree = btree;
_isLeaf = false;
- _first = _btree._pageSize-2;
+ _first = _btree._pageSize - 2;
- _keys = new Object[ _btree._pageSize ];
- _keys[ _btree._pageSize-2 ] = overflow.getLargestKey();
- _keys[ _btree._pageSize-1 ] = root.getLargestKey();
-
- _children = new long[ _btree._pageSize ];
- _children[ _btree._pageSize-2 ] = overflow._recid;
- _children[ _btree._pageSize-1 ] = root._recid;
+ _keys = new Object[_btree._pageSize];
+ _keys[_btree._pageSize - 2] = overflow.getLargestKey();
+ _keys[_btree._pageSize - 1] = root.getLargestKey();
+
+ _children = new long[_btree._pageSize];
+ _children[_btree._pageSize - 2] = overflow._recid;
+ _children[_btree._pageSize - 1] = root._recid;
_recid = _btree._recman.insert( this, this );
}
@@ -181,22 +171,21 @@ public final class BPage
/**
* Root page (first insert) constructor.
*/
- BPage( BTree btree, Object key, Object value )
- throws IOException
+ BPage( BTree btree, Object key, Object value ) throws IOException
{
_btree = btree;
_isLeaf = true;
- _first = btree._pageSize-2;
+ _first = btree._pageSize - 2;
- _keys = new Object[ _btree._pageSize ];
- _keys[ _btree._pageSize-2 ] = key;
- _keys[ _btree._pageSize-1 ] = null; // I am the root BPage for now
-
- _values = new Object[ _btree._pageSize ];
- _values[ _btree._pageSize-2 ] = value;
- _values[ _btree._pageSize-1 ] = null; // I am the root BPage for now
+ _keys = new Object[_btree._pageSize];
+ _keys[_btree._pageSize - 2] = key;
+ _keys[_btree._pageSize - 1] = null; // I am the root BPage for now
+
+ _values = new Object[_btree._pageSize];
+ _values[_btree._pageSize - 2] = value;
+ _values[_btree._pageSize - 1] = null; // I am the root BPage for now
_recid = _btree._recman.insert( this, this );
}
@@ -205,21 +194,23 @@ public final class BPage
/**
* Overflow page constructor. Creates an empty BPage.
*/
- BPage( BTree btree, boolean isLeaf )
- throws IOException
+ BPage( BTree btree, boolean isLeaf ) throws IOException
{
_btree = btree;
_isLeaf = isLeaf;
// page will initially be half-full
- _first = _btree._pageSize/2;
+ _first = _btree._pageSize / 2;
- _keys = new Object[ _btree._pageSize ];
- if ( isLeaf ) {
- _values = new Object[ _btree._pageSize ];
- } else {
- _children = new long[ _btree._pageSize ];
+ _keys = new Object[_btree._pageSize];
+ if ( isLeaf )
+ {
+ _values = new Object[_btree._pageSize];
+ }
+ else
+ {
+ _children = new long[_btree._pageSize];
}
_recid = _btree._recman.insert( this, this );
@@ -232,7 +223,7 @@ public final class BPage
*/
Object getLargestKey()
{
- return _keys[ _btree._pageSize-1 ];
+ return _keys[_btree._pageSize - 1];
}
@@ -241,10 +232,13 @@ public final class BPage
*/
boolean isEmpty()
{
- if ( _isLeaf ) {
- return ( _first == _values.length-1 );
- } else {
- return ( _first == _children.length-1 );
+ if ( _isLeaf )
+ {
+ return ( _first == _values.length - 1 );
+ }
+ else
+ {
+ return ( _first == _children.length - 1 );
}
}
@@ -252,7 +246,8 @@ public final class BPage
/**
* Return true if BPage is full.
*/
- boolean isFull() {
+ boolean isFull()
+ {
return ( _first == 0 );
}
@@ -265,8 +260,7 @@ public final class BPage
* @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 find( int height, Object key ) throws IOException
{
int index = findChildren( key );
@@ -279,10 +273,13 @@ public final class BPage
height -= 1;
- if ( height == 0 ) {
+ if ( height == 0 )
+ {
// leaf BPage
return new Browser( this, index );
- } else {
+ }
+ else
+ {
// non-leaf BPage
BPage child = childBPage( index );
return child.find( height, key );
@@ -295,12 +292,14 @@ public final class BPage
*
* @return TupleBrowser positionned just before the first entry.
*/
- TupleBrowser findFirst()
- throws IOException
+ TupleBrowser findFirst() throws IOException
{
- if ( _isLeaf ) {
+ if ( _isLeaf )
+ {
return new Browser( this, _first );
- } else {
+ }
+ else
+ {
BPage child = childBPage( _first );
return child.findFirst();
}
@@ -320,63 +319,72 @@ public final class BPage
* @return Insertion result containing existing value OR a BPage if the key
* was inserted and provoked a BPage overflow.
*/
- InsertResult insert( int height, Object key, Object value, boolean replace )
- throws IOException
+ InsertResult insert( int height, Object key, Object value, boolean replace ) throws IOException
{
- InsertResult result;
- long overflow;
+ InsertResult result;
+ long overflow;
int index = findChildren( key );
height -= 1;
- if ( height == 0 ) {
+ if ( height == 0 )
+ {
result = new InsertResult();
// inserting on a leaf BPage
overflow = -1;
- if ( DEBUG ) {
- System.out.println( "Bpage.insert() Insert on leaf Bpage key=" + key
- + " value=" + value + " index="+index);
+ if ( DEBUG )
+ {
+ System.out.println( "Bpage.insert() Insert on leaf Bpage key=" + key + " value=" + value + " index="
+ + index );
}
- if ( compare( key, _keys[ index ] ) == 0 ) {
+ if ( compare( key, _keys[index] ) == 0 )
+ {
// key already exists
- if ( DEBUG ) {
- System.out.println( "Bpage.insert() Key already exists." ) ;
+ if ( DEBUG )
+ {
+ System.out.println( "Bpage.insert() Key already exists." );
}
- result._existing = _values[ index ];
- if ( replace ) {
- _values [ index ] = value;
+ result._existing = _values[index];
+ if ( replace )
+ {
+ _values[index] = value;
_btree._recman.update( _recid, this, this );
}
// return the existing key
return result;
}
- } else {
+ }
+ else
+ {
// non-leaf BPage
BPage child = childBPage( index );
result = child.insert( height, key, value, replace );
- if ( result._existing != null ) {
+ if ( result._existing != null )
+ {
// return existing key, if any.
return result;
}
- if ( result._overflow == null ) {
+ if ( result._overflow == null )
+ {
// no overflow means we're done with insertion
return result;
}
// there was an overflow, we need to insert the overflow page
// on this BPage
- if ( DEBUG ) {
+ if ( DEBUG )
+ {
System.out.println( "BPage.insert() Overflow page: " + result._overflow._recid );
}
key = result._overflow.getLargestKey();
overflow = result._overflow._recid;
// update child's largest key
- _keys[ index ] = child.getLargestKey();
+ _keys[index] = child.getLargestKey();
// clean result so we can reuse it
result._overflow = null;
@@ -384,11 +392,15 @@ public final class BPage
// if we get here, we need to insert a new entry on the BPage
// before _children[ index ]
- if ( !isFull() ) {
- if ( height == 0 ) {
- insertEntry( this, index-1, key, value );
- } else {
- insertChild( this, index-1, key, overflow );
+ if ( !isFull() )
+ {
+ if ( height == 0 )
+ {
+ insertEntry( this, index - 1, key, value );
+ }
+ else
+ {
+ insertChild( this, index - 1, key, overflow );
}
_btree._recman.update( _recid, this, this );
return result;
@@ -397,54 +409,72 @@ public final class BPage
// page is full, we must divide the page
int half = _btree._pageSize >> 1;
BPage newPage = new BPage( _btree, _isLeaf );
- if ( index < half ) {
+ if ( index < half )
+ {
// move lower-half of entries to overflow BPage,
// including new entry
- if ( DEBUG ) {
- System.out.println( "Bpage.insert() move lower-half of entries to overflow BPage, including new entry." ) ;
+ if ( DEBUG )
+ {
+ System.out
+ .println( "Bpage.insert() move lower-half of entries to overflow BPage, including new entry." );
}
- if ( height == 0 ) {
+ if ( height == 0 )
+ {
copyEntries( this, 0, newPage, half, index );
- setEntry( newPage, half+index, key, value );
- copyEntries( this, index, newPage, half+index+1, half-index-1 );
- } else {
+ setEntry( newPage, half + index, key, value );
+ copyEntries( this, index, newPage, half + index + 1, half - index - 1 );
+ }
+ else
+ {
copyChildren( this, 0, newPage, half, index );
- setChild( newPage, half+index, key, overflow );
- copyChildren( this, index, newPage, half+index+1, half-index-1 );
+ setChild( newPage, half + index, key, overflow );
+ copyChildren( this, index, newPage, half + index + 1, half - index - 1 );
}
- } else {
+ }
+ else
+ {
// move lower-half of entries to overflow BPage,
// new entry stays on this BPage
- if ( DEBUG ) {
- System.out.println( "Bpage.insert() move lower-half of entries to overflow BPage. New entry stays" ) ;
+ if ( DEBUG )
+ {
+ System.out.println( "Bpage.insert() move lower-half of entries to overflow BPage. New entry stays" );
}
- if ( height == 0 ) {
+ if ( height == 0 )
+ {
copyEntries( this, 0, newPage, half, half );
- copyEntries( this, half, this, half-1, index-half );
- setEntry( this, index-1, key, value );
- } else {
+ copyEntries( this, half, this, half - 1, index - half );
+ setEntry( this, index - 1, key, value );
+ }
+ else
+ {
copyChildren( this, 0, newPage, half, half );
- copyChildren( this, half, this, half-1, index-half );
- setChild( this, index-1, key, overflow );
+ copyChildren( this, half, this, half - 1, index - half );
+ setChild( this, index - 1, key, overflow );
}
}
- _first = half-1;
+ _first = half - 1;
// nullify lower half of entries
- for ( int i=0; i<_first; i++ ) {
- if ( height == 0 ) {
+ for ( int i = 0; i < _first; i++ )
+ {
+ if ( height == 0 )
+ {
setEntry( this, i, null, null );
- } else {
+ }
+ else
+ {
setChild( this, i, null, -1 );
}
}
- if ( _isLeaf ) {
+ if ( _isLeaf )
+ {
// link newly created BPage
newPage._previous = _previous;
newPage._next = _recid;
- if ( _previous != 0 ) {
+ if ( _previous != 0 )
+ {
BPage previous = loadBPage( _previous );
previous._next = newPage._recid;
_btree._recman.update( _previous, previous, this );
@@ -467,8 +497,7 @@ public final class BPage
* @param key Removal key
* @return Remove result object
*/
- RemoveResult remove( int height, Object key )
- throws IOException
+ RemoveResult remove( int height, Object key ) throws IOException
{
RemoveResult result;
@@ -476,59 +505,74 @@ public final class BPage
int index = findChildren( key );
height -= 1;
- if ( height == 0 ) {
+ if ( height == 0 )
+ {
// remove leaf entry
- if ( compare( _keys[ index ], key ) != 0 ) {
+ if ( compare( _keys[index], key ) != 0 )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_514, key ) );
}
result = new RemoveResult();
- result._value = _values[ index ];
+ result._value = _values[index];
removeEntry( this, index );
// update this BPage
_btree._recman.update( _recid, this, this );
- } else {
+ }
+ else
+ {
// recurse into Btree to remove entry on a children page
BPage child = childBPage( index );
result = child.remove( height, key );
// update children
- _keys[ index ] = child.getLargestKey();
+ _keys[index] = child.getLargestKey();
_btree._recman.update( _recid, this, this );
- if ( result._underflow ) {
+ if ( result._underflow )
+ {
// underflow occured
- if ( child._first != half+1 ) {
+ if ( child._first != half + 1 )
+ {
throw new IllegalStateException( I18n.err( I18n.ERR_513, "1" ) );
}
- if ( index < _children.length-1 ) {
+ if ( index < _children.length - 1 )
+ {
// exists greater brother page
- BPage brother = childBPage( index+1 );
+ BPage brother = childBPage( index + 1 );
int bfirst = brother._first;
- if ( bfirst < half ) {
+ if ( bfirst < half )
+ {
// steal entries from "brother" page
int steal = ( half - bfirst + 1 ) / 2;
brother._first += steal;
child._first -= steal;
- if ( child._isLeaf ) {
- copyEntries( child, half+1, child, half+1-steal, half-1 );
- copyEntries( brother, bfirst, child, 2*half-steal, steal );
- } else {
- copyChildren( child, half+1, child, half+1-steal, half-1 );
- copyChildren( brother, bfirst, child, 2*half-steal, steal );
- }
+ if ( child._isLeaf )
+ {
+ copyEntries( child, half + 1, child, half + 1 - steal, half - 1 );
+ copyEntries( brother, bfirst, child, 2 * half - steal, steal );
+ }
+ else
+ {
+ copyChildren( child, half + 1, child, half + 1 - steal, half - 1 );
+ copyChildren( brother, bfirst, child, 2 * half - steal, steal );
+ }
- for ( int i=bfirst; i<bfirst+steal; i++ ) {
- if ( brother._isLeaf ) {
+ for ( int i = bfirst; i < bfirst + steal; i++ )
+ {
+ if ( brother._isLeaf )
+ {
setEntry( brother, i, null, null );
- } else {
+ }
+ else
+ {
setChild( brother, i, null, -1 );
}
}
// update child's largest key
- _keys[ index ] = child.getLargestKey();
+ _keys[index] = child.getLargestKey();
// no change in previous/next BPage
@@ -537,38 +581,49 @@ public final class BPage
_btree._recman.update( brother._recid, brother, this );
_btree._recman.update( child._recid, child, this );
- } else {
+ }
+ else
+ {
// move all entries from page "child" to "brother"
- if ( brother._first != half ) {
+ if ( brother._first != half )
+ {
throw new IllegalStateException( I18n.err( I18n.ERR_513, "2" ) );
}
brother._first = 1;
- if ( child._isLeaf ) {
- copyEntries( child, half+1, brother, 1, half-1 );
- } else {
- copyChildren( child, half+1, brother, 1, half-1 );
+ if ( child._isLeaf )
+ {
+ copyEntries( child, half + 1, brother, 1, half - 1 );
+ }
+ else
+ {
+ copyChildren( child, half + 1, brother, 1, half - 1 );
}
_btree._recman.update( brother._recid, brother, this );
// remove "child" from current BPage
- if ( _isLeaf ) {
- copyEntries( this, _first, this, _first+1, index-_first );
+ if ( _isLeaf )
+ {
+ copyEntries( this, _first, this, _first + 1, index - _first );
setEntry( this, _first, null, null );
- } else {
- copyChildren( this, _first, this, _first+1, index-_first );
+ }
+ else
+ {
+ copyChildren( this, _first, this, _first + 1, index - _first );
setChild( this, _first, null, -1 );
}
_first += 1;
_btree._recman.update( _recid, this, this );
// re-link previous and next BPages
- if ( child._previous != 0 ) {
+ if ( child._previous != 0 )
+ {
BPage prev = loadBPage( child._previous );
prev._next = child._next;
_btree._recman.update( prev._recid, prev, this );
}
- if ( child._next != 0 ) {
+ if ( child._next != 0 )
+ {
BPage next = loadBPage( child._next );
next._previous = child._previous;
_btree._recman.update( next._recid, next, this );
@@ -577,37 +632,43 @@ public final class BPage
// delete "child" BPage
_btree._recman.delete( child._recid );
}
- } else {
+ }
+ else
+ {
// page "brother" is before "child"
- BPage brother = childBPage( index-1 );
+ BPage brother = childBPage( index - 1 );
int bfirst = brother._first;
- if ( bfirst < half ) {
+ if ( bfirst < half )
+ {
// steal entries from "brother" page
int steal = ( half - bfirst + 1 ) / 2;
brother._first += steal;
child._first -= steal;
- if ( child._isLeaf ) {
- copyEntries( brother, 2*half-steal, child,
- half+1-steal, steal );
- copyEntries( brother, bfirst, brother,
- bfirst+steal, 2*half-bfirst-steal );
- } else {
- copyChildren( brother, 2*half-steal, child,
- half+1-steal, steal );
- copyChildren( brother, bfirst, brother,
- bfirst+steal, 2*half-bfirst-steal );
+ if ( child._isLeaf )
+ {
+ copyEntries( brother, 2 * half - steal, child, half + 1 - steal, steal );
+ copyEntries( brother, bfirst, brother, bfirst + steal, 2 * half - bfirst - steal );
+ }
+ else
+ {
+ copyChildren( brother, 2 * half - steal, child, half + 1 - steal, steal );
+ copyChildren( brother, bfirst, brother, bfirst + steal, 2 * half - bfirst - steal );
}
- for ( int i=bfirst; i<bfirst+steal; i++ ) {
- if ( brother._isLeaf ) {
+ for ( int i = bfirst; i < bfirst + steal; i++ )
+ {
+ if ( brother._isLeaf )
+ {
setEntry( brother, i, null, null );
- } else {
+ }
+ else
+ {
setChild( brother, i, null, -1 );
}
}
// update brother's largest key
- _keys[ index-1 ] = brother.getLargestKey();
+ _keys[index - 1] = brother.getLargestKey();
// no change in previous/next BPage
@@ -616,38 +677,49 @@ public final class BPage
_btree._recman.update( brother._recid, brother, this );
_btree._recman.update( child._recid, child, this );
- } else {
+ }
+ else
+ {
// move all entries from page "brother" to "child"
- if ( brother._first != half ) {
+ if ( brother._first != half )
+ {
throw new IllegalStateException( I18n.err( I18n.ERR_513, "3" ) );
}
child._first = 1;
- if ( child._isLeaf ) {
+ if ( child._isLeaf )
+ {
copyEntries( brother, half, child, 1, half );
- } else {
+ }
+ else
+ {
copyChildren( brother, half, child, 1, half );
}
_btree._recman.update( child._recid, child, this );
// remove "brother" from current BPage
- if ( _isLeaf ) {
- copyEntries( this, _first, this, _first+1, index-1-_first );
+ if ( _isLeaf )
+ {
+ copyEntries( this, _first, this, _first + 1, index - 1 - _first );
setEntry( this, _first, null, null );
- } else {
- copyChildren( this, _first, this, _first+1, index-1-_first );
+ }
+ else
+ {
+ copyChildren( this, _first, this, _first + 1, index - 1 - _first );
setChild( this, _first, null, -1 );
}
_first += 1;
_btree._recman.update( _recid, this, this );
// re-link previous and next BPages
- if ( brother._previous != 0 ) {
+ if ( brother._previous != 0 )
+ {
BPage prev = loadBPage( brother._previous );
prev._next = brother._next;
_btree._recman.update( prev._recid, prev, this );
}
- if ( brother._next != 0 ) {
+ if ( brother._next != 0 )
+ {
BPage next = loadBPage( brother._next );
next._previous = brother._previous;
_btree._recman.update( next._recid, next, this );
@@ -676,14 +748,18 @@ public final class BPage
private int findChildren( Object key )
{
int left = _first;
- int right = _btree._pageSize-1;
+ int right = _btree._pageSize - 1;
// binary search
- while ( left < right ) {
+ while ( left < right )
+ {
int middle = ( left + right ) / 2;
- if ( compare( _keys[ middle ], key ) < 0 ) {
- left = middle+1;
- } else {
+ if ( compare( _keys[middle], key ) < 0 )
+ {
+ left = middle + 1;
+ }
+ else
+ {
right = middle;
}
}
@@ -694,42 +770,41 @@ public final class BPage
/**
* Insert entry at given position.
*/
- private static void insertEntry( BPage page, int index,
- Object key, Object value )
+ private static void insertEntry( BPage page, int index, Object key, Object value )
{
Object[] keys = page._keys;
Object[] values = page._values;
int start = page._first;
- int count = index-page._first+1;
+ int count = index - page._first + 1;
// shift entries to the left
- System.arraycopy( keys, start, keys, start-1, count );
- System.arraycopy( values, start, values, start-1, count );
+ System.arraycopy( keys, start, keys, start - 1, count );
+ System.arraycopy( values, start, values, start - 1, count );
page._first -= 1;
- keys[ index ] = key;
- values[ index ] = value;
+ keys[index] = key;
+ values[index] = value;
}
/**
* Insert child at given position.
*/
- private static void insertChild( BPage page, int index,
- Object key, long child )
+ private static void insertChild( BPage page, int index, Object key, long child )
{
Object[] keys = page._keys;
long[] children = page._children;
int start = page._first;
- int count = index-page._first+1;
+ int count = index - page._first + 1;
// shift entries to the left
- System.arraycopy( keys, start, keys, start-1, count );
- System.arraycopy( children, start, children, start-1, count );
+ System.arraycopy( keys, start, keys, start - 1, count );
+ System.arraycopy( children, start, children, start - 1, count );
page._first -= 1;
- keys[ index ] = key;
- children[ index ] = child;
+ keys[index] = key;
+ children[index] = child;
}
-
+
+
/**
* Remove entry at given position.
*/
@@ -738,12 +813,12 @@ public final class BPage
Object[] keys = page._keys;
Object[] values = page._values;
int start = page._first;
- int count = index-page._first;
+ int count = index - page._first;
- System.arraycopy( keys, start, keys, start+1, count );
- keys[ start ] = null;
- System.arraycopy( values, start, values, start+1, count );
- values[ start ] = null;
+ System.arraycopy( keys, start, keys, start + 1, count );
+ keys[start] = null;
+ System.arraycopy( values, start, values, start + 1, count );
+ values[start] = null;
page._first++;
}
@@ -751,29 +826,29 @@ public final class BPage
/**
* 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;
+ /*
+ 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++;
+ }
+ */
- 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 )
{
- page._keys[ index ] = key;
- page._values[ index ] = value;
+ page._keys[index] = key;
+ page._values[index] = value;
}
@@ -782,91 +857,93 @@ public final class BPage
*/
private static void setChild( BPage page, int index, Object key, long recid )
{
- page._keys[ index ] = key;
- page._children[ index ] = recid;
+ page._keys[index] = key;
+ page._children[index] = recid;
}
-
-
+
+
/**
* Copy entries between two BPages
*/
- private static void copyEntries( BPage source, int indexSource,
- BPage dest, int indexDest, int count )
+ private static void copyEntries( BPage source, int indexSource, BPage dest, int indexDest, int count )
{
- System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count);
- System.arraycopy( source._values, indexSource, dest._values, indexDest, count);
+ System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count );
+ System.arraycopy( source._values, indexSource, dest._values, indexDest, count );
}
/**
* Copy child BPage recids between two BPages
*/
- private static void copyChildren( BPage source, int indexSource,
- BPage dest, int indexDest, int count )
+ private static void copyChildren( BPage source, int indexSource, BPage dest, int indexDest, int count )
{
- System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count);
- System.arraycopy( source._children, indexSource, dest._children, indexDest, count);
+ System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count );
+ System.arraycopy( source._children, indexSource, dest._children, indexDest, count );
}
-
+
/**
* Return the child BPage at given index.
*/
- BPage childBPage( int index )
- throws IOException
+ BPage childBPage( int index ) throws IOException
{
- return loadBPage( _children[ index ] );
+ return loadBPage( _children[index] );
}
/**
* Load the BPage at the given recid.
*/
- private BPage loadBPage( long recid )
- throws IOException
+ private BPage loadBPage( long recid ) throws IOException
{
- BPage child = (BPage) _btree._recman.fetch( recid, this );
+ BPage child = ( BPage ) _btree._recman.fetch( recid, this );
child._recid = recid;
child._btree = _btree;
return child;
}
-
+
private final int compare( Object value1, Object value2 )
{
- if ( value1 == null ) {
+ if ( value1 == null )
+ {
return 1;
}
- if ( value2 == null ) {
+ if ( value2 == null )
+ {
return -1;
}
return _btree._comparator.compare( value1, value2 );
}
- static byte[] readByteArray( ObjectInput in )
- throws IOException
+
+ static byte[] readByteArray( ObjectInput in ) throws IOException
{
int len = in.readInt();
- if ( len < 0 ) {
+ if ( len < 0 )
+ {
return null;
}
- byte[] buf = new byte[ len ];
+ byte[] buf = new byte[len];
in.readFully( buf );
return buf;
}
- static void writeByteArray( ObjectOutput out, byte[] buf )
- throws IOException
+ static void writeByteArray( ObjectOutput out, byte[] buf ) throws IOException
{
- if ( buf == null ) {
+ if ( buf == null )
+ {
out.writeInt( -1 );
- } else {
+ }
+ else
+ {
out.writeInt( buf.length );
out.write( buf );
}
}
+
/**
* Dump the structure of the tree on the screen. This is used for debugging
* purposes only.
@@ -874,16 +951,21 @@ public final class BPage
private void dump( int height )
{
String prefix = "";
- for ( int i=0; i<height; i++ ) {
- prefix += " ";
+ for ( int i = 0; i < height; i++ )
+ {
+ prefix += " ";
}
- System.out.println( prefix + "-------------------------------------- BPage recid=" + _recid);
+ System.out.println( prefix + "-------------------------------------- BPage recid=" + _recid );
System.out.println( prefix + "first=" + _first );
- for ( int i=0; i< _btree._pageSize; i++ ) {
- if ( _isLeaf ) {
- System.out.println( prefix + "BPage [" + i + "] " + _keys[ i ] + " " + _values[ i ] );
- } else {
- System.out.println( prefix + "BPage [" + i + "] " + _keys[ i ] + " " + _children[ i ] );
+ for ( int i = 0; i < _btree._pageSize; i++ )
+ {
+ if ( _isLeaf )
+ {
+ System.out.println( prefix + "BPage [" + i + "] " + _keys[i] + " " + _values[i] );
+ }
+ else
+ {
+ System.out.println( prefix + "BPage [" + i + "] " + _keys[i] + " " + _children[i] );
}
}
System.out.println( prefix + "--------------------------------------" );
@@ -894,14 +976,16 @@ public final class BPage
* Recursively dump the state of the BTree on screen. This is used for
* debugging purposes only.
*/
- void dumpRecursive( int height, int level )
- throws IOException
+ void dumpRecursive( int height, int level ) throws IOException
{
height -= 1;
level += 1;
- if ( height > 0 ) {
- for ( int i=_first; i<_btree._pageSize; i++ ) {
- if ( _keys[ i ] == null ) break;
+ if ( height > 0 )
+ {
+ for ( int i = _first; i < _btree._pageSize; i++ )
+ {
+ if ( _keys[i] == null )
+ break;
BPage child = childBPage( i );
child.dump( level );
child.dumpRecursive( height, level );
@@ -916,8 +1000,10 @@ public final class BPage
*/
private void assertConsistency()
{
- for ( int i=_first; i<_btree._pageSize-1; i++ ) {
- if ( compare( (byte[]) _keys[ i ], (byte[]) _keys[ i+1 ] ) >= 0 ) {
+ for ( int i = _first; i < _btree._pageSize - 1; i++ )
+ {
+ if ( compare( ( byte[] ) _keys[i], ( byte[] ) _keys[i + 1] ) >= 0 )
+ {
dump( 0 );
throw new Error( I18n.err( I18n.ERR_515 ) );
}
@@ -929,15 +1015,18 @@ public final class BPage
* Recursively assert the ordering of the BPage entries on this page
* and sub-pages. This is used for testing purposes only.
*/
- void assertConsistencyRecursive( int height )
- throws IOException
+ void assertConsistencyRecursive( int height ) throws IOException
{
assertConsistency();
- if ( --height > 0 ) {
- for ( int i=_first; i<_btree._pageSize; i++ ) {
- if ( _keys[ i ] == null ) break;
+ if ( --height > 0 )
+ {
+ for ( int i = _first; i < _btree._pageSize; i++ )
+ {
+ if ( _keys[i] == null )
+ break;
BPage child = childBPage( i );
- if ( compare( (byte[]) _keys[ i ], child.getLargestKey() ) != 0 ) {
+ if ( compare( ( byte[] ) _keys[i], child.getLargestKey() ) != 0 )
+ {
dump( 0 );
child.dump( 0 );
throw new Error( I18n.err( I18n.ERR_516 ) );
@@ -955,70 +1044,90 @@ public final class BPage
* @return deserialized object
*
*/
- public Object deserialize( byte[] serialized )
- throws IOException
+ public Object deserialize( byte[] serialized ) throws IOException
{
- ByteArrayInputStream bais;
- ObjectInputStream ois;
- BPage bpage;
+ ByteArrayInputStream bais;
+ ObjectInputStream ois;
+ BPage bpage;
bpage = new BPage();
bais = new ByteArrayInputStream( serialized );
ois = new ObjectInputStream( bais );
-
+
bpage._isLeaf = ois.readBoolean();
- if ( bpage._isLeaf ) {
+ if ( bpage._isLeaf )
+ {
bpage._previous = ois.readLong();
bpage._next = ois.readLong();
}
bpage._first = ois.readInt();
- bpage._keys = new Object[ _btree._pageSize ];
- try {
- for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
- if ( _btree._keySerializer == null ) {
- bpage._keys[ i ] = ois.readObject();
- } else {
+ bpage._keys = new Object[_btree._pageSize];
+ try
+ {
+ for ( int i = bpage._first; i < _btree._pageSize; i++ )
+ {
+ if ( _btree._keySerializer == null )
+ {
+ bpage._keys[i] = ois.readObject();
+ }
+ else
+ {
serialized = readByteArray( ois );
- if ( serialized != null ) {
- bpage._keys[ i ] = _btree._keySerializer.deserialize( serialized );
+ if ( serialized != null )
+ {
+ bpage._keys[i] = _btree._keySerializer.deserialize( serialized );
}
}
}
- } catch ( ClassNotFoundException except ) {
+ }
+ catch ( ClassNotFoundException except )
+ {
throw new IOException( except.getLocalizedMessage() );
}
-
- if ( bpage._isLeaf ) {
- bpage._values = new Object[ _btree._pageSize ];
- try {
- for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
- if ( _btree._valueSerializer == null ) {
- bpage._values[ i ] = ois.readObject();
- } else {
+
+ if ( bpage._isLeaf )
+ {
+ bpage._values = new Object[_btree._pageSize];
+ try
+ {
+ for ( int i = bpage._first; i < _btree._pageSize; i++ )
+ {
+ if ( _btree._valueSerializer == null )
+ {
+ bpage._values[i] = ois.readObject();
+ }
+ else
+ {
serialized = readByteArray( ois );
- if ( serialized != null ) {
- bpage._values[ i ] = _btree._valueSerializer.deserialize( serialized );
+ if ( serialized != null )
+ {
+ bpage._values[i] = _btree._valueSerializer.deserialize( serialized );
}
}
}
- } catch ( ClassNotFoundException except ) {
+ }
+ catch ( ClassNotFoundException except )
+ {
throw new IOException( except.getLocalizedMessage() );
}
- } else {
- bpage._children = new long[ _btree._pageSize ];
- for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
- bpage._children[ i ] = ois.readLong();
+ }
+ else
+ {
+ bpage._children = new long[_btree._pageSize];
+ for ( int i = bpage._first; i < _btree._pageSize; i++ )
+ {
+ bpage._children[i] = ois.readLong();
}
}
ois.close();
bais.close();
-
+
return bpage;
}
-
+
/**
* Serialize the content of an object into a byte array.
*
@@ -1026,74 +1135,92 @@ public final class BPage
* @return a byte array representing the object's state
*
*/
- public byte[] serialize( Object obj )
- throws IOException
+ public byte[] serialize( Object obj ) throws IOException
{
- byte[] serialized;
- ByteArrayOutputStream baos;
- ObjectOutputStream oos;
- BPage bpage;
- byte[] data;
-
+ byte[] serialized;
+ ByteArrayOutputStream baos;
+ ObjectOutputStream oos;
+ BPage bpage;
+ byte[] data;
+
// note: It is assumed that BPage instance doing the serialization is the parent
// of the BPage object being serialized.
-
- bpage = (BPage) obj;
+
+ bpage = ( BPage ) obj;
baos = new ByteArrayOutputStream();
- oos = new ObjectOutputStream( baos );
-
+ oos = new ObjectOutputStream( baos );
+
oos.writeBoolean( bpage._isLeaf );
- if ( bpage._isLeaf ) {
+ if ( bpage._isLeaf )
+ {
oos.writeLong( bpage._previous );
oos.writeLong( bpage._next );
}
oos.writeInt( bpage._first );
-
- for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
- if ( _btree._keySerializer == null ) {
- oos.writeObject( bpage._keys[ i ] );
- } else {
- if ( bpage._keys[ i ] != null ) {
- serialized = _btree._keySerializer.serialize( bpage._keys[ i ] );
+
+ for ( int i = bpage._first; i < _btree._pageSize; i++ )
+ {
+ if ( _btree._keySerializer == null )
+ {
+ oos.writeObject( bpage._keys[i] );
+ }
+ else
+ {
+ if ( bpage._keys[i] != null )
+ {
+ serialized = _btree._keySerializer.serialize( bpage._keys[i] );
writeByteArray( oos, serialized );
- } else {
+ }
+ else
+ {
writeByteArray( oos, null );
}
}
}
- if ( bpage._isLeaf ) {
- for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
- if ( _btree._valueSerializer == null ) {
- oos.writeObject( bpage._values[ i ] );
- } else {
- if ( bpage._values[ i ] != null ) {
- serialized = _btree._valueSerializer.serialize( bpage._values[ i ] );
+ if ( bpage._isLeaf )
+ {
+ for ( int i = bpage._first; i < _btree._pageSize; i++ )
+ {
+ if ( _btree._valueSerializer == null )
+ {
+ oos.writeObject( bpage._values[i] );
+ }
+ else
+ {
+ if ( bpage._values[i] != null )
+ {
+ serialized = _btree._valueSerializer.serialize( bpage._values[i] );
writeByteArray( oos, serialized );
- } else {
+ }
+ else
+ {
writeByteArray( oos, null );
}
}
}
- } else {
- for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
- oos.writeLong( bpage._children[ i ] );
+ }
+ else
+ {
+ for ( int i = bpage._first; i < _btree._pageSize; i++ )
+ {
+ oos.writeLong( bpage._children[i] );
}
}
-
+
oos.flush();
data = baos.toByteArray();
oos.close();
baos.close();
return data;
}
-
-
+
/** STATIC INNER CLASS
* Result from insert() method call
*/
- static class InsertResult {
+ static class InsertResult
+ {
/**
* Overflow page.
@@ -1110,7 +1237,8 @@ public final class BPage
/** STATIC INNER CLASS
* Result from remove() method call
*/
- static class RemoveResult {
+ static class RemoveResult
+ {
/**
* Set to true if underlying pages underflowed
@@ -1123,12 +1251,10 @@ public final class BPage
Object _value;
}
-
/** PRIVATE INNER CLASS
* Browser to traverse leaf BPages.
*/
- static class Browser
- extends TupleBrowser
+ static class Browser extends TupleBrowser
{
/**
@@ -1136,7 +1262,6 @@ public final class BPage
*/
private BPage _page;
-
/**
* Current index in the page. The index positionned on the next
* tuple to return.
@@ -1156,41 +1281,49 @@ public final class BPage
_index = index;
}
- public boolean getNext( Tuple tuple )
- throws IOException
+
+ public boolean getNext( Tuple tuple ) throws IOException
{
- if ( _index < _page._btree._pageSize ) {
- if ( _page._keys[ _index ] == null ) {
+ if ( _index < _page._btree._pageSize )
+ {
+ if ( _page._keys[_index] == null )
+ {
// reached end of the tree.
return false;
}
- } else if ( _page._next != 0 ) {
+ }
+ else if ( _page._next != 0 )
+ {
// move to next page
_page = _page.loadBPage( _page._next );
_index = _page._first;
}
- tuple.setKey( _page._keys[ _index ] );
- tuple.setValue( _page._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 tuple ) throws IOException
{
- if ( _index == _page._first ) {
+ if ( _index == _page._first )
+ {
- if ( _page._previous != 0 ) {
+ if ( _page._previous != 0 )
+ {
_page = _page.loadBPage( _page._previous );
_index = _page._btree._pageSize;
- } else {
+ }
+ else
+ {
// reached beginning of the tree
return false;
}
}
_index--;
- tuple.setKey( _page._keys[ _index ] );
- tuple.setValue( _page._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=925852&r1=925851&r2=925852&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 Mar 21 18:22:25 2010
@@ -46,6 +46,7 @@
package jdbm.btree;
+
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
@@ -60,6 +61,7 @@ import jdbm.helper.Serializer;
import jdbm.helper.Tuple;
import jdbm.helper.TupleBrowser;
+
/**
* B+Tree persistent indexing data structure. B+Trees are optimized for
* block-based, random I/O storage because they store multiple keys on
@@ -87,8 +89,7 @@ import jdbm.helper.TupleBrowser;
* @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
* @version $Id: BTree.java,v 1.6 2005/06/25 23:12:31 doomdark Exp $
*/
-public class BTree
- implements Externalizable
+public class BTree implements Externalizable
{
private static final boolean DEBUG = false;
@@ -98,73 +99,62 @@ public class BTree
*/
final static long serialVersionUID = 1L;
-
/**
* Default page size (number of entries per node)
*/
public static final int DEFAULT_SIZE = 16;
-
/**
* Page manager used to persist changes in BPages
*/
protected transient RecordManager _recman;
-
/**
* This BTree's record ID in the PageManager.
*/
private transient long _recid;
-
/**
* Comparator used to index entries.
*/
protected Comparator _comparator;
-
/**
* Serializer used to serialize index keys (optional)
*/
protected Serializer _keySerializer;
-
/**
* Serializer used to serialize index values (optional)
*/
protected Serializer _valueSerializer;
-
/**
* Height of the B+Tree. This is the number of BPages you have to traverse
* to get to a leaf BPage, starting from the root.
*/
private int _height;
-
/**
* Recid of the root BPage
*/
private transient long _root;
-
/**
* Number of entries in each BPage.
*/
protected int _pageSize;
-
/**
* Total number of entries in the BTree
*/
protected int _entries;
-
/**
* Serializer used for BPages of this tree
*/
private transient BPage _bpageSerializer;
-
+
/**
* No-argument constructor used by serialization.
@@ -181,9 +171,7 @@ public class BTree
* @param recman Record manager used for persistence.
* @param comparator Comparator used to order index entries
*/
- public static BTree createInstance( RecordManager recman,
- Comparator comparator )
- throws IOException
+ public static BTree createInstance( RecordManager recman, Comparator comparator ) throws IOException
{
return createInstance( recman, comparator, null, null, DEFAULT_SIZE );
}
@@ -197,14 +185,10 @@ public class BTree
* @param valueSerializer Serializer used to serialize index values (optional)
* @param comparator Comparator used to order index entries
*/
- public static BTree createInstance( RecordManager recman,
- Comparator comparator,
- Serializer keySerializer,
- Serializer valueSerializer )
- throws IOException
+ public static BTree createInstance( RecordManager recman, Comparator comparator, Serializer keySerializer,
+ Serializer valueSerializer ) throws IOException
{
- return createInstance( recman, comparator, keySerializer,
- valueSerializer, DEFAULT_SIZE );
+ return createInstance( recman, comparator, keySerializer, valueSerializer, DEFAULT_SIZE );
}
@@ -217,37 +201,39 @@ public class BTree
* @param valueSerializer Serializer used to serialize index values (optional)
* @param pageSize Number of entries per page (must be even).
*/
- public static BTree createInstance( RecordManager recman,
- Comparator comparator,
- Serializer keySerializer,
- Serializer valueSerializer,
- int pageSize )
- throws IOException
+ public static BTree createInstance( RecordManager recman, Comparator comparator, Serializer keySerializer,
+ Serializer valueSerializer, int pageSize ) throws IOException
{
BTree btree;
- if ( recman == null ) {
+ if ( recman == null )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_517 ) );
}
- if ( comparator == null ) {
+ if ( comparator == null )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_518 ) );
}
- if ( ! ( comparator instanceof Serializable ) ) {
+ if ( !( comparator instanceof Serializable ) )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_519 ) );
}
- if ( keySerializer != null && ! ( keySerializer instanceof Serializable ) ) {
+ if ( keySerializer != null && !( keySerializer instanceof Serializable ) )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_520 ) );
}
- if ( valueSerializer != null && ! ( valueSerializer instanceof Serializable ) ) {
+ if ( valueSerializer != null && !( valueSerializer instanceof Serializable ) )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_521 ) );
}
// make sure there's an even number of entries per BPage
- if ( ( pageSize & 1 ) != 0 ) {
+ if ( ( pageSize & 1 ) != 0 )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_522 ) );
}
@@ -270,10 +256,9 @@ public class BTree
* @param recman RecordManager used to store the persistent btree
* @param recid Record id of the BTree
*/
- public static BTree load( RecordManager recman, long recid )
- throws IOException
+ public static BTree load( RecordManager recman, long recid ) throws IOException
{
- BTree btree = (BTree) recman.fetch( recid );
+ BTree btree = ( BTree ) recman.fetch( recid );
btree._recid = recid;
btree._recman = recman;
btree._bpageSerializer = new BPage();
@@ -294,22 +279,24 @@ public class BTree
* @param replace Set to true to replace an existing key-value pair.
* @return Existing value, if any.
*/
- public synchronized Object insert( Object key, Object value,
- boolean replace )
- throws IOException
+ public synchronized Object insert( Object key, Object value, boolean replace ) throws IOException
{
- if ( key == null ) {
+ if ( key == null )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
}
- if ( value == null ) {
+ if ( value == null )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_524 ) );
}
BPage rootPage = getRoot();
- if ( rootPage == null ) {
+ if ( rootPage == null )
+ {
// BTree is currently empty, create a new root BPage
- if (DEBUG) {
+ if ( DEBUG )
+ {
System.out.println( "BTree.insert() new root BPage" );
}
rootPage = new BPage( this, key, value );
@@ -318,12 +305,16 @@ public class BTree
_entries = 1;
_recman.update( _recid, this );
return null;
- } else {
+ }
+ else
+ {
BPage.InsertResult insert = rootPage.insert( _height, key, value, replace );
boolean dirty = false;
- if ( insert._overflow != null ) {
+ if ( insert._overflow != null )
+ {
// current root page overflowed, we replace with a new root page
- if ( DEBUG ) {
+ if ( DEBUG )
+ {
System.out.println( "BTree.insert() replace root BPage due to overflow" );
}
rootPage = new BPage( this, rootPage, insert._overflow );
@@ -331,11 +322,13 @@ public class BTree
_height += 1;
dirty = true;
}
- if ( insert._existing == null ) {
+ if ( insert._existing == null )
+ {
_entries++;
dirty = true;
}
- if ( dirty ) {
+ if ( dirty )
+ {
_recman.update( _recid, this );
}
// insert might have returned an existing value
@@ -351,35 +344,42 @@ public class BTree
* @return Value associated with the key, or null if no entry with given
* key existed in the BTree.
*/
- public synchronized Object remove( Object key )
- throws IOException
+ public synchronized Object remove( Object key ) throws IOException
{
- if ( key == null ) {
+ if ( key == null )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
}
BPage rootPage = getRoot();
- if ( rootPage == null ) {
+ if ( rootPage == null )
+ {
return null;
}
boolean dirty = false;
BPage.RemoveResult remove = rootPage.remove( _height, key );
- if ( remove._underflow && rootPage.isEmpty() ) {
+ if ( remove._underflow && rootPage.isEmpty() )
+ {
_height -= 1;
dirty = true;
- _recman.delete(_root);
- if ( _height == 0 ) {
+ _recman.delete( _root );
+ if ( _height == 0 )
+ {
_root = 0;
- } else {
- _root = rootPage.childBPage( _pageSize-1 )._recid;
+ }
+ else
+ {
+ _root = rootPage.childBPage( _pageSize - 1 )._recid;
}
}
- if ( remove._value != null ) {
+ if ( remove._value != null )
+ {
_entries--;
dirty = true;
}
- if ( dirty ) {
+ if ( dirty )
+ {
_recman.update( _recid, this );
}
return remove._value;
@@ -392,29 +392,36 @@ public class BTree
* @param key Lookup key.
* @return Value associated with the key, or null if not found.
*/
- public synchronized Object find( Object key )
- throws IOException
+ public synchronized Object find( Object key ) throws IOException
{
- if ( key == null ) {
+ if ( key == null )
+ {
throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
}
BPage rootPage = getRoot();
- if ( rootPage == null ) {
+ if ( rootPage == null )
+ {
return null;
}
Tuple tuple = new Tuple( null, null );
TupleBrowser browser = rootPage.find( _height, key );
- if ( browser.getNext( tuple ) ) {
+ if ( browser.getNext( tuple ) )
+ {
// find returns the matching key or the next ordered key, so we must
// check if we have an exact match
- if ( _comparator.compare( key, tuple.getKey() ) != 0 ) {
+ if ( _comparator.compare( key, tuple.getKey() ) != 0 )
+ {
return null;
- } else {
+ }
+ else
+ {
return tuple.getValue();
}
- } else {
+ }
+ else
+ {
return null;
}
}
@@ -428,13 +435,13 @@ public class BTree
* @return Value associated with the key, or a greater entry, or null if no
* greater entry was found.
*/
- public synchronized Tuple findGreaterOrEqual( Object key )
- throws IOException
+ public synchronized Tuple findGreaterOrEqual( Object key ) throws IOException
{
- Tuple tuple;
- TupleBrowser browser;
+ Tuple tuple;
+ TupleBrowser browser;
- if ( key == null ) {
+ if ( key == null )
+ {
// there can't be a key greater than or equal to "null"
// because null is considered an infinite key.
return null;
@@ -442,9 +449,12 @@ public class BTree
tuple = new Tuple( null, null );
browser = browse( key );
- if ( browser.getNext( tuple ) ) {
+ if ( browser.getNext( tuple ) )
+ {
return tuple;
- } else {
+ }
+ else
+ {
return null;
}
}
@@ -459,11 +469,11 @@ public class BTree
*
* @return Browser positionned at the beginning of the BTree.
*/
- public synchronized TupleBrowser browse()
- throws IOException
+ public synchronized TupleBrowser browse() throws IOException
{
BPage rootPage = getRoot();
- if ( rootPage == null ) {
+ if ( rootPage == null )
+ {
return EmptyBrowser.INSTANCE;
}
TupleBrowser browser = rootPage.findFirst();
@@ -483,11 +493,11 @@ public class BTree
* (Null is considered to be an "infinite" key)
* @return Browser positionned just before the given key.
*/
- public synchronized TupleBrowser browse( Object key )
- throws IOException
+ public synchronized TupleBrowser browse( Object key ) throws IOException
{
BPage rootPage = getRoot();
- if ( rootPage == null ) {
+ if ( rootPage == null )
+ {
return EmptyBrowser.INSTANCE;
}
TupleBrowser browser = rootPage.find( _height, key );
@@ -516,27 +526,27 @@ public class BTree
/**
* Return the root BPage, or null if it doesn't exist.
*/
- private BPage getRoot()
- throws IOException
+ private BPage getRoot() throws IOException
{
- if ( _root == 0 ) {
+ if ( _root == 0 )
+ {
return null;
}
- BPage root = (BPage) _recman.fetch( _root, _bpageSerializer );
+ BPage root = ( BPage ) _recman.fetch( _root, _bpageSerializer );
root._recid = _root;
root._btree = this;
return root;
}
+
/**
* Implement Externalizable interface.
*/
- public void readExternal( ObjectInput in )
- throws IOException, ClassNotFoundException
+ public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException
{
- _comparator = (Comparator) in.readObject();
- _keySerializer = (Serializer) in.readObject();
- _valueSerializer = (Serializer) in.readObject();
+ _comparator = ( Comparator ) in.readObject();
+ _keySerializer = ( Serializer ) in.readObject();
+ _valueSerializer = ( Serializer ) in.readObject();
_height = in.readInt();
_root = in.readLong();
_pageSize = in.readInt();
@@ -547,8 +557,7 @@ public class BTree
/**
* Implement Externalizable interface.
*/
- public void writeExternal( ObjectOutput out )
- throws IOException
+ public void writeExternal( ObjectOutput out ) throws IOException
{
out.writeObject( _comparator );
out.writeObject( _keySerializer );
@@ -564,8 +573,7 @@ public class BTree
{
_valueSerializer = valueSerializer;
}
-
-
+
/*
public void assert() throws IOException {
BPage root = getRoot();
@@ -575,7 +583,6 @@ public class BTree
}
*/
-
/*
public void dump() throws IOException {
BPage root = getRoot();
@@ -585,21 +592,21 @@ public class BTree
}
*/
-
/** PRIVATE INNER CLASS
* Browser returning no element.
*/
- static class EmptyBrowser
- extends TupleBrowser
+ static class EmptyBrowser extends TupleBrowser
{
static TupleBrowser INSTANCE = new EmptyBrowser();
+
public boolean getNext( Tuple tuple )
{
return false;
}
+
public boolean getPrevious( Tuple tuple )
{
return false;
@@ -615,4 +622,3 @@ public class BTree
return _comparator;
}
}
-