Mailing-List: contact commits-help@directory.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@directory.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1210585 - in
 /directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl:
 AvlTable.java AvlTableDupsCursor.java
Date: Mon, 05 Dec 2011 19:17:43 -0000
To: commits@directory.apache.org
From: saya@apache.org
Message-Id: <20111205191743.E302E2388A2C@eris.apache.org>

Author: saya
Date: Mon Dec  5 19:17:43 2011
New Revision: 1210585

URL: http://svn.apache.org/viewvc?rev=1210585&view=rev
Log:
Changed avl table to use ConcurrentNavigableMap, and OrderedSet and its cursor.

TODO: I will add a multithreaded test and try to make it work with txns. Should be useful to have txns tests without the effect of interceptors.

Modified:
    directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java
    directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTableDupsCursor.java

Modified: directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java?rev=1210585&r1=1210584&r2=1210585&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java (original)
+++ directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java Mon Dec  5 19:17:43 2011
@@ -21,15 +21,16 @@ package org.apache.directory.server.xdbm
 
 
 import java.util.Comparator;
+import java.util.Map;
+import java.util.concurrent.ConcurrentNavigableMap;
+import java.util.concurrent.ConcurrentSkipListMap;
 
-import org.apache.directory.server.core.avltree.AvlSingletonOrOrderedSetCursor;
-import org.apache.directory.server.core.avltree.AvlTree;
 import org.apache.directory.server.core.avltree.AvlTreeCursor;
-import org.apache.directory.server.core.avltree.AvlTreeMap;
-import org.apache.directory.server.core.avltree.AvlTreeMapImpl;
 import org.apache.directory.server.core.avltree.AvlTreeMapNoDupsWrapperCursor;
+import org.apache.directory.server.core.avltree.ConcurrentMapCursor;
 import org.apache.directory.server.core.avltree.KeyTupleAvlCursor;
-import org.apache.directory.server.core.avltree.LinkedAvlMapNode;
+import org.apache.directory.server.core.avltree.OrderedSet;
+import org.apache.directory.server.core.avltree.OrderedSetCursor;
 import org.apache.directory.server.core.avltree.SingletonOrOrderedSet;
 import org.apache.directory.server.core.api.partition.index.AbstractTable;
 import org.apache.directory.shared.ldap.model.cursor.Cursor;
@@ -45,14 +46,16 @@ import org.apache.directory.shared.ldap.
  */
 public class AvlTable<K, V> extends AbstractTable<K,V>
 {
-    private final AvlTreeMap<K, V> avl;
+    private final ConcurrentNavigableMap<K, SingletonOrOrderedSet<V>> map;
     private final Comparator<Tuple<K,V>> keyOnlytupleComparator;
     
+    /** Whether dups is enabled */
+    private boolean dupsEnabled;
+    
     
     public AvlTable( String name, final Comparator<K> keyComparator, final Comparator<V> valueComparator, boolean dupsEnabled )
     {
         super( null, name, keyComparator, valueComparator );
-        this.avl = new AvlTreeMapImpl<K, V>( keyComparator, valueComparator, dupsEnabled );
         this.keyOnlytupleComparator = new Comparator<Tuple<K, V>>()
         {
             public int compare( Tuple<K, V> t0, Tuple<K, V> t1 )
@@ -60,6 +63,15 @@ public class AvlTable<K, V> extends Abst
                 return keyComparator.compare( t0.getKey(), t1.getKey() );
             }
         };
+        
+        map = new ConcurrentSkipListMap<K, SingletonOrOrderedSet<V>>( keyComparator );
+        this.dupsEnabled = dupsEnabled;
+    }
+    
+    
+    public ConcurrentNavigableMap<K, SingletonOrOrderedSet<V>> getBackingMap()
+    {
+        return map;
     }
     
 
@@ -68,7 +80,7 @@ public class AvlTable<K, V> extends Abst
      */
     public void close() throws Exception
     {
-        ( ( AvlTreeMapImpl ) avl ).removeAll();
+        map.clear();
     }
 
     
@@ -82,18 +94,16 @@ public class AvlTable<K, V> extends Abst
             return 0;
         }
         
