directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r925852 - in /directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree: BPage.java BTree.java
Date Sun, 21 Mar 2010 18:22:26 GMT
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;
     }
 }
-



Mime
View raw message