You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by sa...@apache.org on 2011/12/05 20:17:43 UTC
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
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() );
}
/*