directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r947346 - in /directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree: BPage.java BTree.java
Date Sat, 22 May 2010 22:38:40 GMT
Author: elecharny
Date: Sat May 22 22:38:40 2010
New Revision: 947346

URL: http://svn.apache.org/viewvc?rev=947346&view=rev
Log:
o Added a setPageSize() method to allow a user to configure it once the BTree has been created.
o Improved the search for a key : if the key already exists, we can spare a useless compare().
Everytime the key is not the rightmost element of a BPage, we don't call compare() for nothing.

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=947346&r1=947345&r2=947346&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 Sat May 22 22:38:40
2010
@@ -266,6 +266,12 @@ public class BPage<K, V> implements Seri
     TupleBrowser<K, V> find( int height, K key ) throws IOException
     {
         int index = this.findChildren( key );
+        
+        if ( index < 0 )
+        {
+            index = -( index + 1 );
+        }
+
         BPage<K, V> child = this;
 
         while ( !child.isLeaf )
@@ -273,6 +279,11 @@ public class BPage<K, V> implements Seri
             // non-leaf BPage
             child = child.loadBPage( child.children[index] );
             index = child.findChildren( key );
+            
+            if ( index < 0 )
+            {
+                index = -( index + 1 );
+            }
         }
 
         return new Browser( child, index );
@@ -318,12 +329,17 @@ public class BPage<K, V> implements Seri
         long overflow;
 
         int index = findChildren( key );
+        boolean keyExists = index < 0;
+        
+        if ( index < 0 )
+        {
+            index = -( index + 1 );
+        }
 
         height -= 1;
         
         if ( height == 0 )
         {
-
             result = new InsertResult<K, V>();
 
             // inserting on a leaf BPage
@@ -334,8 +350,11 @@ public class BPage<K, V> implements Seri
                 System.out.println( "Bpage.insert() Insert on leaf Bpage key=" + key + "
value=" + value + " index="
                     + index );
             }
-            
-            if ( compare( key, keys[index] ) == 0 )
+
+            // This is to deal with the special case where the key already exists.
+            // In this case, the index will contain the key's position, but as a 
+            // negative number
+            if ( keyExists )
             {
                 // key already exists
                 if ( DEBUG )
@@ -509,13 +528,19 @@ public class BPage<K, V> implements Seri
 
         int half = btree.pageSize / 2;
         int index = findChildren( key );
+        boolean keyExists = index < 0;
+        
+        if ( index < 0 )
+        {
+            index = -( index + 1 );
+        }
 
         height -= 1;
         
         if ( height == 0 )
         {
             // remove leaf entry
-            if ( compare( keys[index], key ) != 0 )
+            if ( !keyExists )
             {
                 throw new IllegalArgumentException( I18n.err( I18n.ERR_514, key ) );
             }
@@ -763,7 +788,8 @@ public class BPage<K, V> implements Seri
      * Find the first children node with a key equal or greater than the given
      * key.
      *
-     * @return index of first children with equal or greater key.
+     * @return index of first children with equal or greater key. If the 
+     * key already exists, the index value will be negative
      */
     private int findChildren( K key )
     {
@@ -775,14 +801,31 @@ public class BPage<K, V> implements Seri
         {
             int middle = ( left + right ) >> 1;
             
-            if ( compare( keys[middle], key ) < 0 )
+            int comp = compare( keys[middle], key );
+            
+            if ( comp < 0 )
             {
                 left = middle + 1;
             }
-            else
+            else if ( comp > 0 )
             {
                 right = middle;
             }
+            else
+            {
+                // Special case : the key already exists,
+                // we can return immediately
+                return -middle - 1;
+            }
+        }
+        
+        if ( left == right )
+        {
+            // Special case : we don't know if the key is present
+            if ( compare( keys[left], key ) ==0 )
+            {
+                return -right - 1;
+            }
         }
         
         return right;
@@ -1381,4 +1424,74 @@ public class BPage<K, V> implements Seri
             return true;
         }
     }
+    
+    
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+        
+        if ( isLeaf )
+        {
+            sb.append( "Leaf(" );
+        }
+        else
+        {
+            sb.append( "Node(" );
+        }
+        
+        sb.append( keys.length );
+        sb.append( ") : [" );
+        
+        if ( isLeaf )
+        {
+            boolean isFirst = true;
+            int index = 0;
+            
+            for ( K key : keys )
+            {
+                if ( isFirst )
+                {
+                    isFirst = false;
+                }
+                else
+                {
+                    sb.append( ", " );
+                }
+
+                sb.append( "<" );
+                sb.append( String.valueOf( key ) );
+                sb.append( "/" );
+                sb.append( values[index] );
+                sb.append( ">" );
+                
+                index++;
+            }
+        }
+        else
+        {
+            boolean isFirst = true;
+            //int index = 0;
+            
+            for ( K key : keys )
+            {
+                if ( isFirst )
+                {
+                    isFirst = false;
+                }
+                else
+                {
+                    sb.append( ", " );
+                }
+
+                sb.append( "<" );
+                sb.append( key );
+                //sb.append( "/" );
+                //sb.append( values[index] );
+                sb.append( ">" );
+            }
+        }
+
+        sb.append( "]\n" );
+        return sb.toString();
+    }
 }

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=947346&r1=947345&r2=947346&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 Sat May 22 22:38:40
2010
@@ -234,6 +234,19 @@ public class BTree<K, V> implements Exte
 
         this.recordId = recman.insert( this );
     }
+    
+    
+    public void setPageSize( int pageSize )
+    {
+        if ( ( pageSize & 0x0001 ) != 0 )
+        {
+            this.pageSize = DEFAULT_SIZE;
+        }
+        else
+        {
+            this.pageSize = pageSize;
+        }
+    }
 
 
     /**



Mime
View raw message