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/15 05:36:22 UTC
svn commit: r637350 - in /directory/sandbox/akarasulu/bigbang/apacheds:
btree-base/src/main/java/org/apache/directory/server/core/partition/impl/btree/
jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/
jdbm-store/src/...
Author: akarasulu
Date: Fri Mar 14 21:36:18 2008
New Revision: 637350
URL: http://svn.apache.org/viewvc?rev=637350&view=rev
Log:
adding more test cases and fixing bugs
Modified:
directory/sandbox/akarasulu/bigbang/apacheds/btree-base/src/main/java/org/apache/directory/server/core/partition/impl/btree/Tuple.java
directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmDupsCursor.java
directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmDupsCursorTest.java
Modified: directory/sandbox/akarasulu/bigbang/apacheds/btree-base/src/main/java/org/apache/directory/server/core/partition/impl/btree/Tuple.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/btree-base/src/main/java/org/apache/directory/server/core/partition/impl/btree/Tuple.java?rev=637350&r1=637349&r2=637350&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/btree-base/src/main/java/org/apache/directory/server/core/partition/impl/btree/Tuple.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/btree-base/src/main/java/org/apache/directory/server/core/partition/impl/btree/Tuple.java Fri Mar 14 21:36:18 2008
@@ -119,14 +119,32 @@
this.value = value;
return this;
}
-
-
+
+
+
+
+ /**
+ * Sets both the key and the value for this Tuple in one call and returns
+ * this Tuple object. This is useful for setting the tuples key and value
+ * then returning it.
+ *
+ * @param tupleToCopy the tuple to copy
+ * @return this Tuple itself to set and return
+ */
+ public Tuple<K,V> setBoth( Tuple<K,V> tupleToCopy )
+ {
+ this.key = tupleToCopy.key;
+ this.value = tupleToCopy.value;
+ return this;
+ }
+
+
public String toString()
{
StringBuilder buf = new StringBuilder();
buf.append( "Tuple( '" );
buf.append( key );
- buf.append( " )', '" );
+ buf.append( "', '" );
buf.append( value );
buf.append( "' )" );
return buf.toString();
Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmDupsCursor.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/JdbmDupsCursor.java?rev=637350&r1=637349&r2=637350&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmDupsCursor.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmDupsCursor.java Fri Mar 14 21:36:18 2008
@@ -1,8 +1,6 @@
package org.apache.directory.server.core.partition.impl.btree.jdbm;
-import java.util.Comparator;
-
import jdbm.btree.BTree;
import org.apache.directory.server.core.avltree.AvlTree;
@@ -29,43 +27,33 @@
private final JdbmTable<K,V> table;
/**
- * The Tuple that is used to return values via the get() method. This
- * same Tuple instance will be returned every time. At different
- * positions it may return different values for the same key if the table
- * supports duplicate keys.
+ * An underlying Cursor which returns Tuples whose values are
+ * DupsContainer objects representing either AvlTrees or BTreeRedirect
+ * objects used to store the values of duplicate keys. It does not return
+ * different values for the same key.
*/
- private final Tuple<K,V> returnedTuple = new Tuple<K,V>();
+ private final DupsContainerCursor<K,V> containerCursor;
/**
- * The underlying Cursor which is simply returns Tuples with key value
- * pairs in the btree of the JDBM Table. It does not return different
- * values for the same key: hence it is not duplicate key aware. So for
- * tables supporting duplicate keys, it's Tuple vlaues may contain
- * AvlTree or BTreeRedirect objects. These objects are processed by
- * this outer Cursor to mimic traversal over the Table as if duplicate
- * keys are natively allowed by JDBM.
- *
- * In essence the AvlTree and the BTreeRedirect are used to store multiple
- * values for the same key.
+ * The current Tuple returned from the underlying DupsContainerCursor.
*/
- private final DupsContainerCursor<K,V> containerCursor;
+ private final Tuple<K,DupsContainer<V>> containerTuple = new Tuple<K, DupsContainer<V>>();
/**
- * A Cursor over a set of value objects for the current key. A new Cursor
- * will be created for each new key as we traverse table's that allow for
- * duplicate keys. The Cursor traverses over either a AvlTree object full
+ * A Cursor over a set of value objects for the current key held in the
+ * containerTuple. A new Cursor will be set for each new key as we
+ * traverse. The Cursor traverses over either a AvlTree object full
* of values in a multi-valued key or it traverses over a BTree which
- * contains the values in it's keys.
+ * contains the values in the key field of it's Tuples.
*/
private Cursor<V> dupsCursor;
/**
- * The current Tuple returned from the underlying JdbmNoDupsCursor which
- * may contain a AvlTree or BTreeRedirect for Tuple values. A
- * JdbmNoDupsCursor on a Table that allows duplicates returns AvlTrees or
- * BTreeRedirect objects for Tuple values.
+ * The Tuple that is used to return values via the get() method. This
+ * same Tuple instance will be returned every time. At different
+ * positions it may return different values for the same key.
*/
- private Tuple<K,DupsContainer<V>> containerTuple;
+ private final Tuple<K,V> returnedTuple = new Tuple<K,V>();
/**
* Whether or not a value is available when get() is called.
@@ -102,7 +90,7 @@
if ( containerCursor.next() )
{
- containerTuple = containerCursor.get();
+ containerTuple.setBoth( containerCursor.get() );
if ( containerTuple.getValue().isAvlTree() )
{
@@ -128,66 +116,49 @@
public void beforeFirst() throws Exception
{
- throw new NotImplementedException();
+ clearValue();
+ containerCursor.beforeFirst();
+ containerTuple.setKey( null );
+ containerTuple.setValue( null );
+ dupsCursor = null;
}
public void afterLast() throws Exception
{
- throw new NotImplementedException();
+ clearValue();
+ containerCursor.afterLast();
+ containerTuple.setKey( null );
+ containerTuple.setValue( null );
+ dupsCursor = null;
}
public boolean first() throws Exception
{
- throw new NotImplementedException();
- }
-
-
- private void clearValue()
- {
- returnedTuple.setKey( null );
- returnedTuple.setValue( null );
- valueAvailable = false;
- }
-
+ clearValue();
+ dupsCursor = null;
- public boolean last() throws Exception
- {
- if ( containerCursor.last() )
+ if ( containerCursor.first() )
{
- containerTuple = containerCursor.get();
- DupsContainer values = containerTuple.getValue();
+ containerTuple.setBoth( containerCursor.get() );
- if ( values.isAvlTree() )
+ if ( containerTuple.getValue().isAvlTree() )
{
- //noinspection unchecked
- AvlTree<V> set = values.getAvlTree();
- dupsCursor = new AvlTreeCursor<V>( set );
- if ( ! dupsCursor.previous() )
- {
- clearValue();
- return false;
- }
+ dupsCursor = new AvlTreeCursor<V>( containerTuple.getValue().getAvlTree() );
}
- else if ( values.isBTreeRedirect() )
+ else
{
- BTree tree = table.getBTree( values.getBTreeRedirect() );
- dupsCursor = new KeyCursor<V>( tree, table.getValueComparator() );
- if ( ! dupsCursor.previous() )
- {
- clearValue();
- return false;
- }
+ BTree bt = table.getBTree( containerTuple.getValue().getBTreeRedirect() );
+ dupsCursor = new KeyCursor<V>( bt, table.getValueComparator() );
+ }
+
+ if ( ! dupsCursor.next() )
+ {
+ clearValue();
+ return false;
}
- /*
- * If we get to this point then cursor has more elements and
- * containerTuple holds the Tuple containing the key and the btree or
- * AvlTree of values for that key which the Cursor traverses. All we
- * need to do is populate our tuple object with the key and the value
- * in the cursor.
- */
returnedTuple.setKey( containerTuple.getKey() );
returnedTuple.setValue( dupsCursor.get() );
return valueAvailable = true;
@@ -198,6 +169,22 @@
}
+ public boolean last() throws Exception
+ {
+ clearValue();
+ dupsCursor = null;
+ return valueAvailable = containerCursor.last();
+ }
+
+
+ private void clearValue()
+ {
+ returnedTuple.setKey( null );
+ returnedTuple.setValue( null );
+ valueAvailable = false;
+ }
+
+
public boolean previous() throws Exception
{
/*
@@ -213,37 +200,33 @@
*/
if ( containerCursor.previous() )
{
- containerTuple = containerCursor.get();
+ containerTuple.setBoth( containerCursor.get() );
DupsContainer<V> values = containerTuple.getValue();
if ( values.isAvlTree() )
{
- //noinspection unchecked
AvlTree<V> set = values.getAvlTree();
dupsCursor = new AvlTreeCursor<V>( set );
- dupsCursor.previous();
}
else if ( values.isBTreeRedirect() )
{
BTree tree = table.getBTree( values.getBTreeRedirect() );
- //noinspection unchecked
- dupsCursor = new KeyCursor<V>( tree, ( Comparator<V> ) table.getKeyComparator() );
- dupsCursor.previous();
+ dupsCursor = new KeyCursor<V>( tree, table.getValueComparator() );
+ }
+
+ dupsCursor.afterLast();
+ if ( dupsCursor.previous() )
+ {
+ break;
}
}
else
{
+ dupsCursor = null;
return false;
}
}
- /*
- * If we get to this point then cursor has more elements and
- * containerTuple holds the Tuple containing the key and the btree or
- * AvlTree of values for that key which the Cursor traverses. All we
- * need to do is populate our tuple object with the key and the value
- * in the cursor.
- */
returnedTuple.setKey( containerTuple.getKey() );
returnedTuple.setValue( dupsCursor.get() );
return valueAvailable = true;
@@ -264,26 +247,29 @@
*/
if ( containerCursor.next() )
{
- containerTuple = containerCursor.get();
+ containerTuple.setBoth( containerCursor.get() );
DupsContainer<V> values = containerTuple.getValue();
if ( values.isAvlTree() )
{
- //noinspection unchecked
AvlTree<V> set = values.getAvlTree();
dupsCursor = new AvlTreeCursor<V>( set );
- dupsCursor.next();
}
else if ( values.isBTreeRedirect() )
{
BTree tree = table.getBTree( values.getBTreeRedirect() );
- //noinspection unchecked
- dupsCursor = new KeyCursor<V>( tree, ( Comparator<V> ) table.getKeyComparator() );
- dupsCursor.next();
+ dupsCursor = new KeyCursor<V>( tree, table.getValueComparator() );
+ }
+
+ dupsCursor.beforeFirst();
+ if ( dupsCursor.next() )
+ {
+ break;
}
}
else
{
+ dupsCursor = null;
return false;
}
}
Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmDupsCursorTest.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/JdbmDupsCursorTest.java?rev=637350&r1=637349&r2=637350&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmDupsCursorTest.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmDupsCursorTest.java Fri Mar 14 21:36:18 2008
@@ -92,10 +92,10 @@
@Test
- public void testNextUnderDupLimit() throws Exception
+ public void testNextNoDups() throws Exception
{
// first try without duplicates at all
- for ( int ii = 0; ii < SIZE-2; ii++ )
+ for ( int ii = 0; ii < SIZE-1; ii++ )
{
table.put( ii, ii );
}
@@ -108,6 +108,182 @@
assertEquals( ii, ( int ) tuple.getKey() );
assertEquals( ii, ( int ) tuple.getValue() );
ii++;
+ }
+ }
+
+
+ @Test
+ public void testPreviousNoDups() throws Exception
+ {
+ for ( int ii = 0; ii < SIZE-1; ii++ )
+ {
+ table.put( ii, ii );
+ }
+ Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
+
+ int ii = SIZE-2;
+ while ( cursor.previous() )
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ ii--;
+ }
+ }
+
+
+ @Test
+ public void testNextDups() throws Exception
+ {
+ for ( int ii = 0; ii < SIZE*3; ii++ )
+ {
+ if ( ii > 12 && ii < 17 + SIZE )
+ {
+ table.put( 13, ii );
+ }
+ else
+ {
+ table.put( ii, ii );
+ }
+ }
+ Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
+
+ int ii = 0;
+ while ( cursor.next() )
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ if ( ii > 12 && ii < 17 + SIZE )
+ {
+ assertEquals( 13, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ }
+ else
+ {
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ }
+ ii++;
+ }
+ }
+
+
+ @Test
+ public void testPreviousDups() throws Exception
+ {
+ for ( int ii = 0; ii < SIZE*3; ii++ )
+ {
+ if ( ii > 12 && ii < 17 + SIZE )
+ {
+ table.put( 13, ii );
+ }
+ else
+ {
+ table.put( ii, ii );
+ }
+ }
+ Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
+ cursor.afterLast();
+
+ int ii = SIZE*3 - 1;
+ while ( cursor.previous() )
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ if ( ii > 12 && ii < 17 + SIZE )
+ {
+ assertEquals( 13, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ }
+ else
+ {
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ }
+ ii--;
+ }
+ }
+
+
+ @Test
+ public void testFirstLastUnderDupLimit() throws Exception
+ {
+ for ( int ii = 0; ii < SIZE-1; ii++ )
+ {
+ table.put( ii, ii );
+ }
+ Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
+
+ int ii = 0;
+ while ( cursor.next() )
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ ii++;
+ }
+
+ // now go back to first and traverse all over again
+ cursor.first();
+ ii = 0;
+ do
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ ii++;
+ }
+ while ( cursor.next() );
+
+ // now go backwards
+ ii = SIZE-2;
+ while ( cursor.previous() )
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ ii--;
+ }
+
+ // now advance to last and go backwards again
+ cursor.afterLast();
+ ii = SIZE-2;
+ while ( cursor.previous() )
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ ii--;
+ }
+
+ // advance to first then last and go backwards again
+ cursor.beforeFirst();
+ cursor.afterLast();
+ ii = SIZE-2;
+ while ( cursor.previous() )
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ ii--;
+ }
+ }
+
+
+ @Test
+ public void testLastUnderDupLimit() throws Exception
+ {
+ for ( int ii = 0; ii < SIZE-1; ii++ )
+ {
+ table.put( ii, ii );
+ }
+ Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
+
+ int ii = SIZE-2;
+ while ( cursor.previous() )
+ {
+ Tuple<Integer,Integer> tuple = cursor.get();
+ assertEquals( ii, ( int ) tuple.getKey() );
+ assertEquals( ii, ( int ) tuple.getValue() );
+ ii--;
}
}