Author: manik.surtani(a)jboss.com Date: 2009-03-05 11:22:12 -0500 (Thu, 05 Mar 2009) New Revision: 7860 Added: core/branches/flat/src/main/java/org/horizon/util/HorizonCollections.java core/branches/flat/src/main/java/org/horizon/util/ReversibleOrderedSet.java core/branches/flat/src/main/java/org/horizon/util/VisitableBidirectionalLinkedHashSet.java core/branches/flat/src/test/java/org/horizon/util/VisitableBidirectionalLinkedHashSetTest.java Removed: core/branches/flat/src/main/java/org/horizon/util/ReversibleSet.java core/branches/flat/src/main/java/org/horizon/util/VisitableLinkedHashSet.java core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java Modified: core/branches/flat/src/main/java/org/horizon/context/AbstractContext.java core/branches/flat/src/main/java/org/horizon/context/EntryLookup.java core/branches/flat/src/main/java/org/horizon/context/InvocationContextImpl.java core/branches/flat/src/main/java/org/horizon/context/TransactionContextImpl.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUQueue.java core/branches/flat/src/main/java/org/horizon/interceptors/LockingInterceptor.java core/branches/flat/src/main/java/org/horizon/lock/StripedLockManager.java core/branches/flat/src/main/java/org/horizon/util/BidirectionalLinkedHashMap.java core/branches/flat/src/main/java/org/horizon/util/Immutables.java core/branches/flat/src/main/java/org/horizon/util/ObjectDuplicator.java Log: Minor performance tweaks after a brief profiling session Modified: core/branches/flat/src/main/java/org/horizon/context/AbstractContext.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/context/AbstractContext.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/context/AbstractContext.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -3,14 +3,12 @@ import org.horizon.container.MVCCEntry; import org.horizon.invocation.Options; import org.horizon.util.FastCopyHashMap; -import org.horizon.util.Immutables; +import org.horizon.util.ReversibleOrderedSet; +import org.horizon.util.VisitableBidirectionalLinkedHashSet; import java.util.Arrays; import java.util.Collection; -import java.util.Collections; import java.util.EnumSet; -import java.util.LinkedHashSet; -import java.util.List; import java.util.Map; import java.util.Set; @@ -24,11 +22,7 @@ protected EnumSet<Options> options; protected byte contextFlags; - /** - * LinkedHashSet of locks acquired by the invocation. We use a LinkedHashSet because we need efficient Set semantics - * but also need guaranteed ordering for use by lock release code (see JBCCACHE-874). - */ - protected LinkedHashSet<Object> locks; + protected ReversibleOrderedSet<Object> locks; protected FastCopyHashMap<Object, MVCCEntry> lookedUpEntries = null; @@ -96,7 +90,7 @@ public void addKeyLocked(Object lock) { // no need to worry about concurrency here - a context is only valid for a single thread. - if (locks == null) locks = new LinkedHashSet<Object>(getLockSetSize()); + if (locks == null) locks = new VisitableBidirectionalLinkedHashSet<Object>(false, getLockSetSize()); locks.add(lock); } @@ -108,20 +102,15 @@ if (locks != null) locks.clear(); } - public void addAllKeysLocked(List<Object> newLocks) { - // no need to worry about concurrency here - a context is only valid for a single thread. - if (locks == null) locks = new LinkedHashSet<Object>(getLockSetSize()); - locks.addAll(newLocks); - } - - public List<Object> getKeysLocked() { - return locks == null || locks.isEmpty() ? Collections.emptyList() : Immutables.immutableListConvert(locks); - } - public boolean hasLockedKey(Object lock) { return locks != null && locks.contains(lock); } + public void addAllKeysLocked(Collection<Object> keys) { + if (locks == null) locks = new VisitableBidirectionalLinkedHashSet<Object>(false, getLockSetSize()); + locks.addAll(keys); + } + public MVCCEntry lookupEntry(Object key) { return lookedUpEntries.get(key); } @@ -182,7 +171,7 @@ protected void copyInto(AbstractContext ctx) { if (options != null) ctx.options = EnumSet.copyOf(options); ctx.contextFlags = contextFlags; - if (locks != null) ctx.locks = new LinkedHashSet<Object>(locks); + if (locks != null) ctx.locks = new VisitableBidirectionalLinkedHashSet<Object>(false, locks); if (lookedUpEntries != null) ctx.lookedUpEntries = (FastCopyHashMap<Object, MVCCEntry>) lookedUpEntries.clone(); } } Modified: core/branches/flat/src/main/java/org/horizon/context/EntryLookup.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/context/EntryLookup.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/context/EntryLookup.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -22,8 +22,9 @@ package org.horizon.context; import org.horizon.container.MVCCEntry; +import org.horizon.util.ReversibleOrderedSet; -import java.util.List; +import java.util.Collection; import java.util.Map; /** @@ -36,7 +37,8 @@ /** * Retrieves an entry from the collection of looked up entries in the current scope. * <p/> - * If a transaction is in progress, implementations should delegate to the same method in {@link TransactionContext}. + * If a transaction is in progress, implementations should delegate to the same method in {@link + * TransactionContext}. * <p/> * * @param key key to look up @@ -47,7 +49,8 @@ /** * Retrieves a map of entries looked up within the current scope. * <p/> - * If a transaction is in progress, implementations should delegate to the same method in {@link TransactionContext}. + * If a transaction is in progress, implementations should delegate to the same method in {@link + * TransactionContext}. * <p/> * * @return a map of looked up entries. @@ -57,7 +60,8 @@ /** * Puts an entry in the registry of looked up entries in the current scope. * <p/> - * If a transaction is in progress, implementations should delegate to the same method in {@link TransactionContext}. + * If a transaction is in progress, implementations should delegate to the same method in {@link + * TransactionContext}. * <p/> * * @param key key to store @@ -75,7 +79,7 @@ void clearLookedUpEntries(); /** - * Returns an immutable, defensive copy of the List of locks currently maintained for the current scope. + * Returns the set of locks currently maintained for the current scope. Note that this set is ordered. * <p/> * Note that if a transaction is in scope, implementations should retrieve these locks from the {@link * TransactionContext}. Retrieving locks from this method should always ensure they are retrieved from the @@ -83,7 +87,7 @@ * * @return keys locked in current scope. */ - List<Object> getKeysLocked(); + ReversibleOrderedSet<Object> getKeysLocked(); /** * Adds a List of locks to the currently maintained collection of locks acquired. @@ -94,7 +98,7 @@ * * @param keys keys locked */ - void addAllKeysLocked(List<Object> keys); + void addAllKeysLocked(Collection<Object> keys); /** * Adds a lock to the currently maintained collection of locks acquired. Modified: core/branches/flat/src/main/java/org/horizon/context/InvocationContextImpl.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/context/InvocationContextImpl.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/context/InvocationContextImpl.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -25,10 +25,12 @@ import org.horizon.transaction.GlobalTransaction; import org.horizon.transaction.TransactionTable; import org.horizon.util.FastCopyHashMap; +import org.horizon.util.HorizonCollections; +import org.horizon.util.ReversibleOrderedSet; import javax.transaction.Transaction; +import java.util.Collection; import java.util.Collections; -import java.util.List; import java.util.Map; public class InvocationContextImpl extends AbstractContext implements InvocationContext { @@ -183,21 +185,19 @@ return isFlagSet(ContextFlags.ORIGIN_LOCAL); } - @Override - public List<Object> getKeysLocked() { + public ReversibleOrderedSet<Object> getKeysLocked() { // first check transactional scope if (transactionContext != null) return transactionContext.getKeysLocked(); - return super.getKeysLocked(); + return locks == null ? HorizonCollections.emptyReversibleOrderedSet() : locks; } @Override - public void addAllKeysLocked(List<Object> keys) { + public void addAllKeysLocked(Collection<Object> keys) { // first check transactional scope if (transactionContext != null) transactionContext.addAllKeysLocked(keys); else super.addAllKeysLocked(keys); - } @Override Modified: core/branches/flat/src/main/java/org/horizon/context/TransactionContextImpl.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/context/TransactionContextImpl.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/context/TransactionContextImpl.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -25,6 +25,9 @@ import org.horizon.container.MVCCEntry; import org.horizon.transaction.GlobalTransaction; import org.horizon.util.FastCopyHashMap; +import org.horizon.util.HorizonCollections; +import org.horizon.util.Immutables; +import org.horizon.util.ReversibleOrderedSet; import javax.transaction.RollbackException; import javax.transaction.SystemException; @@ -194,6 +197,10 @@ return hasModifications() || hasLocalModifications(); } + public ReversibleOrderedSet<Object> getKeysLocked() { + return locks == null ? HorizonCollections.emptyReversibleOrderedSet() : Immutables.immutableReversibleOrderedSetCopy(locks); + } + @Override public boolean equals(Object o) { if (this == o) return true; Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUQueue.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUQueue.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUQueue.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -22,7 +22,7 @@ package org.horizon.eviction.algorithms.lru; import org.horizon.eviction.algorithms.BaseEvictionQueue; -import org.horizon.util.VisitableLinkedHashSet; +import org.horizon.util.VisitableBidirectionalLinkedHashSet; import java.util.Iterator; @@ -35,7 +35,7 @@ */ public class LRUQueue extends BaseEvictionQueue { - protected VisitableLinkedHashSet<Object> keys = new VisitableLinkedHashSet<Object>(); + protected VisitableBidirectionalLinkedHashSet<Object> keys = new VisitableBidirectionalLinkedHashSet<Object>(true); @Override public void visit(Object key) { Modified: core/branches/flat/src/main/java/org/horizon/interceptors/LockingInterceptor.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/interceptors/LockingInterceptor.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/interceptors/LockingInterceptor.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -42,10 +42,11 @@ import org.horizon.interceptors.base.CommandInterceptor; import org.horizon.lock.IsolationLevel; import org.horizon.lock.LockManager; +import org.horizon.util.ReversibleOrderedSet; import java.util.ArrayList; +import java.util.Iterator; import java.util.List; -import java.util.ListIterator; import java.util.Map; /** @@ -211,7 +212,7 @@ private void doAfterCall(InvocationContext ctx) { // for non-transactional stuff. if (ctx.getTransactionContext() == null) { - List<Object> locks; + ReversibleOrderedSet<Object> locks; if (!(locks = ctx.getKeysLocked()).isEmpty()) { cleanupLocks(locks, ctx, Thread.currentThread(), true); } else { @@ -237,14 +238,14 @@ } } - private void cleanupLocks(List<Object> keysLocked, InvocationContext ctx, Object owner, boolean commit) { + private void cleanupLocks(ReversibleOrderedSet<Object> keysLocked, InvocationContext ctx, Object owner, boolean commit) { // clean up. // unlocking needs to be done in reverse order. - ListIterator<Object> it = keysLocked.listIterator(keysLocked.size()); + Iterator<Object> it = keysLocked.reverseIterator(); if (commit) { - while (it.hasPrevious()) { - Object key = it.previous(); + while (it.hasNext()) { + Object key = it.next(); MVCCEntry entry = ctx.lookupEntry(key); // could be null with read-committed if (entry != null) entry.commitUpdate(dataContainer); @@ -253,8 +254,8 @@ lockManager.unlock(key, owner); } } else { - while (it.hasPrevious()) { - Object key = it.previous(); + while (it.hasNext()) { + Object key = it.next(); MVCCEntry entry = ctx.lookupEntry(key); // could be null with read-committed if (entry != null) entry.rollbackUpdate(); @@ -269,7 +270,7 @@ @SuppressWarnings("unchecked") private void transactionalCleanup(boolean commit, InvocationContext ctx) { if (ctx.getTransactionContext() != null) { - List<Object> locks = ctx.getTransactionContext().getKeysLocked(); + ReversibleOrderedSet<Object> locks = ctx.getTransactionContext().getKeysLocked(); if (!locks.isEmpty()) cleanupLocks(locks, ctx, ctx.getGlobalTransaction(), commit); else if (trace) Modified: core/branches/flat/src/main/java/org/horizon/lock/StripedLockManager.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/lock/StripedLockManager.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/lock/StripedLockManager.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -29,14 +29,14 @@ import org.horizon.invocation.Options; import org.horizon.logging.Log; import org.horizon.logging.LogFactory; +import org.horizon.util.ReversibleOrderedSet; import org.horizon.util.concurrent.locks.LockContainer; import org.horizon.util.concurrent.locks.OwnableReentrantLock; import org.horizon.util.concurrent.locks.OwnableReentrantLockContainer; import org.horizon.util.concurrent.locks.ReentrantLockContainer; import javax.transaction.TransactionManager; -import java.util.List; -import java.util.ListIterator; +import java.util.Iterator; import static java.util.concurrent.TimeUnit.MILLISECONDS; import java.util.concurrent.locks.Lock; @@ -107,12 +107,12 @@ @SuppressWarnings("unchecked") public void unlock(InvocationContext ctx) { - List<Object> locks = ctx.getKeysLocked(); + ReversibleOrderedSet<Object> locks = ctx.getKeysLocked(); if (!locks.isEmpty()) { // unlocking needs to be done in reverse order. - ListIterator<Object> it = locks.listIterator(locks.size()); - while (it.hasPrevious()) { - Object k = it.previous(); + Iterator<Object> it = locks.reverseIterator(); + while (it.hasNext()) { + Object k = it.next(); if (trace) log.trace("Attempting to unlock " + k); lockContainer.getLock(k).unlock(); } Modified: core/branches/flat/src/main/java/org/horizon/util/BidirectionalLinkedHashMap.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/BidirectionalLinkedHashMap.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/util/BidirectionalLinkedHashMap.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -12,9 +12,9 @@ * Similar to the JDK's {@link java.util.LinkedHashMap} except that this version makes use of the fact that entries are * bidirectionally linked and can hence be nagigated either from the start <i>or</i> from the end. It exposes such * navigability by overriding {@link java.util.Map#keySet()} and {@link java.util.Map#entrySet()} to return {@link - * org.horizon.util.ReversibleSet} rather than a standard JDK {@link java.util.Set}. {@link - * org.horizon.util.ReversibleSet}s allow you to access 2 iterators: one that iterates from start to end, as usual, and - * a reversed one that iterates from end to start instead. + * ReversibleOrderedSet} rather than a standard JDK {@link java.util.Set}. {@link ReversibleOrderedSet}s allow you to + * access 2 iterators: one that iterates from start to end, as usual, and a reversed one that iterates from end to start + * instead. * <p/> * Unline the JDK {@link java.util.LinkedHashMap}, this implementation does not support null keys. * <p/> @@ -22,7 +22,7 @@ * @author Manik Surtani * @since 1.0 */ -public class BidirectionalLinkedHashMap<K, V> extends AbstractMap<K, V> { +public class BidirectionalLinkedHashMap<K, V> extends AbstractMap<K, V> implements Cloneable { /** * The head of the doubly linked list. @@ -206,7 +206,7 @@ * mapping for the key. */ final LinkedEntry<K, V> getEntry(Object key) { - int hash = (key == null) ? 0 : hash(key.hashCode()); + int hash = (key == null) ? 0 : hash(key); for (LinkedEntry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { @@ -231,7 +231,7 @@ */ public V put(K key, V value) { assertKeyNotNull(key); - int hash = hash(key.hashCode()); + int hash = hash(key); int i = indexFor(hash, table.length); for (LinkedEntry<K, V> e = table[i]; e != null; e = e.next) { Object k; @@ -253,7 +253,7 @@ * the table, check for comodification, etc. It calls createEntry rather than addEntry. */ private void putForCreate(K key, V value) { - int hash = (key == null) ? 0 : hash(key.hashCode()); + int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); /** @@ -361,7 +361,7 @@ * contains no mapping for this key. */ final LinkedEntry<K, V> removeEntryForKey(Object key) { - int hash = hash(key.hashCode()); + int hash = hash(key); int i = indexFor(hash, table.length); LinkedEntry<K, V> prev = table[i]; LinkedEntry<K, V> e = prev; @@ -396,7 +396,7 @@ Map.Entry<K, V> entry = (Map.Entry<K, V>) o; Object key = entry.getKey(); - int hash = (key == null) ? 0 : hash(key.hashCode()); + int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); LinkedEntry<K, V> prev = table[i]; LinkedEntry<K, V> e = prev; @@ -717,13 +717,13 @@ } } - public ReversibleSet<K> keySet() { + public ReversibleOrderedSet<K> keySet() { if (keySet == null) keySet = new KeySet(); - return (ReversibleSet<K>) keySet; + return (ReversibleOrderedSet<K>) keySet; } private class KeySet extends AbstractSet<K> - implements ReversibleSet<K> { + implements ReversibleOrderedSet<K> { public Iterator<K> reverseIterator() { return new KeyIterator(true); @@ -752,13 +752,13 @@ } } - public ReversibleSet<Map.Entry<K, V>> entrySet() { + public ReversibleOrderedSet<Entry<K, V>> entrySet() { if (entrySet == null) entrySet = new EntrySet(); - return (ReversibleSet<Map.Entry<K, V>>) entrySet; + return (ReversibleOrderedSet<Entry<K, V>>) entrySet; } private final class EntrySet extends AbstractSet<Map.Entry<K, V>> - implements ReversibleSet<Map.Entry<K, V>> { + implements ReversibleOrderedSet<Entry<K, V>> { public Iterator<Map.Entry<K, V>> reverseIterator() { return new EntryIterator(true); @@ -789,4 +789,28 @@ BidirectionalLinkedHashMap.this.clear(); } } + + /** + * Returns a shallow copy of this <tt>Map</tt> instance: the keys and values themselves are not cloned. + * + * @return a shallow copy of this map. + */ + @SuppressWarnings("unchecked") + public BidirectionalLinkedHashMap clone() { + + BidirectionalLinkedHashMap<K, V> result; + try { + result = (BidirectionalLinkedHashMap<K, V>) super.clone(); + } catch (CloneNotSupportedException e) { + throw new RuntimeException("Should never happen!", e); + } + result.table = new LinkedEntry[table.length]; + result.entrySet = null; + result.modCount = 0; + result.size = 0; + result.init(); + result.putAllForCreate(this); + + return result; + } } Added: core/branches/flat/src/main/java/org/horizon/util/HorizonCollections.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/HorizonCollections.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/util/HorizonCollections.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -0,0 +1,50 @@ +package org.horizon.util; + +import java.util.AbstractSet; +import java.util.Iterator; +import java.util.NoSuchElementException; + +/** + * Static helpers for Horizon-specific collections + * + * @author Manik Surtani + * @since 1.0 + */ +public class HorizonCollections { + private static final ReversibleOrderedSet EMPTY_ROS = new EmptyReversibleOrderedSet(); + + @SuppressWarnings("unchecked") + public static final <T> ReversibleOrderedSet<T> emptyReversibleOrderedSet() { + return (ReversibleOrderedSet<T>) EMPTY_ROS; + } + + private static final class EmptyReversibleOrderedSet extends AbstractSet implements ReversibleOrderedSet { + + Iterator it = new Iterator() { + + public boolean hasNext() { + return false; + } + + public Object next() { + throw new NoSuchElementException(); + } + + public void remove() { + throw new UnsupportedOperationException(); + } + }; + + public Iterator iterator() { + return it; + } + + public int size() { + return 0; + } + + public Iterator reverseIterator() { + return it; + } + } +} Modified: core/branches/flat/src/main/java/org/horizon/util/Immutables.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/Immutables.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/util/Immutables.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -184,7 +184,18 @@ return null; } + public static <T> ReversibleOrderedSet<T> immutableReversibleOrderedSetCopy(ReversibleOrderedSet<T> set) { + Set<? extends T> copy = ObjectDuplicator.duplicateSet(set); + if (copy == null) + // Set uses Collection copy-ctor + copy = attemptCopyConstructor(set, ReversibleOrderedSet.class); + if (copy == null) + copy = new VisitableBidirectionalLinkedHashSet<T>(false, set); + return new ImmutableReversibleOrderedSetWrapper<T>(copy); + } + + public interface Immutable { } @@ -298,7 +309,18 @@ } } + private static class ImmutableReversibleOrderedSetWrapper<E> extends ImmutableCollectionWrapper<E> implements ReversibleOrderedSet<E>, Serializable, Immutable { + private static final long serialVersionUID = 7991492805176142615L; + public ImmutableReversibleOrderedSetWrapper(Set<? extends E> set) { + super(set); + } + + public Iterator<E> reverseIterator() { + return new ImmutableIteratorWrapper<E>(((ReversibleOrderedSet<? extends E>) collection).reverseIterator()); + } + } + static class ImmutableEntry<K, V> implements Entry<K, V> { private K key; private V value; Modified: core/branches/flat/src/main/java/org/horizon/util/ObjectDuplicator.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/ObjectDuplicator.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/util/ObjectDuplicator.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -37,6 +37,15 @@ } @SuppressWarnings("unchecked") + public static <E> ReversibleOrderedSet<E> duplicateReversibleOrderedSet(ReversibleOrderedSet<E> original) { + if (original instanceof VisitableBidirectionalLinkedHashSet) + return (ReversibleOrderedSet<E>) ((VisitableBidirectionalLinkedHashSet) original).clone(); + + return attemptClone(original); + } + + + @SuppressWarnings("unchecked") public static <E> Collection<E> duplicateCollection(Collection<E> original) { if (original instanceof HashSet) return (Set<E>) ((HashSet) original).clone(); Copied: core/branches/flat/src/main/java/org/horizon/util/ReversibleOrderedSet.java (from rev 7856, core/branches/flat/src/main/java/org/horizon/util/ReversibleSet.java) =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/ReversibleOrderedSet.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/util/ReversibleOrderedSet.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -0,0 +1,15 @@ +package org.horizon.util; + +import java.util.Iterator; +import java.util.Set; + +/** + * A set that allows reverse iteration of the set elements, exposed via the {@link #reverseIterator()} method. This + * only really makes sense for ordered Set implementations, such as sets which are linked. + * + * @author Manik Surtani + * @since 1.0 + */ +public interface ReversibleOrderedSet<E> extends Set<E> { + Iterator<E> reverseIterator(); +} Deleted: core/branches/flat/src/main/java/org/horizon/util/ReversibleSet.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/ReversibleSet.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/util/ReversibleSet.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -1,15 +0,0 @@ -package org.horizon.util; - -import java.util.Iterator; -import java.util.Set; - -/** - * A set that allows reverse iteration of the set elements, exposed via the {@link #reverseIterator()} method. This - * only really makes sense for ordered Set implementations. - * - * @author Manik Surtani - * @since 1.0 - */ -public interface ReversibleSet<E> extends Set<E> { - Iterator<E> reverseIterator(); -} Copied: core/branches/flat/src/main/java/org/horizon/util/VisitableBidirectionalLinkedHashSet.java (from rev 7856, core/branches/flat/src/main/java/org/horizon/util/VisitableLinkedHashSet.java) =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/VisitableBidirectionalLinkedHashSet.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/util/VisitableBidirectionalLinkedHashSet.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -0,0 +1,170 @@ +package org.horizon.util; + +import java.util.AbstractSet; +import java.util.Collection; +import java.util.Iterator; + +/** + * Similar to the JDK's {@link java.util.LinkedHashSet} except that it sets the underlying {@link + * java.util.LinkedHashMap}'s <tt>accessOrder</tt> constructor parameter to <tt>true</tt>, allowing for recording of + * visits. To do this, this implementation exposes a {@link #visit(Object)} method to visit a key. + * + * @author Manik Surtani + * @since 1.0 + */ +public class VisitableBidirectionalLinkedHashSet<E> extends AbstractSet<E> implements ReversibleOrderedSet<E>, Cloneable { + + private transient BidirectionalLinkedHashMap<E, Object> map; + + // Dummy value to associate with an Object in the backing Map + private static final Object DUMMY_VALUE = new Object(); + + + /** + * Constructs a new, empty linked hash set with the specified initial capacity and load factor. + * + * @param visitable if true, visiting an element (using {@link #visit(Object)}) will cause that element to be + * moved to the end of the linked list that connects entries. + * @param initialCapacity the initial capacity of the linked hash set + * @param loadFactor the load factor of the linked hash set + * @throws IllegalArgumentException if the initial capacity is less than zero, or if the load factor is nonpositive + */ + public VisitableBidirectionalLinkedHashSet(boolean visitable, int initialCapacity, float loadFactor) { + map = new BidirectionalLinkedHashMap<E, Object>(initialCapacity, loadFactor, visitable); + } + + /** + * Constructs a new, empty linked hash set with the specified initial capacity and the default load factor (0.75). + * + * @param visitable if true, visiting an element (using {@link #visit(Object)}) will cause that element to be + * moved to the end of the linked list that connects entries. + * @param initialCapacity the initial capacity of the LinkedHashSet + * @throws IllegalArgumentException if the initial capacity is less than zero + */ + public VisitableBidirectionalLinkedHashSet(boolean visitable, int initialCapacity) { + this(visitable, initialCapacity, .75f); + } + + /** + * Constructs a new, empty linked hash set with the default initial capacity (16) and load factor (0.75). + * + * @param visitable if true, visiting an element (using {@link #visit(Object)}) will cause that element to be moved + * to the end of the linked list that connects entries. + */ + public VisitableBidirectionalLinkedHashSet(boolean visitable) { + this(visitable, 16, .75f); + } + + /** + * Constructs a new linked hash set with the same elements as the specified collection. The linked hash set is + * created with an initial capacity sufficient to hold the elements in the specified collection and the default load + * factor (0.75). + * + * @param visitable if true, visiting an element (using {@link #visit(Object)}) will cause that element to be moved + * to the end of the linked list that connects entries. + * @param c the collection whose elements are to be placed into this set + * @throws NullPointerException if the specified collection is null + */ + public VisitableBidirectionalLinkedHashSet(boolean visitable, Collection<? extends E> c) { + this(visitable, Math.max(2 * c.size(), 11), .75f); + addAll(c); + } + + /** + * Returns an iterator over the elements in this set. The elements are returned in no particular order. + * + * @return an Iterator over the elements in this set + * @see java.util.ConcurrentModificationException + */ + public Iterator<E> iterator() { + return map.keySet().iterator(); + } + + public Iterator<E> reverseIterator() { + return map.keySet().reverseIterator(); + } + + /** + * Returns the number of elements in this set (its cardinality). + * + * @return the number of elements in this set (its cardinality) + */ + public int size() { + return map.size(); + } + + /** + * Returns <tt>true</tt> if this set contains no elements. + * + * @return <tt>true</tt> if this set contains no elements + */ + public boolean isEmpty() { + return map.isEmpty(); + } + + /** + * Returns <tt>true</tt> if this set contains the specified element. More formally, returns <tt>true</tt> if and only + * if this set contains an element <tt>e</tt> such that <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>. + * + * @param o element whose presence in this set is to be tested + * @return <tt>true</tt> if this set contains the specified element + */ + public boolean contains(Object o) { + return map.containsKey(o); + } + + /** + * Adds the specified element to this set if it is not already present. More formally, adds the specified element + * <tt>e</tt> to this set if this set contains no element <tt>e2</tt> such that <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>. + * If this set already contains the element, the call leaves the set unchanged and returns <tt>false</tt>. + * + * @param e element to be added to this set + * @return <tt>true</tt> if this set did not already contain the specified element + */ + public boolean add(E e) { + return map.put(e, DUMMY_VALUE) == null; + } + + /** + * Removes the specified element from this set if it is present. More formally, removes an element <tt>e</tt> such + * that <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>, if this set contains such an element. Returns + * <tt>true</tt> if this set contained the element (or equivalently, if this set changed as a result of the call). + * (This set will not contain the element once the call returns.) + * + * @param o object to be removed from this set, if present + * @return <tt>true</tt> if the set contained the specified element + */ + public boolean remove(Object o) { + return map.remove(o) == DUMMY_VALUE; + } + + /** + * Visits the key in the underlying Map, by performing a {@link java.util.Map#get(Object)}. This records the access + * and updates the ordering accordingly. + * + * @param key key to visit + */ + public void visit(E key) { + map.get(key); + } + + /** + * Removes all of the elements from this set. The set will be empty after this call returns. + */ + public void clear() { + map.clear(); + } + + @SuppressWarnings("unchecked") + public VisitableBidirectionalLinkedHashSet clone() { + VisitableBidirectionalLinkedHashSet result; + try { + result = (VisitableBidirectionalLinkedHashSet) super.clone(); + } catch (CloneNotSupportedException e) { + throw new RuntimeException("Should never happen", e); + } + + result.map = map.clone(); + return result; + } +} Deleted: core/branches/flat/src/main/java/org/horizon/util/VisitableLinkedHashSet.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/VisitableLinkedHashSet.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/main/java/org/horizon/util/VisitableLinkedHashSet.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -1,148 +0,0 @@ -package org.horizon.util; - -import java.util.AbstractSet; -import java.util.Collection; -import java.util.Iterator; - -/** - * Similar to the JDK's {@link java.util.LinkedHashSet} except that it sets the underlying {@link - * java.util.LinkedHashMap}'s <tt>accessOrder</tt> constructor parameter to <tt>true</tt>, allowing for recording of - * visits. To do this, this implementation exposes a {@link #visit(Object)} method to visit a key. - * - * @author Manik Surtani - * @since 1.0 - */ -public class VisitableLinkedHashSet<E> extends AbstractSet<E> implements ReversibleSet<E> { - - private transient BidirectionalLinkedHashMap<E, Object> map; - - // Dummy value to associate with an Object in the backing Map - private static final Object DUMMY_VALUE = new Object(); - - - /** - * Constructs a new, empty linked hash set with the specified initial capacity and load factor. - * - * @param initialCapacity the initial capacity of the linked hash set - * @param loadFactor the load factor of the linked hash set - * @throws IllegalArgumentException if the initial capacity is less than zero, or if the load factor is nonpositive - */ - public VisitableLinkedHashSet(int initialCapacity, float loadFactor) { - map = new BidirectionalLinkedHashMap<E, Object>(initialCapacity, loadFactor, true); - } - - /** - * Constructs a new, empty linked hash set with the specified initial capacity and the default load factor (0.75). - * - * @param initialCapacity the initial capacity of the LinkedHashSet - * @throws IllegalArgumentException if the initial capacity is less than zero - */ - public VisitableLinkedHashSet(int initialCapacity) { - this(initialCapacity, .75f); - } - - /** - * Constructs a new, empty linked hash set with the default initial capacity (16) and load factor (0.75). - */ - public VisitableLinkedHashSet() { - this(16, .75f); - } - - /** - * Constructs a new linked hash set with the same elements as the specified collection. The linked hash set is - * created with an initial capacity sufficient to hold the elements in the specified collection and the default load - * factor (0.75). - * - * @param c the collection whose elements are to be placed into this set - * @throws NullPointerException if the specified collection is null - */ - public VisitableLinkedHashSet(Collection<? extends E> c) { - this(Math.max(2 * c.size(), 11), .75f); - addAll(c); - } - - /** - * Returns an iterator over the elements in this set. The elements are returned in no particular order. - * - * @return an Iterator over the elements in this set - * @see java.util.ConcurrentModificationException - */ - public Iterator<E> iterator() { - return map.keySet().iterator(); - } - - public Iterator<E> reverseIterator() { - return map.keySet().reverseIterator(); - } - - /** - * Returns the number of elements in this set (its cardinality). - * - * @return the number of elements in this set (its cardinality) - */ - public int size() { - return map.size(); - } - - /** - * Returns <tt>true</tt> if this set contains no elements. - * - * @return <tt>true</tt> if this set contains no elements - */ - public boolean isEmpty() { - return map.isEmpty(); - } - - /** - * Returns <tt>true</tt> if this set contains the specified element. More formally, returns <tt>true</tt> if and only - * if this set contains an element <tt>e</tt> such that <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>. - * - * @param o element whose presence in this set is to be tested - * @return <tt>true</tt> if this set contains the specified element - */ - public boolean contains(Object o) { - return map.containsKey(o); - } - - /** - * Adds the specified element to this set if it is not already present. More formally, adds the specified element - * <tt>e</tt> to this set if this set contains no element <tt>e2</tt> such that <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>. - * If this set already contains the element, the call leaves the set unchanged and returns <tt>false</tt>. - * - * @param e element to be added to this set - * @return <tt>true</tt> if this set did not already contain the specified element - */ - public boolean add(E e) { - return map.put(e, DUMMY_VALUE) == null; - } - - /** - * Removes the specified element from this set if it is present. More formally, removes an element <tt>e</tt> such - * that <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>, if this set contains such an element. Returns - * <tt>true</tt> if this set contained the element (or equivalently, if this set changed as a result of the call). - * (This set will not contain the element once the call returns.) - * - * @param o object to be removed from this set, if present - * @return <tt>true</tt> if the set contained the specified element - */ - public boolean remove(Object o) { - return map.remove(o) == DUMMY_VALUE; - } - - /** - * Visits the key in the underlying Map, by performing a {@link java.util.Map#get(Object)}. This records the access - * and updates the ordering accordingly. - * - * @param key key to visit - */ - public void visit(E key) { - map.get(key); - } - - /** - * Removes all of the elements from this set. The set will be empty after this call returns. - */ - public void clear() { - map.clear(); - } -} Copied: core/branches/flat/src/test/java/org/horizon/util/VisitableBidirectionalLinkedHashSetTest.java (from rev 7856, core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java) =================================================================== --- core/branches/flat/src/test/java/org/horizon/util/VisitableBidirectionalLinkedHashSetTest.java (rev 0) +++ core/branches/flat/src/test/java/org/horizon/util/VisitableBidirectionalLinkedHashSetTest.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -0,0 +1,69 @@ +package org.horizon.util; + +import org.testng.annotations.Test; + +import java.util.Iterator; +import java.util.Set; + +@Test(groups = "unit", testName = "util.VisitableBidirectionalLinkedHashSetTest") +public class VisitableBidirectionalLinkedHashSetTest { + + public void testVisitableSet() { + VisitableBidirectionalLinkedHashSet<Integer> set = new VisitableBidirectionalLinkedHashSet<Integer>(true); + initSet(set); + + testOrderBeforeRemoval(set); + + // now attemp a visit and test that the visits are NOT recorded + set.visit(200); + + // check the forward iterator that everything is in order of entry + Iterator<Integer> it = set.iterator(); + int index = 0; + while (it.hasNext()) { + if (index == 200) index = 201; + if (index == 1000) index = 200; + Integer value = it.next(); + assert value == index++ : "Expecting " + (index - 1) + " but was " + value; + } + + // now check the reverse iterator. + it = set.reverseIterator(); + index = 200; // this should be the first + while (it.hasNext()) { + assert it.next() == index--; + if (index == 199) index = 999; + if (index == 200) index = 199; + } + + for (Iterator i = set.iterator(); i.hasNext();) { + i.next(); + i.remove(); + } + + assert set.isEmpty(); + assert set.size() == 0 : "Expecting size to be 0 but was " + set.size(); + } + + + private void initSet(Set<Integer> set) { + for (int i = 0; i < 1000; i++) set.add(i); + } + + private void testOrderBeforeRemoval(VisitableBidirectionalLinkedHashSet<Integer> set) { + // check the forward iterator that everything is in order of entry + Iterator<Integer> it = set.iterator(); + int index = 0; + while (it.hasNext()) assert it.next() == index++; + assert index == 1000 : "Expected 1000, index was " + index; + assert set.size() == 1000; + // now check the reverse iterator. + it = set.reverseIterator(); + index = 999; + while (it.hasNext()) { + Integer value = it.next(); + assert value == index-- : "failed, expecting " + (index + 1) + " but was " + value; + } + assert index == -1 : "Was " + index + ", instead of -1"; + } +} Deleted: core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java 2009-03-05 16:20:54 UTC (rev 7859) +++ core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java 2009-03-05 16:22:12 UTC (rev 7860) @@ -1,69 +0,0 @@ -package org.horizon.util; - -import org.testng.annotations.Test; - -import java.util.Iterator; -import java.util.Set; - -@Test(groups = "unit", testName = "util.VisitableLinkedHashSetTest") -public class VisitableLinkedHashSetTest { - - public void testVisitableSet() { - VisitableLinkedHashSet<Integer> set = new VisitableLinkedHashSet<Integer>(); - initSet(set); - - testOrderBeforeRemoval(set); - - // now attemp a visit and test that the visits are NOT recorded - set.visit(200); - - // check the forward iterator that everything is in order of entry - Iterator<Integer> it = set.iterator(); - int index = 0; - while (it.hasNext()) { - if (index == 200) index = 201; - if (index == 1000) index = 200; - Integer value = it.next(); - assert value == index++ : "Expecting " + (index - 1) + " but was " + value; - } - - // now check the reverse iterator. - it = set.reverseIterator(); - index = 200; // this should be the first - while (it.hasNext()) { - assert it.next() == index--; - if (index == 199) index = 999; - if (index == 200) index = 199; - } - - for (Iterator i = set.iterator(); i.hasNext();) { - i.next(); - i.remove(); - } - - assert set.isEmpty(); - assert set.size() == 0 : "Expecting size to be 0 but was " + set.size(); - } - - - private void initSet(Set<Integer> set) { - for (int i = 0; i < 1000; i++) set.add(i); - } - - private void testOrderBeforeRemoval(VisitableLinkedHashSet<Integer> set) { - // check the forward iterator that everything is in order of entry - Iterator<Integer> it = set.iterator(); - int index = 0; - while (it.hasNext()) assert it.next() == index++; - assert index == 1000 : "Expected 1000, index was " + index; - assert set.size() == 1000; - // now check the reverse iterator. - it = set.reverseIterator(); - index = 999; - while (it.hasNext()) { - Integer value = it.next(); - assert value == index-- : "failed, expecting " + (index + 1) + " but was " + value; - } - assert index == -1 : "Was " + index + ", instead of -1"; - } -}