Author: manik.surtani(a)jboss.com Date: 2009-02-06 07:27:16 -0500 (Fri, 06 Feb 2009) New Revision: 7657 Added: core/branches/flat/src/main/java/org/horizon/container/CachedEntry.java core/branches/flat/src/main/java/org/horizon/eviction/events/ core/branches/flat/src/main/java/org/horizon/eviction/events/EvictionEvent.java core/branches/flat/src/main/java/org/horizon/eviction/events/InUseEvictionEvent.java core/branches/flat/src/main/java/org/horizon/util/AbstractMap.java core/branches/flat/src/main/java/org/horizon/util/BidirectionalLinkedHashMap.java 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/SkipListTest.java core/branches/flat/src/test/java/org/horizon/util/BidirectionalLinkedHashMapTest.java core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java Removed: core/branches/flat/src/main/java/org/horizon/eviction/EntryEvictionData.java core/branches/flat/src/main/java/org/horizon/eviction/EvictionEvent.java Modified: core/branches/flat/src/main/java/org/horizon/container/DataContainer.java core/branches/flat/src/main/java/org/horizon/container/UnsortedDataContainer.java core/branches/flat/src/main/java/org/horizon/eviction/EvictionAlgorithm.java core/branches/flat/src/main/java/org/horizon/eviction/EvictionManager.java core/branches/flat/src/main/java/org/horizon/eviction/EvictionManagerImpl.java core/branches/flat/src/main/java/org/horizon/eviction/EvictionQueue.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/BaseEvictionAlgorithm.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/BaseEvictionQueue.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/fifo/FIFOAlgorithm.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/fifo/FIFOQueue.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUAlgorithm.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUQueue.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUAlgorithm.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUQueue.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/mru/MRUAlgorithm.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/mru/MRUQueue.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/nullalgo/NullEvictionAlgorithm.java core/branches/flat/src/main/java/org/horizon/eviction/algorithms/nullalgo/NullEvictionQueue.java core/branches/flat/src/main/java/org/horizon/interceptors/EvictionInterceptor.java core/branches/flat/src/main/java/org/horizon/util/FastCopyHashMap.java core/branches/flat/src/test/java/org/horizon/eviction/EvictionFunctionalTest.java core/branches/flat/src/test/java/org/horizon/eviction/EvictionManagerTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/BaseAlgorithmTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/BaseQueueTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/fifo/FifoAlgorithmTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/fifo/FifoQueueTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuAlgorithmTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuQueueTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lru/LruAlgorithmTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lru/LruQueueTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/mru/MruAlgorithmTest.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/mru/MruQueueTest.java Log: Rewrote eviction Added: core/branches/flat/src/main/java/org/horizon/container/CachedEntry.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/container/CachedEntry.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/container/CachedEntry.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,9 @@ +package org.horizon.container; + +/** + * This is a wrapper for a cached entry, containing a reference to key, value and metadata. + * + * @author Manik Surtani + * @since 1.0 + */ + Modified: core/branches/flat/src/main/java/org/horizon/container/DataContainer.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/container/DataContainer.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/container/DataContainer.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -47,4 +47,8 @@ void clear(); Set<K> keySet(); + + long getCreatedTimestamp(K key); + + long getModifiedTimestamp(K key); } Modified: core/branches/flat/src/main/java/org/horizon/container/UnsortedDataContainer.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/container/UnsortedDataContainer.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/container/UnsortedDataContainer.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -34,34 +34,60 @@ * @since 1.0 */ public class UnsortedDataContainer<K, V> implements DataContainer<K, V> { - private final ConcurrentMap<Object, Object> data = new ConcurrentHashMap<Object, Object>(); + private final ConcurrentMap<Object, CachedValue<V>> data = new ConcurrentHashMap<Object, CachedValue<V>>(); private static final Object NULL = new Object(); @SuppressWarnings("unchecked") - private Object maskNull(Object o) { - return o == null ? (K) NULL : (K) o; + private K maskNullKey(K o) { + return o == null ? (K) NULL : o; } - private Object unmaskNull(Object o) { + private K unmaskNullKey(K o) { return (o == NULL) ? null : o; } @SuppressWarnings("unchecked") public V get(K k) { - return (V) unmaskNull(data.get(maskNull(k))); + CachedValue<V> cv = data.get(maskNullKey(k)); + if (cv != null) { + cv.touch(); + return cv.value; + } else { + return null; + } } public void put(K k, V v) { - data.put(maskNull(k), maskNull(v)); + K maskedKey = maskNullKey(k); + + CachedValue<V> cv = data.get(maskedKey); + if (cv == null) { + cv = new CachedValue<V>(v); + data.put(maskedKey, cv); + } else { + cv.touch(); + cv.value = v; + } } public boolean containsKey(K k) { - return data.containsKey(maskNull(k)); + return data.containsKey(maskNullKey(k)); } + public long getModifiedTimestamp(K key) { + CachedValue cv = data.get(maskNullKey(key)); + return cv == null ? -1 : cv.modified; + } + + public long getCreatedTimestamp(K key) { + CachedValue cv = data.get(maskNullKey(key)); + return cv == null ? -1 : cv.created; + } + @SuppressWarnings("unchecked") public V remove(K k) { - return (V) unmaskNull(data.remove(maskNull(k))); + CachedValue<V> cv = data.remove(maskNullKey(k)); + return cv == null ? null : cv.value; } public int size() { @@ -96,7 +122,7 @@ } public boolean contains(Object o) { - return realSet.contains(maskNull(o)); + return realSet.contains(maskNullKey((K) o)); } public boolean remove(Object o) { @@ -121,11 +147,32 @@ @SuppressWarnings("unchecked") public K next() { - return (K) unmaskNull(realIterator.next()); + return unmaskNullKey((K) realIterator.next()); } public void remove() { throw new UnsupportedOperationException(); } } -} + + private static class CachedValue<V> { + V value; + long created; + long modified; + + public CachedValue(V value) { + this.value = value; + created = modified = System.currentTimeMillis(); + } + + public CachedValue(V value, long created, long modified) { + this.value = value; + this.created = created; + this.modified = modified; + } + + public void touch() { + modified = System.currentTimeMillis(); + } + } +} \ No newline at end of file Deleted: core/branches/flat/src/main/java/org/horizon/eviction/EntryEvictionData.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/EntryEvictionData.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/EntryEvictionData.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,167 +0,0 @@ -/* - * JBoss, Home of Professional Open Source. - * Copyright 2000 - 2008, Red Hat Middleware LLC, and individual contributors - * as indicated by the @author tags. See the copyright.txt file in the - * distribution for a full listing of individual contributors. - * - * This is free software; you can redistribute it and/or modify it - * under the terms of the GNU Lesser General Public License as - * published by the Free Software Foundation; either version 2.1 of - * the License, or (at your option) any later version. - * - * This software is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this software; if not, write to the Free - * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA - * 02110-1301 USA, or see the FSF site: http://www.fsf.org. - */ -package org.horizon.eviction; - -/** - * Value object used in queue - * - * @author Ben Wang 2-2004 - * @author Daniel Huang - dhuang(a)jboss.org - * @since 1.0 - */ -public class EntryEvictionData { - private long modifiedTimeStamp; - private long creationTimeStamp; - private int numberOfVisits; - private Object key; - - private long inUseTimeoutTimestamp; - private boolean currentlyInUse = false; - - /** - * Private constructor that automatically sets the creation time stamp of the node entry. - */ - private EntryEvictionData() { - this.creationTimeStamp = System.currentTimeMillis(); - } - - public EntryEvictionData(Object key) { - this(); - setKey(key); - } - - public EntryEvictionData(int numberOfVisits, long modifiedTimeStamp, Object key) { - this(key); - this.numberOfVisits = numberOfVisits; - this.modifiedTimeStamp = modifiedTimeStamp; - } - - /** - * Is the node currently in use. - * - * @return true if the node is currently marked as in use. - */ - public boolean isCurrentlyInUse() { - return currentlyInUse; - } - - public void setCurrentlyInUse(boolean currentlyInUse, long inUseTimeout) { - this.currentlyInUse = currentlyInUse; - if (inUseTimeout > 0) { - this.inUseTimeoutTimestamp = System.currentTimeMillis() + inUseTimeout; - } - } - - public long getInUseTimeoutTimestamp() { - return this.inUseTimeoutTimestamp; - } - - /** - * Get modified time stamp. This stamp is created during the node is processed so it has some fuzy tolerance in - * there. - * - * @return The last modified time stamp - */ - public long getModifiedTimeStamp() { - return modifiedTimeStamp; - } - - public void setModifiedTimeStamp(long modifiedTimeStamp) { - this.modifiedTimeStamp = modifiedTimeStamp; - } - - /** - * Get the time stamp for when the node entry was created. - * - * @return The node entry creation time stamp - */ - public long getCreationTimeStamp() { - return creationTimeStamp; - } - - public void setCreationTimeStamp(long creationTimeStamp) { - this.creationTimeStamp = creationTimeStamp; - } - - public int getNumberOfVisits() { - return numberOfVisits; - } - - public void setNumberOfVisits(int numberOfVisits) { - this.numberOfVisits = numberOfVisits; - } - - public Object getKey() { - return key; - } - - void setKey(Object key) { - this.key = key; - } - - @Override - public int hashCode() { - return key.hashCode(); - } - - public boolean isNodeInUseAndNotTimedOut() { - if (isCurrentlyInUse()) { - if (getInUseTimeoutTimestamp() == 0) { - return true; - } - - if (System.currentTimeMillis() < getInUseTimeoutTimestamp()) { - return true; - } - } - return false; - } - - @Override - public boolean equals(Object o) { - if (!(o instanceof EntryEvictionData)) - return false; - EntryEvictionData ne = (EntryEvictionData) o; - return key.equals(ne.getKey()); - } - - @Override - public String toString() { - StringBuilder output = new StringBuilder(); - output.append("Fqn: "); - if (key != null) { - output.append(key); - } else { - output.append(" null"); - } - - output.append(" CreateTime: ").append(this.getCreationTimeStamp()); - output.append(" Visits: ").append(this.getNumberOfVisits()); - output.append(" ModifiedTime: ").append(this.getModifiedTimeStamp()); - output.append(" CurrentlyInUse: ").append(this.isCurrentlyInUse()); - return output.toString(); - } - - public void incrementNumberOfVisits() { - numberOfVisits++; - } -} Modified: core/branches/flat/src/main/java/org/horizon/eviction/EvictionAlgorithm.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/EvictionAlgorithm.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/EvictionAlgorithm.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -23,58 +23,58 @@ import org.horizon.Cache; import org.horizon.config.EvictionAlgorithmConfig; -import org.horizon.eviction.EvictionEvent.Type; +import org.horizon.container.DataContainer; +import org.horizon.eviction.events.EvictionEvent; +import org.horizon.eviction.events.EvictionEvent.Type; +import org.horizon.lifecycle.Lifecycle; import java.util.concurrent.BlockingQueue; /** - * Interface for all eviction algorithms. - * <p/> - * Note: None of the Eviction classes are thread safe. It is assumed that an individual instance of an EvictionPolicy/ - * EvictionAlgorithm/EvictionQueue/EvictionConfiguration are only operated on by one thread at any given time. + * Interface for all eviction algorithms. There is no requirement for implementations to be thread safe, as the {@link + * org.horizon.eviction.EvictionManager} will guarantee that only a single thread will access the algorithm + * implementation at any given time. * - * @author (various) + * @author Manik Surtani * @since 1.0 */ -public interface EvictionAlgorithm { +public interface EvictionAlgorithm extends Lifecycle { /** * Entry point for eviction algorithm. Invoking this will cause the algorithm to process the queue of {@link * EvictionEvent}s passed in. * - * @param queue blocking queue of {@link org.horizon.eviction.EvictionEvent}s to process. + * @param queue blocking queue of {@link org.horizon.eviction.events.EvictionEvent}s to process. * @throws EvictionException if there is a problem processing any of these events */ void process(BlockingQueue<EvictionEvent> queue) throws EvictionException; /** - * Reset the whole eviction queue. The queue may need to be reset due to corrupted state, for example. + * Reset the eviction queue. */ void resetEvictionQueue(); /** - * Get the EvictionQueue implementation used by this algorithm. + * Sets the eviction action policy, so the algorithm knows what to do when an entry is to be evicted. * - * @return an EvictionQueue instance that is able to sort keys for eviction as dictated by the eviction algorithm - */ - EvictionQueue getEvictionQueue(); - - /** - * Sets the eviction action policy, so the algorithm knows what to do when a node is to be evicted. - * * @param evictionAction eviction action instance to use */ void setEvictionAction(EvictionAction evictionAction); /** - * Assigns the algorithm instance to a given Cache. + * Initializes the algorithm instance by passing in the cache instance, data container and configuration * * @param cache cache to work with + * @param dataContiner the cache's data container * @param evictionAlgorithmConfig algorithm configuration to use */ - void assignToCache(Cache<?, ?> cache, EvictionAlgorithmConfig evictionAlgorithmConfig); + void init(Cache<?, ?> cache, DataContainer<?, ?> dataContiner, + EvictionAlgorithmConfig evictionAlgorithmConfig); /** - * Tests whether the algorithm would ignore certain event types on certain Fqns. + * Tests whether the algorithm would ignore certain event types. This is an optimization on the {@link + * org.horizon.eviction.EvictionManager} so that events that would eventually be ignored in {@link + * #process(java.util.concurrent.BlockingQueue)} would not be added to the event queue, keeping the queue smaller and + * leaving more space to deal with more important event types. * * @param eventType event type to test for * @return true if the event representing the parameters would be ignored by this algorithm or not. @@ -82,11 +82,6 @@ boolean canIgnoreEvent(Type eventType); /** - * Invoked by the region manager when the enclosing region is initialized. - */ - void initialize(); - - /** * @return the type of the {@link org.horizon.config.EvictionAlgorithmConfig} bean used to configure this * implementation of {@link org.horizon.eviction.EvictionAlgorithm} */ Deleted: core/branches/flat/src/main/java/org/horizon/eviction/EvictionEvent.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/EvictionEvent.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/EvictionEvent.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,107 +0,0 @@ -/* - * JBoss, Home of Professional Open Source. - * Copyright 2000 - 2008, Red Hat Middleware LLC, and individual contributors - * as indicated by the @author tags. See the copyright.txt file in the - * distribution for a full listing of individual contributors. - * - * This is free software; you can redistribute it and/or modify it - * under the terms of the GNU Lesser General Public License as - * published by the Free Software Foundation; either version 2.1 of - * the License, or (at your option) any later version. - * - * This software is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this software; if not, write to the Free - * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA - * 02110-1301 USA, or see the FSF site: http://www.fsf.org. - */ -package org.horizon.eviction; - -/** - * An eviction event records activity on nodes in the cache. These are recorded for processing later. - * - * @author (various) - * @since 1.0 - */ -public class EvictionEvent { - private Object key; - private Type type; - - private long inUseTimeout; - private long creationTimestamp; - - public EvictionEvent() { - } - - public static enum Type { - ADD_ENTRY_EVENT, - REMOVE_ENTRY_EVENT, - VISIT_ENTRY_EVENT, - CLEAR_CACHE_EVENT, - MARK_IN_USE_EVENT, - UNMARK_IN_USE_EVENT - } - - public EvictionEvent(Object key, Type type) { - this.key = key; - this.type = type; - this.creationTimestamp = System.currentTimeMillis(); - } - - public EvictionEvent(Object key, Type type, long creationTimestamp) { - this.key = key; - this.type = type; - this.creationTimestamp = creationTimestamp; - } - - public long getCreationTimestamp() { - return creationTimestamp; - } - - public void setCreationTimestamp(long creationTimestamp) { - this.creationTimestamp = creationTimestamp; - } - - public long getInUseTimeout() { - return inUseTimeout; - } - - public void setInUseTimeout(long inUseTimeout) { - this.inUseTimeout = inUseTimeout; - } - - public Object getKey() { - return key; - } - - public void setKey(Object key) { - this.key = key; - } - - public void setEventType(Type event) { - type = event; - } - - public Type getEventType() { - return type; - } - - @Override - public String toString() { - return "EvictedEventNode[key=" + key + " event=" + type + "]"; - } - - /** - * Copies this evicted event node to create a new one with the same values, except with a new Fqn root. - * - * @param key new Fqn root to use - * @return a new EvictedEventNode instance - */ - public EvictionEvent copy(Object key) { - return new EvictionEvent(key, type); - } -} Modified: core/branches/flat/src/main/java/org/horizon/eviction/EvictionManager.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/EvictionManager.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/EvictionManager.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,6 +1,7 @@ package org.horizon.eviction; import net.jcip.annotations.ThreadSafe; +import org.horizon.eviction.events.EvictionEvent; import org.horizon.factories.annotations.NonVolatile; import org.horizon.factories.scopes.Scope; import org.horizon.factories.scopes.Scopes; @@ -9,7 +10,23 @@ import java.util.concurrent.TimeUnit; /** - * Central component that deals with eviction of cache entries + * Central component that deals with eviction of cache entries. This component manages a queue of events taking place + * on the cache. This queue is typically populated by the {@link org.horizon.interceptors.EvictionInterceptor} calling + * {@link #registerEvictionEvent(Object, org.horizon.eviction.events.EvictionEvent.Type)}. + * <p/> + * In certain special cases, this component may be manipulated by direct interaction with end user code. An example of + * this is the use of the {@link #markKeyCurrentlyInUse(Object, long, java.util.concurrent.TimeUnit)} and {@link # + * markKeyCurrentlyInUse (Object, long, java.util.concurrent.TimeUnit)} methods, to prevent certain entries from being + * evicted even if their "time is up". + * <p/> + * Another case where direct interaction may take place is where no eviction thread is configured (e.g., with + * <tt>wakeUpInterval</tt> set to <tt>0</tt>, the same as {@link org.horizon.config.EvictionConfig#setWakeUpInterval(long)} + * being set to <tt>0</tt>). + * <p/> + * In such cases, user code may want to manually process the eviction queue, by calling {@link + * #processEvictionQueues()}. This is sometimes desirable, such as when user code already has a maintenance thread + * periodically running and does not want to incur the cost of an additional eviction thread. + * <p/> * * @author Mircea.Markus(a)jboss.com * @author Manik Surtani @@ -21,17 +38,17 @@ public interface EvictionManager extends Lifecycle { /** - * Processes the eviction event queue by passing it to the configured eviction algorithm + * Processes the eviction event queue. */ void processEvictionQueues(); /** - * Clears the eviction event queue used for processing eviction. + * Clears the eviction event queue. */ void resetEvictionQueues(); /** - * Registers an eviction event eviction event queue for later processing by {@link #processEvictionQueues()}. + * Registers an event on the eviction event queue for later processing by {@link #processEvictionQueues()}. * * @param key key of the cache entry to register an event for * @param eventType type of event @@ -41,19 +58,19 @@ /** * Marks a key as being currently in use, so that it is not considered for eviction even if the condifured algorithm - * selects it for eviction. + * selects it for eviction. It may be considered for eviction when the queue is next processed though. * * @param key entry key to mark * @param timeout duration for which the entry should be considered as in-use * @param unit time unit */ - void markNodeCurrentlyInUse(Object key, long timeout, TimeUnit unit); + void markKeyCurrentlyInUse(Object key, long timeout, TimeUnit unit); /** - * Un-marks a key as being currently in use, if it was marked using {@link #markNodeCurrentlyInUse(Object, long, - * java.util.concurrent.TimeUnit)} Unmarking makes the node vulnerable to eviction again. + * Un-marks a key as being currently in use, if it was marked using {@link #markKeyCurrentlyInUse(Object, long, + * java.util.concurrent.TimeUnit)} Unmarking makes the entry vulnerable to eviction again. * * @param key entry key to unmark */ - void unmarkNodeCurrentlyInUse(Object key); + void unmarkKeyCurrentlyInUse(Object key); } Modified: core/branches/flat/src/main/java/org/horizon/eviction/EvictionManagerImpl.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/EvictionManagerImpl.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/EvictionManagerImpl.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -5,6 +5,9 @@ import org.horizon.config.Configuration; import org.horizon.config.EvictionAlgorithmConfig; import org.horizon.config.EvictionConfig; +import org.horizon.container.DataContainer; +import org.horizon.eviction.events.EvictionEvent; +import org.horizon.eviction.events.InUseEvictionEvent; import org.horizon.factories.KnownComponentNames; import org.horizon.factories.annotations.ComponentName; import org.horizon.factories.annotations.Inject; @@ -35,20 +38,22 @@ ScheduledFuture evictionTask; // event queue - private BlockingQueue<EvictionEvent> evictionEventQueue; + BlockingQueue<EvictionEvent> evictionEventQueue; int capacityWarnThreshold = 0; // components to be injected ScheduledExecutorService executor; Configuration configuration; Cache cache; + private DataContainer<?, ?> dataContainer; @Inject public void initialize((a)ComponentName(KnownComponentNames.EVICTION_SCHEDULED_EXECUTOR) ScheduledExecutorService executor, - Configuration configuration, Cache cache) { + Configuration configuration, Cache cache, DataContainer dataContainer) { this.executor = executor; this.configuration = configuration; this.cache = cache; + this.dataContainer = dataContainer; } @Start @@ -68,24 +73,28 @@ // 2. now ensure we instantiate the eviction algorithm class evictionAlgorithmConfig = evictionConfig.getAlgorithmConfig(); evictionAlgorithm = createEvictionAlgorithm(evictionAlgorithmConfig, evictionConfig.getActionPolicyClass()); + evictionAlgorithm.start(); // 3. And finally set up the eviction timer task if (evictionConfig.getWakeUpInterval() <= 0) { log.info("wakeUpInterval is <= 0, not starting eviction thread"); } else { - evictionTask = executor.scheduleWithFixedDelay(new Runnable() { - public void run() { - processEvictionQueues(); - } - }, evictionConfig.getWakeUpInterval(), evictionConfig.getWakeUpInterval(), TimeUnit.MILLISECONDS); + evictionTask = executor.scheduleWithFixedDelay(new ScheduledTask(), evictionConfig.getWakeUpInterval(), + evictionConfig.getWakeUpInterval(), TimeUnit.MILLISECONDS); } } } + class ScheduledTask implements Runnable { + public void run() { + processEvictionQueues(); + } + } + @Stop public void stop() { if (evictionTask != null) evictionTask.cancel(true); - if (evictionAlgorithm != null) evictionAlgorithm.resetEvictionQueue(); + if (evictionAlgorithm != null) evictionAlgorithm.stop(); evictionAlgorithm = null; if (evictionEventQueue != null) evictionEventQueue.clear(); evictionEventQueue = null; @@ -106,11 +115,11 @@ return ee; } - public void markNodeCurrentlyInUse(Object key, long duration, TimeUnit unit) { - registerEvictionEvent(key, EvictionEvent.Type.MARK_IN_USE_EVENT).setInUseTimeout(unit.toMillis(duration)); + public void markKeyCurrentlyInUse(Object key, long duration, TimeUnit unit) { + registerEvictionEvent(new InUseEvictionEvent(key, unit.toMillis(duration))); } - public void unmarkNodeCurrentlyInUse(Object key) { + public void unmarkKeyCurrentlyInUse(Object key) { registerEvictionEvent(key, EvictionEvent.Type.UNMARK_IN_USE_EVENT); } @@ -145,7 +154,7 @@ if (trace) log.trace("Instantiating {0}", algoConfig.getEvictionAlgorithmClassName()); EvictionAlgorithm algorithm = (EvictionAlgorithm) Util.getInstance(algoConfig.getEvictionAlgorithmClassName()); algorithm.setEvictionAction(evictionAction); - algorithm.assignToCache(cache, algoConfig); + algorithm.init(cache, dataContainer, algoConfig); return algorithm; } catch (Exception e) { log.fatal("Unable to instantiate eviction algorithm {0}", e, algoConfig.getEvictionAlgorithmClassName()); Modified: core/branches/flat/src/main/java/org/horizon/eviction/EvictionQueue.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/EvictionQueue.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/EvictionQueue.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -22,15 +22,23 @@ package org.horizon.eviction; /** - * Eviction Queue interface defines a contract for the Eviction Queue implementations used by EvictionPolicies. + * The eviction queue interface defines a contract for the queue implementations used by {@link EvictionAlgorithm} + * implementations. Queues are meant to be sorted in order of preference of keys for eviction, such that by using the + * iterator exposed by the queue, the first element would be the most preferable to evict. * <p/> - * Note: None of the Eviction classes are thread safe. It is assumed that an individual instance of an EvictionPolicy/ - * EvictionAlgorithm/EvictionQueue/EvictionConfiguration are only operated on by one thread at any given time. + * The iterator provided should support {@link java.util.Iterator#remove()}. + * <p/> + * Note that there is no requirement that implementations should be thread safe, as the {@link + * org.horizon.eviction.EvictionManager} would guarantee that only a single thread ever acccess the eviction queue at + * any given time. + * <p/> + * Note that this is not to be confused with a JDK {@link java.util.Queue}, as it has no bearing or relationship to one, + * although implementations may choose to use a JDK {@link java.util.Queue} as an underlying data structure. * - * @author Daniel Huang (dhuang(a)jboss.org) + * @author Manik Surtani * @since 1.0 */ -public interface EvictionQueue extends Iterable<EntryEvictionData> { +public interface EvictionQueue extends Iterable<Object> { /** * Tests whether queue is empty @@ -39,16 +47,13 @@ */ boolean isEmpty(); - // /** - * Retrieve eviction entry data representing a specific key - * <p/> - * This will return null if the entry is not found. + * Informs the queue that an entry has been visited. Implementations may choose to ignore this invocation, or use it + * to update internal ordering based on the type of queue. * - * @param key key to find - * @return eviction entry data representing the specified key + * @param key key visited */ - EntryEvictionData get(Object key); + void visit(Object key); /** @@ -69,9 +74,9 @@ /** * Add entry eviction data to the queue * - * @param entryEvictionData to add. Must not be null. + * @param key key to add. Must not be null. */ - void add(EntryEvictionData entryEvictionData); + void add(Object key); /** * Get the size of the queue Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/BaseEvictionAlgorithm.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/BaseEvictionAlgorithm.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/BaseEvictionAlgorithm.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -23,28 +23,28 @@ import org.horizon.Cache; import org.horizon.config.EvictionAlgorithmConfig; -import org.horizon.eviction.EntryEvictionData; +import org.horizon.container.DataContainer; import org.horizon.eviction.EvictionAction; import org.horizon.eviction.EvictionAlgorithm; import org.horizon.eviction.EvictionAlgorithmConfigBase; -import org.horizon.eviction.EvictionEvent; -import org.horizon.eviction.EvictionEvent.Type; import org.horizon.eviction.EvictionException; import org.horizon.eviction.EvictionQueue; +import org.horizon.eviction.events.EvictionEvent; +import org.horizon.eviction.events.EvictionEvent.Type; +import org.horizon.eviction.events.InUseEvictionEvent; import org.horizon.logging.Log; import org.horizon.logging.LogFactory; +import java.util.HashMap; import java.util.Iterator; +import java.util.Map; import java.util.concurrent.BlockingQueue; import java.util.concurrent.LinkedBlockingQueue; import java.util.concurrent.TimeUnit; /** - * Abstract Event Processing Eviction Algorithm. This class is used to implement basic event processing for Eviction - * Algorithms. To extend this abstract class to make an Eviction Algorithm, implement the abstract methods and a - * policy. + * Abstract Eviction Algorithm. This class is used to implement basic event processing for eviction algorithms. * - * @author (various) * @author <a href="mailto:galder.zamarreno@jboss.com">Galder Zamarreno</a> * @author Manik Surtani * @since 1.0 @@ -53,58 +53,71 @@ private static final Log log = LogFactory.getLog(BaseEvictionAlgorithm.class); private static final boolean trace = log.isTraceEnabled(); - protected EvictionAction evictionAction; - protected EvictionAlgorithmConfigBase evictionAlgorithmConfig; - protected BlockingQueue recycleQueue; + protected EvictionAction action; + protected EvictionAlgorithmConfigBase config; + // blocking queue of cache keys + protected BlockingQueue<Object> recycleQueue; protected EvictionQueue evictionQueue; protected Cache cache; + protected DataContainer dataContainer; + // cache keys and expiry time + protected Map<Object, Long> keysInUse = new HashMap<Object, Long>(); /** - * This method will create an EvictionQueue implementation and prepare it for use. + * This method will create a new EvictionQueue instance and prepare it for use. * - * @return The created EvictionQueue to be used as the eviction queue for this algorithm. - * @see org.horizon.eviction.EvictionQueue + * @return A new EvictionQueue */ - protected abstract EvictionQueue setupEvictionQueue() throws EvictionException; + protected abstract EvictionQueue createEvictionQueue(); /** - * This method will check whether the given entry should be evicted or not. + * This method tests whether the next entry should be evicted due to cache size constraints being hit. * - * @param entry entry to consider - * @return true if the entry is to be evicted, false otherwise + * @return true if the entry should be evicted, false if no more evictions are needed. */ - protected boolean shouldEvictEntry(EntryEvictionData entry, int originalQueueSize) { - // first test max and min entries - if (evictionAlgorithmConfig.getMaxEntries() > -1) { - int currentSize = evictionQueue.size(); + protected boolean needToEvict(int originalQueueSize) { + // test max and min entries + if (config.getMaxEntries() > -1) { // entry count eviction is enabled! - if (evictionAlgorithmConfig.getMaxEntries() < currentSize) return true; - if (evictionAlgorithmConfig.getMaxEntries() < originalQueueSize && - evictionAlgorithmConfig.getMinEntries() > -1 && - evictionAlgorithmConfig.getMinEntries() < currentSize) + int currentSize = evictionQueue.size(); + + // exceeded max entries! + if (config.getMaxEntries() < currentSize) return true; + + // below max entries now, but the current run exceeded, and we need to get down to minEntries (if configured) + if (config.getMaxEntries() < originalQueueSize && + config.getMinEntries() > -1 && + config.getMinEntries() < currentSize) return true; } - + // configured to hold unlimited entries, or we haven't hit any thresholds yet return false; } protected BaseEvictionAlgorithm() { - recycleQueue = new LinkedBlockingQueue(500000); + // size of the recycle queue + // TODO make this configurable!! + recycleQueue = new LinkedBlockingQueue<Object>(500000); } - public synchronized void initialize() { - if (evictionQueue == null) { - evictionQueue = setupEvictionQueue(); - } + public synchronized void start() { + if (evictionQueue == null) evictionQueue = createEvictionQueue(); } + public synchronized void stop() { + if (evictionQueue != null) evictionQueue.clear(); + keysInUse.clear(); + recycleQueue.clear(); + } + public void setEvictionAction(EvictionAction evictionAction) { - this.evictionAction = evictionAction; + this.action = evictionAction; } - public void assignToCache(Cache<?, ?> cache, EvictionAlgorithmConfig evictionAlgorithmConfig) { + public void init(Cache<?, ?> cache, DataContainer<?, ?> dataContainer, EvictionAlgorithmConfig evictionAlgorithmConfig) { this.cache = cache; - this.evictionAlgorithmConfig = (EvictionAlgorithmConfigBase) evictionAlgorithmConfig; + this.dataContainer = dataContainer; + this.config = (EvictionAlgorithmConfigBase) evictionAlgorithmConfig; } public boolean canIgnoreEvent(Type eventType) { @@ -112,24 +125,20 @@ } /** - * Process the given eviction event queue. Eviction Processing encompasses the following: - * <p/> - * - Add/Remove/Visit Nodes - Prune according to Eviction Algorithm - Empty/Retry the recycle queue of previously - * evicted but locked (during actual cache eviction) nodes. + * Process the given eviction event queue. Eviction Pprocessing encompasses the following: * * @param eventQueue queue containing eviction events * @throws EvictionException */ public void process(BlockingQueue<EvictionEvent> eventQueue) throws EvictionException { if (trace) log.trace("processing eviction event queue"); - initialize(); processQueues(eventQueue); emptyRecycleQueue(); prune(); } public void resetEvictionQueue() { - // a no-op + if (evictionQueue != null) evictionQueue.clear(); } /** @@ -139,10 +148,10 @@ * @see EvictionQueue */ public EvictionQueue getEvictionQueue() { - return this.evictionQueue; + return evictionQueue; } - protected EvictionEvent getNextInQueue(BlockingQueue<EvictionEvent> queue) { + protected EvictionEvent nextEvent(BlockingQueue<EvictionEvent> queue) { try { return queue.poll(0, TimeUnit.SECONDS); } @@ -153,11 +162,7 @@ } /** - * Event processing for Evict/Add/Visiting of nodes. - * <p/> - * - On AddEvents a new element is added into the eviction queue - On RemoveEvents, the removed element is removed - * from the eviction queue. - On VisitEvents, the visited node has its eviction statistics updated (idleTime, - * numberOfVisists, etc..) + * Process the event queue * * @param queue queue to inspect * @throws EvictionException in the event of problems @@ -165,139 +170,88 @@ protected void processQueues(BlockingQueue<EvictionEvent> queue) throws EvictionException { EvictionEvent event; int count = 0; - while ((event = getNextInQueue(queue)) != null) { - count++; + long startTime = System.currentTimeMillis(); + + while ((event = nextEvent(queue)) != null) { + if (trace) count++; switch (event.getEventType()) { case ADD_ENTRY_EVENT: - processAddedEntries(event); + processAddedEntries(event.getKey()); break; case REMOVE_ENTRY_EVENT: - processRemovedEntries(event); + processRemovedEntries(event.getKey()); break; case VISIT_ENTRY_EVENT: - processVisitedEntries(event); + processVisitedEntries(event.getKey()); break; case CLEAR_CACHE_EVENT: processClearCacheEvent(); break; case MARK_IN_USE_EVENT: - processMarkInUseNodes(event.getKey(), event.getInUseTimeout()); + processMarkInUseNodes(event.getKey(), ((InUseEvictionEvent) event).getInUseTimeout()); break; case UNMARK_IN_USE_EVENT: processUnmarkInUseNodes(event.getKey()); break; default: - throw new RuntimeException("Illegal Eviction Event type " + event.getEventType()); + throw new EvictionException("Illegal eviction event type " + event.getEventType()); } } - log.trace("processed {0} eviction events", count); + if (trace) + log.trace("processed {0} eviction events in {1} millis", count, System.currentTimeMillis() - startTime); } - protected boolean evict(EntryEvictionData data) { - if (data != null) { - log.trace("Attempting to evict {0}", data); - if (!evictionAction.evict(data.getKey())) { - try { - boolean result = recycleQueue.offer(data.getKey(), 5, TimeUnit.SECONDS); - if (!result) { - log.warn("Unable to add key {0} to the recycle queue." + - "This is often sign that " + - "evictions are not occurring and nodes that should be " + - "evicted are piling up waiting to be evicted.", data.getKey()); - } + protected void evictOrRecycle(Object key) { + log.trace("Attempting to evict {0}", key); + if (!action.evict(key)) { + try { + boolean result = recycleQueue.offer(key, 5, TimeUnit.SECONDS); + if (!result) { + log.warn("Unable to add key {0} to the recycle queue." + + "This is often sign that " + + "evictions are not occurring and nodes that should be " + + "evicted are piling up waiting to be evicted.", key); } - catch (InterruptedException e) { - log.debug("InterruptedException", e); - } } - return true; - } else { - return false; + catch (InterruptedException e) { + log.debug("InterruptedException", e); + } } } protected void processMarkInUseNodes(Object key, long inUseTimeout) throws EvictionException { log.trace("Marking {0} as in use with a usage timeout of {1}", key, inUseTimeout); - - EntryEvictionData ne = evictionQueue.get(key); - if (ne != null) { - ne.setCurrentlyInUse(true, inUseTimeout); - } + keysInUse.put(key, inUseTimeout + System.currentTimeMillis()); } protected void processUnmarkInUseNodes(Object key) throws EvictionException { log.trace("Unmarking node {0} as in use", key); - - EntryEvictionData ne = evictionQueue.get(key); - if (ne != null) { - ne.setCurrentlyInUse(false, 0); - } + keysInUse.remove(key); } - protected void processAddedEntries(EvictionEvent evictedEventNode) throws EvictionException { - Object key = evictedEventNode.getKey(); + protected void processAddedEntries(Object key) throws EvictionException { log.trace("Adding entry {0} to eviction queue", key); - EntryEvictionData data = evictionQueue.get(key); - if (data != null) { - data.setModifiedTimeStamp(evictedEventNode.getCreationTimestamp()); - data.incrementNumberOfVisits(); - log.trace("Queue already contains key. Processing it as visited."); - processVisitedEntries(evictedEventNode); + if (evictionQueue.contains(key)) { + evictionQueue.visit(key); + log.trace("Key already exists so treating as a visit"); } else { - data = new EntryEvictionData(1, evictedEventNode.getCreationTimestamp(), key); - data.setCreationTimeStamp(evictedEventNode.getCreationTimestamp()); - evictionQueue.add(data); - log.trace("Added successfully to eviction queue"); + evictionQueue.add(key); } } - protected void processRemovedEntries(EvictionEvent evictedEventNode) throws EvictionException { - Object key = evictedEventNode.getKey(); - + protected void processRemovedEntries(Object key) throws EvictionException { log.trace("Removing key {0} from eviction queue and attempting eviction", key); - - EntryEvictionData data = evictionQueue.get(key); - if (data != null) { - evictionQueue.remove(key); - } else { - log.trace("Can't find entry eviction data associated with key {0}. Could have been evicted earlier.", key); - return; - } - - log.trace("Removed from eviction queue"); + evictionQueue.remove(key); } protected void processClearCacheEvent() throws EvictionException { log.trace("Clearing eviction queue"); evictionQueue.clear(); - log.trace("Cleared eviction queue"); } - - /** - * Visit a node in cache. - * <p/> - * This method will update the numVisits and modifiedTimestamp properties. These properties are used as statistics to - * determine eviction (LRU, LFU, MRU, etc..) - * <p/> - * *Note* that this method updates entries by reference and does not put them back into the queue. For some sorted - * collections, a remove, and a re-add is required to maintain the sorted order of the elements. - * - * @throws EvictionException - */ - protected void processVisitedEntries(EvictionEvent evictionEvent) throws EvictionException { - Object key = evictionEvent.getKey(); - EntryEvictionData data = evictionQueue.get(key); - if (data == null) { - if (trace) log.trace("Visiting entry {0} that has not added to eviction queues before.", key); - this.processAddedEntries(evictionEvent); - return; - } - // note this method will visit and modify the node statistics by reference! - // if a collection is only guaranteed sort order by adding to the collection, - // this implementation will not guarantee sort order. - data.incrementNumberOfVisits(); - data.setModifiedTimeStamp(evictionEvent.getCreationTimestamp()); + protected void processVisitedEntries(Object key) throws EvictionException { + log.trace("Visiting entry {0}", key); + evictionQueue.visit(key); } /** @@ -326,7 +280,7 @@ if (trace) log.trace("emptying recycle bin. Evict key " + key); // Still doesn't work - if (!evictionAction.evict(key)) { + if (!action.evict(key)) { try { recycleQueue.put(key); } @@ -340,10 +294,13 @@ protected void prune() throws EvictionException { int originalQueueSize = evictionQueue.size(); - for (Iterator<EntryEvictionData> it = evictionQueue.iterator(); it.hasNext();) { - EntryEvictionData data = it.next(); - if (data != null && shouldEvictEntry(data, originalQueueSize)) { - if (shouldNotOverrideEviction(data) && evict(data)) it.remove(); + for (Iterator<Object> it = evictionQueue.iterator(); it.hasNext();) { + Object key = it.next(); + if (key != null && needToEvict(originalQueueSize)) { + if (shouldNotOverrideEviction(key) && isNotMarkedInUse(key)) { + evictOrRecycle(key); + it.remove(); + } } else { break; // assume the rest won't need to be evicted either } @@ -361,11 +318,17 @@ /** * A helper for implementations that support the minimum time to live property * - * @param data eviction data on the entry to consider + * @param key key to consider * @return true if the entry is younger than the minimum time to live, false otherwise. */ - protected boolean shouldNotOverrideEviction(EntryEvictionData data) { - long minTTL = evictionAlgorithmConfig.getMinTimeToLive(); - return minTTL < 1 || (data.getModifiedTimeStamp() + minTTL < System.currentTimeMillis()); + private boolean shouldNotOverrideEviction(Object key) { + long minTTL = config.getMinTimeToLive(); + long lastModified = dataContainer.getModifiedTimestamp(key); + return minTTL < 1 || lastModified < 0 || (lastModified + minTTL < System.currentTimeMillis()); } + + private boolean isNotMarkedInUse(Object key) { + Long expiryTime = keysInUse.get(key); + return expiryTime == null || (expiryTime < System.currentTimeMillis() && keysInUse.remove(key) != null); + } } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/BaseEvictionQueue.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/BaseEvictionQueue.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/BaseEvictionQueue.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -3,7 +3,12 @@ import org.horizon.eviction.EvictionQueue; public abstract class BaseEvictionQueue implements EvictionQueue { + public boolean isEmpty() { return size() == 0; } + + public void visit(Object key) { + // default impl to ignore this + } } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/fifo/FIFOAlgorithm.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/fifo/FIFOAlgorithm.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/fifo/FIFOAlgorithm.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -26,8 +26,6 @@ import org.horizon.eviction.EvictionException; import org.horizon.eviction.EvictionQueue; import org.horizon.eviction.algorithms.BaseEvictionAlgorithm; -import org.horizon.logging.Log; -import org.horizon.logging.LogFactory; /** * First-in-first-out algorithm used to evict cache entries @@ -37,10 +35,7 @@ */ @NotThreadSafe public class FIFOAlgorithm extends BaseEvictionAlgorithm { - private static final Log log = LogFactory.getLog(FIFOAlgorithm.class); - - @Override - protected EvictionQueue setupEvictionQueue() throws EvictionException { + protected EvictionQueue createEvictionQueue() throws EvictionException { return new FIFOQueue(); } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/fifo/FIFOQueue.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/fifo/FIFOQueue.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/fifo/FIFOQueue.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -21,53 +21,49 @@ */ package org.horizon.eviction.algorithms.fifo; -import org.horizon.eviction.EntryEvictionData; import org.horizon.eviction.algorithms.BaseEvictionQueue; import java.util.Iterator; -import java.util.LinkedHashMap; -import java.util.Map; +import java.util.LinkedHashSet; /** - * FIFO Eviction Queue implementation for FIFO Policy. + * First in, first out eviction queue implementation for the {@link FIFOAlgorithm}. Guarantees O(1) for put, remove, + * and the iterator. Ignores {@link org.horizon.eviction.EvictionQueue#visit(Object)} as it doesn't order on visitor + * count. * - * @author Daniel Huang (dhuang(a)jboss.org) + * @author Manik Surtani * @since 1.0 */ public class FIFOQueue extends BaseEvictionQueue { - private Map<Object, EntryEvictionData> keyMap; + private LinkedHashSet<Object> orderedKeys; protected FIFOQueue() { - keyMap = new LinkedHashMap<Object, EntryEvictionData>(); - // We use a LinkedHashMap here because we want to maintain FIFO ordering and still get the benefits of - // O(n) = 1 for add/remove/search. + orderedKeys = new LinkedHashSet<Object>(); + // We use a LinkedHashSet here because we want to maintain FIFO ordering and still get the benefits of + // O(1) for put/remove/iterate } - public EntryEvictionData get(Object key) { - return keyMap.get(key); - } - public boolean contains(Object key) { - return keyMap.containsKey(key); + return orderedKeys.contains(key); } public void remove(Object key) { - keyMap.remove(key); + orderedKeys.remove(key); } - public void add(EntryEvictionData entryEvictionData) { - if (!keyMap.containsKey(entryEvictionData.getKey())) keyMap.put(entryEvictionData.getKey(), entryEvictionData); + public void add(Object key) { + if (!orderedKeys.contains(key)) orderedKeys.add(key); } public int size() { - return keyMap.size(); + return orderedKeys.size(); } public void clear() { - keyMap.clear(); + orderedKeys.clear(); } - public Iterator<EntryEvictionData> iterator() { - return keyMap.values().iterator(); + public Iterator<Object> iterator() { + return orderedKeys.iterator(); } } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUAlgorithm.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUAlgorithm.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUAlgorithm.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -23,98 +23,23 @@ import net.jcip.annotations.NotThreadSafe; import org.horizon.config.EvictionAlgorithmConfig; -import org.horizon.eviction.EvictionEvent; import org.horizon.eviction.EvictionException; import org.horizon.eviction.EvictionQueue; import org.horizon.eviction.algorithms.BaseEvictionAlgorithm; -import org.horizon.logging.Log; -import org.horizon.logging.LogFactory; -import java.util.concurrent.BlockingQueue; - /** - * Least Frequently Used algorithm for cache eviction. Note that this algorithm is not thread-safe. - * <p/> - * This algorithm relies on maxNodes and minNodes to operate correctly. Eviction takes place using Least Frequently Used - * algorithm. A node A that is used less than a node B is evicted sooner. - * <p/> - * The minNodes property defines a threshold for eviction. If minNodes = 100, the LFUAlgorithm will not evict the cache - * to anything less than 100 elements still left in cache. The maxNodes property defines the maximum number of nodes the - * cache will accept before eviction. maxNodes = 0 means that this region is unbounded. minNodes = 0 means that the - * eviction queue will attempt to bring the cache of this region to 0 elements (evict all elements) whenever it is run. - * <p/> - * This algorithm uses a sorted eviction queue. The eviction queue is sorted in ascending order based on the number of - * times a node is visited. The more frequently a node is visited, the less likely it will be evicted. + * Least Frequently Used algorithm for cache eviction. * * @author Manik Surtani * @since 1.0 */ @NotThreadSafe public class LFUAlgorithm extends BaseEvictionAlgorithm { - private static final Log log = LogFactory.getLog(LFUAlgorithm.class); - private static final boolean trace = log.isTraceEnabled(); - boolean evictionQueueRequiresSort = false; - - /** - * Will create a LFUQueue to be used as the underlying eviction queue. - * - * @return The created LFUQueue. - * @throws org.horizon.eviction.EvictionException - * - */ - @Override - protected EvictionQueue setupEvictionQueue() throws EvictionException { + protected EvictionQueue createEvictionQueue() throws EvictionException { return new LFUQueue(); } - @Override - protected void prune() throws EvictionException { - super.prune(); - - // clean up the Queue's eviction removals - ((LFUQueue) this.evictionQueue).doBatchRemove(); - } - public Class<? extends EvictionAlgorithmConfig> getConfigurationClass() { return LFUAlgorithmConfig.class; } - - @Override - protected void processQueues(BlockingQueue<EvictionEvent> queue) throws EvictionException { - evictionQueueRequiresSort = false; - try { - super.processQueues(queue); - if (evictionQueueRequiresSort) { - if (trace) log.trace("Eviction queue requires re-sort. Re-sorting."); - resortEvictionQueue(); - } - } finally { - evictionQueueRequiresSort = false; - } - } - - @Override - protected void processAddedEntries(EvictionEvent event) { - evictionQueueRequiresSort = true; - super.processAddedEntries(event); - } - - @Override - protected void processVisitedEntries(EvictionEvent event) { - evictionQueueRequiresSort = true; - super.processVisitedEntries(event); - } - - /** - * This method is called to resort the queue after add or visit events have occurred. - */ - protected void resortEvictionQueue() { - long begin = System.currentTimeMillis(); - ((LFUQueue) evictionQueue).reSortEvictionQueue(); - - if (trace) { - log.trace("Took {0} millis to re-sort queue with {1} elements", - System.currentTimeMillis() - begin, getEvictionQueue().size()); - } - } } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUQueue.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUQueue.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUQueue.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -21,41 +21,38 @@ */ package org.horizon.eviction.algorithms.lfu; -import org.horizon.eviction.EntryEvictionData; +import org.horizon.CacheException; import org.horizon.eviction.algorithms.BaseEvictionQueue; -import java.util.Collections; -import java.util.Comparator; import java.util.HashMap; -import java.util.HashSet; import java.util.Iterator; -import java.util.LinkedList; -import java.util.Map; -import java.util.Set; +import java.util.PriorityQueue; /** - * LFUQueue EvictionQueue implementation for LFU Policy. + * Least frequently used queue for use with the {@link org.horizon.eviction.algorithms.lfu.LFUAlgorithm}. This + * implementation guarantees O(ln n) for put and remove operations, and 2O(ln n) for visits since this requires a + * re-sort. * <p/> - * The queue is sorted in least frequently used order. + * // TODO investigate using a Fibonacci Heap or a Brodal Queue (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8133) + * instead of a TreeMap to implement // Since this will give us O(1) for insert, iteration and O(ln n) for remove and + * visit * - * @author Daniel Huang (dhuang(a)jboss.org) + * @author Manik Surtani * @since 1.0 */ public class LFUQueue extends BaseEvictionQueue { - Map<Object, EntryEvictionData> keyMap; - LinkedList<EntryEvictionData> evictionList; - Set<EntryEvictionData> removalQueue; - private Comparator<EntryEvictionData> comparator; + PriorityQueue<VisitableKey> keys = new PriorityQueue<VisitableKey>(); + HashMap<Object, VisitableKey> keyMap = new HashMap<Object, VisitableKey>(); - protected LFUQueue() { - keyMap = new HashMap<Object, EntryEvictionData>(); - comparator = new LFUComparator(); - evictionList = new LinkedList<EntryEvictionData>(); - removalQueue = new HashSet<EntryEvictionData>(); - } + public void visit(Object key) { + VisitableKey vk = keyMap.get(key); + if (vk != null) { - public EntryEvictionData get(Object key) { - return keyMap.get(key); + // need to remove and add to reorder the tree + keys.remove(vk); + vk.visits++; + keys.add(vk); + } } public boolean contains(Object key) { @@ -63,22 +60,18 @@ } public void remove(Object key) { - EntryEvictionData data = keyMap.remove(key); - if (data != null) { - // don't remove directly from the LinkedList otherwise we will incur a O(n) = n - // performance penalty for every removal! In the prune method for LFU, we will iterate the LinkedList through ONCE - // doing a single O(n) = n operation and removal. This is much preferred over running O(n) = n every single time - // remove is called. There is also special logic in the getFirstNodeEntry that will know to check - // the removalQueue before returning. - this.removalQueue.add(data); + VisitableKey vk = keyMap.remove(key); + if (vk != null) { + if (!keys.remove(vk)) throw new CacheException("Problem removing key " + key); } } - public void add(EntryEvictionData entryEvictionData) { - if (!keyMap.containsKey(entryEvictionData)) { - Object key = entryEvictionData.getKey(); - keyMap.put(key, entryEvictionData); - evictionList.add(entryEvictionData); + public void add(Object key) { + if (!keyMap.containsKey(key)) { + VisitableKey vk = new VisitableKey(); + vk.key = key; + keyMap.put(key, vk); + keys.add(vk); } } @@ -86,76 +79,78 @@ return keyMap.size(); } + @Override + public boolean isEmpty() { + return keyMap.size() == 0 && keys.size() == 0; + } + public void clear() { keyMap.clear(); - evictionList.clear(); - removalQueue.clear(); + keys.clear(); } - public void reSortEvictionQueue() { - Collections.sort(evictionList, comparator); - } + public Iterator<Object> iterator() { + return new Iterator<Object>() { - /** - * Anything removed using {@link #remove(Object)} or removing using the iterator does not actually get removed until - * this method is called. - */ - public void doBatchRemove() { - Iterator<EntryEvictionData> it = evictionList.iterator(); - while (it.hasNext() && removalQueue.size() > 0) { - if (removalQueue.remove(it.next())) it.remove(); - } - } + Iterator<VisitableKey> vkIter = keys.iterator(); + Object lastKey; - public Iterator<EntryEvictionData> iterator() { - //return evictionList.iterator(); - return new Iterator<EntryEvictionData>() { - Iterator<EntryEvictionData> delegate = evictionList.iterator(); - EntryEvictionData current; - public boolean hasNext() { - return delegate.hasNext(); + return vkIter.hasNext(); } - public EntryEvictionData next() { - current = delegate.next(); - return current; + public Object next() { + lastKey = vkIter.next().key; + return lastKey; } public void remove() { - if (current != null) LFUQueue.this.remove(current.getKey()); + if (lastKey == null) throw new IllegalStateException("Call next() before remove()!"); + vkIter.remove(); + keyMap.remove(lastKey); } }; } - /** - * Comparator class for LFU. - * <p/> - * This class will sort the eviction queue in the correct eviction order. The top of the list should evict before the - * bottom of the list. - * <p/> - * The sort is based on ascending order of visits. - * <p/> - * This class has a natural ordering that is inconsistent with equals as defined by the java.lang.Comparator - * contract. - */ - protected static class LFUComparator implements Comparator<EntryEvictionData> { + class VisitableKey implements Comparable { + Object key; + int visits; - public int compare(EntryEvictionData data1, EntryEvictionData data2) { - if (data1.equals(data2)) return 0; - - int neNodeHits = data1.getNumberOfVisits(); - int ne2NodeHits = data2.getNumberOfVisits(); - - if (neNodeHits > ne2NodeHits) { - return 1; - } else if (neNodeHits < ne2NodeHits) { + public int compareTo(Object o) { + if (o == null) return -1; + if (o instanceof VisitableKey) { + VisitableKey other = (VisitableKey) o; + return other.visits - visits; + } else { return -1; - } else if (neNodeHits == ne2NodeHits) { - return 0; } - throw new RuntimeException("Should never reach this condition"); } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + VisitableKey that = (VisitableKey) o; + + if (key != null ? !key.equals(that.key) : that.key != null) return false; + + return true; + } + + @Override + public int hashCode() { + return key != null ? key.hashCode() : 0; + } + + @Override + public String toString() { + return "VisitableKey{" + + "key=" + key + + ", visits=" + visits + + '}'; + } } + } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUAlgorithm.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUAlgorithm.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUAlgorithm.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -23,84 +23,22 @@ import net.jcip.annotations.NotThreadSafe; import org.horizon.config.EvictionAlgorithmConfig; -import org.horizon.eviction.EntryEvictionData; import org.horizon.eviction.EvictionException; import org.horizon.eviction.EvictionQueue; import org.horizon.eviction.algorithms.BaseEvictionAlgorithm; -import org.horizon.logging.Log; -import org.horizon.logging.LogFactory; -import java.util.Iterator; - /** - * Least recently Used algorithm to evict cache entries + * Least recently used algorithm to evict cache entries * * @author Manik Surtani * @since 1.0 */ @NotThreadSafe public class LRUAlgorithm extends BaseEvictionAlgorithm { - private static final Log log = LogFactory.getLog(LRUAlgorithm.class); - private static final boolean trace = log.isTraceEnabled(); - - @Override - protected EvictionQueue setupEvictionQueue() throws EvictionException { + protected EvictionQueue createEvictionQueue() throws EvictionException { return new LRUQueue(); } - @Override - protected void prune() throws EvictionException { - LRUQueue lruQueue = (LRUQueue) evictionQueue; - int origSize = evictionQueue.size(); - - EntryEvictionData data; - Iterator<EntryEvictionData> it = lruQueue.iterateLRUQueue(); - while (it.hasNext()) { - data = it.next(); - if (data.isNodeInUseAndNotTimedOut()) continue; - if (shouldEvictEntry(data, origSize) && shouldNotOverrideEviction(data)) { - it.remove(); - lruQueue.removeNodeEntryFromMaxAge(data); - this.evict(data); - } else { - break; - } - } - - it = lruQueue.iterateMaxAgeQueue(); - while (it.hasNext()) { - data = it.next(); - if (data.isNodeInUseAndNotTimedOut()) continue; - if (shouldEvictEntry(data, origSize) && shouldNotOverrideEviction(data)) { - it.remove(); - lruQueue.removeNodeEntryFromLRU(data); - this.evict(data); - } else { - break; - } - } - - int maxNodes = evictionAlgorithmConfig.getMaxEntries(); - if (maxNodes <= 0) { - return; - } - - it = lruQueue.iterateLRUQueue(); - while (evictionQueue.size() > maxNodes && it.hasNext()) { - data = it.next(); - if (trace) { - log.trace("Node " + data.getKey() + " will be evicted because of exceeding the maxNode limit." + - " maxNode: " + maxNodes + " but current queue size is: " + evictionQueue.size()); - } - - if (!data.isNodeInUseAndNotTimedOut() && shouldNotOverrideEviction(data)) { - it.remove(); - lruQueue.removeNodeEntryFromMaxAge(data); - this.evict(data); - } - } - } - public Class<? extends EvictionAlgorithmConfig> getConfigurationClass() { return LRUAlgorithmConfig.class; } 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-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lru/LRUQueue.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -21,110 +21,56 @@ */ package org.horizon.eviction.algorithms.lru; -import org.horizon.eviction.EntryEvictionData; import org.horizon.eviction.algorithms.BaseEvictionQueue; +import org.horizon.util.VisitableLinkedHashSet; import java.util.Iterator; -import java.util.LinkedHashMap; -import java.util.Map; /** - * LRU Eviction Queue implementation. - * <p/> - * This eviction queue will iterate properly through two sorted lists. One sorted by maxAge and the other sorted by - * idleTime. + * Least Recently Used eviction queue implementation for the {@link LRUAlgorithm}. Guarantees O(1) for put, remove, and + * the iterator. * - * @author Daniel Huang (dhuang(a)jboss.org) + * @author Manik Surtani * @since 1.0 */ public class LRUQueue extends BaseEvictionQueue { - Map<Object, EntryEvictionData> maxAgeQueue; - Map<Object, EntryEvictionData> lruQueue; - protected LRUQueue() { - maxAgeQueue = new LinkedHashMap<Object, EntryEvictionData>(); - lruQueue = new LinkedHashMap<Object, EntryEvictionData>(16, 0.75f, true); - } + protected VisitableLinkedHashSet<Object> keys = new VisitableLinkedHashSet<Object>(); - public EntryEvictionData get(Object key) { - return lruQueue.get(key); + @Override + public void visit(Object key) { + keys.visit(key); } public boolean contains(Object key) { - return maxAgeQueue.containsKey(key); + return keys.contains(key); } public void remove(Object key) { - if (contains(key)) { - EntryEvictionData data1 = lruQueue.remove(key); - EntryEvictionData data2 = maxAgeQueue.remove(key); - if (data1 == null || data2 == null) { - throw new RuntimeException("The queues are out of sync."); - } - } + keys.remove(key); } - public void add(EntryEvictionData entryEvictionData) { - if (!contains(entryEvictionData)) { - Object key = entryEvictionData.getKey(); - maxAgeQueue.put(key, entryEvictionData); - lruQueue.put(key, entryEvictionData); - } + public void add(Object key) { + if (keys.contains(key)) + keys.visit(key); + else + keys.add(key); } public int size() { - return maxAgeQueue.size(); + return keys.size(); } public void clear() { - maxAgeQueue.clear(); - lruQueue.clear(); + keys.clear(); } - public Iterator<EntryEvictionData> iterator() { - return new LRUQueueIterator(lruQueue, maxAgeQueue); + public Iterator<Object> iterator() { + return keys.iterator(); } - public Iterator<EntryEvictionData> iterateLRUQueue() { - return new LRUQueueIterator(lruQueue, maxAgeQueue); + @Override + public String toString() { + return keys.toString(); } - - public void removeNodeEntryFromMaxAge(EntryEvictionData data) { - maxAgeQueue.remove(data.getKey()); - } - - public Iterator<EntryEvictionData> iterateMaxAgeQueue() { - return new LRUQueueIterator(maxAgeQueue, lruQueue); - } - - public void removeNodeEntryFromLRU(EntryEvictionData data) { - lruQueue.remove(data.getKey()); - } - - private class LRUQueueIterator implements Iterator<EntryEvictionData> { - Iterator<EntryEvictionData> delegate; - Map<Object, EntryEvictionData> secondaryStructure; - EntryEvictionData current; - - private LRUQueueIterator(Map<Object, EntryEvictionData> primaryStructure, Map<Object, EntryEvictionData> secondaryStructure) { - delegate = primaryStructure.values().iterator(); - this.secondaryStructure = secondaryStructure; - } - - public boolean hasNext() { - return delegate.hasNext(); - } - - public EntryEvictionData next() { - current = delegate.next(); - return current; - } - - public void remove() { - delegate.remove(); - if (current != null) { - maxAgeQueue.remove(current.getKey()); - } - } - } } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/mru/MRUAlgorithm.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/mru/MRUAlgorithm.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/mru/MRUAlgorithm.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -23,32 +23,22 @@ import net.jcip.annotations.NotThreadSafe; import org.horizon.config.EvictionAlgorithmConfig; -import org.horizon.eviction.EvictionEvent; import org.horizon.eviction.EvictionException; import org.horizon.eviction.EvictionQueue; import org.horizon.eviction.algorithms.BaseEvictionAlgorithm; /** - * Most Recently Used Algorithm. - * <p/> - * This algorithm will evict the most recently used cache entries from cache. + * Most recently used algorithm. This algorithm will evict the most recently used cache entries from cache. * * @author Manik Surtani * @since 1.0 */ @NotThreadSafe public class MRUAlgorithm extends BaseEvictionAlgorithm { - @Override - protected EvictionQueue setupEvictionQueue() throws EvictionException { + protected EvictionQueue createEvictionQueue() throws EvictionException { return new MRUQueue(); } - @Override - protected void processVisitedEntries(EvictionEvent evictedEventNode) throws EvictionException { - super.processVisitedEntries(evictedEventNode); - ((MRUQueue) evictionQueue).moveToTopOfStack(evictedEventNode.getKey()); - } - public Class<? extends EvictionAlgorithmConfig> getConfigurationClass() { return MRUAlgorithmConfig.class; } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/mru/MRUQueue.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/mru/MRUQueue.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/mru/MRUQueue.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -21,107 +21,21 @@ */ package org.horizon.eviction.algorithms.mru; -import org.horizon.eviction.EntryEvictionData; -import org.horizon.eviction.algorithms.BaseEvictionQueue; +import org.horizon.eviction.algorithms.lru.LRUQueue; -import java.util.HashMap; import java.util.Iterator; -import java.util.LinkedList; -import java.util.Map; /** - * MRU Eviction Queue implementation. - * <p/> - * This nodeMap is sorted by MRU. The first entry in the nodeMap will also be the most recently used entry. The sort is - * implicit based on a Stack that we can implicitly sort to the top by moving a node that is used to the top of the - * eviction stack. + * Most Recently Used eviction queue implementation for the {@link MRUAlgorithm}. Guarantees O(1) for put, remove, and + * the iterator. * - * @author Daniel Huang (dhuang(a)jboss.org) + * @author Manik Surtani * @since 1.0 */ -public class MRUQueue extends BaseEvictionQueue { - // we use our own Stack/Linked List implementation here because it guarantees O(n) = 1 for add, remove, get and - // we can sort it in order of MRU implicitly while still getting O(n) = 1 access time - // throughout. - Map<Object, EntryEvictionData> keyMap; - LinkedList<EntryEvictionData> list; +public class MRUQueue extends LRUQueue { - protected MRUQueue() { - keyMap = new HashMap<Object, EntryEvictionData>(); - list = new LinkedList<EntryEvictionData>(); - } - - /** - * This call moves an entry to the top of the stack. - * <p/> - * When an entry is visited this method should be called to guarantee MRU ordering. - * - * @param key entry key to move to the top of the stack. - */ - protected void moveToTopOfStack(Object key) { - EntryEvictionData data = keyMap.get(key); - if (data != null) { - list.remove(data); - list.addFirst(data); - } - } - - public EntryEvictionData get(Object key) { - return keyMap.get(key); - } - - public boolean contains(Object key) { - return keyMap.containsKey(key); - } - - public void remove(Object key) { - EntryEvictionData data = keyMap.remove(key); - if (data != null) list.remove(data); - } - - public void add(EntryEvictionData entryEvictionData) { - if (!keyMap.containsKey(entryEvictionData.getKey())) { - list.addLast(entryEvictionData); - keyMap.put(entryEvictionData.getKey(), entryEvictionData); - } - } - - public int size() { - return list.size(); - } - - public void clear() { - keyMap.clear(); - list.clear(); - } - - public Iterator<EntryEvictionData> iterator() { - return new Iterator<EntryEvictionData>() { - Iterator<EntryEvictionData> delegate = list.iterator(); - EntryEvictionData current; - - public boolean hasNext() { - return delegate.hasNext(); - } - - public EntryEvictionData next() { - current = delegate.next(); - return current; - } - - public void remove() { - // this will remove it from the list - delegate.remove(); - // now to take care of the key map - if (current != null) { - keyMap.remove(current.getKey()); - } - } - }; - } - @Override - public String toString() { - return list.toString(); + public Iterator<Object> iterator() { + return keys.reverseIterator(); } } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/nullalgo/NullEvictionAlgorithm.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/nullalgo/NullEvictionAlgorithm.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/nullalgo/NullEvictionAlgorithm.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -23,12 +23,13 @@ import org.horizon.Cache; import org.horizon.config.EvictionAlgorithmConfig; +import org.horizon.container.DataContainer; import org.horizon.eviction.EvictionAction; import org.horizon.eviction.EvictionAlgorithm; -import org.horizon.eviction.EvictionEvent; -import org.horizon.eviction.EvictionEvent.Type; import org.horizon.eviction.EvictionException; import org.horizon.eviction.EvictionQueue; +import org.horizon.eviction.events.EvictionEvent; +import org.horizon.eviction.events.EvictionEvent.Type; import java.util.concurrent.BlockingQueue; @@ -65,7 +66,7 @@ // no-op } - public void assignToCache(Cache<?, ?> cache, EvictionAlgorithmConfig evictionAlgorithmConfig) { + public void init(Cache<?, ?> cache, DataContainer<?, ?> dataContainer, EvictionAlgorithmConfig evictionAlgorithmConfig) { // no-op } @@ -81,11 +82,15 @@ return true; // always ignore everything! } - public void initialize() { + public Class<? extends EvictionAlgorithmConfig> getConfigurationClass() { + return NullEvictionAlgorithmConfig.class; + } + + public void start() { // no-op } - public Class<? extends EvictionAlgorithmConfig> getConfigurationClass() { - return NullEvictionAlgorithmConfig.class; + public void stop() { + // no-op } } Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/nullalgo/NullEvictionQueue.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/nullalgo/NullEvictionQueue.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/nullalgo/NullEvictionQueue.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -21,7 +21,6 @@ */ package org.horizon.eviction.algorithms.nullalgo; -import org.horizon.eviction.EntryEvictionData; import org.horizon.eviction.algorithms.BaseEvictionQueue; import java.util.Iterator; @@ -48,7 +47,7 @@ /** * No-op */ - public void add(EntryEvictionData entryEvictionData) { + public void add(Object key) { // no-op } @@ -59,10 +58,6 @@ // no-op } - public EntryEvictionData get(Object key) { - return null; // no-op - } - /** * Returns <code>false</code> */ @@ -80,7 +75,7 @@ /** * Returns an <code>Iterator</code> whose <code>hasNext()</code> returns <code>false</code>. */ - public Iterator<EntryEvictionData> iterator() { + public Iterator<Object> iterator() { return NullQueueIterator.INSTANCE; } @@ -91,7 +86,7 @@ // no-op } - static class NullQueueIterator implements Iterator<EntryEvictionData> { + static class NullQueueIterator implements Iterator<Object> { private static final NullQueueIterator INSTANCE = new NullQueueIterator(); private NullQueueIterator() { @@ -101,7 +96,7 @@ return false; } - public EntryEvictionData next() { + public Object next() { throw new NoSuchElementException("No more elements"); } Copied: core/branches/flat/src/main/java/org/horizon/eviction/events/EvictionEvent.java (from rev 7633, core/branches/flat/src/main/java/org/horizon/eviction/EvictionEvent.java) =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/events/EvictionEvent.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/eviction/events/EvictionEvent.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,98 @@ +/* + * JBoss, Home of Professional Open Source. + * Copyright 2000 - 2008, Red Hat Middleware LLC, and individual contributors + * as indicated by the @author tags. See the copyright.txt file in the + * distribution for a full listing of individual contributors. + * + * This is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation; either version 2.1 of + * the License, or (at your option) any later version. + * + * This software is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this software; if not, write to the Free + * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA + * 02110-1301 USA, or see the FSF site: http://www.fsf.org. + */ +package org.horizon.eviction.events; + +/** + * An eviction event records activity on nodes in the cache. These are recorded for processing later. + * + * @author (various) + * @since 1.0 + */ +public class EvictionEvent { + Object key; + Type type; + + public static enum Type { + ADD_ENTRY_EVENT, + REMOVE_ENTRY_EVENT, + VISIT_ENTRY_EVENT, + CLEAR_CACHE_EVENT, + MARK_IN_USE_EVENT, + UNMARK_IN_USE_EVENT + } + + public EvictionEvent(Object key, Type type) { + this.key = key; + this.type = type; + } + + public Object getKey() { + return key; + } + + public void setKey(Object key) { + this.key = key; + } + + public void setEventType(Type event) { + type = event; + } + + public Type getEventType() { + return type; + } + + @Override + public String toString() { + return "EvictedEventNode[key=" + key + " event=" + type + "]"; + } + + /** + * Copies this evicted event node to create a new one with the same values, except with a new Fqn root. + * + * @param key new Fqn root to use + * @return a new EvictedEventNode instance + */ + public EvictionEvent copy(Object key) { + return new EvictionEvent(key, type); + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + EvictionEvent that = (EvictionEvent) o; + + if (key != null ? !key.equals(that.key) : that.key != null) return false; + if (type != that.type) return false; + + return true; + } + + @Override + public int hashCode() { + int result = key != null ? key.hashCode() : 0; + result = 31 * result + (type != null ? type.hashCode() : 0); + return result; + } +} Property changes on: core/branches/flat/src/main/java/org/horizon/eviction/events/EvictionEvent.java ___________________________________________________________________ Name: svn:executable + * Name: svn:keywords + Id Revision Name: svn:eol-style + LF Added: core/branches/flat/src/main/java/org/horizon/eviction/events/InUseEvictionEvent.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/events/InUseEvictionEvent.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/eviction/events/InUseEvictionEvent.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,52 @@ +package org.horizon.eviction.events; + +/** + * An eviction event used to mark an entry as in-use. + * + * @author Manik Surtani + * @since 1.0 + */ +public class InUseEvictionEvent extends EvictionEvent { + + long inUseTimeout; + + public InUseEvictionEvent(Object key, long inUseTimeout) { + super(key, Type.MARK_IN_USE_EVENT); + this.inUseTimeout = inUseTimeout; + } + + public long getInUseTimeout() { + return inUseTimeout; + } + + public void setInUseTimeout(long inUseTimeout) { + this.inUseTimeout = inUseTimeout; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + InUseEvictionEvent that = (InUseEvictionEvent) o; + if (!super.equals(o)) return false; + if (inUseTimeout != that.inUseTimeout) return false; + + return true; + } + + @Override + public int hashCode() { + int hc = super.hashCode(); + return hc * 31 + (int) (inUseTimeout ^ (inUseTimeout >>> 32)); + } + + @Override + public String toString() { + return "InUseEvictionEvent{" + + "key=" + key + + ", type=" + type + + ", inUseTimeout=" + inUseTimeout + + '}'; + } +} Modified: core/branches/flat/src/main/java/org/horizon/interceptors/EvictionInterceptor.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/interceptors/EvictionInterceptor.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/interceptors/EvictionInterceptor.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -28,9 +28,9 @@ import org.horizon.commands.write.RemoveCommand; import org.horizon.commands.write.ReplaceCommand; import org.horizon.context.InvocationContext; -import org.horizon.eviction.EvictionEvent; -import static org.horizon.eviction.EvictionEvent.Type.*; import org.horizon.eviction.EvictionManager; +import org.horizon.eviction.events.EvictionEvent; +import static org.horizon.eviction.events.EvictionEvent.Type.*; import org.horizon.factories.annotations.Inject; import org.horizon.interceptors.base.CommandInterceptor; Added: core/branches/flat/src/main/java/org/horizon/util/AbstractMap.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/AbstractMap.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/util/AbstractMap.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,94 @@ +package org.horizon.util; + +import java.util.Collection; +import java.util.Map; +import java.util.Set; + +/** + * Similar to the JDK's AbstractMap, this provides common functionality for custom map implementations. + * + * @author Manik Surtani + * @since 1.0 + */ +public abstract class AbstractMap<K, V> implements Map<K, V> { + + /** + * Marks null keys. + */ + private static final Object NULL = new Object(); + + // views + protected transient Set<Map.Entry<K, V>> entrySet = null; + protected transient Set<K> keySet = null; + protected transient Collection<V> values = null; + + + // The normal bit spreader... + protected static final int hash(Object key) { + int h = key.hashCode(); + h ^= (h >>> 20) ^ (h >>> 12); + return h ^ (h >>> 7) ^ (h >>> 4); + } + + @SuppressWarnings("unchecked") + protected static final <K> K maskNull(K key) { + return key == null ? (K) NULL : key; + } + + protected static final <K> K unmaskNull(K key) { + return key == NULL ? null : key; + } + + protected static final boolean eq(Object o1, Object o2) { + return o1 == o2 || (o1 != null && o1.equals(o2)); + } + +// +// protected static class SimpleEntry<K, V> implements Map.Entry<K, V> { +// private K key; +// private V value; +// +// SimpleEntry(K key, V value) { +// this.key = key; +// this.value = value; +// } +// +// SimpleEntry(Map.Entry<K, V> entry) { +// this.key = entry.getKey(); +// this.value = entry.getValue(); +// } +// +// public K getKey() { +// return key; +// } +// +// public V getValue() { +// return value; +// } +// +// public V setValue(V value) { +// V old = this.value; +// this.value = value; +// return old; +// } +// +// public boolean equals(Object o) { +// if (this == o) +// return true; +// +// if (!(o instanceof Map.Entry)) +// return false; +// Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; +// return eq(key, e.getKey()) && eq(value, e.getValue()); +// } +// +// public int hashCode() { +// return hash(key) ^ +// (value == null ? 0 : hash(value)); +// } +// +// public String toString() { +// return getKey() + "=" + getValue(); +// } +// } +} Added: core/branches/flat/src/main/java/org/horizon/util/BidirectionalLinkedHashMap.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/BidirectionalLinkedHashMap.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/util/BidirectionalLinkedHashMap.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,800 @@ +package org.horizon.util; + +import java.util.AbstractCollection; +import java.util.AbstractSet; +import java.util.Collection; +import java.util.ConcurrentModificationException; +import java.util.Iterator; +import java.util.Map; +import java.util.NoSuchElementException; + +/** + * A LinkedHashMap that allows an optional direction flag for the doubly linked list connecting pointers. The only real + * difference between this implementation and the JDK's {@link java.util.LinkedHashMap} is the provision of the // TODO + * + * @author Manik Surtani + */ +public class BidirectionalLinkedHashMap<K, V> extends AbstractMap<K, V> { + + /** + * The head of the doubly linked list. + */ + private transient LinkedEntry<K, V> header; + + /** + * The iteration ordering method for this linked hash map: <tt>true</tt> for access-order, <tt>false</tt> for + * insertion-order. + * + * @serial + */ + private final boolean accessOrder; + + + /** + * The default initial capacity - MUST be a power of two. + */ + static final int DEFAULT_INITIAL_CAPACITY = 16; + + /** + * The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. + * MUST be a power of two <= 1<<30. + */ + static final int MAXIMUM_CAPACITY = 1 << 30; + + /** + * The load factor used when none specified in constructor. + */ + static final float DEFAULT_LOAD_FACTOR = 0.75f; + + /** + * The table, resized as necessary. Length MUST Always be a power of two. + */ + transient LinkedEntry[] table; + + /** + * The number of key-value mappings contained in this map. + */ + transient int size; + + /** + * The next size value at which to resize (capacity * load factor). + * + * @serial + */ + int threshold; + + /** + * The load factor for the hash table. + * + * @serial + */ + final float loadFactor; + + /** + * The number of times this HashMap has been structurally modified Structural modifications are those that change the + * number of mappings in the HashMap or otherwise modify its internal structure (e.g., rehash). This field is used + * to make iterators on Collection-views of the HashMap fail-fast. (See ConcurrentModificationException). + */ + transient volatile int modCount; + + /** + * Constructs an empty <tt>HashMap</tt> with the specified initial capacity and load factor. + * + * @param initialCapacity the initial capacity + * @param loadFactor the load factor + * @throws IllegalArgumentException if the initial capacity is negative or the load factor is nonpositive + */ + public BidirectionalLinkedHashMap(int initialCapacity, float loadFactor) { + this(initialCapacity, loadFactor, false); + } + + /** + * Constructs an empty <tt>LinkedHashMap</tt> instance with the specified initial capacity, load factor and ordering + * mode. + * + * @param initialCapacity the initial capacity + * @param loadFactor the load factor + * @param accessOrder the ordering mode - <tt>true</tt> for access-order, <tt>false</tt> for insertion-order + * @throws IllegalArgumentException if the initial capacity is negative or the load factor is nonpositive + */ + public BidirectionalLinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { + if (initialCapacity < 0) + throw new IllegalArgumentException("Illegal initial capacity: " + + initialCapacity); + if (initialCapacity > MAXIMUM_CAPACITY) + initialCapacity = MAXIMUM_CAPACITY; + if (loadFactor <= 0 || Float.isNaN(loadFactor)) + throw new IllegalArgumentException("Illegal load factor: " + + loadFactor); + + // Find a power of 2 >= initialCapacity + int capacity = 1; + while (capacity < initialCapacity) + capacity <<= 1; + + this.loadFactor = loadFactor; + threshold = (int) (capacity * loadFactor); + table = new LinkedEntry[capacity]; + this.accessOrder = accessOrder; + init(); + } + + /** + * Constructs an empty <tt>HashMap</tt> with the specified initial capacity and the default load factor (0.75). + * + * @param initialCapacity the initial capacity. + * @throws IllegalArgumentException if the initial capacity is negative. + */ + public BidirectionalLinkedHashMap(int initialCapacity) { + this(initialCapacity, DEFAULT_LOAD_FACTOR); + } + + /** + * Constructs an empty <tt>HashMap</tt> with the default initial capacity (16) and the default load factor (0.75). + */ + public BidirectionalLinkedHashMap() { + this.loadFactor = DEFAULT_LOAD_FACTOR; + threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); + table = new LinkedEntry[DEFAULT_INITIAL_CAPACITY]; + accessOrder = false; + init(); + } + + /** + * Constructs a new <tt>HashMap</tt> with the same mappings as the specified <tt>Map</tt>. The <tt>HashMap</tt> is + * created with default load factor (0.75) and an initial capacity sufficient to hold the mappings in the specified + * <tt>Map</tt>. + * + * @param m the map whose mappings are to be placed in this map + * @throws NullPointerException if the specified map is null + */ + public BidirectionalLinkedHashMap(Map<? extends K, ? extends V> m) { + this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, + DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR, false); + putAllForCreate(m); + } + + // internal utilities + + /** + * Returns index for hash code h. + */ + static int indexFor(int h, int length) { + return h & (length - 1); + } + + /** + * Returns the number of key-value mappings in this map. + * + * @return the number of key-value mappings in this map + */ + //@Override + public int size() { + return size; + } + + /** + * Returns <tt>true</tt> if this map contains no key-value mappings. + * + * @return <tt>true</tt> if this map contains no key-value mappings + */ + //@Override + public boolean isEmpty() { + return size == 0; + } + + /** + * Returns <tt>true</tt> if this map contains a mapping for the specified key. + * + * @param key The key whose presence in this map is to be tested + * @return <tt>true</tt> if this map contains a mapping for the specified key. + */ + public boolean containsKey(Object key) { + return getEntry(key) != null; + } + + /** + * Returns the entry associated with the specified key in the HashMap. Returns null if the HashMap contains no + * mapping for the key. + */ + final LinkedEntry<K, V> getEntry(Object key) { + int hash = (key == null) ? 0 : hash(key.hashCode()); + for (LinkedEntry<K, V> e = table[indexFor(hash, table.length)]; + e != null; + e = e.next) { + Object k; + if (e.hash == hash && + ((k = e.key) == key || (key != null && key.equals(k)))) + return e; + } + return null; + } + + + /** + * Associates the specified value with the specified key in this map. If the map previously contained a mapping for + * the key, the old value is replaced. + * + * @param key key with which the specified value is to be associated + * @param value value to be associated with the specified key + * @return the previous value associated with <tt>key</tt>, or <tt>null</tt> if there was no mapping for + * <tt>key</tt>. (A <tt>null</tt> return can also indicate that the map previously associated <tt>null</tt> + * with <tt>key</tt>.) + */ + public V put(K key, V value) { + if (key == null) + return putForNullKey(value); + int hash = hash(key.hashCode()); + int i = indexFor(hash, table.length); + for (LinkedEntry<K, V> e = table[i]; e != null; e = e.next) { + Object k; + if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { + V oldValue = e.value; + e.value = value; + e.recordAccess(this); + return oldValue; + } + } + + modCount++; + addEntry(hash, key, value, i); + return null; + } + + /** + * Offloaded version of put for null keys + */ + private V putForNullKey(V value) { + for (LinkedEntry<K, V> e = table[0]; e != null; e = e.next) { + if (e.key == null) { + V oldValue = e.value; + e.value = value; + e.recordAccess(this); + return oldValue; + } + } + modCount++; + addEntry(0, null, value, 0); + return null; + } + + /** + * This method is used instead of put by constructors and pseudoconstructors (clone, readObject). It does not resize + * 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 i = indexFor(hash, table.length); + + /** + * Look for preexisting entry for key. This will never happen for + * clone or deserialize. It will only happen for construction if the + * input Map is a sorted map whose ordering is inconsistent w/ equals. + */ + for (LinkedEntry<K, V> e = table[i]; e != null; e = e.next) { + Object k; + if (e.hash == hash && + ((k = e.key) == key || (key != null && key.equals(k)))) { + e.value = value; + return; + } + } + + createEntry(hash, key, value, i); + } + + private void putAllForCreate(Map<? extends K, ? extends V> m) { + for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext();) { + Map.Entry<? extends K, ? extends V> e = i.next(); + putForCreate(e.getKey(), e.getValue()); + } + } + + /** + * Rehashes the contents of this map into a new array with a larger capacity. This method is called automatically + * when the number of keys in this map reaches its threshold. + * <p/> + * If current capacity is MAXIMUM_CAPACITY, this method does not resize the map, but sets threshold to + * Integer.MAX_VALUE. This has the effect of preventing future calls. + * + * @param newCapacity the new capacity, MUST be a power of two; must be greater than current capacity unless current + * capacity is MAXIMUM_CAPACITY (in which case value is irrelevant). + */ + void resize(int newCapacity) { + LinkedEntry[] oldTable = table; + int oldCapacity = oldTable.length; + if (oldCapacity == MAXIMUM_CAPACITY) { + threshold = Integer.MAX_VALUE; + return; + } + + LinkedEntry[] newTable = new LinkedEntry[newCapacity]; + transfer(newTable); + table = newTable; + threshold = (int) (newCapacity * loadFactor); + } + + /** + * Copies all of the mappings from the specified map to this map. These mappings will replace any mappings that this + * map had for any of the keys currently in the specified map. + * + * @param m mappings to be stored in this map + * @throws NullPointerException if the specified map is null + */ + public void putAll(Map<? extends K, ? extends V> m) { + int numKeysToBeAdded = m.size(); + if (numKeysToBeAdded == 0) + return; + + /* + * Expand the map if the map if the number of mappings to be added + * is greater than or equal to threshold. This is conservative; the + * obvious condition is (m.size() + size) >= threshold, but this + * condition could result in a map with twice the appropriate capacity, + * if the keys to be added overlap with the keys already in this map. + * By using the conservative calculation, we subject ourself + * to at most one extra resize. + */ + if (numKeysToBeAdded > threshold) { + int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1); + if (targetCapacity > MAXIMUM_CAPACITY) + targetCapacity = MAXIMUM_CAPACITY; + int newCapacity = table.length; + while (newCapacity < targetCapacity) + newCapacity <<= 1; + if (newCapacity > table.length) + resize(newCapacity); + } + + for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext();) { + Map.Entry<? extends K, ? extends V> e = i.next(); + put(e.getKey(), e.getValue()); + } + } + + /** + * Removes the mapping for the specified key from this map if present. + * + * @param key key whose mapping is to be removed from the map + * @return the previous value associated with <tt>key</tt>, or <tt>null</tt> if there was no mapping for + * <tt>key</tt>. (A <tt>null</tt> return can also indicate that the map previously associated <tt>null</tt> + * with <tt>key</tt>.) + */ + public V remove(Object key) { + LinkedEntry<K, V> e = removeEntryForKey(key); + return (e == null ? null : e.value); + } + + /** + * Removes and returns the entry associated with the specified key in the HashMap. Returns null if the HashMap + * contains no mapping for this key. + */ + final LinkedEntry<K, V> removeEntryForKey(Object key) { + int hash = (key == null) ? 0 : hash(key.hashCode()); + int i = indexFor(hash, table.length); + LinkedEntry<K, V> prev = table[i]; + LinkedEntry<K, V> e = prev; + + while (e != null) { + LinkedEntry<K, V> next = e.next; + Object k; + if (e.hash == hash && + ((k = e.key) == key || (key != null && key.equals(k)))) { + modCount++; + size--; + if (prev == e) + table[i] = next; + else + prev.next = next; + e.recordRemoval(this); + return e; + } + prev = e; + e = next; + } + + return e; + } + + /** + * Special version of remove for EntrySet. + */ + final LinkedEntry<K, V> removeMapping(Object o) { + if (!(o instanceof Map.Entry)) + return null; + + Map.Entry<K, V> entry = (Map.Entry<K, V>) o; + Object key = entry.getKey(); + int hash = (key == null) ? 0 : hash(key.hashCode()); + int i = indexFor(hash, table.length); + LinkedEntry<K, V> prev = table[i]; + LinkedEntry<K, V> e = prev; + + while (e != null) { + LinkedEntry<K, V> next = e.next; + if (e.hash == hash && e.equals(entry)) { + modCount++; + size--; + if (prev == e) + table[i] = next; + else + prev.next = next; + e.recordRemoval(this); + return e; + } + prev = e; + e = next; + } + + return e; + } + + /** + * Removes all of the mappings from this map. The map will be empty after this call returns. + */ + public void clear() { + modCount++; + LinkedEntry[] tab = table; + for (int i = 0; i < tab.length; i++) + tab[i] = null; + size = 0; + header.before = header.after = header; + } + + static class LinkedEntry<K, V> implements Map.Entry<K, V> { + final K key; + V value; + LinkedEntry<K, V> next; + final int hash; + + // These fields comprise the doubly linked list used for iteration. + LinkedEntry<K, V> before, after; + + /** + * Creates new entry. + */ + LinkedEntry(int h, K k, V v, LinkedEntry<K, V> n) { + value = v; + next = n; + key = k; + hash = h; + } + + /** + * Removes this entry from the linked list. + */ + private void remove() { + before.after = after; + after.before = before; + } + + /** + * Inserts this entry before the specified existing entry in the list. + */ + private void addBefore(LinkedEntry<K, V> existingEntry) { + after = existingEntry; + before = existingEntry.before; + before.after = this; + after.before = this; + } + + /** + * This method is invoked by the superclass whenever the value of a pre-existing entry is read by Map.get or + * modified by Map.set. If the enclosing Map is access-ordered, it moves the entry to the end of the list; + * otherwise, it does nothing. + */ + void recordAccess(BidirectionalLinkedHashMap<K, V> lm) { + if (lm.accessOrder) { + lm.modCount++; + remove(); + addBefore(lm.header); + } + } + + void recordRemoval(BidirectionalLinkedHashMap<K, V> m) { + remove(); + } + + public final K getKey() { + return key; + } + + public final V getValue() { + return value; + } + + public final V setValue(V newValue) { + V oldValue = value; + value = newValue; + return oldValue; + } + + public final boolean equals(Object o) { + if (!(o instanceof Map.Entry)) + return false; + Map.Entry e = (Map.Entry) o; + Object k1 = getKey(); + Object k2 = e.getKey(); + if (k1 == k2 || (k1 != null && k1.equals(k2))) { + Object v1 = getValue(); + Object v2 = e.getValue(); + if (v1 == v2 || (v1 != null && v1.equals(v2))) + return true; + } + return false; + } + + public final int hashCode() { + return (key == null ? 0 : key.hashCode()) ^ + (value == null ? 0 : value.hashCode()); + } + + public final String toString() { + return getKey() + "=" + getValue(); + } + } + + // These methods are used when serializing HashSets + int capacity() { + return table.length; + } + + float loadFactor() { + return loadFactor; + } + + /** + * Called by superclass constructors and pseudoconstructors (clone, readObject) before any entries are inserted into + * the map. Initializes the chain. + */ + void init() { + header = new LinkedEntry<K, V>(-1, null, null, null); + header.before = header.after = header; + } + + /** + * Transfers all entries to new table array. This method is called by superclass resize. It is overridden for + * performance, as it is faster to iterate using our linked list. + */ + void transfer(LinkedEntry[] newTable) { + int newCapacity = newTable.length; + for (LinkedEntry<K, V> e = header.after; e != header; e = e.after) { + int index = indexFor(e.hash, newCapacity); + e.next = newTable[index]; + newTable[index] = e; + } + } + + + /** + * Returns <tt>true</tt> if this map maps one or more keys to the specified value. + * + * @param value value whose presence in this map is to be tested + * @return <tt>true</tt> if this map maps one or more keys to the specified value + */ + public boolean containsValue(Object value) { + // Overridden to take advantage of faster iterator + if (value == null) { + for (LinkedEntry e = header.after; e != header; e = e.after) + if (e.value == null) + return true; + } else { + for (LinkedEntry e = header.after; e != header; e = e.after) + if (value.equals(e.value)) + return true; + } + return false; + } + + /** + * Returns the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the + * key. + * <p/> + * <p>More formally, if this map contains a mapping from a key {@code k} to a value {@code v} such that {@code + * (key==null ? k==null : key.equals(k))}, then this method returns {@code v}; otherwise it returns {@code null}. + * (There can be at most one such mapping.) + * <p/> + * <p>A return value of {@code null} does not <i>necessarily</i> indicate that the map contains no mapping for the + * key; it's also possible that the map explicitly maps the key to {@code null}. The {@link #containsKey containsKey} + * operation may be used to distinguish these two cases. + */ + public V get(Object key) { + LinkedEntry<K, V> e = getEntry(key); + if (e == null) + return null; + e.recordAccess(this); + return e.value; + } + + private abstract class LinkedHashIterator<T> implements Iterator<T> { + LinkedEntry<K, V> nextEntry; + LinkedEntry<K, V> lastReturned = null; + boolean directionReversed; + + protected LinkedHashIterator(boolean directionReversed) { + this.directionReversed = directionReversed; + nextEntry = directionReversed ? header.before : header.after; +// nextEntry = header; + } + + /** + * The modCount value that the iterator believes that the backing List should have. If this expectation is + * violated, the iterator has detected concurrent modification. + */ + int expectedModCount = modCount; + + public boolean hasNext() { + return nextEntry != header; + } + + public void remove() { + if (lastReturned == null) + throw new IllegalStateException(); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + + BidirectionalLinkedHashMap.this.remove(lastReturned.key); + lastReturned = null; + expectedModCount = modCount; + } + + LinkedEntry<K, V> nextEntry() { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + if (nextEntry == header) + throw new NoSuchElementException(); + + LinkedEntry<K, V> e = lastReturned = nextEntry; + nextEntry = directionReversed ? e.before : e.after; + return e; + } + } + + private class KeyIterator extends LinkedHashIterator<K> { + protected KeyIterator(boolean directionReversed) { + super(directionReversed); + } + + public K next() { + return nextEntry().getKey(); + } + } + + private class ValueIterator extends LinkedHashIterator<V> { + protected ValueIterator(boolean directionReversed) { + super(directionReversed); + } + + public V next() { + return nextEntry().value; + } + } + + private class EntryIterator extends LinkedHashIterator<Map.Entry<K, V>> { + protected EntryIterator(boolean directionReversed) { + super(directionReversed); + } + + public Map.Entry<K, V> next() { + return nextEntry(); + } + } + + /** + * This override alters behavior of superclass put method. It causes newly allocated entry to get inserted at the end + * of the linked list and removes the eldest entry if appropriate. + */ + void addEntry(int hash, K key, V value, int bucketIndex) { + createEntry(hash, key, value, bucketIndex); + + // Grow capacity if appropriate + if (size >= threshold) resize(2 * table.length); + } + + /** + * This override differs from addEntry in that it doesn't resize the table or remove the eldest entry. + */ + void createEntry(int hash, K key, V value, int bucketIndex) { + LinkedEntry<K, V> old = table[bucketIndex]; + LinkedEntry<K, V> e = new LinkedEntry<K, V>(hash, key, value, old); + table[bucketIndex] = e; + e.addBefore(header); + size++; + } + + public Collection<V> values() { + if (values == null) values = new Values(); + return values; + } + + private final class Values extends AbstractCollection<V> { + public Iterator<V> iterator() { + return new ValueIterator(false); + } + + public int size() { + return BidirectionalLinkedHashMap.this.size(); + } + + public boolean contains(Object o) { + return containsValue(o); + } + + public void clear() { + BidirectionalLinkedHashMap.this.clear(); + } + } + + public ReversibleSet<K> keySet() { + if (keySet == null) keySet = new KeySet(); + return (ReversibleSet<K>) keySet; + } + + private class KeySet extends AbstractSet<K> + implements ReversibleSet<K> { + + public Iterator<K> reverseIterator() { + return new KeyIterator(true); + } + + public Iterator<K> iterator() { + return new KeyIterator(false); + } + + public void clear() { + BidirectionalLinkedHashMap.this.clear(); + } + + public boolean contains(Object o) { + return containsKey(o); + } + + public boolean remove(Object o) { + int size = size(); + BidirectionalLinkedHashMap.this.remove(o); + return size() < size; + } + + public int size() { + return BidirectionalLinkedHashMap.this.size(); + } + } + + public ReversibleSet<Map.Entry<K, V>> entrySet() { + if (entrySet == null) entrySet = new EntrySet(); + return (ReversibleSet<Map.Entry<K, V>>) entrySet; + } + + private final class EntrySet extends AbstractSet<Map.Entry<K, V>> + implements ReversibleSet<Map.Entry<K, V>> { + + public Iterator<Map.Entry<K, V>> reverseIterator() { + return new EntryIterator(true); + } + + public Iterator<Map.Entry<K, V>> iterator() { + return new EntryIterator(false); + } + + @SuppressWarnings("unchecked") + public boolean contains(Object o) { + if (!(o instanceof Map.Entry)) + return false; + Map.Entry<K, V> e = (Map.Entry<K, V>) o; + LinkedEntry<K, V> candidate = getEntry(e.getKey()); + return candidate != null && candidate.equals(e); + } + + public boolean remove(Object o) { + return removeMapping(o) != null; + } + + public int size() { + return size; + } + + public void clear() { + BidirectionalLinkedHashMap.this.clear(); + } + } +} Modified: core/branches/flat/src/main/java/org/horizon/util/FastCopyHashMap.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/FastCopyHashMap.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/main/java/org/horizon/util/FastCopyHashMap.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -24,7 +24,6 @@ import java.io.IOException; import java.io.Serializable; import java.util.AbstractCollection; -import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Collection; import java.util.ConcurrentModificationException; @@ -41,11 +40,6 @@ */ public class FastCopyHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable { /** - * Marks null keys. - */ - private static final Object NULL = new Object(); - - /** * Serialization ID */ private static final long serialVersionUID = 10929568968762L; @@ -90,11 +84,6 @@ */ private transient int modCount; - // Cached views - private transient KeySet keySet; - private transient Values values; - private transient EntrySet entrySet; - public FastCopyHashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Can not have a negative size table!"); @@ -142,31 +131,11 @@ this(DEFAULT_CAPACITY); } - // The normal bit spreader... - private static final int hash(Object key) { - int h = key.hashCode(); - h ^= (h >>> 20) ^ (h >>> 12); - return h ^ (h >>> 7) ^ (h >>> 4); - } - - @SuppressWarnings("unchecked") - private static final <K> K maskNull(K key) { - return key == null ? (K) NULL : key; - } - - private static final <K> K unmaskNull(K key) { - return key == NULL ? null : key; - } - private int nextIndex(int index, int length) { index = (index >= length - 1) ? 0 : index + 1; return index; } - private static final boolean eq(Object o1, Object o2) { - return o1 == o2 || (o1 != null && o1.equals(o2)); - } - private static final int index(int hashCode, int length) { return hashCode & (length - 1); } @@ -412,27 +381,6 @@ System.out.println(" Max Distance: " + maxSkew); } - public Set<Map.Entry<K, V>> entrySet() { - if (entrySet == null) - entrySet = new EntrySet(); - - return entrySet; - } - - public Set<K> keySet() { - if (keySet == null) - keySet = new KeySet(); - - return keySet; - } - - public Collection<V> values() { - if (values == null) - values = new Values(); - - return values; - } - @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { s.defaultReadObject(); @@ -478,18 +426,6 @@ } } - private static final class Entry<K, V> { - final K key; - final int hash; - final V value; - - Entry(K key, int hash, V value) { - this.key = key; - this.hash = hash; - this.value = value; - } - } - private abstract class FasyCopyHashMapIterator<E> implements Iterator<E> { private int next = 0; private int expectedCount = modCount; @@ -589,7 +525,6 @@ } } - private class KeyIterator extends FasyCopyHashMapIterator<K> { public K next() { return unmaskNull(nextEntry().key); @@ -603,7 +538,7 @@ } private class EntryIterator extends FasyCopyHashMapIterator<Map.Entry<K, V>> { - private class WriteThroughEntry extends SimpleEntry<K, V> { + private class WriteThroughEntry extends java.util.AbstractMap.SimpleEntry<K, V> { WriteThroughEntry(K key, V value) { super(key, value); } @@ -620,9 +555,36 @@ Entry<K, V> e = nextEntry(); return new WriteThroughEntry(unmaskNull(e.key), e.value); } + } + public Collection<V> values() { + if (values == null) values = new Values(); + return values; } + private final class Values extends AbstractCollection<V> { + public Iterator<V> iterator() { + return new ValueIterator(); + } + + public int size() { + return FastCopyHashMap.this.size(); + } + + public boolean contains(Object o) { + return containsValue(o); + } + + public void clear() { + FastCopyHashMap.this.clear(); + } + } + + public Set<K> keySet() { + if (keySet == null) keySet = new KeySet(); + return keySet; + } + private class KeySet extends AbstractSet<K> { public Iterator<K> iterator() { return new KeyIterator(); @@ -647,18 +609,9 @@ } } - private class Values extends AbstractCollection<V> { - public Iterator<V> iterator() { - return new ValueIterator(); - } - - public void clear() { - FastCopyHashMap.this.clear(); - } - - public int size() { - return FastCopyHashMap.this.size(); - } + public Set<Map.Entry<K, V>> entrySet() { + if (entrySet == null) entrySet = new EntrySet(); + return entrySet; } private class EntrySet extends AbstractSet<Map.Entry<K, V>> { @@ -688,51 +641,15 @@ } } - protected static class SimpleEntry<K, V> implements Map.Entry<K, V> { - private K key; - private V value; + private static final class Entry<K, V> { + final K key; + final int hash; + final V value; - SimpleEntry(K key, V value) { + Entry(K key, int hash, V value) { this.key = key; + this.hash = hash; this.value = value; } - - SimpleEntry(Map.Entry<K, V> entry) { - this.key = entry.getKey(); - this.value = entry.getValue(); - } - - public K getKey() { - return key; - } - - public V getValue() { - return value; - } - - public V setValue(V value) { - V old = this.value; - this.value = value; - return old; - } - - public boolean equals(Object o) { - if (this == o) - return true; - - if (!(o instanceof Map.Entry)) - return false; - Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; - return eq(key, e.getKey()) && eq(value, e.getValue()); - } - - public int hashCode() { - return hash(key) ^ - (value == null ? 0 : hash(value)); - } - - public String toString() { - return getKey() + "=" + getValue(); - } } } Added: core/branches/flat/src/main/java/org/horizon/util/ReversibleSet.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/ReversibleSet.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/util/ReversibleSet.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -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. + * + * @author Manik Surtani + * @since 1.0 + */ +public interface ReversibleSet<E> extends Set<E> { + Iterator<E> reverseIterator(); +} Added: core/branches/flat/src/main/java/org/horizon/util/VisitableLinkedHashSet.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/util/VisitableLinkedHashSet.java (rev 0) +++ core/branches/flat/src/main/java/org/horizon/util/VisitableLinkedHashSet.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,148 @@ +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(); + } +} Added: core/branches/flat/src/test/java/org/horizon/SkipListTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/SkipListTest.java (rev 0) +++ core/branches/flat/src/test/java/org/horizon/SkipListTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,64 @@ +package org.horizon; + +import org.testng.annotations.Test; + +import java.util.TreeMap; + +/** + * // TODO: Manik: Document this! + * + * @author Manik Surtani + */ +@Test +public class SkipListTest { + + public void test() { + TreeMap m = new TreeMap(); + m.put(new Thing(50), "x"); + Thing t = new Thing(20); + m.put(t, "x"); + m.put(new Thing(40), "x"); + m.put(new Thing(70), "x"); + + System.out.println(m); + + t.number = 99; + System.out.println(m); + } + + public static class Thing implements Comparable { + Integer number; + + public Thing(Integer number) { + this.number = number; + } + + public int compareTo(Object o) { + return number.compareTo(((Thing) o).number); + } + + @Override + public String toString() { + return "Thing{" + + "number=" + number + + '}'; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + Thing thing = (Thing) o; + + if (number != null ? !number.equals(thing.number) : thing.number != null) return false; + + return true; + } + + @Override + public int hashCode() { + return number != null ? number.hashCode() : 0; + } + } +} Modified: core/branches/flat/src/test/java/org/horizon/eviction/EvictionFunctionalTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/EvictionFunctionalTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/EvictionFunctionalTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -7,16 +7,19 @@ import org.horizon.manager.CacheManager; import org.horizon.manager.DefaultCacheManager; import org.horizon.notifications.Listener; +import org.horizon.notifications.cachelistener.annotation.CacheEntryEvicted; import org.horizon.notifications.cachelistener.event.CacheEntryEvictedEvent; import org.horizon.util.TestingUtil; import org.testng.annotations.AfterMethod; import org.testng.annotations.BeforeMethod; import org.testng.annotations.Test; +import java.util.HashSet; +import java.util.Set; import java.util.concurrent.CountDownLatch; import java.util.concurrent.TimeUnit; -@Test(groups = "functional", sequential = true, enabled = false) +@Test(groups = "functional", sequential = true, enabled = true) public class EvictionFunctionalTest { Cache cache; EvictionListener el; @@ -47,25 +50,31 @@ public void testEviction() throws InterruptedException { el.latch = new CountDownLatch(1); - for (int i = 0; i < 11; i++) { + for (int i = 0; i < 20; i++) { cache.put(i, "value"); } assert el.latch.await(60, TimeUnit.SECONDS); - for (int i = 1; i < 11; i++) { - assert cache.containsKey(i); - } + for (int i = 10; i < 20; i++) assert cache.containsKey(i); - assert !cache.containsKey(0); + for (int i = 0; i < 10; i++) assert !cache.containsKey(i); } @Listener public static class EvictionListener { + Set<Integer> expectedKeys = new HashSet<Integer>(); CountDownLatch latch; + public EvictionListener() { + for (int i = 0; i < 10; i++) expectedKeys.add(i); + } + + @CacheEntryEvicted public void handle(CacheEntryEvictedEvent event) { + System.out.println("Saw event " + event); if (event.isPre()) { - latch.countDown(); + assert expectedKeys.remove(event.getKey()); + if (expectedKeys.isEmpty()) latch.countDown(); } } } Modified: core/branches/flat/src/test/java/org/horizon/eviction/EvictionManagerTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/EvictionManagerTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/EvictionManagerTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,7 +1,76 @@ package org.horizon.eviction; +import org.easymock.EasyMock; +import static org.easymock.EasyMock.*; +import org.horizon.config.Configuration; +import org.horizon.config.EvictionConfig; +import org.horizon.eviction.algorithms.fifo.FIFOAlgorithmConfig; +import org.horizon.eviction.events.EvictionEvent; +import org.horizon.eviction.events.InUseEvictionEvent; import org.testng.annotations.Test; +import java.util.concurrent.BlockingQueue; +import java.util.concurrent.ScheduledExecutorService; +import java.util.concurrent.ScheduledFuture; +import java.util.concurrent.TimeUnit; + @Test(groups = "unit") public class EvictionManagerTest { + + private Configuration getCfg() { + Configuration cfg = new Configuration(); + EvictionConfig ecfg = new EvictionConfig(); + ecfg.setAlgorithmConfig(new FIFOAlgorithmConfig()); // for now + cfg.setEvictionConfig(ecfg); + return cfg; + } + + public void testNoEvictionThread() { + EvictionManagerImpl em = new EvictionManagerImpl(); + Configuration cfg = getCfg(); + cfg.getEvictionConfig().setWakeUpInterval(0); + + ScheduledExecutorService mockService = EasyMock.createMock(ScheduledExecutorService.class); + em.initialize(mockService, cfg, null, null); + replay(mockService); + em.start(); + + assert em.evictionTask == null : "Eviction task is not null! Should not have scheduled anything!"; + verify(mockService); // expect that the executor was never used!! + } + + public void testWakeupInterval() { + EvictionManagerImpl em = new EvictionManagerImpl(); + Configuration cfg = getCfg(); + cfg.getEvictionConfig().setWakeUpInterval(789); + + ScheduledExecutorService mockService = EasyMock.createMock(ScheduledExecutorService.class); + em.initialize(mockService, cfg, null, null); + + ScheduledFuture mockFuture = createNiceMock(ScheduledFuture.class); + expect(mockService.scheduleWithFixedDelay(isA(EvictionManagerImpl.ScheduledTask.class), eq((long) 789), + eq((long) 789), eq(TimeUnit.MILLISECONDS))) + .andReturn(mockFuture).once(); + replay(mockService); + em.start(); + + assert em.evictionTask == mockFuture; + verify(mockService); // expect that the executor was never used!! + } + + public void testMarkInUse() throws InterruptedException { + EvictionManagerImpl em = new EvictionManagerImpl(); + em.evictionEventQueue = createMock(BlockingQueue.class); + em.evictionAlgorithm = createNiceMock(EvictionAlgorithm.class); + expect(em.evictionEventQueue.size()).andReturn(0).anyTimes(); + em.evictionEventQueue.put(eq(new InUseEvictionEvent("x", 7000))); + expectLastCall().once(); + em.evictionEventQueue.put(eq(new EvictionEvent("x", EvictionEvent.Type.UNMARK_IN_USE_EVENT))); + expectLastCall().once(); + + replay(em.evictionEventQueue); + em.markKeyCurrentlyInUse("x", 7, TimeUnit.SECONDS); + em.unmarkKeyCurrentlyInUse("x"); + verify(em.evictionEventQueue); + } } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/BaseAlgorithmTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/BaseAlgorithmTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/BaseAlgorithmTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -3,12 +3,13 @@ import org.easymock.EasyMock; import static org.easymock.EasyMock.*; import org.horizon.config.EvictionAlgorithmConfig; -import org.horizon.eviction.EntryEvictionData; +import org.horizon.container.DataContainer; import org.horizon.eviction.EvictionAction; import org.horizon.eviction.EvictionAlgorithm; import org.horizon.eviction.EvictionAlgorithmConfigBase; -import org.horizon.eviction.EvictionEvent; -import static org.horizon.eviction.EvictionEvent.Type.*; +import org.horizon.eviction.events.EvictionEvent; +import static org.horizon.eviction.events.EvictionEvent.Type.*; +import org.horizon.eviction.events.InUseEvictionEvent; import org.horizon.util.Util; import org.testng.annotations.Test; @@ -21,9 +22,17 @@ protected abstract EvictionAlgorithmConfigBase getNewEvictionAlgorithmConfig(); - protected EvictionAlgorithm createAndInit(EvictionAlgorithmConfig cfg) throws Exception { - EvictionAlgorithm a = (EvictionAlgorithm) Util.getInstance(cfg.getEvictionAlgorithmClassName()); - a.assignToCache(null, cfg); + protected BaseEvictionAlgorithm createAndInit(EvictionAlgorithmConfig cfg) throws Exception { + DataContainer dc = createNiceMock(DataContainer.class); + expect(dc.getModifiedTimestamp(anyObject())).andReturn(System.currentTimeMillis()).anyTimes(); + replay(dc); + return createAndInit(cfg, dc); + } + + protected BaseEvictionAlgorithm createAndInit(EvictionAlgorithmConfig cfg, DataContainer dc) throws Exception { + BaseEvictionAlgorithm a = (BaseEvictionAlgorithm) Util.getInstance(cfg.getEvictionAlgorithmClassName()); + a.init(null, dc, cfg); + a.start(); return a; } @@ -31,8 +40,11 @@ EvictionAlgorithmConfigBase cfg = getNewEvictionAlgorithmConfig(); cfg.setMinTimeToLive(2 * 60 * 60 * 1000); // something enormous - 2 hrs cfg.setMaxEntries(5); - EvictionAlgorithm a = createAndInit(cfg); - EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); + DataContainer dc = createMock(DataContainer.class); + expect(dc.getModifiedTimestamp(anyObject())).andReturn(System.currentTimeMillis()).anyTimes(); + replay(dc); + BaseEvictionAlgorithm a = createAndInit(cfg, dc); + EvictionAction mockAction = createMock(EvictionAction.class); a.setEvictionAction(mockAction); BlockingQueue<EvictionEvent> eventQueue = new LinkedBlockingQueue<EvictionEvent>(); for (int i = 0; i < 10; i++) eventQueue.put(new EvictionEvent(i, EvictionEvent.Type.ADD_ENTRY_EVENT)); @@ -45,18 +57,19 @@ a.process(eventQueue); verify(mockAction); - for (EntryEvictionData data : a.getEvictionQueue()) { + + reset(dc); + for (Object k : a.getEvictionQueue()) { // change the creation timestamp to before 2 hrs in the past // for all even keys - Integer key = (Integer) data.getKey(); + Integer key = (Integer) k; if (key % 2 == 0) { - data.setCreationTimeStamp(1); - data.setModifiedTimeStamp(1); + expect(dc.getModifiedTimestamp(eq(key))).andReturn((long) 1).once(); EvictionEvent e = new EvictionEvent(key, EvictionEvent.Type.VISIT_ENTRY_EVENT); - e.setCreationTimestamp(1); eventQueue.put(e); } else { + expect(dc.getModifiedTimestamp(eq(key))).andReturn(System.currentTimeMillis()).once(); eventQueue.put(new EvictionEvent(key, EvictionEvent.Type.VISIT_ENTRY_EVENT)); } } @@ -70,11 +83,19 @@ expect(mockAction.evict(eq(4))).andReturn(true).once(); expect(mockAction.evict(eq(6))).andReturn(true).once(); expect(mockAction.evict(eq(8))).andReturn(true).once(); - replay(mockAction); + replay(mockAction, dc); a.process(eventQueue); verify(mockAction); } + protected boolean timeOrderedQueue() { + return true; + } + + protected boolean reverseOrder() { + return false; + } + public void testNumEntries1() throws Exception { EvictionAlgorithmConfigBase config = getNewEvictionAlgorithmConfig(); config.setMaxEntries(4); @@ -86,16 +107,26 @@ eventQueue.put(new EvictionEvent("four", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("five", ADD_ENTRY_EVENT)); EvictionAlgorithm algo = createAndInit(config); - EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); + EvictionAction mockAction = createMock(EvictionAction.class); algo.setEvictionAction(mockAction); // should prune down to 2 entries - EasyMock.expect(mockAction.evict(eq("one"))).andReturn(true).once(); - EasyMock.expect(mockAction.evict(eq("two"))).andReturn(true).once(); - EasyMock.expect(mockAction.evict(eq("three"))).andReturn(true).once(); - EasyMock.replay(mockAction); + if (timeOrderedQueue()) { + if (reverseOrder()) { + expect(mockAction.evict(eq("five"))).andReturn(true).once(); + expect(mockAction.evict(eq("four"))).andReturn(true).once(); + expect(mockAction.evict(eq("three"))).andReturn(true).once(); + } else { + expect(mockAction.evict(eq("one"))).andReturn(true).once(); + expect(mockAction.evict(eq("two"))).andReturn(true).once(); + expect(mockAction.evict(eq("three"))).andReturn(true).once(); + } + } else { + expect(mockAction.evict(anyObject())).andReturn(true).times(3); + } + replay(mockAction); algo.process(eventQueue); - EasyMock.verify(mockAction); + verify(mockAction); } @@ -107,7 +138,7 @@ eventQueue.put(new EvictionEvent("one", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("two", ADD_ENTRY_EVENT)); EvictionAlgorithm algo = createAndInit(config); - EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); + EvictionAction mockAction = createMock(EvictionAction.class); algo.setEvictionAction(mockAction); // should prune down to 2 entries @@ -128,11 +159,20 @@ eventQueue.put(new EvictionEvent("three", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("four", ADD_ENTRY_EVENT)); EvictionAlgorithm algo = createAndInit(config); - EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); + EvictionAction mockAction = createMock(EvictionAction.class); algo.setEvictionAction(mockAction); // should prune down to equal to maxEntries - EasyMock.expect(mockAction.evict(eq("one"))).andReturn(true).once(); + if (timeOrderedQueue()) { + if (reverseOrder()) { + EasyMock.expect(mockAction.evict(eq("four"))).andReturn(true).once(); + } else { + EasyMock.expect(mockAction.evict(eq("one"))).andReturn(true).once(); + } + } else { + EasyMock.expect(mockAction.evict(anyObject())).andReturn(true).once(); + } + EasyMock.replay(mockAction); algo.process(eventQueue); EasyMock.verify(mockAction); @@ -148,7 +188,7 @@ eventQueue.put(new EvictionEvent("three", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("four", ADD_ENTRY_EVENT)); EvictionAlgorithm algo = createAndInit(config); - EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); + EvictionAction mockAction = createMock(EvictionAction.class); algo.setEvictionAction(mockAction); // expecting nothing to be evicted @@ -167,11 +207,19 @@ eventQueue.put(new EvictionEvent("three", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("four", ADD_ENTRY_EVENT)); EvictionAlgorithm algo = createAndInit(config); - EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); + EvictionAction mockAction = createMock(EvictionAction.class); algo.setEvictionAction(mockAction); // should prune down to equal to maxEntries - EasyMock.expect(mockAction.evict(eq("one"))).andReturn(true).once(); + if (timeOrderedQueue()) { + if (reverseOrder()) { + EasyMock.expect(mockAction.evict(eq("four"))).andReturn(true).once(); + } else { + EasyMock.expect(mockAction.evict(eq("one"))).andReturn(true).once(); + } + } else { + EasyMock.expect(mockAction.evict(anyObject())).andReturn(true).once(); + } EasyMock.replay(mockAction); algo.process(eventQueue); EasyMock.verify(mockAction); @@ -185,7 +233,7 @@ eventQueue.put(new EvictionEvent("two", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("three", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("four", ADD_ENTRY_EVENT)); - EvictionAlgorithm algo = createAndInit(config); + BaseEvictionAlgorithm algo = createAndInit(config); EvictionAction mockAction = EasyMock.createNiceMock(EvictionAction.class); algo.setEvictionAction(mockAction); @@ -194,12 +242,12 @@ EasyMock.replay(mockAction); algo.process(eventQueue); - assert algo.getEvictionQueue().size() == 4; + assert algo.evictionQueue.size() == 4; eventQueue.put(new EvictionEvent("three", REMOVE_ENTRY_EVENT)); algo.process(eventQueue); assert algo.getEvictionQueue().size() == 3; - assert algo.getEvictionQueue().get("three") == null; + assert !algo.getEvictionQueue().contains("three"); } public void testClearEvent() throws Exception { @@ -210,7 +258,7 @@ eventQueue.put(new EvictionEvent("two", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("three", ADD_ENTRY_EVENT)); eventQueue.put(new EvictionEvent("four", ADD_ENTRY_EVENT)); - EvictionAlgorithm algo = createAndInit(config); + BaseEvictionAlgorithm algo = createAndInit(config); EvictionAction mockAction = EasyMock.createNiceMock(EvictionAction.class); algo.setEvictionAction(mockAction); @@ -224,6 +272,76 @@ eventQueue.put(new EvictionEvent("three", CLEAR_CACHE_EVENT)); algo.process(eventQueue); assert algo.getEvictionQueue().size() == 0; - assert algo.getEvictionQueue().get("three") == null; + assert !algo.getEvictionQueue().contains("three"); } + + public void testMarkInUseControl() throws Exception { + EvictionAlgorithmConfigBase config = getNewEvictionAlgorithmConfig(); + config.setMaxEntries(1); + BlockingQueue<EvictionEvent> eventQueue = new LinkedBlockingQueue<EvictionEvent>(); + eventQueue.put(new EvictionEvent("one", ADD_ENTRY_EVENT)); + eventQueue.put(new EvictionEvent("two", ADD_ENTRY_EVENT)); + BaseEvictionAlgorithm algo = createAndInit(config); + EvictionAction mockAction = EasyMock.createNiceMock(EvictionAction.class); + algo.setEvictionAction(mockAction); + + // should prune down to equal to maxEntries + if (timeOrderedQueue()) { + if (reverseOrder()) { + expect(mockAction.evict(eq("two"))).andReturn(true).once(); + } else { + expect(mockAction.evict(eq("one"))).andReturn(true).once(); + } + } else { + expect(mockAction.evict(anyObject())).andReturn(true).once(); + } + + replay(mockAction); + algo.process(eventQueue); + verify(mockAction); + + assert algo.keysInUse.isEmpty(); + } + + public void testMarkInUse() throws Exception { + EvictionAlgorithmConfigBase config = getNewEvictionAlgorithmConfig(); + config.setMaxEntries(1); + BlockingQueue<EvictionEvent> eventQueue = new LinkedBlockingQueue<EvictionEvent>(); + eventQueue.put(new EvictionEvent("one", ADD_ENTRY_EVENT)); + eventQueue.put(new EvictionEvent("two", ADD_ENTRY_EVENT)); + eventQueue.put(new InUseEvictionEvent("one", 200000)); + eventQueue.put(new InUseEvictionEvent("two", 200000)); + BaseEvictionAlgorithm algo = createAndInit(config); + EvictionAction mockAction = EasyMock.createNiceMock(EvictionAction.class); + algo.setEvictionAction(mockAction); + + // Nothing should happen + replay(mockAction); + algo.process(eventQueue); + verify(mockAction); + + assert algo.keysInUse.size() == 2; + + eventQueue = new LinkedBlockingQueue<EvictionEvent>(); + eventQueue.put(new EvictionEvent("one", UNMARK_IN_USE_EVENT)); + eventQueue.put(new EvictionEvent("two", UNMARK_IN_USE_EVENT)); + + reset(mockAction); + // should prune down to equal to maxEntries + if (timeOrderedQueue()) { + if (reverseOrder()) { + expect(mockAction.evict(eq("two"))).andReturn(true).once(); + } else { + expect(mockAction.evict(eq("one"))).andReturn(true).once(); + } + } else { + expect(mockAction.evict(anyObject())).andReturn(true).once(); + } + + replay(mockAction); + algo.process(eventQueue); + verify(mockAction); + + assert algo.keysInUse.isEmpty(); + } } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/BaseQueueTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/BaseQueueTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/BaseQueueTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,21 +1,16 @@ package org.horizon.eviction.algorithms; -import org.horizon.eviction.EntryEvictionData; import org.horizon.eviction.EvictionQueue; import org.testng.annotations.Test; @Test(groups = "unit") public abstract class BaseQueueTest { - protected EntryEvictionData getFirstEntry(EvictionQueue q) { + protected Object getFirstEntry(EvictionQueue q) { return q.iterator().next(); } - protected Object getFirstEntryKey(EvictionQueue q) { - return q.iterator().next().getKey(); - } - protected void fillQueue(EvictionQueue q, int numEntries) { - for (int i = 0; i < numEntries; i++) q.add(new EntryEvictionData(i)); + for (int i = 0; i < numEntries; i++) q.add(i); } protected abstract EvictionQueue getNewEvictionQueue(); @@ -35,16 +30,29 @@ assert q.contains(999); assert !q.contains(1000); - for (int i = 0; i < 1000; i++) { - assert q.get(i).getKey().equals(i); - } + testContents(q); for (int i = 0; i < 1000; i++) { assert q.size() == 1000 - i; q.remove(i); } + assert q.size() == 0 : "Was expecting size=0 but it was " + q.size(); assert q.isEmpty(); - assert q.size() == 0; } + + protected int[] expectedKeysForSizingTest() { + int[] ints = new int[1000]; + for (int i = 0; i < 1000; i++) ints[i] = i; + return ints; + } + + protected void testContents(EvictionQueue q) { + int i = 0; + int[] expected = expectedKeysForSizingTest(); + for (Object key : q) { + assert key.equals(expected[i]); + if (i < 1000) i++; + } + } } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/fifo/FifoAlgorithmTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/fifo/FifoAlgorithmTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/fifo/FifoAlgorithmTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,62 +1,10 @@ package org.horizon.eviction.algorithms.fifo; -import org.easymock.EasyMock; -import static org.easymock.EasyMock.*; -import org.horizon.eviction.EntryEvictionData; -import org.horizon.eviction.EvictionAction; -import org.horizon.eviction.EvictionEvent; import org.horizon.eviction.algorithms.BaseAlgorithmTest; import org.testng.annotations.Test; -import java.util.concurrent.BlockingQueue; -import java.util.concurrent.LinkedBlockingQueue; - @Test(groups = "unit") public class FifoAlgorithmTest extends BaseAlgorithmTest { - - public void testMaxEntries() throws Exception { - FIFOAlgorithmConfig config = new FIFOAlgorithmConfig(); - config.setMaxEntries(5); - - FIFOAlgorithm algo = (FIFOAlgorithm) createAndInit(config); - EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); - algo.setEvictionAction(mockAction); - - BlockingQueue<EvictionEvent> eventQueue = new LinkedBlockingQueue<EvictionEvent>(); - for (int i = 0; i < 10; i++) eventQueue.put(new EvictionEvent(i, EvictionEvent.Type.ADD_ENTRY_EVENT)); - - for (int i = 0; i < 5; i++) expect(mockAction.evict(eq(i))).andReturn(true).once(); - replay(mockAction); - algo.process(eventQueue); - verify(mockAction); - - // now verify the order. - int index = 5; - for (EntryEvictionData data : algo.getEvictionQueue()) { - assert data.getKey().equals(index); - index++; - } - - // now verify the same order still exists after visiting the entries - for (int i = 5; i < 10; i++) { - eventQueue.put(new EvictionEvent(i, EvictionEvent.Type.VISIT_ENTRY_EVENT)); - } - for (int i = 5; i < 10; i++) { - eventQueue.put(new EvictionEvent(i, EvictionEvent.Type.VISIT_ENTRY_EVENT)); - } - - algo.process(eventQueue); - - assert 5 == algo.getEvictionQueue().size(); - - // now verify the order. - index = 5; - for (EntryEvictionData data : algo.getEvictionQueue()) { - assert data.getKey().equals(index); - index++; - } - } - protected FIFOAlgorithmConfig getNewEvictionAlgorithmConfig() { return new FIFOAlgorithmConfig(); } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/fifo/FifoQueueTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/fifo/FifoQueueTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/fifo/FifoQueueTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,6 +1,5 @@ package org.horizon.eviction.algorithms.fifo; -import org.horizon.eviction.EntryEvictionData; import org.horizon.eviction.EvictionQueue; import org.horizon.eviction.algorithms.BaseQueueTest; import org.testng.annotations.Test; @@ -9,33 +8,34 @@ @Test(groups = "unit") public class FifoQueueTest extends BaseQueueTest { + public void testOrder() throws Exception { FIFOQueue queue = new FIFOQueue(); fillQueue(queue, 5000); - assert getFirstEntryKey(queue).equals(0); + assert getFirstEntry(queue).equals(0); // now make sure the ordering is correct. int k = 0; - for (Iterator<EntryEvictionData> i = queue.iterator(); i.hasNext();) { - EntryEvictionData data = i.next(); - assert data.getKey().equals(k); + for (Iterator<Object> i = queue.iterator(); i.hasNext();) { + Object key = i.next(); + assert key.equals(k); i.remove(); k++; if (k == 2500) break; } - assert getFirstEntryKey(queue).equals(2500); + assert getFirstEntry(queue).equals(2500); assert 2500 == queue.size(); assert !queue.isEmpty(); k = 2500; - for (Iterator<EntryEvictionData> i = queue.iterator(); i.hasNext();) { - EntryEvictionData data = i.next(); - assert data.getKey().equals(k); + for (Iterator<Object> i = queue.iterator(); i.hasNext();) { + Object key = i.next(); + assert key.equals(k); i.remove(); k++; } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuAlgorithmTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuAlgorithmTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuAlgorithmTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -5,55 +5,11 @@ @Test(groups = "unit") public class LfuAlgorithmTest extends BaseAlgorithmTest { -// public void testMinTimeToLive() throws Exception { -// LFUAlgorithmConfig cfg = getNewEvictionAlgorithmConfig(); -// cfg.setMinTimeToLive(2 * 60 * 60 * 1000); // something enormous - 2 hrs -// cfg.setMaxEntries(5); -// EvictionAlgorithm a = createAndInit(cfg); -// EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); -// a.setEvictionAction(mockAction); -// BlockingQueue<EvictionEvent> eventQueue = new LinkedBlockingQueue<EvictionEvent>(); -// for (int i = 0; i < 10; i++) eventQueue.put(new EvictionEvent(i, ADD_ENTRY_EVENT)); -// -// assert eventQueue.size() == 10; -// -// // what do we expect to happen on the eviction action class? -// // nothing at this stage. -// replay(mockAction); -// a.process(eventQueue); -// verify(mockAction); -// -// for (EntryEvictionData data : a.getEvictionQueue()) { -// // change the creation timestamp to before 2 hrs in the past -// // for all even keys -// Integer key = (Integer) data.getKey(); -// -// if (key % 2 == 0) { -// EvictionEvent e = new EvictionEvent(key, EvictionEvent.Type.VISIT_ENTRY_EVENT); -// e.setCreationTimestamp(1); -// data.setCreationTimeStamp(1); -// data.setModifiedTimeStamp(1); -// eventQueue.put(e); -// } else { -// eventQueue.put(new EvictionEvent(key, EvictionEvent.Type.VISIT_ENTRY_EVENT)); -// } -// } -// -// assert eventQueue.size() == 10; -// -// // this time we expect all even numbered keys to get evicted, since they are least frequently visited -// reset(mockAction); -// expect(mockAction.evict(eq(0))).andReturn(true).once(); -// expect(mockAction.evict(eq(2))).andReturn(true).once(); -// expect(mockAction.evict(eq(4))).andReturn(true).once(); -// expect(mockAction.evict(eq(6))).andReturn(true).once(); -// expect(mockAction.evict(eq(8))).andReturn(true).once(); -// replay(mockAction); -// a.process(eventQueue); -// verify(mockAction); -// } + @Override + protected boolean timeOrderedQueue() { + return false; + } - protected LFUAlgorithmConfig getNewEvictionAlgorithmConfig() { return new LFUAlgorithmConfig(); } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuQueueTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuQueueTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuQueueTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,74 +1,78 @@ package org.horizon.eviction.algorithms.lfu; -import org.horizon.eviction.EntryEvictionData; import org.horizon.eviction.EvictionQueue; import org.horizon.eviction.algorithms.BaseQueueTest; import org.testng.annotations.Test; +import java.util.HashSet; import java.util.Iterator; +import java.util.Set; @Test(groups = "unit") public class LfuQueueTest extends BaseQueueTest { + + @Override + protected void testContents(EvictionQueue q) { + // we should expect the keys in any order here, since they all have an equal visit count + Set<Integer> allKeys = intSet(1000); + + for (Object key : q) assert allKeys.remove(key); + + assert allKeys.isEmpty(); + } + + private Set<Integer> intSet(int count) { + Set<Integer> s = new HashSet<Integer>(); + for (int i = 0; i < count; i++) s.add(i); + return s; + } + public void testOrder() throws Exception { LFUQueue queue = (LFUQueue) getNewEvictionQueue(); fillQueue(queue, 500); assert 500 == queue.size(); - queue.reSortEvictionQueue(); + Set<Integer> allKeys = intSet(500); + for (Object key : queue) assert allKeys.remove(key) : "Unexpected key " + key + " encountered!"; + assert allKeys.isEmpty() : "Not all keys were encountered. Remaining keys " + allKeys; + for (int i = 1; i < 500; i += 2) queue.visit(i); // visit all the even keys - assert 500 == queue.size(); + System.out.println("Set: " + queue.keys); + System.out.println("KeyMap: " + queue.keyMap); - int k = 0; - for (EntryEvictionData entry : queue) { - assert entry.getKey().equals(k); - if (k % 2 == 0) entry.incrementNumberOfVisits(); - k++; - } + assert (Integer) getFirstEntry(queue) % 2 == 1 : "We don't know which odd key this would be"; - queue.reSortEvictionQueue(); - - assert getFirstEntryKey(queue).equals(1); - // now check the sort order. - k = 0; - for (EntryEvictionData entry : queue) { - if (k < 250) - assert 0 == entry.getNumberOfVisits(); - else - assert 1 == entry.getNumberOfVisits(); - k++; + for (Object key : queue) { + Integer k = (Integer) key; + assert queue.keyMap.get(key).visits == k % 2 : "Expecting " + (k % 2) + " visits on key " + key + " but it was " + queue.keyMap.get(key).visits; } - k = 0; - for (Iterator<EntryEvictionData> it = queue.iterator(); it.hasNext() && it.next() != null;) { + int k = 0; + for (Iterator<Object> it = queue.iterator(); it.hasNext() && it.next() != null;) { if (k == 250) break; it.remove(); k++; } - queue.doBatchRemove(); - assert 250 == queue.size(); assert !queue.contains(275); - for (int i = 0; i < 500; i++) { - if (i % 2 == 0) { - EntryEvictionData data = queue.get(i); - assert 1 == data.getNumberOfVisits(); - if (i > 250) data.incrementNumberOfVisits(); - } + for (int i = 0; i < 500; i += 2) { + queue.visit(i); + LFUQueue.VisitableKey data = queue.keyMap.get(i); + assert 1 == data.visits : "Expected visit count to be 1 but it was " + data.visits + " on key " + i; + if (i > 250) queue.visit(i); // visit again! } - queue.reSortEvictionQueue(); assert 250 == queue.size(); - k = 0; - for (EntryEvictionData entry : queue) { - if (k <= 125) - assert 1 == entry.getNumberOfVisits(); + for (Object key : queue) { + k = (Integer) key; + if (k <= 250) + assert 1 == queue.keyMap.get(key).visits : "Expected visit count to be 1 but it was " + queue.keyMap.get(key).visits + " on key " + key; else - assert 2 == entry.getNumberOfVisits(); - k++; + assert 2 == queue.keyMap.get(key).visits : "Expected visit count to be 2 but it was " + queue.keyMap.get(key).visits + " on key " + key; } } @@ -77,7 +81,6 @@ fillQueue(queue, 500); assert 500 == queue.size(); - assert 500 == queue.evictionList.size(); assert 500 == queue.keyMap.size(); int i = 0; @@ -86,21 +89,6 @@ i++; } assert 250 == queue.size(); - - for (EntryEvictionData data : queue.removalQueue) { - int currentIndex = (Integer) data.getKey(); - assert 0 == currentIndex % 2; - - assert !queue.contains(currentIndex); - assert queue.evictionList.contains(data); - } - - assert 500 == queue.evictionList.size(); - - queue.doBatchRemove(); - - assert 0 == queue.removalQueue.size(); - assert 250 == queue.evictionList.size(); } protected EvictionQueue getNewEvictionQueue() { Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lru/LruAlgorithmTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lru/LruAlgorithmTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lru/LruAlgorithmTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -5,56 +5,7 @@ @Test(groups = "unit") public class LruAlgorithmTest extends BaseAlgorithmTest { - protected LRUAlgorithmConfig getNewEvictionAlgorithmConfig() { return new LRUAlgorithmConfig(); } -// -// public void testMinTimeToLive() throws Exception { -// LRUAlgorithmConfig cfg = getNewEvictionAlgorithmConfig(); -// cfg.setMinTimeToLive(2 * 60 * 60 * 1000); // something enormous - 2 hrs -// cfg.setMaxEntries(5); -// EvictionAlgorithm a = createAndInit(cfg); -// EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); -// a.setEvictionAction(mockAction); -// BlockingQueue<EvictionEvent> eventQueue = new LinkedBlockingQueue<EvictionEvent>(); -// for (int i = 0; i < 10; i++) eventQueue.put(new EvictionEvent(i, EvictionEvent.Type.ADD_ENTRY_EVENT)); -// -// assert eventQueue.size() == 10; -// -// // what do we expect to happen on the eviction action class? -// // nothing at this stage. -// replay(mockAction); -// a.process(eventQueue); -// verify(mockAction); -// -// for (EntryEvictionData data : a.getEvictionQueue()) { -// // change the creation timestamp to before 2 hrs in the past -// // for all even keys -// Integer key = (Integer) data.getKey(); -// -// if (key % 2 == 0) { -// data.setCreationTimeStamp(1); -// data.setModifiedTimeStamp(1); -// EvictionEvent e = new EvictionEvent(key, EvictionEvent.Type.VISIT_ENTRY_EVENT); -// e.setCreationTimestamp(1); -// eventQueue.put(e); -// } else { -// eventQueue.put(new EvictionEvent(key, EvictionEvent.Type.VISIT_ENTRY_EVENT)); -// } -// } -// -// assert eventQueue.size() == 10; -// -// // this time we expect all even numbered keys to get evicted. -// reset(mockAction); -// expect(mockAction.evict(eq(0))).andReturn(true).once(); -// expect(mockAction.evict(eq(2))).andReturn(true).once(); -// expect(mockAction.evict(eq(4))).andReturn(true).once(); -// expect(mockAction.evict(eq(6))).andReturn(true).once(); -// expect(mockAction.evict(eq(8))).andReturn(true).once(); -// replay(mockAction); -// a.process(eventQueue); -// verify(mockAction); -// } } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lru/LruQueueTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lru/LruQueueTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lru/LruQueueTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,6 +1,5 @@ package org.horizon.eviction.algorithms.lru; -import org.horizon.eviction.EntryEvictionData; import org.horizon.eviction.EvictionQueue; import org.horizon.eviction.algorithms.BaseQueueTest; import org.testng.annotations.Test; @@ -20,78 +19,46 @@ for (int i = 0; i < 500; i++) { if ((i < 100) || (i >= 300 && i < 400)) { // visit the entries from 0-99 and the entries from 300 - 399 - reorderByLRU(queue, i); + queue.visit(i); } } - // visiting the nodes should have no affect on the maxAgeQueue. - Iterator<EntryEvictionData> maxAgeIt = queue.iterateMaxAgeQueue(); - int count = 0; - long lastTs = 0; - while (maxAgeIt.hasNext()) { - EntryEvictionData data = maxAgeIt.next(); - assert lastTs <= data.getCreationTimeStamp(); - lastTs = data.getCreationTimeStamp(); - count++; - } + int[] expectedOrder = new int[500]; - Iterator<EntryEvictionData> lruIt = queue.iterateLRUQueue(); - count = 0; - while (lruIt.hasNext()) { - EntryEvictionData data = lruIt.next(); - int index = (Integer) data.getKey(); + // least recently udes first + // this is 100 - 299, then 400 - 499 + int index = 0; + for (int i = 100; i < 300; i++) expectedOrder[index++] = i; + for (int i = 400; i < 500; i++) expectedOrder[index++] = i; - // the last 200 in the list should be the visisted LRU ones. - if (count >= 300 && count < 400) - assert count - 300 == index; - else if (count >= 400 && count < 500) - assert count - 100 == index; - else if (count < 200) - assert count + 100 == index; - else if (count >= 200 && count < 300) - assert count + 200 == index; + // then 0 - 99, and then 300 - 399 + for (int i = 0; i < 100; i++) expectedOrder[index++] = i; + for (int i = 300; i < 400; i++) expectedOrder[index++] = i; - count++; + int i = 0; + for (Iterator<Object> it = queue.iterator(); it.hasNext();) { + assert it.next().equals(expectedOrder[i++]); + it.remove(); } - Object key = getFirstEntryKey(queue); - queue.remove(key); - assert 499 == queue.size(); - - EntryEvictionData data = queue.iterateLRUQueue().next(); - queue.remove(data.getKey()); - assert 498 == queue.size(); - } - - public void testEmptyingInternalCollections() { - LRUQueue queue = new LRUQueue(); - fillQueue(queue, 1000); - assert queue.size() == 1000; - assert queue.maxAgeQueue.size() == 1000; - assert queue.lruQueue.size() == 1000; - - for (Iterator<EntryEvictionData> it = queue.iterator(); it.hasNext() && it.next() != null;) it.remove(); - assert queue.isEmpty(); - assert queue.maxAgeQueue.isEmpty(); - assert queue.lruQueue.isEmpty(); } - public void testGetFirstLRUNodeEntry() throws Exception { + public void testReordering() throws Exception { LRUQueue queue = new LRUQueue(); fillQueue(queue, 100); for (int i = 0; i < 100; i++) { - // this should move all the even numbered entries to the bottom of the lruQueue. - // maxAgeQueue should be unaffected. - if (i % 2 == 0) reorderByLRU(queue, i); +// this should move all the even numbered entries to the bottom of the lruQueue. +// maxAgeQueue should be unaffected. + if (i % 2 == 0) queue.visit(i); } assert 100 == queue.size(); int count = 0; - for (Iterator<EntryEvictionData> it = queue.iterateLRUQueue(); it.hasNext();) { - int nodeIndex = (Integer) it.next().getKey(); + for (Iterator<Object> it = queue.iterator(); it.hasNext();) { + int nodeIndex = (Integer) it.next(); if (count < 50) { // the top 50 should be all odds in the lruQueue/ @@ -105,35 +72,4 @@ } assert queue.isEmpty(); } - - public void testGetFirstMaxAgeNodeEntriy() throws Exception { - LRUQueue queue = new LRUQueue(); - fillQueue(queue, 100); - - for (int i = 0; i < 100; i++) { - // this should move all the even numbered NodeEntries to the bottom of the lruQueue. - // maxAgeQueue should be unaffected. - if (i % 2 == 0) { - reorderByLRU(queue, i); - } - } - - int count = 0; - for (Iterator<EntryEvictionData> it = queue.iterateMaxAgeQueue(); it.hasNext();) { - int nodeIndex = (Integer) it.next().getKey(); - assert count == nodeIndex; - it.remove(); - count++; - } - - assert queue.isEmpty(); - } - - private void reorderByLRU(LRUQueue queue, Object key) { - // leave the max age queue alone - it is like a fifo. - - // the lru queue is access ordered. meaning the most recently read item is moved to the bottom of the queue. - // simply calling get against it visits it and will cause LinkedHashMap to move it to the bottom of the queue. - queue.lruQueue.get(key); - } } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/mru/MruAlgorithmTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/mru/MruAlgorithmTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/mru/MruAlgorithmTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -8,66 +8,9 @@ protected MRUAlgorithmConfig getNewEvictionAlgorithmConfig() { return new MRUAlgorithmConfig(); } -// -// public void testMinTimeToLive() throws Exception { -// MRUAlgorithmConfig cfg = getNewEvictionAlgorithmConfig(); -// cfg.setMinTimeToLive(2 * 60 * 60 * 1000); // something enormous - 2 hrs -// cfg.setMaxEntries(5); -// EvictionAlgorithm a = createAndInit(cfg); -// EvictionAction mockAction = EasyMock.createMock(EvictionAction.class); -// a.setEvictionAction(mockAction); -// BlockingQueue<EvictionEvent> eventQueue = new LinkedBlockingQueue<EvictionEvent>(); -// for (int i = 0; i < 10; i++) eventQueue.put(new EvictionEvent(i, EvictionEvent.Type.ADD_ENTRY_EVENT)); -// -// assert eventQueue.size() == 10; -// -// // what do we expect to happen on the eviction action class? -// // nothing at this stage. -// replay(mockAction); -// a.process(eventQueue); -// verify(mockAction); -// -// -// // the MRU queue doesn't actually work on timestamps, but instead considers the most recently accessed, and uses a stack. -// for (EntryEvictionData data : a.getEvictionQueue()) { -// Integer key = (Integer) data.getKey(); -// -// if (key % 2 == 1) { -// // so first touch all of the odd keys. -// data.setCreationTimeStamp(1); -// data.setModifiedTimeStamp(1); -// EvictionEvent e = new EvictionEvent(key, EvictionEvent.Type.VISIT_ENTRY_EVENT); -// e.setCreationTimestamp(1); -// eventQueue.put(e); -// } -// } -// // and now the event ones -// for (EntryEvictionData data : a.getEvictionQueue()) { -// Integer key = (Integer) data.getKey(); -// -// if (key % 2 == 0) { -// // so first touch all of the odd keys. -// data.setCreationTimeStamp(1); -// data.setModifiedTimeStamp(1); -// EvictionEvent e = new EvictionEvent(key, EvictionEvent.Type.VISIT_ENTRY_EVENT); -// e.setCreationTimestamp(1); -// eventQueue.put(e); -// } -// } -// -// -// // so that the even keys will be the most recently used. -// assert eventQueue.size() == 10; -// -// // this time we expect all even numbered keys to get evicted. -// reset(mockAction); -// expect(mockAction.evict(eq(0))).andReturn(true).once(); -// expect(mockAction.evict(eq(2))).andReturn(true).once(); -// expect(mockAction.evict(eq(4))).andReturn(true).once(); -// expect(mockAction.evict(eq(6))).andReturn(true).once(); -// expect(mockAction.evict(eq(8))).andReturn(true).once(); -// replay(mockAction); -// a.process(eventQueue); -// verify(mockAction); -// } + + @Override + protected boolean reverseOrder() { + return true; + } } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/mru/MruQueueTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/mru/MruQueueTest.java 2009-02-06 10:03:13 UTC (rev 7656) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/mru/MruQueueTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -1,7 +1,5 @@ package org.horizon.eviction.algorithms.mru; -import org.horizon.eviction.EntryEvictionData; -import org.horizon.eviction.EvictionQueue; import org.horizon.eviction.algorithms.BaseQueueTest; import org.testng.annotations.Test; @@ -9,35 +7,76 @@ @Test(groups = "unit") public class MruQueueTest extends BaseQueueTest { - protected EvictionQueue getNewEvictionQueue() { + protected MRUQueue getNewEvictionQueue() { return new MRUQueue(); } public void testOrder() throws Exception { - MRUQueue queue = new MRUQueue(); + MRUQueue queue = getNewEvictionQueue(); + fillQueue(queue, 500); + + for (int i = 0; i < 500; i++) { + if ((i < 100) || (i >= 300 && i < 400)) { + // visit the entries from 0-99 and the entries from 300 - 399 + queue.visit(i); + } + } + + int[] expectedOrder = new int[500]; + + // most recently used first + int index = 0; + // this is 399 - 300, then 99 - 0 + for (int i = 399; i > 299; i--) expectedOrder[index++] = i; + for (int i = 99; i > -1; i--) expectedOrder[index++] = i; + + // then 499 - 400, then 299 - 100 + for (int i = 499; i > 399; i--) expectedOrder[index++] = i; + for (int i = 299; i > 99; i--) expectedOrder[index++] = i; + + int i = 0; + for (Iterator<Object> it = queue.iterator(); it.hasNext();) { + assert it.next().equals(expectedOrder[i++]); + it.remove(); + } + + assert queue.isEmpty(); + } + + public void testReordering() throws Exception { + MRUQueue queue = getNewEvictionQueue(); fillQueue(queue, 100); + for (int i = 0; i < 100; i++) { - if (i % 2 == 0) { - EntryEvictionData data = queue.get(i); - data.setModifiedTimeStamp(System.currentTimeMillis()); - queue.moveToTopOfStack(i); - } +// this should move all the even numbered entries to the bottom of the lruQueue. +// maxAgeQueue should be unaffected. + if (i % 2 == 0) queue.visit(i); } + assert 100 == queue.size(); + int count = 0; - for (Iterator<EntryEvictionData> it = queue.iterator(); it.hasNext();) { - EntryEvictionData data = it.next(); + for (Iterator<Object> it = queue.iterator(); it.hasNext();) { + int nodeIndex = (Integer) it.next(); + if (count < 50) { - assert data.getModifiedTimeStamp() > 0; + // the top 50 should be all evens in the mruQueue + assert nodeIndex % 2 == 0; } else { - assert data.getModifiedTimeStamp() == 0; + // the bottom fifty should all be odd #'s (and 0) + assert nodeIndex % 2 != 0; } it.remove(); count++; } - assert queue.isEmpty(); - assert queue.keyMap.isEmpty(); - assert queue.list.isEmpty(); } + + @Override + protected int[] expectedKeysForSizingTest() { + int[] ints = new int[1000]; + int index = 0; + for (int i = 999; i > -1; i--) ints[index++] = i; + return ints; + } } Added: core/branches/flat/src/test/java/org/horizon/util/BidirectionalLinkedHashMapTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/util/BidirectionalLinkedHashMapTest.java (rev 0) +++ core/branches/flat/src/test/java/org/horizon/util/BidirectionalLinkedHashMapTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,98 @@ +package org.horizon.util; + +import org.testng.annotations.Test; + +import java.util.Iterator; +import java.util.Map; + +@Test(groups = "unit") +public class BidirectionalLinkedHashMapTest { + public void testIterators() { + BidirectionalLinkedHashMap<Integer, Object> map = new BidirectionalLinkedHashMap<Integer, Object>(); + initMap(map); + + testOrderBeforeRemoval(map); + + // Remove some stuff and check that the order is still in tact + for (int i = 500; i < 600; i++) map.remove(i); + + testOrderAfterRemoval(map); + + // now attemp a visit and test that the visits are NOT recorded + map.get(200); + + // order should still be maintained + testOrderAfterRemoval(map); + } + + public void testAccessOrderIterators() { + BidirectionalLinkedHashMap<Integer, Object> map = new BidirectionalLinkedHashMap<Integer, Object>( + BidirectionalLinkedHashMap.DEFAULT_INITIAL_CAPACITY, + BidirectionalLinkedHashMap.DEFAULT_LOAD_FACTOR, + true + ); + initMap(map); + + testOrderBeforeRemoval(map); + + // now attemp a visit and test that the visits are NOT recorded + map.get(200); + + // check the forward iterator that everything is in order of entry + Iterator<Integer> it = map.keySet().iterator(); + int index = 0; + while (it.hasNext()) { + if (index == 200) index = 201; + if (index == 1000) index = 200; + assert it.next() == index++; + } + + // now check the reverse iterator. + it = map.keySet().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; + } + } + + + private void initMap(Map<Integer, Object> map) { + Object value = new Object(); + for (int i = 0; i < 1000; i++) map.put(i, value); + } + + private void testOrderBeforeRemoval(BidirectionalLinkedHashMap<Integer, Object> map) { + // check the forward iterator that everything is in order of entry + Iterator<Integer> it = map.keySet().iterator(); + int index = 0; + while (it.hasNext()) assert it.next() == index++; + + assert index == 999 : "Was expecting 999, was " + index; + + // now check the reverse iterator. + it = map.keySet().reverseIterator(); + while (it.hasNext()) assert it.next() == index--; + + assert index == 0 : "Was expecting 0, was " + index; + } + + + private void testOrderAfterRemoval(BidirectionalLinkedHashMap<Integer, Object> map) { + Iterator<Integer> it = map.keySet().iterator(); + int index = 0; + while (it.hasNext()) { + if (index == 500) index = 600; // 500 - 599 have been removed + assert it.next() == index++; + } + + // now check the reverse iterator. + it = map.keySet().reverseIterator(); + index = 999; + while (it.hasNext()) { + if (index == 599) index = 499; // 500 - 599 have been removed + assert it.next() == index--; + } + } +} Added: core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java (rev 0) +++ core/branches/flat/src/test/java/org/horizon/util/VisitableLinkedHashSetTest.java 2009-02-06 12:27:16 UTC (rev 7657) @@ -0,0 +1,69 @@ +package org.horizon.util; + +import org.testng.annotations.Test; + +import java.util.Iterator; +import java.util.Set; + +@Test(groups = "unit") +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"; + } +} \ No newline at end of file