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:10:36 UTC
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/
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 );
+ }
+ }
+}