-        LinkedAvlMapNode<K, V> node = avl.find( key );
+        SingletonOrOrderedSet<V> set = map.get( key );
         
-        if ( node == null )
+        if ( set == null )
         {
             return 0;
         }
         
-        SingletonOrOrderedSet<V> val = node.getValue();
-        
-        if ( val.isOrderedSet() )
+        if ( set.isOrderedSet() )
         {
-            return val.getOrderedSet().getSize();
+            return set.getOrderedSet().getSize();
         }
         
         return 1;
@@ -110,21 +120,19 @@ public class AvlTable<K, V> extends Abst
             return null;
         }
         
-        LinkedAvlMapNode<K, V> node = avl.find( key );
+        SingletonOrOrderedSet<V> set = map.get( key );
         
-        if ( node == null )
+        if ( set == null )
         {
             return null;
         }
         
-        SingletonOrOrderedSet<V> val = node.getValue();
-        
-        if ( val.isOrderedSet() )
+        if ( set.isOrderedSet() )
         {
-            return val.getOrderedSet().getFirst().getKey();
+            return set.getOrderedSet().first();
         }
         
-        return val.getSingleton();
+        return set.getSingleton();
     }
 
     
@@ -133,7 +141,7 @@ public class AvlTable<K, V> extends Abst
      */
     public int greaterThanCount( K key ) throws Exception
     {
-        return avl.getSize();
+        return count;
     }
 
     
@@ -147,7 +155,7 @@ public class AvlTable<K, V> extends Abst
             return false;
         }
         
-        return avl.find( key ) != null;
+        return ( map.get( key ) != null );
     }
 
     
@@ -156,12 +164,31 @@ public class AvlTable<K, V> extends Abst
      */
     public boolean has( K key, V value ) throws Exception
     {
-        if ( key == null )
+        if ( key == null || value == null )
+        {
+            return false;
+        }
+        
+        SingletonOrOrderedSet<V> set = map.get( key );
+        
+        if ( set == null )
         {
             return false;
         }
         
-        return avl.find( key, value ) != null;
+        if ( set.isOrderedSet() )
+        {
+            return set.getOrderedSet().contains( value );
+        }
+        
+        V singletonValue = set.getSingleton();
+        
+        if ( valueComparator.compare( singletonValue, value ) == 0 )
+        {
+            return true;
+        }
+        
+        return false;
     }
 
     
@@ -175,7 +202,7 @@ public class AvlTable<K, V> extends Abst
             return false;
         }
         
-        return avl.findGreaterOrEqual( key ) != null;
+        return ( map.ceilingKey( key ) != null );
     }
 
     
@@ -189,20 +216,37 @@ public class AvlTable<K, V> extends Abst
             return false;
         }
         
-        LinkedAvlMapNode<K, V> node = avl.findGreaterOrEqual( key );
+        Map.Entry<K,SingletonOrOrderedSet<V>> entry = map.lastEntry();
+        
+        if ( entry == null )
+        {
+            return false;
+        }
+        
+        K lastKey = entry.getKey();
+        SingletonOrOrderedSet<V> lastSet = entry.getValue();
+        
+        // Null values shouldnt be allowed 
+        if ( lastSet == null )
+        {
+            throw new RuntimeException( "AvlTable: Null value in map for key: " + lastKey );
+        }
         
-        if ( node == null )
+        if (  keyComparator.compare( lastKey, key ) > 0 )
+        {
+            return true;
+        }
+        else if ( keyComparator.compare( lastKey, key ) < 0 )
         {
             return false;
         }
         
-        if ( node.getValue().isOrderedSet() )
+        if ( lastSet.isOrderedSet() )
         {
-            AvlTree<V> values = node.getValue().getOrderedSet();
-            return values.findGreaterOrEqual( val ) != null;
+            return lastSet.getOrderedSet().hasGreaterOrEqual( val );
         }
         
-        return valueComparator.compare( node.getValue().getSingleton(), val ) >= 0;
+        return valueComparator.compare( lastSet.getSingleton(), val ) >= 0;
     }
 
     
@@ -216,7 +260,7 @@ public class AvlTable<K, V> extends Abst
             return false;
         }
         
