TimeoutMap.java
/*
* Copyright (c) 2008, Harald Kuhr
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* * Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* * Neither the name of the copyright holder nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package com.twelvemonkeys.util;
import java.io.Serializable;
import java.util.*;
/**
* A {@code Map} implementation that removes (expires) its elements after
* a given period. The map is by default backed by a {@link java.util.HashMap},
* or can be instantiated with any given {@code Map} as backing.
* <p>
* Notes to consider when using this map:
* </p>
* <ul>
* <li>Elements may not expire on the exact millisecond as expected.</li>
* <li>The value returned by the {@code size()} method of the map, or any of
* its collection views, may not represent
* the exact number of entries in the map at any given time.</li>
* <li>Elements in this map may expire at any time
* (but never between invocations of {@code Iterator.hasNext()}
* and {@code Iterator.next()} or {@code Iterator.remove()},
* when iterating the collection views).</li>
* </ul>
*
* @author <a href="mailto:harald.kuhr@gmail.com">Harald Kuhr</a>
* @version $Id: //depot/branches/personal/haraldk/twelvemonkeys/release-2/twelvemonkeys-core/src/main/java/com/twelvemonkeys/util/TimeoutMap.java#2 $
*/
// TODO: Consider have this Map extend LinkedMap.. That way the removeExpired
// method only have to run from the first element, until it finds an element
// that should not expire, as elements are in insertion order.
// and next expiry time would be the time of the first element.
// TODO: Consider running the removeExpiredEntries method in a separate (deamon) thread
// TODO: - or document why it is not such a good idea.
public class TimeoutMap<K, V> extends AbstractDecoratedMap<K, V> implements ExpiringMap<K, V>, Serializable, Cloneable {
/**
* Expiry time
*/
protected long expiryTime = 60000L; // 1 minute
//////////////////////
private volatile long nextExpiryTime = Long.MAX_VALUE;
//////////////////////
/**
* Creates a {@code TimeoutMap} with the default expiry time of 1 minute.
* This {@code TimeoutMap} will be backed by a new {@code HashMap} instance.
* <p>
* <small>This is constructor is here to comply with the recommendations for
* "standard" constructors in the {@code Map} interface.</small>
* </p>
*
* @see #TimeoutMap(long)
*/
public TimeoutMap() {
super();
}
/**
* Creates a {@code TimeoutMap} containing the same elements as the given map
* with the default expiry time of 1 minute.
* This {@code TimeoutMap} will be backed by a new {@code HashMap} instance,
* and <em>not</em> the map passed in as a paramter.
* <p>
* <small>This is constructor is here to comply with the recommendations for
* "standard" constructors in the {@code Map} interface.</small>
* </p>
*
* @param pContents the map whose mappings are to be placed in this map.
* May be {@code null}.
* @see #TimeoutMap(java.util.Map, Map, long)
* @see java.util.Map
*/
public TimeoutMap(Map<? extends K, ? extends V> pContents) {
super(pContents);
}
/**
* Creates a {@code TimeoutMap} with the given expiry time (milliseconds).
* This {@code TimeoutMap} will be backed by a new {@code HashMap} instance.
*
* @param pExpiryTime the expiry time (time to live) for elements in this map
*/
public TimeoutMap(long pExpiryTime) {
this();
expiryTime = pExpiryTime;
}
/**
* Creates a {@code TimeoutMap} with the given expiry time (milliseconds).
* This {@code TimeoutMap} will be backed by the given {@code Map}.
* <p>
* <em>Note that structurally modifying the backing map directly (not
* through this map or its collection views), is not allowed, and will
* produce undeterministic exceptions.</em>
* </p>
*
* @param pBacking the map that will be used as backing.
* @param pContents the map whose mappings are to be placed in this map.
* May be {@code null}.
* @param pExpiryTime the expiry time (time to live) for elements in this map
*/
public TimeoutMap(Map<K, Map.Entry<K, V>> pBacking, Map<? extends K, ? extends V> pContents, long pExpiryTime) {
super(pBacking, pContents);
expiryTime = pExpiryTime;
}
/**
* Gets the maximum time any value will be kept in the map, before it expires.
*
* @return the expiry time
*/
public long getExpiryTime() {
return expiryTime;
}
/**
* Sets the maximum time any value will be kept in the map, before it expires.
* Removes any items that are older than the specified time.
*
* @param pExpiryTime the expiry time (time to live) for elements in this map
*/
public void setExpiryTime(long pExpiryTime) {
long oldEexpiryTime = expiryTime;
expiryTime = pExpiryTime;
if (expiryTime < oldEexpiryTime) {
// Expire now
nextExpiryTime = 0;
removeExpiredEntries();
}
}
/**
* Returns the number of key-value mappings in this map. If the
* map contains more than {@code Integer.MAX_VALUE} elements, returns
* {@code Integer.MAX_VALUE}.
*
* @return the number of key-value mappings in this map.
*/
public int size() {
removeExpiredEntries();
return entries.size();
}
/**
* Returns {@code true} if this map contains no key-value mappings.
*
* @return {@code true} if this map contains no key-value mappings.
*/
public boolean isEmpty() {
return size() <= 0;
}
/**
* Returns {@code true} if this map contains a mapping for the specified
* pKey.
*
* @param pKey pKey whose presence in this map is to be tested.
* @return {@code true} if this map contains a mapping for the specified
* pKey.
*/
public boolean containsKey(Object pKey) {
removeExpiredEntries();
return entries.containsKey(pKey);
}
/**
* Returns the value to which this map maps the specified pKey. Returns
* {@code null} if the map contains no mapping for this pKey. A return
* value of {@code null} does not <i>necessarily</i> indicate that the
* map contains no mapping for the pKey; it's also possible that the map
* explicitly maps the pKey to {@code null}. The {@code containsKey}
* operation may be used to distinguish these two cases.
*
* @param pKey pKey whose associated value is to be returned.
* @return the value to which this map maps the specified pKey, or
* {@code null} if the map contains no mapping for this pKey.
* @see #containsKey(java.lang.Object)
*/
public V get(Object pKey) {
TimedEntry entry = (TimedEntry) entries.get(pKey);
if (entry == null) {
return null;
}
else if (entry.isExpired()) {
//noinspection SuspiciousMethodCalls
entries.remove(pKey);
processRemoved(entry);
return null;
}
return entry.getValue();
}
/**
* Associates the specified pValue with the specified pKey in this map
* (optional operation). If the map previously contained a mapping for
* this pKey, the old pValue is replaced.
*
* @param pKey pKey with which the specified pValue is to be associated.
* @param pValue pValue to be associated with the specified pKey.
* @return previous pValue associated with specified pKey, or {@code null}
* if there was no mapping for pKey. A {@code null} return can
* also indicate that the map previously associated {@code null}
* with the specified pKey, if the implementation supports
* {@code null} values.
*/
public V put(K pKey, V pValue) {
TimedEntry entry = (TimedEntry) entries.get(pKey);
V oldValue;
if (entry == null) {
oldValue = null;
entry = createEntry(pKey, pValue);
entries.put(pKey, entry);
}
else {
oldValue = entry.mValue;
entry.setValue(pValue);
entry.recordAccess(this);
}
// Need to remove expired objects every now and then
// We do it in the put method, to avoid resource leaks over time.
removeExpiredEntries();
modCount++;
return oldValue;
}
/**
* Removes the mapping for this pKey from this map if present (optional
* operation).
*
* @param pKey pKey whose mapping is to be removed from the map.
* @return previous value associated with specified pKey, or {@code null}
* if there was no mapping for pKey. A {@code null} return can
* also indicate that the map previously associated {@code null}
* with the specified pKey, if the implementation supports
* {@code null} values.
*/
public V remove(Object pKey) {
TimedEntry entry = (TimedEntry) entries.remove(pKey);
return (entry != null) ? entry.getValue() : null;
}
/**
* Removes all mappings from this map.
*/
public void clear() {
entries.clear(); // Finally something straightforward.. :-)
init();
}
/*protected*/ TimedEntry createEntry(K pKey, V pValue) {
return new TimedEntry(pKey, pValue);
}
/**
* Removes any expired mappings.
*/
protected void removeExpiredEntries() {
// Remove any expired elements
long now = System.currentTimeMillis();
if (now > nextExpiryTime) {
removeExpiredEntriesSynced(now);
}
}
/**
* Okay, I guess this do resemble DCL...
*
* @param pTime now
*/
// TODO: Write some exhausting multi-threaded unit-tests.
private synchronized void removeExpiredEntriesSynced(long pTime) {
if (pTime > nextExpiryTime) {
////
long next = Long.MAX_VALUE;
nextExpiryTime = next; // Avoid multiple runs...
for (Iterator<Entry<K, V>> iterator = new EntryIterator(); iterator.hasNext();) {
TimedEntry entry = (TimedEntry) iterator.next();
////
long expires = entry.expires();
if (expires < next) {
next = expires;
}
////
}
////
nextExpiryTime = next;
}
}
public Collection<V> values() {
removeExpiredEntries();
return super.values();
}
public Set<Entry<K, V>> entrySet() {
removeExpiredEntries();
return super.entrySet();
}
public Set<K> keySet() {
removeExpiredEntries();
return super.keySet();
}
// Subclass overrides these to alter behavior of views' iterator() method
protected Iterator<K> newKeyIterator() {
return new KeyIterator();
}
protected Iterator<V> newValueIterator() {
return new ValueIterator();
}
protected Iterator<Entry<K, V>> newEntryIterator() {
return new EntryIterator();
}
public void processRemoved(Entry pRemoved) {
}
/**
* Note: Iterating through this iterator will remove any expired values.
*/
private abstract class TimeoutMapIterator<E> implements Iterator<E> {
Iterator<Entry<K, Entry<K, V>>> mIterator = entries.entrySet().iterator();
BasicEntry<K, V> mNext;
long mNow = System.currentTimeMillis();
public void remove() {
mNext = null; // advance
mIterator.remove();
}
public boolean hasNext() {
if (mNext != null) {
return true; // Never expires between hasNext and next/remove!
}
while (mNext == null && mIterator.hasNext()) {
Entry<K, Entry<K, V>> entry = mIterator.next();
TimedEntry timed = (TimedEntry) entry.getValue();
if (timed.isExpiredBy(mNow)) {
// Remove from map, and continue
mIterator.remove();
processRemoved(timed);
}
else {
// Go with this entry
mNext = timed;
return true;
}
}
return false;
}
BasicEntry<K, V> nextEntry() {
if (!hasNext()) {
throw new NoSuchElementException();
}
BasicEntry<K, V> entry = mNext;
mNext = null; // advance
return entry;
}
}
private class KeyIterator extends TimeoutMapIterator<K> {
public K next() {
return nextEntry().mKey;
}
}
private class ValueIterator extends TimeoutMapIterator<V> {
public V next() {
return nextEntry().mValue;
}
}
private class EntryIterator extends TimeoutMapIterator<Entry<K, V>> {
public Entry<K, V> next() {
return nextEntry();
}
}
/**
* Keeps track of timed objects
*/
private class TimedEntry extends BasicEntry<K, V> {
private long mTimestamp;
TimedEntry(K pKey, V pValue) {
super(pKey, pValue);
updateTimestamp();
}
public V setValue(V pValue) {
updateTimestamp();
return super.setValue(pValue);
}
private void updateTimestamp() {
mTimestamp = System.currentTimeMillis();
long expires = expires();
if (expires < nextExpiryTime) {
nextExpiryTime = expires;
}
}
final boolean isExpired() {
return isExpiredBy(System.currentTimeMillis());
}
final boolean isExpiredBy(final long pTime) {
return pTime > expires();
}
final long expires() {
return mTimestamp + expiryTime;
}
}
}