directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r637683 - 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 23:12:08 GMT
Author: akarasulu
Date: Sun Mar 16 16:12:06 2008
New Revision: 637683

URL: http://svn.apache.org/viewvc?rev=637683&view=rev
Log:
changes to JdbmTable ...

 o added more test cases for full 100% test coverage
 o simplified and fixed inefficiencies
 o added capability to revert back to using AVL tree instead of B+Tree when 
   remove operations drop the count below the duplicate limit


Modified:
    directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java
    directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmMasterTable.java
    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
    directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableWithDuplicatesTest.java

Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.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/JdbmIndex.java?rev=637683&r1=637682&r2=637683&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java
Sun Mar 16 16:12:06 2008
@@ -420,7 +420,7 @@
     /**
      * @see Index#add(Object, Long)
      */
-    public synchronized void add( K attrVal, Long id ) throws IOException
+    public synchronized void add( K attrVal, Long id ) throws Exception
     {
         forward.put( getNormalized( attrVal ), id );
         reverse.put( id, getNormalized( attrVal ) );

Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmMasterTable.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/JdbmMasterTable.java?rev=637683&r1=637682&r2=637683&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmMasterTable.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmMasterTable.java
Sun Mar 16 16:12:06 2008
@@ -102,7 +102,7 @@
     }
 
 
-    public E put( E entry, Long id ) throws IOException
+    public E put( E entry, Long id ) throws Exception
     {
         return super.put( id, entry );
     }
@@ -114,7 +114,7 @@
     }
 
 
-    public Long getCurrentId() throws IOException
+    public Long getCurrentId() throws Exception
     {
         Long id;
 
@@ -134,7 +134,7 @@
     }
 
 
-    public Long getNextId() throws IOException
+    public Long getNextId() throws Exception
     {
         Long nextVal;
         Long lastVal;
@@ -169,7 +169,7 @@
     }
 
 
-    public void setProperty( String property, String value ) throws IOException
+    public void setProperty( String property, String value ) throws Exception
     {
         synchronized ( adminTbl )
         {

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=637683&r1=637682&r2=637683&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 16:12:06 2008
@@ -22,15 +22,12 @@
 
 import jdbm.RecordManager;
 import jdbm.btree.BTree;
-import jdbm.helper.Serializer;
-import jdbm.helper.TupleBrowser;
+import jdbm.helper.*;
 
-import org.apache.directory.server.core.avltree.AvlTree;
-import org.apache.directory.server.core.avltree.AvlTreeMarshaller;
-import org.apache.directory.server.core.avltree.Marshaller;
-import org.apache.directory.server.core.avltree.LinkedAvlNode;
+import org.apache.directory.server.core.avltree.*;
 import org.apache.directory.server.core.cursor.Cursor;
 import org.apache.directory.server.core.partition.impl.btree.*;
+import org.apache.directory.server.core.partition.impl.btree.Tuple;
 import org.apache.directory.server.schema.SerializableComparator;
 import org.apache.directory.shared.ldap.util.SynchronizedLRUMap;
 
@@ -151,30 +148,26 @@
 
         long recId = recMan.getNamedObject( name );
 
-        //
-        // Load existing BTree
-        //
-
-        if ( recId != 0 )
-        {
-            bt = BTree.load( recMan, recId );
-            recId = recMan.getNamedObject( name + SZSUFFIX );
-            count = ( Integer ) recMan.fetch( recId );
-        }
-        else
+        if ( recId == 0 ) // Create new main BTree
         {
             // we do not use the value serializer in the btree since duplicates will use
             // either BTreeRedirect objects or AvlTree objects whose marshalling is
             // explicitly managed by this code.  Value serialization is delegated to these
             // marshallers.
-            
+
             bt = BTree.createInstance( recMan, keyComparator, keySerializer, null );
             recId = bt.getRecid();
             recMan.setNamedObject( name, recId );
             recId = recMan.insert( 0 );
             recMan.setNamedObject( name + SZSUFFIX, recId );
         }
-        
+        else // Load existing BTree
+        {
+            bt = BTree.load( recMan, recId );
+            recId = recMan.getNamedObject( name + SZSUFFIX );
+            count = ( Integer ) recMan.fetch( recId );
+        }
+
     }
 
 
@@ -341,7 +334,7 @@
 
         if ( ! allowsDuplicates )
         {
-            if ( null == getNoDups( key ) )
+            if ( null == bt.find( key ) )
             {
                 return 0;
             }
@@ -351,21 +344,12 @@
             }
         }
 