-        return avl.findLessOrEqual( key ) != null;
+        return ( map.floorEntry( key ) != null );
     }
 
     
@@ -230,20 +274,37 @@ public class AvlTable<K, V> extends Abst
             return false;
         }
         
-        LinkedAvlMapNode<K, V> node = avl.findLessOrEqual( key );
+        Map.Entry<K,SingletonOrOrderedSet<V>> entry = map.firstEntry();
         
-        if ( node == null )
+        if ( entry == null )
         {
             return false;
         }
         
-        if ( node.getValue().isOrderedSet() )
+        K firstKey = entry.getKey();
+        SingletonOrOrderedSet<V> firstSet = entry.getValue();
+        
+        // Null values shouldnt be allowed 
+        if ( firstSet == null )
+        {
+            throw new RuntimeException( "AvlTable: Null value in map for key: " + firstKey );
+        }
+        
+        if (  keyComparator.compare( firstKey, key ) < 0 )
         {
-            AvlTree<V> values = node.getValue().getOrderedSet();
-            return values.findLessOrEqual( val ) != null;
+            return true;
+        }
+        else if ( keyComparator.compare( firstKey, key ) > 0 )
+        {
+            return false;
         }
         
-        return valueComparator.compare( node.getValue().getSingleton(), val ) <= 0;
+        if ( firstSet.isOrderedSet() )
+        {
+            return firstSet.getOrderedSet().hasLessOrEqual( val );
+        }
+        
+        return valueComparator.compare( firstSet.getSingleton(), val ) <= 0;
     }
 
 
@@ -252,7 +313,7 @@ public class AvlTable<K, V> extends Abst
      */
     public boolean isDupsEnabled()
     {
-        return avl.isDupsAllowed();
+        return dupsEnabled;
     }
     
 
@@ -268,40 +329,74 @@ public class AvlTable<K, V> extends Abst
     /**
      * {@inheritDoc}
      */
-    public void put( K key, V value ) throws Exception
+    public synchronized void put( K key, V value ) throws Exception
     {
         if ( key == null || value == null )
         {
             return;
         }
         
-        if ( avl.insert( key, value ) == null )
+        SingletonOrOrderedSet<V> set = map.get( key );
+        
+        if ( set == null )
         {
+           
+            if ( dupsEnabled )
+            {
+                OrderedSet<V> orderedSet = new OrderedSet<V>( valueComparator );
+                orderedSet.insert( value );
+                set = new SingletonOrOrderedSet<V>( orderedSet ); 
+            }
+            else
+            {
+                set = new SingletonOrOrderedSet<V>( value );
+            }
+            
+            map.put( key, set );
             count++;
+                
+            return;
+        }
+        
+        if ( set.isOrderedSet() )
+        {
+            if ( set.getOrderedSet().insert( value ) == true )
+            {
+                count++;
+            }
+            
+            return;
         }
+        
+        // Replace existing value
+        set.setSingleton( value );
+        
+        return;
     }
 
     
     /**
      * {@inheritDoc}
      */
