directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From s...@apache.org
Subject svn commit: r1210581 - in /directory/apacheds/branches/apacheds-txns/core-avl/src: main/java/org/apache/directory/server/core/avltree/ test/java/org/apache/directory/server/core/avltree/ test/java/org/apache/directory/server/core/avltree/avl/
Date Mon, 05 Dec 2011 19:10:36 GMT
Author: saya
Date: Mon Dec  5 19:10:35 2011
New Revision: 1210581

URL: http://svn.apache.org/viewvc?rev=1210581&view=rev
Log:
Changes for using ConcurrentSkipListMap as the backing store for avl partition. 
OrderedSet.java: Provides a set abstraction using a ConcurrentNavigableMap.

ConcurrentNavigableMapCursor.java: Provides a cursor over a concurrent map.

OrdererdSetCursor.java: Provides a cursor over OrderedSet using ConcurrentMapCursor.

OrderedSetMarshaller.java: Provides serialization/deserialization for ordered set.

AvlTreeNoDupsWrapperCursor.java and KeyTupleAvlCursor.java are changed to use the concurrent
map cursor and ordered set cursor.

Removed rest of Avl Tree related classes. 

Added:
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/ConcurrentMapCursor.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSet.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetCursor.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetMarshaller.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/OrderedSetCursorTest.java
Removed:
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlSingletonOrOrderedSetCursor.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeImpl.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMap.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapImpl.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMarshaller.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeSingleton.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlMapNode.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/LinkedAvlNode.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapTest.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMarshallerTest.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreePerfTest.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/avl/
Modified:
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
    directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java

