directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r637536 - 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 04:27:36 GMT
Author: akarasulu
Date: Sat Mar 15 21:27:35 2008
New Revision: 637536

URL: http://svn.apache.org/viewvc?rev=637536&view=rev
Log:
implemented before and after methods for dups cursor and added test cases

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

Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsContainer.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/DupsContainer.java?rev=637536&r1=637535&r2=637536&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsContainer.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsContainer.java
Sat Mar 15 21:27:35 2008
@@ -24,15 +24,10 @@
 
 
 /**
- * A wrapper around duplicate key values.  This class wraps either a single
- * value, an AvlTree or a BTreeRedirect.  Only the AvlTree and BTreeRedirect
- * forms are used for the two value persistence mechanisms used to implement
- * duplicate keys over JDBM btrees.  The value form is almost a hack so we can
- * pass a value to the DupsContainerCursor to position it without breaking
- * with the API.  The positioning methods expect a Tuple with a K key object
- * and a value of DupsContainer<V> for the Tuple value so we have this form
- * to facilitate that.  For most practical purposes the value form can be
- * ignored
+ * A wrapper around duplicate key values.  This class wraps either an AvlTree
+ * or a BTreeRedirect.  The AvlTree and BTreeRedirect forms are used for the
+ * two value persistence mechanisms used to implement duplicate keys over JDBM
+ * btrees.  
  *
  * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
  * @version $Rev$
@@ -40,23 +35,13 @@
 public class DupsContainer<V>
 {
     private final AvlTree<V> avlTree;
-    private final V value;
     private final BTreeRedirect btreeRedirect;
 
 
-    DupsContainer( V value )
-    {
-        this.value = value;
-        avlTree = null;
-        btreeRedirect = null;
-    }
-
-
     DupsContainer( AvlTree<V> avlTree )
     {
         this.avlTree = avlTree;
         btreeRedirect = null;
-        value = null;
     }
 
 
@@ -64,7 +49,6 @@
     {
         avlTree = null;
         this.btreeRedirect = btreeRedirect;
-        value = null;
     }
 
 
@@ -77,23 +61,6 @@
     final boolean isAvlTree()
     {
         return avlTree != null;
-    }
-
-
-    final boolean isValue()
-    {
-        return value != null;
-    }
-
-
-    final V getValue()
-    {
-        if ( value == null )
-        {
-            throw new IllegalStateException( "this is not a value container" );
-        }
-
-        return value;
     }
 
 

Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsCursor.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/DupsCursor.java?rev=637536&r1=637535&r2=637536&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsCursor.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsCursor.java
Sat Mar 15 21:27:35 2008
@@ -9,7 +9,6 @@
 import org.apache.directory.server.core.cursor.Cursor;
 import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
 import org.apache.directory.server.core.partition.impl.btree.Tuple;
-import org.apache.directory.shared.ldap.NotImplementedException;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -65,6 +64,7 @@
     {
         this.table = table;
         this.containerCursor = new DupsContainerCursor<K,V>( table );
+        LOG.debug( "Created on table {}", table );
     }
 
 
@@ -74,43 +74,113 @@
     }
 
 
-    /**
-     * Advances this Cursor just before the record with key and value equal to 
-     * those provided in the Tuple argument.  If the key is not present the 
-     * Cursor advances to just before the greatest value of the key less than 
-     * but not greater than the one provided by the Tuple argument.  If the 
-     * key is present but the value is not present the Cursor advances to the 
-     * element with the same key containing a value less than but not greater
-     * than the value in the Tuple.
-     */
     public void before( Tuple<K,V> element ) throws Exception
     {
-        DupsContainer<V> container = new DupsContainer<V>( element.getValue()
);
-        containerCursor.before( new Tuple<K,DupsContainer<V>>( element.getKey(),
container ) );
+        containerCursor.before( new Tuple<K,DupsContainer<V>>( element.getKey(),
null ) );
         
         if ( containerCursor.next() )
         {
             containerTuple.setBoth( containerCursor.get() );
-            
-            if ( containerTuple.getValue().isAvlTree() )
+            DupsContainer<V> values = containerTuple.getValue();
+
+            if ( values.isAvlTree() )
+            {
+                AvlTree<V> set = values.getAvlTree();
+                dupsCursor = new AvlTreeCursor<V>( set );
+            }
+            else if ( values.isBTreeRedirect() )
             {
-                LOG.debug( "Duplicates tuple {} stored in a AvlTree", containerTuple );
-                AvlTree<V> set = containerTuple.getValue().getAvlTree();
+                BTree tree = table.getBTree( values.getBTreeRedirect() );
+                dupsCursor = new KeyCursor<V>( tree, table.getValueComparator() );
             }
-            else 
+
+            if ( element.getValue() == null )
+            {
+                return;
+            }
+
+            // don't bother advancing the dupsCursor unless we're on same key
+            if ( table.getKeyComparator().compare( containerTuple.getKey(), element.getKey()
) != 0 )
             {
-                LOG.debug( "Duplicates tuple {} are stored in a BTree", containerTuple );
-                BTreeRedirect redirect = containerTuple.getValue().getBTreeRedirect();
+                return;
             }
+
+            dupsCursor.before( element.getValue() );
+            return;
         }
 
-//        throw new NotImplementedException();
+        clearValue();
+        containerTuple.setKey( null );
+        containerTuple.setValue( null );
     }
 
 
     public void after( Tuple<K,V> element ) throws Exception
     {
-        throw new NotImplementedException();
+        /*
+         * There is a subtle difference between after and before handling
+         * with dupicate key values.  Say we have the following tuples:
+         *
+         * (0, 0)
+         * (1, 1)
+         * (1, 2)
+         * (1, 3)
+         * (2, 2)
+         *
+         * If we request an after cursor on (1, 2).  We must make sure that
+         * the container cursor does not advance after the entry with key 1
+         * since this would result in us skip returning (1. 3) on the call to
+         * next which will incorrectly return (2, 2) instead.
+         *
+         * So if the value is null in the element then we don't care about
+         * this obviously since we just want to advance past the duplicate key
+         * values all together.  But when it is not null, then we want to
+         * go right before this key instead of after it.
+         */
+
+        if ( element.getValue() == null )
+        {
+            containerCursor.after( new Tuple<K,DupsContainer<V>>( element.getKey(),
null ) );
+        }
+        else
+        {
+            containerCursor.before( new Tuple<K,DupsContainer<V>>( element.getKey(),
null ) );
+        }
+
+        if ( containerCursor.next() )
+        {
+            containerTuple.setBoth( containerCursor.get() );
+            DupsContainer<V> values = containerTuple.getValue();
+
+            if ( values.isAvlTree() )
+            {
+                AvlTree<V> set = values.getAvlTree();
+                dupsCursor = new AvlTreeCursor<V>( set );
+            }
+            else if ( values.isBTreeRedirect() )
+            {
+                BTree tree = table.getBTree( values.getBTreeRedirect() );
+                dupsCursor = new KeyCursor<V>( tree, table.getValueComparator() );
+            }
+
+            if ( element.getValue() == null )
+            {
+                return;
+            }
+
+            // don't bother advancing the dupsCursor unless we're on same key
+            if ( table.getKeyComparator().compare( containerTuple.getKey(), element.getKey()
) != 0 )
+            {
+                return;
+            }
+
+            dupsCursor.after( element.getValue() );
+            return;
+        }
+
+        clearValue();
+        containerTuple.setKey( null );
+        containerTuple.setValue( null );
     }
 
 