-        DupsContainer values = getDups( key );
-        
-        // -------------------------------------------------------------------
-        // Handle the use of a AvlTree for storing duplicates
-        // -------------------------------------------------------------------
-
+        DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
         if ( values.isAvlTree() )
         {
             return values.getAvlTree().getSize();
         }
 
-        // -------------------------------------------------------------------
-        // Handle the use of a BTree for storing duplicates
-        // -------------------------------------------------------------------
-
         return getBTree( values.getBTreeRedirect() ).size();
     }
 
@@ -393,11 +377,11 @@
 
         if ( ! allowsDuplicates )
         {
-            return getNoDups( key );
+            //noinspection unchecked
+            return ( V ) bt.find( key );
         }                         
 
-        DupsContainer values = getDups( key );
-
+        DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
         if ( values.isAvlTree() )
         {
             //noinspection unchecked
@@ -413,7 +397,10 @@
 
         // Handle values if they are stored in another BTree
         BTree tree = getBTree( values.getBTreeRedirect() );
-        return firstKey( tree );
+        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+        tree.browse().getNext( tuple );
+        //noinspection unchecked
+        return ( V ) tuple.getKey();
     }
 
     
@@ -434,8 +421,7 @@
             		"does not contain a value comparator which is needed to answer your ordering
question." );
         }
 
-        DupsContainer values = getDups( key );
-
+        DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
         if ( values.isAvlTree() )
         {
             AvlTree<V> set = values.getAvlTree();
@@ -466,8 +452,7 @@
             		"does not contain a value comparator which is needed to answer your ordering
question." );
         }
 
-        DupsContainer values = getDups( key );
-
+        DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
         if ( values.isAvlTree() )
         {
             AvlTree<V> set = values.getAvlTree();
@@ -568,19 +553,18 @@
 
         if ( ! allowsDuplicates )
         {
-            V stored = getNoDups( key );
+            //noinspection unchecked
+            V stored = ( V ) bt.find( key );
             return null != stored && stored.equals( value );
         }
         
-        DupsContainer values = getDups( key );
-        
+        DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
         if ( values.isAvlTree() )
         {
-            //noinspection unchecked
             return values.getAvlTree().find( value ) != null;
         }
         
-        return btreeHas( getBTree( values.getBTreeRedirect() ), value );
+        return getBTree( values.getBTreeRedirect() ).find( value ) != null;
     }
     
 
@@ -598,7 +582,7 @@
      * java.lang.Object)
      */
     @SuppressWarnings("unchecked")
-    public V put( K key, V value ) throws IOException
+    public V put( K key, V value ) throws Exception
     {
         if ( value == null || key == null )
         {
@@ -619,15 +603,13 @@
             return replaced;
         }
         
-        DupsContainer values = getDups( key );
-        
+        DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
         if ( values.isAvlTree() )
         {
             AvlTree<V> set = values.getAvlTree();
+            replaced = set.insert( value );
             
-            V result = set.insert( value );
-            
-            if ( result != null )// if the value already present returns the same value
+            if ( replaced != null )// if the value already present returns the same value
             {
                 return value;
             }
@@ -636,12 +618,11 @@
             {
                 BTree tree = convertToBTree( set );
                 BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() );
-                replaced = ( V ) bt.insert( key,
-                        BTreeRedirectMarshaller.INSTANCE.serialize( redirect ), true );
+                bt.insert( key, BTreeRedirectMarshaller.INSTANCE.serialize( redirect ), true
);
             }
             else
             {
-                replaced = ( V ) bt.insert( key, marshaller.serialize( set ), true );
+                bt.insert( key, marshaller.serialize( set ), true );
             }
 
             count++;
@@ -649,12 +630,13 @@
         }
         
         BTree tree = getBTree( values.getBTreeRedirect() );
+        replaced = ( V ) tree.insert( value, EMPTY_BYTES, true );
         
-        if ( insertDupIntoBTree( tree, value ) )
+        if ( replaced == null )
         {
             count++;
         }
