directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r637640 - in /directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src: main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/ test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/
Date Sun, 16 Mar 2008 20:13:33 GMT
Author: akarasulu
Date: Sun Mar 16 13:13:31 2008
New Revision: 637640

URL: http://svn.apache.org/viewvc?rev=637640&view=rev
Log:
fixed major performance issue with hasLessOrEqual() lookups from older code and greatly simplifed
the code with more test coverage

Modified:
    directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java
    directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableNoDuplicatesTest.java

Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java?rev=637640&r1=637639&r2=637640&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java
Sun Mar 16 13:13:31 2008
@@ -514,66 +514,40 @@
      */
     public boolean hasLessOrEqual( K key ) throws IOException
     {
-        // See if we can find the border between keys greater than and less
-        // than in the set of keys.  This will be the spot we search from.
+        // Can only find greater than or equal to with JDBM so we find that
+        // and work backwards to see if we can find one less than the key
         jdbm.helper.Tuple tuple = bt.findGreaterOrEqual( key );
 
-        // Test for equality first since it satisfies both greater/less than
+        // Test for equality first since it satisfies equal to condition
         //noinspection unchecked
         if ( null != tuple && keyComparator.compare( ( K ) tuple.getKey(), key )
== 0 )
         {
             return true;
         }
 
-        // Less than searches are not as efficient or easy as greaterOrEqual.
-        // We need to scan up from the begining if findGreaterOrEqual failed
-        // or scan down if findGreaterOrEqual succeed.
-        TupleBrowser browser;
         if ( null == tuple )
         {
-            // findGreaterOrEqual failed so we create a tuple and scan from
-            // the lowest values up via getNext comparing each key to key
-            tuple = new jdbm.helper.Tuple();
-            browser = bt.browse();
-
-            // We should at most have to read one key.  If 1st key is not
-            // less than or equal to key then all keys are > key
-            // since the keys are assorted in ascending order based on the
-            // comparator.
-            if ( browser.getNext( tuple ) )
-            {
-                //noinspection unchecked
-                return keyComparator.compare( ( K ) tuple.getKey(), key ) <= 0;
-            }
+            /*
+             * Jdbm failed to find a key greater than or equal to the argument
+             * which means all the keys in the table are less than the
+             * supplied key argument.  We can hence return true if the table
+             * contains any Tuples.
+             */
+            return count > 0;
         }
         else
         {
-            // findGreaterOrEqual succeeded so use the existing tuple and
-            // scan the down from the highest key less than key via
-            // getPrevious while comparing each key to key.
-            browser = bt.browse( tuple.getKey() );
-
-            // The above call positions the browser just before the given
-            // key so we need to step forward once then back.  Remember this
-            // key represents a key greater than or equal to key.
-            //noinspection unchecked
-            if ( keyComparator.compare( ( K ) tuple.getKey(), key ) <= 0 )
+            /*
+             * We have the next tuple whose key is the next greater than the
+             * key argument supplied.  We use this key to advance a browser to
+             * that tuple and scan down to lesser Tuples until we hit one
+             * that is less than the key argument supplied.  Usually this will
+             * be the previous tuple if it exists.
+             */
+            TupleBrowser browser = bt.browse( tuple.getKey() );
+            if ( browser.getPrevious( tuple ) )
             {
                 return true;
-            }
-
-            browser.getNext( tuple );
-
-            // We should at most have to read one key, but we don't short
-            // the search as in the search above first because the chance of
-            // unneccessarily looping is nil since values get smaller.
-            while ( browser.getPrevious( tuple ) )
-            {
-                //noinspection unchecked
-                if ( keyComparator.compare( ( K ) tuple.getKey(), key ) <= 0 )
-                {
-                    return true;
-                }
             }
         }
 

Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableNoDuplicatesTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableNoDuplicatesTest.java?rev=637640&r1=637639&r2=637640&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableNoDuplicatesTest.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableNoDuplicatesTest.java
Sun Mar 16 13:13:31 2008
@@ -251,7 +251,14 @@
         assertFalse( table.has( 1 ) );
     }
     
+
+    @Test
+    public void testPut() throws Exception
+    {
+
+    }
     
+
     @Test
     public void testHas() throws Exception
     {
@@ -279,6 +286,9 @@
         assertFalse( table.has( SIZE ) );
         assertFalse( table.hasGreaterOrEqual( SIZE ) );
         assertTrue( table.hasLessOrEqual( SIZE ) );
+        table.remove( 10 );
+        table.remove( 11 );
+        assertTrue( table.hasLessOrEqual( 11 ) );
         
         try
         {



Mime
View raw message