-    public void remove( K key ) throws Exception
+    public synchronized void remove( K key ) throws Exception
     {
         if ( key == null )
         {
             return;
         }
         
-        SingletonOrOrderedSet<V> value = avl.remove( key );
+        SingletonOrOrderedSet<V> set = map.get( key );
         
-        if ( value == null )
+        if ( set == null )
         {
             return;
         }
-
-        if ( value.isOrderedSet() )
+        
+        map.remove( key );
+        
+        if ( set.isOrderedSet() )
         {
-            count -= value.getOrderedSet().getSize();
+            count -= set.getOrderedSet().getSize();
         }
         else
         {
@@ -313,12 +408,38 @@ public class AvlTable<K, V> extends Abst
     /**
      * {@inheritDoc}
      */
-    public void remove( K key, V value ) throws Exception
+    public synchronized void remove( K key, V value ) throws Exception
     {
-        if ( avl.remove( key, value ) != null )
+        if ( key == null || value == null )
+        {
+            return;
+        }
+        
+        SingletonOrOrderedSet<V> set = map.get( key );
+        
+        if ( set == null )
         {
-            count--;
+            return;
         }
+        
+        if ( set.isOrderedSet() )
+        {
+            if ( set.getOrderedSet().remove( value ) == true  )
+            {
+                count --;
+                
+                if ( set.getOrderedSet().getSize() == 0 )
+                {
+                    map.remove( key );
+                }
+            }
+            
+            return;
+        }
+        
+        // Remove singleton value
+        map.remove( key );
+        count--;    
     }
     
     
@@ -327,9 +448,9 @@ public class AvlTable<K, V> extends Abst
      */
     public Cursor<Tuple<K, V>> cursor() throws Exception
     {
-        if ( ! avl.isDupsAllowed() )
+        if ( ! dupsEnabled )
         {
-            return new AvlTreeMapNoDupsWrapperCursor<K, V>( new AvlSingletonOrOrderedSetCursor<K,V>( avl ) );
+            return new AvlTreeMapNoDupsWrapperCursor<K, V>( new ConcurrentMapCursor<K,SingletonOrOrderedSet<V>>( map ) );
         }
 
         return new AvlTableDupsCursor<K, V>( this );
@@ -346,19 +467,19 @@ public class AvlTable<K, V> extends Abst
             return new EmptyCursor<Tuple<K,V>>();
         }
         
-        LinkedAvlMapNode<K, V> node = avl.find( key );
+        SingletonOrOrderedSet<V> set = map.get( key );
         
-        if ( node == null )
+        if ( set == null )
         {
             return new EmptyCursor<Tuple<K,V>>();
         }
         
-        if ( node.getValue().isOrderedSet() )
+        if ( set.isOrderedSet() )
         {
-            return new KeyTupleAvlCursor<K,V>( node.getValue().getOrderedSet(), key );
+            return new KeyTupleAvlCursor<K,V>( set.getOrderedSet(), key );
         }
         
-        return new SingletonCursor<Tuple<K,V>>( new Tuple<K,V>( key, node.getValue().getSingleton() ), 
+        return new SingletonCursor<Tuple<K,V>>( new Tuple<K,V>( key, set.getSingleton() ), 
                 keyOnlytupleComparator );
     }
 
@@ -373,30 +494,19 @@ public class AvlTable<K, V> extends Abst
             return new EmptyCursor<V>();
         }
         
-        LinkedAvlMapNode<K, V> node = avl.find( key );
+        SingletonOrOrderedSet<V> set = map.get( key );
         
-        if ( node == null )
+        if ( set == null )
         {
             return new EmptyCursor<V>();
         }
         
-        if ( node.getValue().isOrderedSet() )
+        if ( set.isOrderedSet() )
         {
-            return new AvlTreeCursor<V>( node.getValue().getOrderedSet() );
+            return new OrderedSetCursor<V>( set.getOrderedSet() );
         }
         
-        return new SingletonCursor<V>( node.getValue().getSingleton(), valueComparator );
+        return new SingletonCursor<V>( set.getSingleton(), valueComparator );
     }
 
-
-    /**
-     * Returns the internal AvlTreeMap so other classes like Cursors
-     * in the same package can access it.
-     *
-     * @return AvlTreeMap used to store Tuples
-     */
-    AvlTreeMap<K, V> getAvlTreeMap()
-    {
-        return avl;
-    }
 }

Modified: directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTableDupsCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTableDupsCursor.java?rev=1210585&r1=1210584&r2=1210585&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTableDupsCursor.java (original)
+++ directory/apacheds/branches/apacheds-txns/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTableDupsCursor.java Mon Dec  5 19:17:43 2011
@@ -20,9 +20,10 @@
 package org.apache.directory.server.xdbm.impl.avl;
 
 
-import org.apache.directory.server.core.avltree.AvlSingletonOrOrderedSetCursor;
-import org.apache.directory.server.core.avltree.AvlTree;
 import org.apache.directory.server.core.avltree.AvlTreeCursor;
+import org.apache.directory.server.core.avltree.ConcurrentMapCursor;
+import org.apache.directory.server.core.avltree.OrderedSet;
+import org.apache.directory.server.core.avltree.OrderedSetCursor;
 import org.apache.directory.server.core.avltree.SingletonOrOrderedSet;
 import org.apache.directory.shared.ldap.model.cursor.AbstractTupleCursor;
 import org.apache.directory.shared.ldap.model.cursor.Cursor;
