| ExpiryFolder.java |
/*
* $Id: ExpiryFolder.java,v 1.64 2012/03/15 21:07:39 agoubard Exp $
*
* See the COPYRIGHT file for redistribution and use restrictions.
*/
package org.xins.common.collections.expiry;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import org.xins.common.Log;
import org.xins.common.MandatoryArgumentChecker;
import org.xins.common.Utils;
import org.xins.common.text.TextUtils;
/**
* Expiry folder. Contains values indexed by key. Entries in this folder will
* expire after a predefined amount of time, unless their lifetime is extended
* within that timeframe. This is done using the {@link #get(Object)} method.
*
* <p>Listeners are supported. Listeners are added using the
* {@link #addListener(ExpiryListener)} method and removed using the
* {@link #removeListener(ExpiryListener)} method. If a listener is registered
* multiple times, it will receive the events multiple times as well. And it
* will have to be removed multiple times as well.
*
* <p>This class is thread-safe.
*
* @version $Revision: 1.64 $ $Date: 2012/03/15 21:07:39 $
* @author <a href="mailto:ernst@ernstdehaan.com">Ernst de Haan</a>
* @author <a href="mailto:anthony.goubard@japplis.com">Anthony Goubard</a>
*
* @since XINS 1.0.0
*/
public final class ExpiryFolder {
/**
* The name of this class.
*/
private static final String CLASSNAME = ExpiryFolder.class.getName();
/**
* The initial size for the queue of threads waiting to obtain read or
* write access to a resource.
*/
private static final int INITIAL_QUEUE_SIZE = 89;
/**
* The number of instances of this class.
*/
private static int INSTANCE_COUNT;
/**
* Lock object for <code>INSTANCE_COUNT</code>.
*/
private static final Object INSTANCE_COUNT_LOCK = new Object();
/**
* Lock object.
*/
private final Object _lock;
/**
* The instance number of this instance.
*/
private final int _instanceNum;
/**
* The name of this expiry folder.
*/
private final String _name;
/**
* The strategy used. This field cannot be <code>null</code>.
*/
private ExpiryStrategy _strategy;
/**
* Flag that indicates whether the associated strategy has already stopped.
* If it has, then this folder becomes invalid.
*/
private boolean _strategyStopped;
/**
* String representation. Cannot be <code>null</code>.
*/
private final String _asString;
/**
* The most recently accessed entries. This field cannot be
* <code>null</code>. The entries in this map will expire after
* {@link ExpiryStrategy#getTimeOut()} milliseconds, plus at maximum
* {@link ExpiryStrategy#getPrecision()} milliseconds.
*/
private HashMap _recentlyAccessed;
/**
* Number of active slots. Always equals
* {@link #_slots}<code>.length</code>.
*/
private final int _slotCount;
/**
* The index of the last slot. This is always
* {@link #_slotCount}<code> - 1</code>.
*/
private final int _lastSlot;
/**
* Slots to contain the maps with entries that are not the most recently
* accessed. The further back in the array, the sooner the entries will
* expire.
*/
private HashMap[] _slots;
/**
* The set of listeners. May be empty, but never is <code>null</code>.
*/
private ArrayList _listeners;
/**
* Constructs a new <code>ExpiryFolder</code> with the specified name and
* strategy. When the strategy is stopped (see
* {@link ExpiryStrategy#stop()} then this folder becomes invalid and can
* no longer be used.
*
* @param name
* description of this folder, to be used in log and exception messages,
* not <code>null</code>.
*
* @param strategy
* the strategy that should be applied, not <code>null</code>.
*
* @throws IllegalArgumentException
* if <code>name == null || strategy == null</code>.
*
* @throws IllegalStateException
* if the strategy is already stopped.
*
* @since XINS 1.0.1
*/
public ExpiryFolder(final String name,
final ExpiryStrategy strategy)
throws IllegalArgumentException, IllegalStateException {
// Determine instance number
synchronized (INSTANCE_COUNT_LOCK) {
_instanceNum = INSTANCE_COUNT++;
}
String constructorDetail = "#" + _instanceNum + " [name=" + TextUtils.quote(name)
+ "; strategy=" + TextUtils.quote(strategy.toString()) + ']';
// Check arguments
MandatoryArgumentChecker.check("name", name, "strategy", strategy);
// Initialize fields
_lock = new Object();
_name = name;
_strategy = strategy;
_strategyStopped = false;
_asString = CLASSNAME + ' ' + constructorDetail;
_recentlyAccessed = new HashMap(INITIAL_QUEUE_SIZE);
_slotCount = strategy.getSlotCount();
_slots = new HashMap[_slotCount];
_lastSlot = _slotCount - 1;
_listeners = new ArrayList(5);
// Initialize all slots to a new HashMap
for (int i = 0; i < _slotCount; i++) {
_slots[i] = new HashMap(INITIAL_QUEUE_SIZE);
}
// Notify the strategy that we listen to it. If the strategy has already
// stopped, then this will throw an IllegalStateException
strategy.folderAdded(this);
// Constructed ExpiryFolder
Log.log_1408(_instanceNum, _name);
}
/**
* Checks that the associated expiry strategy was not yet stopped. If it
* was, then an {@link IllegalStateException} is thrown.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} was stopped.
*/
private void assertStrategyNotStopped()
throws IllegalStateException {
if (_strategyStopped) {
throw new IllegalStateException(
"The associated ExpiryStrategy has stopped already.");
}
}
/**
* Callback method, called by the <code>ExpiryStrategy</code> to indicate
* it was stopped.
*/
void strategyStopped() {
synchronized (_lock) {
_strategyStopped = true;
_strategy = null;
_recentlyAccessed = null;
_slots = null;
_listeners = null;
}
}
/**
* Checks whether this object is considered equal to the argument.
*
* @param obj
* the object to compare with.
*
* @return
* <code>true</code> if this object is considered equal to
* <code>obj</code>, or <code>false</code> otherwise.
*
* @see Object#equals(Object)
*/
public boolean equals(final Object obj) {
boolean equal = false;
if (obj instanceof ExpiryFolder) {
ExpiryFolder that = (ExpiryFolder) obj;
// Avoid a potential deadlock by always locking on the instance with
// the lowest instance number first
Object firstLock = (_instanceNum < that._instanceNum) ? _lock : that._lock;
Object secondLock = (_instanceNum < that._instanceNum) ? that._lock : _lock;
synchronized (firstLock) {
synchronized (secondLock) {
if (_strategy.equals(that._strategy)) {
if (_name.equals(that._name)) {
if (_recentlyAccessed.equals(that._recentlyAccessed)) {
equal = true;
for (int i = 0; i < _slotCount && equal; i++) {
if (! _slots[i].equals(that._slots[i])) {
equal = false;
}
}
}
}
}
}
}
}
return equal;
}
/**
* Returns a hash code value for the object.
*
* @return
* a hash code value for this object.
*
* @see Object#hashCode()
* @see #equals(Object)
*/
public int hashCode() {
return _strategy.hashCode() & _name.hashCode();
}
/**
* Returns the name given to this expiry folder.
*
* @return
* the name assigned to this expiry folder, not <code>null</code>.
*/
public String getName() {
return _name;
}
/**
* Returns the unique instance number.
*
* @return
* the unique instance number, which is <code>0</code> for the first
* <code>ExpiryFolder</code> instance, <code>1</code> for the second,
* etc.
*/
int getInstanceNum() {
return _instanceNum;
}
/**
* Notifies this map that the precision time frame has passed since the
* last tick.
*
* <p>Entries that are expirable may be removed from this folder.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*/
void tick() throws IllegalStateException {
// Check state
assertStrategyNotStopped();
HashMap toBeExpired;
HashMap refMap = null;
synchronized (_lock) {
// Shift the slots
toBeExpired = _slots[_lastSlot];
for (int i = _lastSlot; i > 0; i--) {
_slots[i] = _slots[i - 1];
}
_slots[0] = _recentlyAccessed;
// Removed the entries expired in the last slot
if (!_slots[_lastSlot].isEmpty()) {
Iterator iterator = _slots[_lastSlot].entrySet().iterator();
while (iterator.hasNext()) {
// Get the next Map.Entry from the iterator
Map.Entry me = (Map.Entry) iterator.next();
// Determine key and entry object
Object key = me.getKey();
Entry entry = (Entry) me.getValue();
if (entry.isExpired()) {
iterator.remove();
if (refMap == null) {
refMap = new HashMap();
}
refMap.put(key, entry.getReference());
}
}
}
// Copy all references from the wrapping Entry objects
if (!toBeExpired.isEmpty()) {
Iterator iterator = toBeExpired.entrySet().iterator();
while (iterator.hasNext()) {
// Get the next Map.Entry from the iterator
Map.Entry me = (Map.Entry) iterator.next();
// Get the key and the entry
Object key = me.getKey();
Entry entry = (Entry) me.getValue();
if (entry.isExpired()) {
// Create a map for the object references, if necessary
if (refMap == null) {
refMap = new HashMap();
}
// Store the entry that needs expiring in the refMap
refMap.put(key, entry.getReference());
} else {
String detail = "Entry marked for expiry should "
+ "have expired. Key as string is \""
+ entry.getReference().toString() + "\".";
Utils.logProgrammingError(detail);
}
}
}
// Recycle the old HashMap
toBeExpired.clear();
_recentlyAccessed = toBeExpired;
}
// Determine how may objects are to be sent to the listeners
int refMapSize = refMap == null
? 0
: refMap.size();
// Log this
Log.log_1400(_instanceNum, _name, refMapSize);
// If set of objects for listeners is empty, then short-circuit
if (refMapSize < 1 || _listeners.size() < 1) {
return;
}
// XXX: Should we do this in separate thread(s) ?
// Get a copy of the list of listeners
synchronized (_listeners) {
// If appropriate, notify the listeners
if (refMap != null && !refMap.isEmpty()) {
Map unmodifiableExpired = Collections.unmodifiableMap(refMap);
int listenerCount = _listeners.size();
for (int i = 0; i < listenerCount; i++) {
ExpiryListener listener = (ExpiryListener) _listeners.get(i);
listener.expired(this, unmodifiableExpired);
}
}
}
}
/**
* Adds the specified object as a listener for expiry events.
*
* @param listener
* the listener to be registered, cannot be <code>null</code>.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*
* @throws IllegalArgumentException
* if <code>listener == null</code>.
*/
public void addListener(final ExpiryListener listener)
throws IllegalStateException, IllegalArgumentException {
// Check state
assertStrategyNotStopped();
// Check arguments
MandatoryArgumentChecker.check("listener", listener);
synchronized (_listeners) {
_listeners.add(listener);
}
}
/**
* Removes the specified object as a listener for expiry events.
*
* <p>If the listener cannot be found, then nothing happens.
*
* @param listener
* the listener to be unregistered, cannot be <code>null</code>.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*
* @throws IllegalArgumentException
* if <code>listener == null</code>.
*/
public void removeListener(final ExpiryListener listener)
throws IllegalStateException, IllegalArgumentException {
// Check state
assertStrategyNotStopped();
// Check arguments
MandatoryArgumentChecker.check("listener", listener);
synchronized (_listeners) {
_listeners.remove(listener);
}
}
/**
* Determines the number of non-expired entries in the specified
* <code>HashMap</code>. If any entries are expired, they will be removed.
*
* @param map
* the map in which the non-expired entries are counted.
*
* @return
* the size of the specified map, always >= 0.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*/
private int sizeOf(final Map map) throws IllegalStateException {
// Check state
assertStrategyNotStopped();
int size = 0;
synchronized (_lock) {
Iterator iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
// Get the next Map.Entry from the iterator
Map.Entry me = (Map.Entry) iterator.next();
// Get the entry
Entry entry = (Entry) me.getValue();
if (!entry.isExpired()) {
size++;
}
}
}
return size;
}
/**
* Gets the number of entries.
*
* @return
* the number of entries in this expiry folder, always >= 0.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*/
public int size()
throws IllegalStateException {
// Check state
assertStrategyNotStopped();
synchronized (_lock) {
int size = sizeOf(_recentlyAccessed);
for (int i = 0; i < _slotCount; i++) {
size += sizeOf(_slots[i]);
}
return size;
}
}
/**
* Gets the value associated with a key and extends the lifetime of the
* matching entry, if there was a match.
*
* <p>The more recently the specified entry was accessed, the faster the
* lookup.
*
* @param key
* the key to lookup, cannot be <code>null</code>.
*
* @return
* the value associated with the specified key, or <code>null</code> if
* and only if this folder does not contain an entry with the specified
* key.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*
* @throws IllegalArgumentException
* if <code>key == null</code>.
*/
public Object get(final Object key)
throws IllegalStateException, IllegalArgumentException {
// Check state
assertStrategyNotStopped();
// Check arguments
MandatoryArgumentChecker.check("key", key);
// Search in the recently accessed map first
Entry entry;
synchronized (_lock) {
entry = (Entry) _recentlyAccessed.get(key);
// Entry found in recently accessed
if (entry != null) {
// Entry is already expired
if (entry.isExpired()) {
return null;
// Entry is not expired, touch it and return the reference
} else {
entry.touch();
return entry.getReference();
}
// Not found in recently accessed, look in slots
} else {
// Go through all slots
for (int i = 0; i < _slotCount; i++) {
entry = (Entry) _slots[i].remove(key);
if (entry != null) {
// Entry is already expired, update the map and size and
// return null
if (entry.isExpired()) {
return null;
// Entry is not expired, touch it, store in the recently
// accessed and return the reference
} else {
entry.touch();
_recentlyAccessed.put(key, entry);
return entry.getReference();
}
}
}
// Nothing found in any of the slots
return null;
}
}
}
/**
* Finds the value associated with a key. The lifetime of the matching
* entry is not extended.
*
* <p>The more recently the specified entry was accessed, the faster the
* lookup.
*
* @param key
* the key to lookup, cannot be <code>null</code>.
*
* @return
* the value associated with the specified key, or <code>null</code> if
* and only if this folder does not contain an entry with the specified
* key.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*
* @throws IllegalArgumentException
* if <code>key == null</code>.
*/
public Object find(final Object key)
throws IllegalStateException, IllegalArgumentException {
// Check state
assertStrategyNotStopped();
// Check arguments
MandatoryArgumentChecker.check("key", key);
Object value;
// Search in the recently accessed map first
synchronized (_lock) {
value = _recentlyAccessed.get(key);
// If not found, then look in the slots
if (value == null) {
for (int i = 0; i < _slotCount && value == null; i++) {
value = _slots[i].get(key);
}
}
}
if (value == null) {
return null;
}
Entry entry = (Entry) value;
if (entry.isExpired()) {
return null;
} else {
return entry.getReference();
}
}
/**
* Associates the specified key with the specified value.
*
* @param key
* they key for the entry, cannot be <code>null</code>.
*
* @param value
* they value for the entry, cannot be <code>null</code>.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*
* @throws IllegalArgumentException
* if <code>key == null || value == null</code>.
*/
public void put(final Object key, final Object value)
throws IllegalStateException, IllegalArgumentException {
// Check state
assertStrategyNotStopped();
// Check arguments
MandatoryArgumentChecker.check("key", key, "value", value);
// Store the association in the set of recently accessed entries
synchronized (_lock) {
Entry entry = new Entry(value);
_recentlyAccessed.put(key, entry);
}
}
/**
* Removes the specified key from this folder.
*
* @param key
* the key for the entry, cannot be <code>null</code>.
*
* @return
* the old value associated with the specified key, or <code>null</code>
* if and only if this folder does not contain an entry with the
* specified key.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*
* @throws IllegalArgumentException
* if <code>key == null</code>.
*/
public Object remove(final Object key)
throws IllegalStateException, IllegalArgumentException {
// Check state
assertStrategyNotStopped();
// Check arguments
MandatoryArgumentChecker.check("key", key);
Object value;
// Remove the key in the set of recently accessed entries
synchronized (_recentlyAccessed) {
value = _recentlyAccessed.remove(key);
}
// If not found, then look in the slots
if (value == null) {
synchronized (_slots) {
for (int i = 0; i < _slotCount && value == null; i++) {
value = _slots[i].remove(key);
}
}
}
if (value == null) {
return null;
}
Entry entry = (Entry) value;
if (entry.isExpired()) {
return null;
} else {
return entry.getReference();
}
}
/**
* Copies the entries of this <code>ExpiryFolder</code> into another one.
* This method does not perform a deep copy, so if a key is added or
* removed, both folders will be modified.
*
* @param newFolder
* the new folder where the entries should be copied into,
* cannot be <code>null</code>, cannot be <code>this</code>.
*
* @throws IllegalStateException
* if the associated {@link ExpiryStrategy} has stopped already.
*
* @throws IllegalArgumentException
* if <code>newFolder == null</code> or <code>newFolder == this</code>
* or if the precision of <code>newFolder</code> is not the same as for
* this <code>ExpiryFolder</code>.
*/
public void copy(final ExpiryFolder newFolder)
throws IllegalStateException, IllegalArgumentException {
// Check arguments
MandatoryArgumentChecker.check("newFolder", newFolder);
if (newFolder == this) {
String detail = "Folder can not be copied into itself.";
Utils.logProgrammingError(detail);
throw new IllegalArgumentException(detail);
}
if (newFolder._strategy.getPrecision() != _strategy.getPrecision()) {
String detail = "Folders must have the same precision.";
Utils.logProgrammingError(detail);
throw new IllegalArgumentException(detail);
}
// Avoid a potential deadlock by always locking on the instance with the
// lowest instance number first
Object firstLock = (_instanceNum < newFolder._instanceNum) ? _lock : newFolder._lock;
Object secondLock = (_instanceNum < newFolder._instanceNum) ? newFolder._lock : _lock;
synchronized (firstLock) {
synchronized (secondLock) {
// Copy the recentlyAccessed
newFolder._recentlyAccessed = new HashMap(_recentlyAccessed);
// Copy the slots
for (int i = 0; i < _slotCount && i < newFolder._slotCount; i++) {
newFolder._slots[i] = new HashMap(_slots[i]);
}
}
}
}
/**
* Returns the strategy associated with this folder.
*
* @return
* the strategy, never <code>null</code>.
*
* @throws IllegalStateException
* if the associated strategy has already stopped.
*/
public ExpiryStrategy getStrategy()
throws IllegalStateException {
// Check state
assertStrategyNotStopped();
return _strategy;
}
/**
* Returns a textual representation of this object.
*
* @return
* a textual representation of this <code>ExpiryFolder</code>, which
* includes the name.
*/
public String toString() {
return _asString;
}
/**
* Entry in an expiry folder. Combination of the referenced object and a
* timestamp. The timestamp indicates when the object should be expired.
*
* @version $Revision: 1.64 $ $Date: 2012/03/15 21:07:39 $
* @author <a href="mailto:ernst@ernstdehaan.com">Ernst de Haan</a>
*/
private class Entry {
/**
* Constructs a new <code>Entry</code>.
*
* @param reference
* reference to the object, should not be <code>null</code> (although
* it is not checked).
*/
private Entry(final Object reference) {
_reference = reference;
touch();
}
/**
* Reference to the object. Should not be <code>null</code>.
*/
private final Object _reference;
/**
* The time at which this entry should expire.
*/
private long _expiryTime;
/**
* Returns a hash code value for the object.
*
* @return
* a hash code value for this object.
*
* @see Object#hashCode()
* @see #equals(Object)
*/
public int hashCode() {
return _reference.hashCode();
}
/**
* Checks whether this object is considered equal to the argument.
*
* @param obj
* the object to compare with.
*
* @return
* <code>true</code> if this object is considered equal to
* <code>obj</code>, or <code>false</code> otherwise.
*
* @see Object#equals(Object)
*/
public boolean equals(final Object obj) {
boolean equal;
if (obj instanceof Entry) {
Entry that = (Entry) obj;
equal = _reference.equals(that._reference);
} else {
equal = false;
}
return equal;
}
/**
* Retrieves the reference to the object.
*
* @return
* the reference to the object, should not be <code>null</code>.
*/
public Object getReference() {
return _reference;
}
/**
* Checks if this entry is expired.
*
* @return
* <code>true</code> if this entry is expired, <code>false</code>
* otherwise.
*/
public boolean isExpired() {
return System.currentTimeMillis() >= _expiryTime;
}
/**
* Touches this entry, resetting the expiry time.
*/
public void touch() {
_expiryTime = System.currentTimeMillis() + _strategy.getTimeOut();
}
}
}