-        return null;
+        return replaced;
     }
     
 
@@ -664,9 +646,15 @@
      */
     public V remove( K key, V value ) throws IOException
     {
+        if ( key == null )
+        {
+            return null;
+        }
+
         if ( ! allowsDuplicates )
         {
-            V oldValue = getNoDups( key );
+            //noinspection unchecked
+            V oldValue = ( V ) bt.find( key );
         
             // Remove the value only if it is the same as value.
             if ( oldValue != null && oldValue.equals( value ) )
@@ -679,16 +667,9 @@
             return null;
         }
 
-        DupsContainer values = getDups( key );
-        
-        if ( values == null )
-        {
-            return null;
-        }
-        
+        DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
         if ( values.isAvlTree() )
         {
-            //noinspection unchecked
             AvlTree<V> set = values.getAvlTree();
 
             // If removal succeeds then remove if set is empty else replace it
@@ -709,13 +690,19 @@
             return null;
         }
 
-        // TODO might be nice to add code here that reverts to a AvlTree
         // if the number of duplicates falls below the numDupLimit value
         BTree tree = getBTree( values.getBTreeRedirect() );
         if ( removeDupFromBTree( tree, value ) )
         {
-            if ( tree.size() == 0 )
+            /*
+             * If we drop below the duplicate limit then we revert from using
+             * a Jdbm BTree to using an in memory AvlTree.
+             */
+            if ( tree.size() <= numDupLimit )
             {
+                AvlTree<V> avlTree = convertToAvlTree( tree );
+                bt.insert( key, marshaller.serialize( avlTree ), true );
+                recMan.delete( tree.getRecid() );
             }
             
             count--;
@@ -727,11 +714,15 @@
 
 
     /**
-     * @see Table#remove(java.lang.Object)
+     * @see Table#remove(Object)
      */
     public V remove( K key ) throws IOException
     {
-        //noinspection unchecked
+        if ( key == null )
+        {
+            return null;
+        }
+
         Object returned = bt.remove( key );
 
         if ( null == returned )
@@ -746,25 +737,20 @@
             return ( V ) returned;
         }
 
-        if ( ! ( returned instanceof byte[] ) )
-        {
-            throw new IllegalStateException( "Expecting byte[] from returned element." );
-        }
-
         byte[] serialized = ( byte[] ) returned;
 
-        if ( ! BTreeRedirectMarshaller.isRedirect( serialized ) )
+        if ( BTreeRedirectMarshaller.isRedirect( serialized ) )
+        {
+            BTree tree = getBTree( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized
) );
+            this.count -= tree.size();
+            return removeAll( tree );
+        }
+        else
         {
-            //noinspection unchecked
             AvlTree<V> set = marshaller.deserialize( serialized );
             this.count -= set.getSize();
             return set.getFirst().getKey();
         }
-
-        //noinspection ConstantConditions
-        BTree tree = getBTree( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized )
);
-        this.count -= tree.size();
-        return removeAll( tree );
     }
 
 
@@ -801,16 +787,7 @@
     public void sync() throws IOException
     {
         long recId = recMan.getNamedObject( name + SZSUFFIX );
-
-        if ( 0 == recId )
-        {
-            //noinspection UnusedAssignment
-            recId = recMan.insert( count );
-        }
-        else
-        {
-            recMan.update( recId, count );
-        }
+        recMan.update( recId, count );
     }
 
     
@@ -821,28 +798,10 @@
     
 
     // ------------------------------------------------------------------------
-    // Private Utility Methods 
+    // Private/Package Utility Methods 
     // ------------------------------------------------------------------------
 
 
-    private V getNoDups( K key ) throws IOException
-    {
-        if ( null == key )
-        {
-            return null;
-        }
-
-        if ( ! allowsDuplicates )
-        {
-            //noinspection unchecked
-            return ( V ) bt.find( key );
-        }
-
-        throw new IllegalStateException(
-                "This method should not be called when duplicates are enabled" );
-    }
-
-
     DupsContainer<V> getDupsContainer( byte[] serialized ) throws IOException
     {
         if ( serialized == null )
@@ -859,23 +818,6 @@
     }
 
 