Modified: directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsCursorTest.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/DupsCursorTest.java?rev=637536&r1=637535&r2=637536&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsCursorTest.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/jdbm-store/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsCursorTest.java
Sat Mar 15 21:27:35 2008
@@ -433,4 +433,174 @@
         cursor.before( new Tuple<Integer, Integer>( 7, 2 ) );
         assertFalse( cursor.available() );
     }
+
+
+    @Test
+    public void testBeforeAfterBelowDupLimit() throws Exception
+    {
+        for ( int ii = 0; ii < SIZE*2 - 1; ii++ )
+        {
+            if ( ii > 12 && ii < 17 ) // keys with multiple values
+            {
+                table.put( 13, ii );
+            }
+            else if ( ii > 17 && ii < 21 ) // adds hole with no keys for ii
+            {
+            }
+            else // keys with single values
+            {
+                table.put( ii, ii );
+            }
+        }
+
+        // test before to advance just before a key with a single value
+        int ii = 5;
+        Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
+        cursor.before( new Tuple<Integer,Integer>( 5, 5 ) );
+        while ( cursor.next() )
+        {
+            if ( ii > 17 && ii < 21 )
+            {
+                assertFalse( table.has( ii ) );
+                continue;
+            }
+
+            Tuple<Integer,Integer> tuple = cursor.get();
+            if ( ii > 12 && ii < 17 )
+            {
+                assertEquals( 13, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            else
+            {
+                assertEquals( ii, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            ii++;
+        }
+
+        // test after to advance just before a key with a single value
+        ii = 6;
+        cursor = table.cursor();
+        cursor.after( new Tuple<Integer,Integer>( 5, null ) );
+        while ( cursor.next() )
+        {
+            if ( ii > 17 && ii < 21 )
+            {
+                assertFalse( table.has( ii ) );
+                continue;
+            }
+
+            Tuple<Integer,Integer> tuple = cursor.get();
+            if ( ii > 12 && ii < 17 )
+            {
+                assertEquals( 13, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            else
+            {
+                assertEquals( ii, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            ii++;
+        }
+
+        // test before to advance just before a key & value with multiple
+        // values for the key - we should advance just before the value
+        cursor = table.cursor();
+        cursor.before( new Tuple<Integer,Integer>( 13, 14 ) );
+
+        cursor.next();
+        Tuple<Integer,Integer> tuple = cursor.get();
+        assertEquals( 13, ( int ) tuple.getKey() );
+        assertEquals( 14, ( int ) tuple.getValue() );
+        ii = 15;
+
+        while ( cursor.next() )
+        {
+            if ( ii > 17 && ii < 21 )
+            {
+                assertFalse( table.has( ii ) );
+                continue;
+            }
+
+            tuple = cursor.get();
+            if ( ii > 12 && ii < 17 )
+            {
+                assertEquals( 13, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            else
+            {
+                assertEquals( ii, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            ii++;
+        }
+
+        // test after to advance just before a key & value with multiple
+        // values for the key - we should advance just before the value
+        cursor = table.cursor();
+        cursor.after( new Tuple<Integer,Integer>( 13, 14 ) );
+
+        cursor.next();
+        tuple = cursor.get();
+        assertEquals( 13, ( int ) tuple.getKey() );
+        assertEquals( 15, ( int ) tuple.getValue() );
+        ii=16;
+
+        while ( cursor.next() )
+        {
+            if ( ii > 17 && ii < 21 )
+            {
+                assertFalse( table.has( ii ) );
+                continue;
+            }
+
+            tuple = cursor.get();
+            if ( ii > 12 && ii < 17 )
+            {
+                assertEquals( 13, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            else
+            {
+                assertEquals( ii, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            ii++;
+        }
+
+        // test after to advance just before a key that does not exist
+        cursor = table.cursor();
+        cursor.after( new Tuple<Integer,Integer>( 18, null ) );
+
+        cursor.next();
+        tuple = cursor.get();
+        assertEquals( 21, ( int ) tuple.getKey() );
+        assertEquals( 21, ( int ) tuple.getValue() );
+        ii=22;
+
+        while ( cursor.next() )
+        {
+            if ( ii > 17 && ii < 21 )
+            {
+                assertFalse( table.has( ii ) );
+                continue;
+            }
+
+            tuple = cursor.get();
+            if ( ii > 12 && ii < 17 )
+            {
+                assertEquals( 13, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            else
+            {
+                assertEquals( ii, ( int ) tuple.getKey() );
+                assertEquals( ii, ( int ) tuple.getValue() );
+            }
+            ii++;
+        }
+    }
 }



Mime
View raw message