Modified: directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java?rev=1210581&r1=1210580&r2=1210581&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java
(original)
+++ directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsWrapperCursor.java
Mon Dec  5 19:10:35 2011
@@ -33,11 +33,11 @@ import org.apache.directory.shared.ldap.
  */
 public class AvlTreeMapNoDupsWrapperCursor<K,V> extends AbstractTupleCursor<K, V>
 {
-    private final AvlSingletonOrOrderedSetCursor<K, V> wrapped;
+    private final ConcurrentMapCursor<K, SingletonOrOrderedSet<V>> wrapped;
     private final Tuple<K,V> returnedTuple = new Tuple<K, V>();
     
     
-    public AvlTreeMapNoDupsWrapperCursor( AvlSingletonOrOrderedSetCursor<K, V> wrapped
)
+    public AvlTreeMapNoDupsWrapperCursor( ConcurrentMapCursor<K, SingletonOrOrderedSet<V>>
wrapped )
     {
         this.wrapped = wrapped;
     }
@@ -111,8 +111,7 @@ public class AvlTreeMapNoDupsWrapperCurs
             
             if ( tuple.getValue().isOrderedSet() )
             {
-                System.out.println( "tuple key = " + tuple.getKey() );
-                tuple.getValue().getOrderedSet().printTree();
+                throw new IllegalStateException( "Avl: No dups cursor has a set of elemets
for its value" + tuple.getKey() );
             }
             
             returnedTuple.setBoth( tuple.getKey(), tuple.getValue().getSingleton() );

Added: directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/ConcurrentMapCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/ConcurrentMapCursor.java?rev=1210581&view=auto
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/ConcurrentMapCursor.java
(added)
+++ directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/ConcurrentMapCursor.java
Mon Dec  5 19:10:35 2011
@@ -0,0 +1,314 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+package org.apache.directory.server.core.avltree;
+
+import java.util.Iterator;
+import java.util.concurrent.ConcurrentNavigableMap;
+
+import org.apache.directory.shared.ldap.model.cursor.AbstractTupleCursor;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.model.cursor.Tuple;
+
+public class ConcurrentMapCursor<K,V> extends AbstractTupleCursor<K,V>
+{
+    /** Backing map */
+    private ConcurrentNavigableMap<K,V> map;
+    
+    /** Keeps track of whether the cursor is positioned */
+    private boolean positioned;
+    
+    /** Keeps track of whether moving next */
+    private boolean movingNext;
+    
+    /** Currently available value */
+    private Tuple<K, V> returnedTuple = new Tuple();
+    
+    /** true if value is available */
+    private K availableKey;
+    
+    /** Iterator over the keys */
+    Iterator<K> it;
+    
+    public ConcurrentMapCursor( ConcurrentNavigableMap<K,V> map )
+    {
+        this.map = map;
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean available()
+    {
+        return ( availableKey != null );
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public Tuple<K,V> get() throws Exception
+    {
+        if ( availableKey != null )
+        {
+            return returnedTuple;
+        }
+
+        throw new InvalidCursorPositionException();
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void after( Tuple<K,V> element ) throws Exception
+    {
+        afterKey( element.getKey() );
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void before( Tuple<K,V> element ) throws Exception
+    {
+        beforeKey( element.getKey() );   
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void afterKey( K key ) throws Exception
+    {
+        availableKey = null;
+        positioned = true;
+        movingNext = true;
+
+        if ( key == null )
+        {
+            afterLast();
+            return;
+        }
+
+        
+        // Simply position the iterator past the given element.
+        it = map.tailMap( key, false ).keySet().iterator();      
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void beforeKey( K key ) throws Exception
+    {
+        availableKey = null;
+        positioned = true;
+        movingNext = true;
+        
+        if ( key == null )
+        {
+            beforeFirst();
+            return;
+        }
+        
+        // Simply position the iterator past the given element.
+        it = map.tailMap( key, true ).keySet().iterator();      
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void afterValue( K key, V value ) throws Exception
+    {
+        throw new UnsupportedOperationException( "This Cursor does not support duplicate
keys." );
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void beforeValue( K key, V value ) throws Exception
+    {
+        throw new UnsupportedOperationException( "This Cursor does not support duplicate
keys." );
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void beforeFirst() throws Exception
+    {
+        positioned = true;
+        availableKey = null;
+        movingNext = true;
+        
+        it = map.keySet().iterator();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void afterLast() throws Exception
+    {
+        positioned = true;
+        availableKey = null;
+        movingNext = false;
+
+        it = map.keySet().descendingIterator();
+        
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+
+        return next();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean last() throws Exception
+    {
+        afterLast();
+
+        return previous();
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean previous() throws Exception
+    {
+        if ( positioned == false )
+        {
+            afterLast();
+        }
+
+        // If currently moving in the next() direction, then get a descending iterator using
the last availableValue
+        if ( movingNext == true )
+        {
+            if ( availableKey == null )
+            {
+                if ( it.hasNext() )
+                {
+                    availableKey = it.next();
+                }
+            }
+
+            if ( availableKey == null )
+            {
+                it = map.keySet().descendingIterator();
+            }
+            else
+            {
+                it = map.headMap( availableKey, false ).keySet().descendingIterator();
+            }
+
+            availableKey = null;
+            movingNext = false;
+        }
+
+        
+        V value;
+        availableKey = null;
+        
+        while ( it.hasNext() )
+        {
+            availableKey = it.next();
+            value = map.get( availableKey );
+            
+            if ( value != null )
+            {
+                returnedTuple.setBoth( availableKey, value );
+                break;
+            }
+            
+            availableKey = null;
+        }
+       
+        return ( availableKey != null );
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean next() throws Exception
+    {
+        if ( positioned == false )
+        {
+            beforeFirst();
+        }
+
+        // If currently moving in the previous() direction, then get a increasing iterator
using the last availableValue
+        if ( movingNext == false )
+        {
+            if ( availableKey == null )
+            {
+                if ( it.hasNext() )
+                {
+                    availableKey = it.next();
+                }
+            }
+
+            if ( availableKey == null )
+            {
+                it = map.keySet().iterator();
+            }
+            else
+            {
+                it = map.tailMap( availableKey, false ).keySet().iterator();
+            }
+
+            availableKey = null;
+            movingNext = true;
+        }
+
+
+        availableKey = null;
+        V value;
+        
+        while ( it.hasNext() )
+        {
+            availableKey = it.next();
+            value = map.get( availableKey );
+            
+            if ( value != null )
+            {
+                returnedTuple.setBoth( availableKey, value );
+                break;
+            }
+            
+            availableKey = null;
+        }
+       
+        return ( availableKey != null );
+    }
+}

Modified: directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java?rev=1210581&r1=1210580&r2=1210581&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
(original)
+++ directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
Mon Dec  5 19:10:35 2011
@@ -34,7 +34,7 @@ import org.apache.directory.shared.ldap.
  */
 public class KeyTupleAvlCursor<K,V> extends AbstractTupleCursor<K,V>
 {
-    private final AvlTreeCursor<V> wrapped;
+    private final OrderedSetCursor<V> wrapped;
     private final K key;
 
     private Tuple<K,V> returnedTuple = new Tuple<K,V>();
@@ -47,10 +47,10 @@ public class KeyTupleAvlCursor<K,V> exte
      * @param avlTree the AvlTree to build a Tuple returning Cursor over
      * @param key the constant key for which values are returned
      */
-    public KeyTupleAvlCursor( AvlTree<V> avlTree, K key )
+    public KeyTupleAvlCursor( OrderedSet<V> set, K key )
     {
         this.key = key;
-        this.wrapped = new AvlTreeCursor<V>( avlTree );
+        this.wrapped = new OrderedSetCursor<V>( set );
     }
 
 

Added: directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSet.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSet.java?rev=1210581&view=auto
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSet.java
(added)
+++ directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSet.java
Mon Dec  5 19:10:35 2011
@@ -0,0 +1,144 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+package org.apache.directory.server.core.avltree;
+
+import java.util.Comparator;
+import java.util.concurrent.ConcurrentNavigableMap;
+import java.util.concurrent.ConcurrentSkipListMap;
+
+public class OrderedSet<V>
+{
+    /** string used for all values */
+    private final static String EMPTY_STRING = "";
+    
+    /** Backing store */
+    private ConcurrentNavigableMap<V, String> orderedMap;
+    
+    /** Size of the map */
+    private int count = 0;
+    
+    /** Value comparator */
+    Comparator<V> valueComparator;
+    
+    
+    public Comparator<V> getValueComparator()
+    {
+        return valueComparator;
+    }
+    
+    public OrderedSet( Comparator<V> comparator )
+    {
+        orderedMap = new ConcurrentSkipListMap<V, String>( comparator );
+        valueComparator = comparator;
+    }
+    
+    
+    public ConcurrentNavigableMap<V, String> getBackingMap()
+    {
+        return orderedMap;
+    }
+    
+    public synchronized boolean insert( V value )
+    {
+        if ( value == null )
+        {
+            throw new IllegalArgumentException( "Cannot insert null value into ordered set"
);
+        }
+        
+        String existingString = orderedMap.put( value, EMPTY_STRING );
+        
+        if ( existingString == null )
+        {
+            count++;
+            return true;
+        }
+        else
+        {
+            return false;
+        }
+    }
+    
+    
+    public synchronized boolean remove( V value )
+    {
+        if ( value == null )
+        {
+            throw new IllegalArgumentException( "Cannot remove null value from ordered set"
);
+        }
+        
+        
+        if ( orderedMap.remove( value ) != null )
+        {
+            count--;
+            return true;
+        }
+        else
+        {
+            return false;
+        }
+    }
+    
+    
+    public boolean contains( V value )
+    {
+        String contained = orderedMap.get( value );
+        
+        return ( contained != null );
+    }
+    
+    public V first()
+    {
+        return orderedMap.firstKey();
+    }
+    
+    public V last()
+    {
+        return orderedMap.lastKey();
+    }
+    
+    
+    public boolean hasGreaterOrEqual( V value )
+    {
+        if ( value == null )
+        {
+            return false;
+        }
+        
+        return ( orderedMap.ceilingKey( value ) != null );
+    }
+    
+    
+    public boolean hasLessOrEqual( V value )
+    {
+        if ( value == null )
+        {
+            return false;
+        }
+        
+        return ( orderedMap.floorKey( value ) != null );
+    }
+    
+    
+    public int getSize()
+    {        
+        return count; 
+    }
+
+}

Added: directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetCursor.java?rev=1210581&view=auto
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetCursor.java
(added)
+++ directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetCursor.java
Mon Dec  5 19:10:35 2011
@@ -0,0 +1,116 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+package org.apache.directory.server.core.avltree;
+
+import java.util.Comparator;
+
+import org.apache.directory.shared.ldap.model.cursor.AbstractCursor;
+import org.apache.directory.shared.ldap.model.cursor.Cursor;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+
+public class OrderedSetCursor<V> extends AbstractCursor<V>
+{
+    /** Backing set */
+    private OrderedSet<V> set;
+    
+    /** Cursor for the map backing OrderedSet */
+    private ConcurrentMapCursor<V, String> wrappedCursor;
+    
+    public OrderedSetCursor( OrderedSet<V> set )
+    {
+        this.set = set;
+        wrappedCursor = new ConcurrentMapCursor<V, String>( set.getBackingMap() );
+    }
+    
+    
+    public Comparator<V> getValueComparator()
+    {
+        return set.getValueComparator();
+    }
+    
+    
+    public void after( V value ) throws Exception
+    {
+       wrappedCursor.afterKey( value );
+    }
+
+
+    public void afterLast() throws Exception
+    {
+       wrappedCursor.afterLast();
+    }
+
+
+    public boolean available()
+    {
+        return wrappedCursor.available();
+    }
+
+
+    public void before( V value ) throws Exception
+    {
+        wrappedCursor.beforeKey( value );
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        wrappedCursor.beforeFirst();
+    }
+
+
+    public boolean first() throws Exception
+    {
+        return wrappedCursor.first();
+    }
+
+
+    public V get() throws Exception
+    {
+        V value;
+        
+        if ( wrappedCursor.available() )
+        {
+            value = wrappedCursor.get().getKey();
+            
+            return value;
+        }
+        
+        throw new InvalidCursorPositionException();
+    }
+
+
+    public boolean last() throws Exception
+    {
+        return wrappedCursor.last();
+    }
+
+
+    public boolean next() throws Exception
+    {
+        return wrappedCursor.next();
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        return wrappedCursor.previous();
+    }
+}

Added: directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetMarshaller.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetMarshaller.java?rev=1210581&view=auto
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetMarshaller.java
(added)
+++ directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/OrderedSetMarshaller.java
Mon Dec  5 19:10:35 2011
@@ -0,0 +1,206 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+package org.apache.directory.server.core.avltree;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Comparator;
+import java.util.Iterator;
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.shared.util.Strings;
+
+public class OrderedSetMarshaller<V>
+{
+    /** used for serialized form of an empty AvlTree */
+    private static final byte[] EMPTY_SET = new byte[1];
+    
+    /** marshaller to be used for marshalling the keys */
+    private Marshaller<V> valueMarshaller;
+    
+    /** value Comparator for the ordered set */
+    private Comparator<V> comparator;
+    
+    /**
+     * Creates a new instance of AvlTreeMarshaller with a custom key
+     * Marshaller.
+     *
+     * @param comparator Comparator to be used for key comparision
+     * @param keyMarshaller marshaller for keys
+     */
+    public OrderedSetMarshaller( Comparator<V> comparator, Marshaller<V> valueMarshaller
)
+    {
+        this.comparator = comparator;
+        this.valueMarshaller = valueMarshaller;
+    }
+
+
+    /**
+     * Creates a new instance of AvlTreeMarshaller with the default key
+     * Marshaller which uses Java Serialization.
+     *
+     * @param comparator Comparator to be used for key comparision
+     */
+    public OrderedSetMarshaller( Comparator<V> comparator )
+    {
+        this.comparator = comparator;
+        this.valueMarshaller = ( Marshaller<V> ) DefaultMarshaller.INSTANCE;
+    }
+
+
+    /**
+     * Marshals the given tree to bytes
+     * @param tree the tree to be marshalled
+     */
+    public byte[] serialize( OrderedSet<V> set )
+    {
+        if ( ( set == null ) || ( set.getSize() == 0 ) )
+        {
+            return EMPTY_SET;
+        }
+
+        ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
+        DataOutputStream out = new DataOutputStream( byteStream );
+        byte[] data = null;
+        Iterator<V> it = set.getBackingMap().keySet().iterator(); 
+        
+        try
+        {
+            out.writeByte( 0 ); // represents the start of an Array byte stream
+            out.writeInt( set.getSize() );
+
+            while ( it.hasNext() )
+            {
+                V value = it.next();
+                byte[] bytes = valueMarshaller.serialize( value );
+                
+                // Write the key length
+                out.writeInt( bytes.length );
+                
+                // Write the key if its length is not null
+                if ( bytes.length != 0 )
+                {
+                    out.write( bytes );
+                }
+            }
+            
+            out.flush();
+        }
+        catch( IOException e )
+        {
+            e.printStackTrace();
+        }
+        finally
+        {
+            try
+            {
+                out.close();
+            }
+            catch ( IOException e ) 
+            {
+                e.printStackTrace();
+            }
+        }
+        
+        return data;
+    }
+
+    
+    /**
+     * Creates an Array from given bytes of data.
+     * 
+     * @param data byte array to be converted into an array  
+     */
+    public OrderedSet<V> deserialize( byte[] data ) throws IOException
+    {
+        OrderedSet<V> set = new OrderedSet( comparator );
+        
+        //LOG.debug( "Deserializing the tree, called by {}", Reflection.getCallerClass( 2
).getSimpleName() );
+
+        ByteArrayInputStream bin = null;
+        DataInputStream din = null;
+        
+        try
+        {
+            if ( ( data == null ) || ( data.length == 0 ) )
+            {
+                throw new IOException( I18n.err( I18n.ERR_439 ) );
+            }
+    
+            if ( ( data.length == 1 ) && ( data[0] == 0 ) )
+            {
+                // Return empty set
+                
+                return set;
+            }
+    
+            bin = new ByteArrayInputStream( data );
+            din = new DataInputStream( bin );
+            
+            byte startByte = din.readByte();
+            
+            if( startByte != 0 )
+            {
+                throw new IOException( I18n.err( I18n.ERR_440 ) );
+            }
+            
+            V value;
+            int size = din.readInt();
+            
+            for ( int i = 0; i < size; i++ )
+            {
+                // Read the object's size
+                int dataSize = din.readInt();
+                
+                if ( dataSize != 0 )
+                {
+                    byte[] bytes = new byte[ dataSize ];
+                    
+                    din.readFully( bytes );
+                    value = valueMarshaller.deserialize( bytes );
+                    set.insert( value );
+                }
+            }
+            
+            return set;
+        }
+        catch (NullPointerException npe )
+        {
+            System.out.println( I18n.err( I18n.ERR_441, Strings.dumpBytes(data) ) );
+            throw npe;
+        }
+        finally
+        {
+         
+            if ( bin != null )
+            {
+                bin.close();
+            }
+            
+            if ( din != null )
+            {
+                din.close();
+            }
+        }
+    }
+}

Modified: directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java?rev=1210581&r1=1210580&r2=1210581&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java
(original)
+++ directory/apacheds/branches/apacheds-txns/core-avl/src/main/java/org/apache/directory/server/core/avltree/SingletonOrOrderedSet.java
Mon Dec  5 19:10:35 2011
@@ -19,18 +19,20 @@
  */
 package org.apache.directory.server.core.avltree;
 
+import java.util.concurrent.ConcurrentNavigableMap;
+
 import org.apache.directory.server.i18n.I18n;
 
 
 /**
- * Stores either a single object or many of them in an AvlTree.
+ * Stores either a single object or many of them in a ConcurrentNavigableMap.
  *
  * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
  */
 public class SingletonOrOrderedSet<V>
 {
     private V singleton;
-    private AvlTree<V> orderedSet;
+    private OrderedSet<V> orderedSet;
     
     
     /**
@@ -55,7 +57,7 @@ public class SingletonOrOrderedSet<V>
      *
      * @param orderedSet the set of ordered values
      */
-    public SingletonOrOrderedSet( AvlTree<V> orderedSet )
+    public SingletonOrOrderedSet( OrderedSet<V> orderedSet )
     {
         if ( orderedSet == null )
         {
@@ -137,7 +139,7 @@ public class SingletonOrOrderedSet<V>
      * @return the set of ordered values before nulling it out
      * @exception RuntimeException if already in singleton mode
      */
-    public AvlTree<V> switchToSingleton( V singleton )
+    public OrderedSet<V> switchToSingleton( V singleton )
     {
         if ( singleton == null )
         {
@@ -149,7 +151,7 @@ public class SingletonOrOrderedSet<V>
             throw new RuntimeException( I18n.err( I18n.ERR_451 ) );
         }
         
-        AvlTree<V> retval = this.orderedSet;
+        OrderedSet<V> retval = this.orderedSet;
         this.orderedSet = null;
         this.singleton = singleton;
         return retval;
@@ -162,7 +164,7 @@ public class SingletonOrOrderedSet<V>
      * @return the ordered set
      * @exception RuntimeException if in singleton mode
      */
-    public AvlTree<V> getOrderedSet()
+    public OrderedSet<V> getOrderedSet()
     {
         if ( orderedSet != null )
         {
@@ -180,7 +182,7 @@ public class SingletonOrOrderedSet<V>
      * @return the old set of ordered values
      * @exception RuntimeException if in singleton mode
      */
-    public AvlTree<V> setOrderedSet( AvlTree<V> orderedSet )
+    public OrderedSet<V> setOrderedSet( OrderedSet<V> orderedSet )
     {
         if ( orderedSet == null )
         {
@@ -192,7 +194,7 @@ public class SingletonOrOrderedSet<V>
             throw new RuntimeException( I18n.err( I18n.ERR_453 ) );
         }
         
-        AvlTree<V> retval = this.orderedSet;
+        OrderedSet<V> retval = this.orderedSet;
         this.orderedSet = orderedSet;
         return retval;
     }
@@ -206,7 +208,7 @@ public class SingletonOrOrderedSet<V>
      * @return the singleton to return before nulling it out
      * @throws RuntimeException if the mode is already in orderedSet mode.
      */
-    public V switchToOrderedSet( AvlTree<V> orderedSet )
+    public V switchToOrderedSet( OrderedSet<V> orderedSet )
     {
         if ( orderedSet == null )
         {

Added: directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/OrderedSetCursorTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/OrderedSetCursorTest.java?rev=1210581&view=auto
==============================================================================
--- directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/OrderedSetCursorTest.java
(added)
+++ directory/apacheds/branches/apacheds-txns/core-avl/src/test/java/org/apache/directory/server/core/avltree/OrderedSetCursorTest.java
Mon Dec  5 19:10:35 2011
@@ -0,0 +1,384 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+package org.apache.directory.server.core.avltree;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.Comparator;
+
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.junit.Test;
+
+public class OrderedSetCursorTest
+{
+    @Test
+    public void testEmptyCursor() throws Exception
+    {
+        OrderedSet<Integer> set = new OrderedSet<Integer>( new IntegerComparator()
);
+        OrderedSetCursor<Integer> cursor = new OrderedSetCursor<Integer>( set
);
+        
+        assertFalse( cursor.isClosed() );
+        assertFalse( cursor.available() );
+        
+        try
+        {
+            cursor.get();
+            fail( "Should not get here" );
+        }
+        catch ( InvalidCursorPositionException e )
+        {
+            assertNotNull( e );
+        }
+        
+        cursor.beforeFirst();
+        assertFalse( cursor.available() );
+        
+        cursor.afterLast();
+        assertFalse( cursor.available() );
+        
+        assertFalse( cursor.first() );
+        assertFalse( cursor.available() );
+        
+        assertFalse( cursor.last() );
+        assertFalse( cursor.available() );
+        
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+
+        cursor.before( 3 );
+        assertFalse( cursor.available() );
+        
+        cursor.after( 3 );
+        assertFalse( cursor.available() );
+        
+        cursor.close();
+        assertTrue( cursor.isClosed() );
+    }
+    
+    
+    @Test
+    public void testOneEntryCursor() throws Exception
+    {
+        OrderedSet<Integer> set = new OrderedSet<Integer>( new IntegerComparator()
);
+        set.insert( new Integer( 7 ) );
+        OrderedSetCursor<Integer> cursor = new OrderedSetCursor<Integer>( set
);
+        
+        assertFalse( cursor.isClosed() );
+        assertFalse( cursor.available() );
+        
+        try
+        {
+            cursor.get();
+            fail( "Should not get here" );
+        }
+        catch ( InvalidCursorPositionException e )
+        {
+            assertNotNull( e );
+        }
+        
+        cursor.beforeFirst();
+        assertFalse( cursor.available() );
+        assertFalse( cursor.previous() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+        
+        cursor.afterLast();
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        assertTrue( cursor.first() );
+        assertTrue( cursor.available() );
+        
+        assertTrue( cursor.last() );
+        assertTrue( cursor.available() );
+        
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+
+        cursor.before( 3 );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+
+        cursor.before( 3 );
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+
+        cursor.after( 3 );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+
+        cursor.after( 3 );
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+
+        cursor.before( 7 );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+
+        cursor.before( 7 );
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+
+        cursor.after( 7 );
+        assertFalse( cursor.available() );
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+
+        cursor.after( 7 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+
+        cursor.before( 9 );
+        assertFalse( cursor.available() );
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+
+        cursor.before( 9 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+    }
+    
+    
+    @Test
+    public void testManyEntriesCursor() throws Exception
+    {        
+        OrderedSet<Integer> set = new OrderedSet<Integer>( new IntegerComparator()
);
+        set.insert( new Integer( 3 ) );
+        set.insert( new Integer( 7 ) );
+        set.insert( new Integer( 10 ) );
+        set.insert( new Integer( 11 ) );
+        OrderedSetCursor<Integer> cursor = new OrderedSetCursor<Integer>( set
);
+        
+        assertFalse( cursor.isClosed() );
+        assertFalse( cursor.available() );
+        assertEquals( 4, set.getSize() );
+        
+        try
+        {
+            cursor.get();
+            fail( "Should not get here" );
+        }
+        catch ( InvalidCursorPositionException e )
+        {
+            assertNotNull( e );
+        }
+        
+        cursor.beforeFirst();
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, cursor.get().intValue() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, cursor.get().intValue() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, cursor.get().intValue() );
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        
+        cursor.afterLast();
+        assertFalse( cursor.available() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, cursor.get().intValue() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, cursor.get().intValue() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, cursor.get().intValue() );
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+        
+        assertTrue( cursor.first() );
+        assertTrue( cursor.available() );
+        
+        assertTrue( cursor.last() );
+        assertTrue( cursor.available() );
+        
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+
+        // position before first object
+        cursor.after( 2 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, cursor.get().intValue() );
+
+        cursor.after( 2 );
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+
+        // position on first object
+        cursor.after( 3 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+
+        cursor.after( 3 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, cursor.get().intValue() );
+
+        // position after first object
+        cursor.after( 5 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+
+        cursor.after( 5 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, cursor.get().intValue() );
+
+        // position before last object
+        cursor.after( 10 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, cursor.get().intValue() );
+
+        cursor.after( 10 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, cursor.get().intValue() );
+
+        // position on last object
+        cursor.after( 11 );
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+
+        cursor.after( 11 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, cursor.get().intValue() );
+
+        // position after last object
+        cursor.after( 20 );
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+
+        cursor.after( 20 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, cursor.get().intValue() );
+
+        // position after last object
+        cursor.before( 20 );
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+
+        cursor.before( 20 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, cursor.get().intValue() );
+
+        // position on last object
+        cursor.before( 11 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, cursor.get().intValue() );
+
+        cursor.before( 11 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, cursor.get().intValue() );
+
+        // position before last object
+        cursor.before( 10 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, cursor.get().intValue() );
+
+        cursor.before( 10 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+
+        // position after first object
+        cursor.before( 5 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, cursor.get().intValue() );
+
+        cursor.before( 5 );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, cursor.get().intValue() );
+
+        // position on first object
+        cursor.before( 3 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, cursor.get().intValue() );
+
+        cursor.before( 3 );
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+
+        // position before first object
+        cursor.before( 2 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, cursor.get().intValue() );
+
+        cursor.before( 2 );
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+    }
+   
+    
+    class IntegerComparator implements Comparator<Integer>
+    {
+        public int compare( Integer o1, Integer o2 )
+        {
+            return o1.compareTo( o2 );
+        }
+    }
+}



Mime
View raw message