-    private DupsContainer<V> getDups( K key ) throws IOException
-    {
-        if ( null == key )
-        {
-            return null;
-        }
-
-        if ( allowsDuplicates )
-        {
-            return getDupsContainer( ( byte[] ) bt.find( key ) );
-        }
-
-        throw new IllegalStateException(
-                "This method should not be called when duplicates are enabled" );
-    }
-
-
     /**
      * Returns the main BTree used by this table.
      *
@@ -900,23 +842,6 @@
     }
 
 
-    private V firstKey ( BTree tree ) throws IOException
-    {
-        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
-        boolean success = tree.browse().getNext( tuple );
-            
-        if ( success )
-        {
-            //noinspection unchecked
-            return ( V ) tuple.getKey();
-        }
-        else
-        {
-            return null;
-        }
-    }
-
-    
     private boolean btreeHas( BTree tree, V key, boolean isGreaterThan ) throws IOException
     {
         jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
@@ -928,71 +853,31 @@
         }
         else
         {
-            boolean success = browser.getPrevious( tuple );
-            if ( success )
+            if ( browser.getPrevious( tuple ) )
             {
                 return true;
             }
             else
             {
                 /*
-                 * Calls to getPrevious() will return a lower key even
-                 * if there exists a key equal to the one searched
-                 * for.  Since isGreaterThan when false really means
-                 * 'less than or equal to' we must check to see if
-                 * the key in front is equal to the key argument provided.
+                 * getPrevious() above fails which means the browser has is
+                 * before the first Tuple of the btree.  A call to getNext()
+                 * should work every time.
                  */
-                success = browser.getNext( tuple );
-                if ( success )
-                {
-                    /*
-                     * Note that keys in these embedded BTrees really store
-                     * duplicate values of similar keys in this BTree.
-                     */
-
-                    //noinspection unchecked
-                    V biggerKey = ( V ) tuple.getKey();
-                    if ( valueComparator.compare( key, biggerKey ) == 0 )
-                    {
-                        return true;
-                    }
-                }
-                return false;
-            }
-        }
-    }
-
-
-    private boolean btreeHas( BTree tree, V key ) throws IOException
-    {
-        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
-        
-        TupleBrowser browser = tree.browse( key );
-        boolean success = browser.getNext( tuple );
-        if ( success )
-        {
-            /*
-             * Note that keys in these embedded BTrees really store
-             * duplicate values of similar keys in this BTree.
-             */
+                browser.getNext( tuple );
 
-            //noinspection unchecked
-            if ( valueComparator.compare( key, ( V ) tuple.getKey() ) == 0 )
-            {
-                return true;
+                /*
+                 * Since the browser is positioned now on the Tuple with the
+                 * smallest key we just need to check if it equals this key
+                 * which is the only chance for returning true.
+                 */
+                //noinspection unchecked
+                V firstKey = ( V ) tuple.getKey();
+                return valueComparator.compare( key, firstKey ) == 0;
             }
         }
-
-        return false;
     }
 
-    
-    private boolean insertDupIntoBTree( BTree tree, V value ) throws IOException
-    {
-        Object replaced = tree.insert( value, EMPTY_BYTES, true );
-        return null == replaced;
-    }
-    
 
     private boolean removeDupFromBTree( BTree tree, V value ) throws IOException
     {
@@ -1003,27 +888,43 @@
         }
         return null != removed;
     }
+
+
+    private AvlTree<V> convertToAvlTree( BTree bTree ) throws IOException
+    {
+        AvlTree<V> avlTree = new AvlTree<V>( valueComparator );
+        TupleBrowser browser = bTree.browse();
+        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+        while ( browser.getNext( tuple ) )
+        {
+            //noinspection unchecked
+            avlTree.insert( ( V ) tuple.getKey() );
+        }
+
+        return avlTree;
+    }
     
 
-    private BTree convertToBTree( AvlTree<V> set ) throws IOException
+    private BTree convertToBTree( AvlTree<V> avlTree ) throws Exception
     {
-        BTree tree;
+        BTree bTree;
 
         if ( valueSerializer != null )
         {
-            tree = BTree.createInstance( recMan, valueComparator, valueSerializer, null );
+            bTree = BTree.createInstance( recMan, valueComparator, valueSerializer, null
);
         }
         else
         {
-            tree = BTree.createInstance( recMan, valueComparator );
+            bTree = BTree.createInstance( recMan, valueComparator );
         }
 
-        List<V> keys = set.getKeys();
-        for ( V element : keys )
+        Cursor<V> keys = new AvlTreeCursor<V>( avlTree );
+        keys.beforeFirst();
+        while ( keys.next() )
         {
-            tree.insert( element, EMPTY_BYTES, true );
+            bTree.insert( keys.get(), EMPTY_BYTES, true );
         }
-        return tree;
+        return bTree;
     }
     
     

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=637683&r1=637682&r2=637683&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 16:12:06 2008
@@ -253,9 +253,28 @@
     
 
     @Test
