You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ak...@apache.org on 2008/03/17 00:12:08 UTC
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/
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.