@@ -51,7 +52,7 @@ public class AvlTableDupsCursor<K,V> ext
      * The underlying wrapped cursor which returns Tuples whose values are
      * either V objects or AvlTree objects.
      */
-    private final AvlSingletonOrOrderedSetCursor<K, V> wrappedCursor;
+    private final ConcurrentMapCursor<K, SingletonOrOrderedSet<V>> wrappedCursor;
     
     /**
      * A Cursor over a set of value objects for the current key held in the
@@ -84,7 +85,7 @@ public class AvlTableDupsCursor<K,V> ext
     public AvlTableDupsCursor( AvlTable<K,V> table )
     {
         this.table = table;
-        this.wrappedCursor = new AvlSingletonOrOrderedSetCursor<K, V>( table.getAvlTreeMap() );
+        this.wrappedCursor = new ConcurrentMapCursor<K, SingletonOrOrderedSet<V>>( table.getBackingMap() );
         LOG.debug( "Created on table {}", table.getName() );
     }
 
@@ -121,13 +122,13 @@ public class AvlTableDupsCursor<K,V> ext
             
             if ( wrappedTuple.getValue().isOrderedSet() )
             {
-                AvlTree<V> avlTree = wrappedTuple.getValue().getOrderedSet();
-                dupsCursor = new AvlTreeCursor<V>( avlTree );
+                OrderedSet<V> orderedSet = wrappedTuple.getValue().getOrderedSet();
+                dupsCursor = new OrderedSetCursor<V>( orderedSet );
             }
             else
             {
                 dupsCursor = new SingletonCursor<V>( 
-                    wrappedTuple.getValue().getSingleton(), wrappedCursor.getValuComparator() );
+                    wrappedTuple.getValue().getSingleton(), table.getValueComparator() );
             }
             
             if ( value == null )
@@ -209,12 +210,12 @@ public class AvlTableDupsCursor<K,V> ext
 
             if ( values.isOrderedSet() )
             {
-                AvlTree<V> set = values.getOrderedSet();
-                dupsCursor = new AvlTreeCursor<V>( set );
+                OrderedSet<V> set = values.getOrderedSet();
+                dupsCursor = new OrderedSetCursor<V>( set );
             }
             else
             {
-                dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
+                dupsCursor = new SingletonCursor<V>( values.getSingleton(), table.getValueComparator() );
             }
 
             if ( value == null )
@@ -301,11 +302,11 @@ public class AvlTableDupsCursor<K,V> ext
 
             if ( values.isOrderedSet() )
             {
-                dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() );
+                dupsCursor = new OrderedSetCursor<V>( values.getOrderedSet() );
             }
             else
             {
-                dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
+                dupsCursor = new SingletonCursor<V>( values.getSingleton(), table.getValueComparator() );
             }
 
             /*
@@ -356,11 +357,11 @@ public class AvlTableDupsCursor<K,V> ext
 
             if ( values.isOrderedSet() )
             {
-                dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() );
+                dupsCursor = new OrderedSetCursor<V>( values.getOrderedSet() );
             }
             else
             {
-                dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
+                dupsCursor = new SingletonCursor<V>( values.getSingleton(), table.getValueComparator() );
             }
 
             /*
@@ -402,11 +403,11 @@ public class AvlTableDupsCursor<K,V> ext
 
                 if ( values.isOrderedSet())
                 {
-                    dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() );
+                    dupsCursor = new OrderedSetCursor<V>( values.getOrderedSet() );
                 }
                 else
                 {
-                    dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
+                    dupsCursor = new SingletonCursor<V>( values.getSingleton(), table.getValueComparator() );
                 }
 
                 /*
@@ -462,11 +463,11 @@ public class AvlTableDupsCursor<K,V> ext
 
                 if ( values.isOrderedSet() )
                 {
-                    dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() );
+                    dupsCursor = new OrderedSetCursor<V>( values.getOrderedSet() );
                 }
                 else
                 {
-                    dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
+                    dupsCursor = new SingletonCursor<V>( values.getSingleton(), table.getValueComparator() );
                 }
 
                 /*