+    public void testRemove() throws Exception
+    {
+        table.put( 1, 1 );
+        assertEquals( 1, ( int ) table.remove( 1 ) );
+        table.put( 10, 10 );
+        assertNull( table.remove( 10, 11 ) );
+        assertNull( table.remove( null ) );
+        assertNull( table.remove( null, null ) );
+    }
+
+
+    @Test
     public void testPut() throws Exception
     {
+        final int SIZE = 15;
 
+        for ( int ii = 0; ii < SIZE; ii++ )
+        {
+            table.put( ii, ii );
+        }
+        assertEquals( SIZE, table.count() );
+        assertNotNull( table.put( 0, 0 ) );
     }
     
 

Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableWithDuplicatesTest.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/JdbmTableWithDuplicatesTest.java?rev=637683&r1=637682&r2=637683&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableWithDuplicatesTest.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableWithDuplicatesTest.java
Sun Mar 16 16:12:06 2008
@@ -28,6 +28,8 @@
 
 import org.apache.directory.server.core.partition.impl.btree.Table;
 import org.apache.directory.server.core.partition.impl.btree.TupleRenderer;
+import org.apache.directory.server.core.partition.impl.btree.Tuple;
+import org.apache.directory.server.core.cursor.Cursor;
 import org.apache.directory.server.schema.SerializableComparator;
 import org.apache.directory.server.schema.registries.ComparatorRegistry;
 import org.apache.directory.shared.ldap.schema.syntax.ComparatorDescription;
@@ -206,40 +208,63 @@
         assertFalse( table.hasGreaterOrEqual( 1, 0 ) );
         assertFalse( table.hasLessOrEqual( 1, 0 ) );
     }
-    
-    
+
+
+    @Test
+    public void testPut() throws Exception
+    {
+        final int SIZE = 15;
+
+        for ( int ii = 0; ii < SIZE; ii++ )
+        {
+            table.put( ii, ii );
+        }
+        assertEquals( SIZE, table.count() );
+        assertNotNull( table.put( 0, 0 ) );
+
+        // add some duplicates
+        for ( int ii = 0; ii < SIZE*2; ii++ )
+        {
+            table.put( SIZE*2, ii );
+        }
+        assertEquals( SIZE*3, table.count() );
+        assertNotNull( table.put( 0, 0 ) );
+        assertNotNull( table.put( SIZE*2, 0 ) );
+    }
+
+
     @Test
     public void testHas() throws Exception
     {
         assertFalse( table.has( 1 ) );
         
-        for ( int ii = 0; ii < SIZE; ii++ )
+        for ( int ii = 0; ii < SIZE*2; ii++ )
         {
             table.put( 1, ii );
         }
-        assertEquals( SIZE, table.count() );
+        assertEquals( SIZE*2, table.count() );
 
         assertTrue( table.has( 1 ) );
         assertTrue( table.has( 1, 0 ) );
-        assertFalse( table.has( 1, SIZE ) );
+        assertFalse( table.has( 1, SIZE*2 ) );
 
         assertTrue( table.hasGreaterOrEqual( 1, 0 ) );
         assertTrue( table.hasLessOrEqual( 1, 0 ) );
         assertFalse( table.hasLessOrEqual( 1, -1 ) );
 
-        assertTrue( table.hasGreaterOrEqual( 1, SIZE - 1 ) );
-        assertTrue( table.hasLessOrEqual( 1, SIZE - 1 ) );
-        assertTrue( table.hasGreaterOrEqual( 1, SIZE - 1 ) );
-        assertTrue( table.hasLessOrEqual( 1, SIZE ) );
-        assertFalse( table.hasGreaterOrEqual( 1, SIZE ) );
-        assertFalse( table.has( 1, SIZE ) );
+        assertTrue( table.hasGreaterOrEqual( 1, SIZE*2 - 1 ) );
+        assertTrue( table.hasLessOrEqual( 1, SIZE*2 - 1 ) );
+        assertTrue( table.hasGreaterOrEqual( 1, SIZE*2 - 1 ) );
+        assertTrue( table.hasLessOrEqual( 1, SIZE*2 ) );
+        assertFalse( table.hasGreaterOrEqual( 1, SIZE*2 ) );
+        assertFalse( table.has( 1, SIZE*2 ) );
 
         // let's go over the this limit now and ask the same questions
-        table.put( 1, SIZE );
+        table.put( 1, SIZE*2 );
 
         assertTrue( table.has( 1 ) );
         assertTrue( table.has( 1, 0 ) );
-        assertTrue( table.has( 1, SIZE ) );
+        assertTrue( table.has( 1, SIZE*2 ) );
         assertFalse( table.has( null, null ) );
 
         assertTrue( table.hasGreaterOrEqual( 1, 0 ) );
@@ -248,15 +273,13 @@
         assertFalse( table.hasGreaterOrEqual( null, null ) );
         assertFalse( table.hasLessOrEqual( null, null ) );
 
-        assertTrue( table.hasGreaterOrEqual( 1, SIZE ) );
-        assertTrue( table.hasLessOrEqual( 1, SIZE ) );
-        assertTrue( table.hasGreaterOrEqual( 1, SIZE ) );
-        assertTrue( table.hasLessOrEqual( 1, SIZE + 1 ) );
-        assertFalse( table.hasGreaterOrEqual( 1, SIZE + 1 ) );
-        assertFalse( table.has( 1, SIZE+1 ) );
+        assertTrue( table.hasGreaterOrEqual( 1, SIZE*2 ) );
+        assertTrue( table.hasLessOrEqual( 1, SIZE*2 ) );
+        assertTrue( table.hasGreaterOrEqual( 1, SIZE*2 ) );
+        assertTrue( table.hasLessOrEqual( 1, SIZE*2 + 1 ) );
+        assertFalse( table.hasGreaterOrEqual( 1, SIZE*2 + 1 ) );
+        assertFalse( table.has( 1, SIZE*2 + 1 ) );
         
-        table.remove( 1 );
-
         // now do not add duplicates and check has( key, boolean )
         for ( int ii = 0; ii < SIZE; ii++ )
         {
@@ -279,15 +302,69 @@
         assertFalse( table.has( SIZE ) );
         assertFalse( table.hasGreaterOrEqual( SIZE ) );
         assertTrue( table.hasLessOrEqual( SIZE ) );
+
+        for ( int ii = 0; ii < SIZE; ii++ )
+        {
+            if ( ii == 1 ) // don't delete the node which had multiple values
+            {
+                continue;
+            }
+            table.remove( ii, ii );
+        }
+        
+        // delete all values of the duplicate key one by one
+        for ( int ii = 0; ii < SIZE * 2 + 1; ii++ )
+        {
+            table.remove( 1, ii );
+        }
+
+        Cursor<Tuple<Integer, Integer>> cursor = table.cursor();
+        System.out.println( "remaining ..." );
+        cursor.beforeFirst();
+        while ( cursor.next() )
+        {
+            System.out.println( cursor.get() );
+        }
+
+        assertFalse( table.hasLessOrEqual( 1 ) );
+        assertFalse( table.hasLessOrEqual( 1, 10 ) );
+        assertFalse( table.hasGreaterOrEqual( 1 ) );
+        assertFalse( table.hasGreaterOrEqual( 1, 0 ) );
+
+        table.put( 1, 0 );
+
     }
 
     
     @Test
     public void testRemove() throws Exception
     {
+        assertEquals( 0, table.count() );
+
         table.put( 1, 1 );
         table.put( 1, 2 );
-        table.remove( 1 );
+        assertEquals( 2, table.count() );
+        assertEquals( 1, ( int ) table.remove( 1 ) );
+        assertEquals( 0, table.count() );
+
+        table.put( 10, 10 );
+        assertEquals( 1, table.count() );
+        assertNull( table.remove( 10, 11 ) );
+        assertEquals( 1, table.count() );
+        assertNotNull( table.remove( 10, 10 ) );
+        assertEquals( 0, table.count() );
+
+        // add duplicates
+        for ( int ii = 0; ii < SIZE*2; ii++ )
+        {
+            table.put( 0, ii );
+        }
+
+        assertEquals( SIZE*2, table.count() );
+        assertNull( table.remove( 0, 100 ) );
+        assertEquals( SIZE*2, table.count() );
+
+        assertEquals( 0, ( int ) table.remove( 0 ) );
     }
     
     
@@ -325,46 +402,49 @@
     @Test
     public void testDuplicateLimit() throws Exception
     {
-        for ( int ii = 0; ii < SIZE-1; ii++ )
+        for ( int ii = 0; ii < SIZE; ii++ )
         {
             table.put( 1, ii );
         }
-        assertEquals( SIZE-1, table.count() );
-        
-        table.put( 1, SIZE-1 );
         assertEquals( SIZE, table.count() );
-        
-        // this switches to B+Trees in JDBM implementations
+        assertEquals( SIZE, table.count( 1 ) );
+
+        // this switches to B+Trees from AvlTree
         table.put( 1, SIZE );
-        assertEquals( SIZE+1, table.count() );
-        
-        table.put( 1, SIZE+1 );
-        assertEquals( SIZE+2, table.count() );
+        assertEquals( SIZE + 1, table.count() );
+        assertEquals( SIZE + 1, table.count( 1 ) );
 
+        // go one more over still a B+Tree
+        table.put( 1, SIZE + 1 );
+        assertEquals( SIZE + 2, table.count() );
+        assertEquals( SIZE + 2, table.count( 1 ) );
         assertEquals( 0, ( int ) table.get( 1 ) );
         
         // now start removing and see what happens 
-        table.remove( 1, SIZE+1 );
-        assertFalse( table.has( 1, SIZE+1 ) );
-        assertEquals( SIZE+1, table.count() );
-    
+        table.remove( 1, SIZE + 1 );
+        assertFalse( table.has( 1, SIZE + 1 ) );
+        assertTrue( table.has( 1, SIZE ) );
+        assertEquals( SIZE + 1, table.count() );
+        assertEquals( SIZE + 1, table.count( 1 ) );
+
+        // this switches to AvlTree from B+Trees
         table.remove( 1, SIZE );
         assertFalse( table.has( 1, SIZE ) );
         assertEquals( SIZE, table.count() );
         assertEquals( SIZE, table.count( 1 ) );
         assertTrue( 0 == table.get( 1 ) );
     
-        for ( int ii = SIZE-1; ii >= 0; ii-- )
+        for ( int ii = SIZE - 1; ii >= 0; ii-- )
         {
             table.remove( 1, ii );
         }
         assertEquals( 0, table.count() );
 
-        for ( int ii = 0; ii < SIZE-1; ii++ )
+        for ( int ii = 0; ii < SIZE - 1; ii++ )
         {
             table.put( 1, ii );
         }
-        assertEquals( SIZE-1, table.count() );
+        assertEquals( SIZE - 1, table.count() );
         table.remove( 1 );
         assertEquals( 0, table.count() );
     }
@@ -417,7 +497,27 @@
         assertEquals( 0, table.count( 1 ) );
         assertFalse( table.has( 1 ) );
     }
-    
+
+
+    @Test
+    public void testMiscellaneous() throws Exception
+    {
+        assertNotNull( ( ( JdbmTable ) table ).getMarshaller() );
+        ( ( JdbmTable ) table ).close();
+
+        // test value btree creation without serializer
+        table = new JdbmTable<Integer,Integer>( "test", SIZE, recman,
+                new SerializableComparator<Integer>( "" ),
+                new SerializableComparator<Integer>( "" ),
+                new IntegerSerializer(), null );
+        assertNull( ( ( JdbmTable ) table ).getValueSerializer() );
+        for ( int ii = 0; ii < SIZE + 1; ii++ )
+        {
+            table.put( 0, ii );
+        }
+        assertEquals( 0, ( int ) table.remove( 0 ) );
+    }
+
     
     /**
      * Let's test keys with a null or lack of any values.



Mime
View raw message