/*---------------------------------------------------------------------------*\
$Id: 613efae30015df20794b2c176cdf408a3d17dfbf $
---------------------------------------------------------------------------
This software is released under a BSD-style license:
Copyright (c) 2004-2007 Brian M. Clapper. All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. The end-user documentation included with the redistribution, if any,
must include the following acknowlegement:
"This product includes software developed by Brian M. Clapper
(bmc@clapper.org, http://www.clapper.org/bmc/). That software is
copyright (c) 2004-2007 Brian M. Clapper."
Alternately, this acknowlegement may appear in the software itself,
if wherever such third-party acknowlegements normally appear.
3. Neither the names "clapper.org", "clapper.org Java Utility Library",
nor any of the names of the project contributors may be used to
endorse or promote products derived from this software without prior
written permission. For written permission, please contact
bmc@clapper.org.
4. Products derived from this software may not be called "clapper.org
Java Utility Library", nor may "clapper.org" appear in their names
without prior written permission of Brian M. Clapper.
THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED 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 BRIAN M. CLAPPER 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 org.clapper.util.misc;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.io.Serializable;
import java.util.Collection;
/**
* An LRUMap implements a Map of a fixed maximum size
* that enforces a least recently used discard policy. When the
* LRUMap is full (i.e., contains the maximum number of entries),
* any attempt to insert a new entry causes one of the least recently used
* entries to be discarded.
*
* Note:
*
*
* - The put() method "touches" (or "refreshes") an object,
* making it "new" again, even if it simply replaces the value for
* an existing key.
*
- The get() method also refreshes the retrieved object,
* but the iterator(), containsValue() and
* containsKey() methods do not refresh the objects in the
* cache.
*
- This implementation is not synchronized. If multiple threads
* access this map concurrently, and at least one of the threads
* modifies the map structurally, it must be synchronized externally.
* Unlike other Map implementations, even a simple
* get() operation structurally modifies an LRUMap.
* Synchronization can be accomplished by synchronizing on some
* object that naturally encapsulates the map. If no such object
* exists, the map should be "wrapped" using the
* Collections.synchronizedMap() method. This is best done
* at creation time, to prevent accidental unsynchronized access to
* the map:
*
Map m = Collections.synchronizedMap (new LRUMap (...));
*
*
* There are other, similar implementations. For instance, see the
* {@link LRUMap}
* class in the
* {@link Apache Jakarta Commons Collection}
* API. (This leads to the obvious question: Why write another one? The primary
* answer is that I did not want to add another third-party library dependency.
* Plus, I wanted to experiment with this algorithm.)
*
* @version $Revision$
*
* @author Copyright © 2004-2007 Brian M. Clapper
*/
public class LRUMap
extends AbstractMap
implements Cloneable, Serializable
{
/*----------------------------------------------------------------------*\
Public Constants
\*----------------------------------------------------------------------*/
/**
* The default load factor, if one isn't specified to the constructor
*/
public static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The default initial capacity, if one isn't specified to the
* constructor
*/
public static final int DEFAULT_INITIAL_CAPACITY = 16;
/*----------------------------------------------------------------------*\
Inner Classes
\*----------------------------------------------------------------------*/
/**
* Set of Map.Entry (really, LRULinkedListEntry) objects returned by
* the LRUMap.entrySet() method.
*/
private class EntrySet extends AbstractSet>
{
private EntrySet()
{
// Nothing to do
}
public Iterator> iterator()
{
return new Iterator>()
{
EntryIterator it = new EntryIterator();
public Map.Entry next()
{
return (Map.Entry) it.next();
}
public boolean hasNext()
{
return it.hasNext();
}
public void remove()
{
it.remove();
}
};
}
public boolean contains (Object o)
{
boolean has = false;
if (o instanceof Map.Entry)
{
Map.Entry e = (Map.Entry) o;
Object key = e.getKey();
has = LRUMap.this.containsKey (key);
}
return has;
}
public boolean remove (Object o)
{
return (LRUMap.this.remove (o) != null);
}
public int size()
{
return LRUMap.this.size();
}
public void clear()
{
LRUMap.this.clear();
}
}
/**
* Iterator returned by EntrySet.iterator()
*/
private class EntryIterator implements Iterator
{
private LRULinkedListEntry current;
EntryIterator()
{
current = lruQueue.head;
}
public LRULinkedListEntry next()
{
LRULinkedListEntry result = current;
current = current.next;
return result;
}
public boolean hasNext()
{
return (current != null);
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
/**
* Set of key objects returned by the LRUMap.keySet() method.
*/
private class KeySet extends AbstractSet
{
private KeySet()
{
// Nothing to do
}
public Iterator iterator()
{
return new KeySetIterator();
}
public boolean contains (Object key)
{
return LRUMap.this.containsKey (key);
}
public boolean remove (Object key)
{
return (LRUMap.this.remove (key) != null);
}
public int size()
{
return LRUMap.this.size();
}
public void clear()
{
LRUMap.this.clear();
}
}
/**
* Iterator returned by KeySet.iterator()
*/
private class KeySetIterator implements Iterator
{
private LRULinkedListEntry current;
KeySetIterator()
{
current = lruQueue.head;
}
public K next()
{
LRULinkedListEntry result = current;
current = current.next;
return result.key;
}
public boolean hasNext()
{
return (current != null);
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
/**
* Shallow set that implements a set of values backed by the map.
*/
private class ValueSet extends AbstractSet
{
private ValueSet()
{
// Nothing to do
}
public void clear()
{
throw new UnsupportedOperationException();
}
public boolean contains (Object o)
{
return LRUMap.this.containsValue(o);
}
public boolean containsAll (Collection c)
{
boolean contains = true;
for (Object o : c)
{
if (! contains(o))
{
contains = false;
break;
}
}
return contains;
}
public boolean isEmpty()
{
return LRUMap.this.isEmpty();
}
public Iterator iterator()
{
return new ValueSetIterator();
}
public boolean remove (Object o)
{
throw new UnsupportedOperationException();
}
public int size()
{
return LRUMap.this.size();
}
}
/**
* Iterator returned by ValueSet.iterator()
*/
private class ValueSetIterator implements Iterator
{
private LRULinkedListEntry current;
ValueSetIterator()
{
current = lruQueue.head;
}
public V next()
{
LRULinkedListEntry result = current;
current = current.next;
return result.value;
}
public boolean hasNext()
{
return (current != null);
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
/**
* Entry in the internal linked list (queue) of LRU entries. Implements
* Map.Entry for convenience.
*/
private final class LRULinkedListEntry implements Map.Entry
{
LRULinkedListEntry previous = null;
LRULinkedListEntry next = null;
K key = null;
V value = null;
LRULinkedListEntry (K key, V value)
{
setKeyValue (key, value);
}
public boolean equals (Object o)
{
return LRULinkedListEntry.class.isInstance (o);
}
public int hashCode()
{
return key.hashCode();
}
public K getKey()
{
return key;
}
public V getValue()
{
return value;
}
void setKeyValue (K key, V value)
{
this.key = key;
this.value = value;
}
public V setValue (V value)
{
V oldValue = this.value;
this.value = value;
return oldValue;
}
}
/**
* Internal linked list that implements the LRU queue. Each entry in the
* hash map of objects also points to one of these, allowing the hash map
* to remain untouched even as the linked list entries get reordered.
*/
private class LRULinkedList
{
LRULinkedListEntry head = null;
LRULinkedListEntry tail = null;
int size = 0;
private LRULinkedList()
{
// Nothing to do
}
protected void finalize()
throws Throwable
{
clear();
super.finalize();
}
void addToTail (LRULinkedListEntry entry)
{
entry.next = null;
entry.previous = tail;
if (head == null)
{
head = entry;
tail = entry;
}
else
{
entry.previous = tail;
tail.next = entry;
}
size++;
}
void addToHead (LRULinkedListEntry entry)
{
entry.next = null;
entry.previous = null;
if (head == null)
{
assert (tail == null);
head = entry;
tail = entry;
}
else
{
entry.next = head;
head.previous = entry;
head = entry;
}
size++;
}
void remove (LRULinkedListEntry entry)
{
if (entry.next != null)
entry.next.previous = entry.previous;
if (entry.previous != null)
entry.previous.next = entry.next;
if (entry == head) // NOPMD (legal reference comparison)
head = entry.next;
if (entry == tail) // NOPMD (legal reference comparison)
tail = entry.previous;
entry.next = null;
entry.previous = null;
size--;
assert (size >= 0);
}
LRULinkedListEntry removeTail()
{
LRULinkedListEntry result = tail;
if (result != null)
remove (result);
return result;
}
void moveToHead (LRULinkedListEntry entry)
{
remove (entry);
addToHead (entry);
}
void clear()
{
while (head != null)
{
LRULinkedListEntry next = head.next;
head.next = null;
head.previous = null;
head.key = null;
head.value = null;
head = next;
}
tail = null;
size = 0;
}
}
/**
* Wraps any ObjectRemovalListener passed into addRemovalListener().
* Keeps track of both the listener and its "automaticOnly" status
*/
private static class RemovalListenerWrapper
implements ObjectRemovalListener
{
boolean automaticOnly;
ObjectRemovalListener realListener;
RemovalListenerWrapper (ObjectRemovalListener realListener,
boolean automaticOnly)
{
this.realListener = realListener;
this.automaticOnly = automaticOnly;
}
public void objectRemoved (ObjectRemovalEvent event)
{
realListener.objectRemoved (event);
}
}
/*----------------------------------------------------------------------*\
Private Static Variables
\*----------------------------------------------------------------------*/
/**
* See JDK 1.5 version of java.io.Serializable
*/
private static final long serialVersionUID = 1L;
/*----------------------------------------------------------------------*\
Type Aliases
\*----------------------------------------------------------------------*/
/**
* Type alias
*/
private class ListenerMap extends HashMap
{
ListenerMap()
{
super();
}
}
/**
* Type alias for actual hash table
*/
private class EntryMap extends HashMap
{
EntryMap (int initialCapacity, float loadFactor)
{
super (initialCapacity, loadFactor);
}
}
/*----------------------------------------------------------------------*\
Private Variables
\*----------------------------------------------------------------------*/
private int maxCapacity;
private float loadFactor;
private int initialCapacity;
private EntryMap hash;
private LRULinkedList lruQueue;
private ListenerMap removalListeners = null;
/*----------------------------------------------------------------------*\
Constructors
\*----------------------------------------------------------------------*/
/**
* Construct a new empty map with a default capacity and load factor,
* and the specified maximum capacity.
*
* @param maxCapacity the maximum number of entries permitted in the
* map. Must not be negative.
*/
public LRUMap (int maxCapacity)
{
this (DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, maxCapacity);
}
/**
* Construct a new empty map with the specified initial capacity,
* a default load factor, and the specified maximum capacity.
*
* @param initialCapacity the initial capacity
* @param maxCapacity the maximum number of entries permitted in the
* map. Must not be negative.
*/
public LRUMap (int initialCapacity, int maxCapacity)
{
this (initialCapacity, DEFAULT_LOAD_FACTOR, maxCapacity);
}
/**
* Constructs a new, empty map with the specified initial capacity,
* load factor, and maximum capacity.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param maxCapacity the maximum number of entries permitted in the
* map. Must not be negative.
*/
public LRUMap (int initialCapacity, float loadFactor, int maxCapacity)
{
assert (maxCapacity > 0);
assert (loadFactor > 0.0);
assert (initialCapacity > 0);
if (initialCapacity > maxCapacity)
initialCapacity = maxCapacity;
this.maxCapacity = maxCapacity;
this.loadFactor = loadFactor;
this.initialCapacity = initialCapacity;
this.hash = new EntryMap (initialCapacity, loadFactor);
this.lruQueue = new LRULinkedList();
}
/**
* Constructs a new map with the same mappings and parameters as the
* given LRUMap. The initial capacity and load factor is
* the same as for the parent HashMap class. The insertion
* order of the keys is preserved.
*
* @param map the map whose mappings are to be copied
*/
public LRUMap (LRUMap map)
{
this (map.initialCapacity, map.loadFactor, map.maxCapacity);
doPutAll (map);
}
/*----------------------------------------------------------------------*\
Public Methods
\*----------------------------------------------------------------------*/
/**
* Add an EventListener that will be called whenever an
* object is removed from the cache. If automaticOnly is
* true, then the listener is only notified for objects that
* are removed automatically when the cache needs to be cleared to make
* room for new objects. If automaticOnly is false,
* then the listener is notified whenever an object is removed for any
* reason, include a call to the {@link #remove remove()} method.
*
* Note that when this map announces the removal of an object, it
* passes an {@link ObjectRemovalEvent} that contains a
* java.util.Map.Entry object that wraps the actual object
* that was removed. That way, both the key and the value are available
* for the removed object.
*
* @param listener the listener to add
* @param automaticOnly see above
*
* @see #removeRemovalListener
*/
public synchronized void
addRemovalListener (ObjectRemovalListener listener, boolean automaticOnly)
{
if (removalListeners == null)
removalListeners = new ListenerMap();
removalListeners.put (listener,
new RemovalListenerWrapper (listener,
automaticOnly));
}
/**
* Remove an EventListener from the set of listeners to be invoked
* when an object is removed from the cache.
*
* @param listener the listener to add
*
* @return true if the listener was in the list and was removed,
* false otherwise
*
* @see #addRemovalListener
*/
public synchronized boolean
removeRemovalListener (ObjectRemovalListener listener)
{
boolean removed = false;
if ((removalListeners != null) &&
(removalListeners.remove(listener) != null))
{
removed = true;
}
return removed;
}
/**
* Remove all mappings from this map.
*/
public void clear()
{
hash.clear();
lruQueue.clear();
}
/**
* Determine whether this map contains a mapping for a given key. Note
* that this implementation of containsKey() does not refresh
* the object in the cache.
*
* @param key the key to find
*
* @return true if the key is in the map, false if not
*/
public boolean containsKey (Object key)
{
return hash.containsKey (key);
}
/**
* Determine whether this map contains a given value. Note that this
* implementation of containsValue() does not refresh the
* objects in the cache.
*
* @param value the value to find
*
* @return true if the value is in the map, false if not
*/
public boolean containsValue (Object value)
{
boolean contains = false;
for (LRULinkedListEntry entry : hash.values())
{
if (entry.getValue().equals(value))
{
contains = true;
break;
}
}
return contains;
}
/**
* Get a set view of the mappings in this map. Each element in this set
* is a Map.Entry. The collection is backed by the map, so
* changes to the map are reflected in the collection, and vice-versa.
* The collection supports element removal, which removes the
* corresponding mapping from the map, via the
* Iterator.remove, Collection.remove,
* removeAll, retainAll, and clear
* operations. It does not support the add or addAll
* operations.
*
* @return the entry set
*/
public Set> entrySet()
{
return new EntrySet();
}
/**
* Retrieve an object from the map. Retrieving an object from an
* LRU map "refreshes" the object so that it is among the most recently
* used objects.
*
* @param key the object's key in the map.
*
* @return the associated object, or null if not found
*/
public V get (Object key)
{
V value = null;
LRULinkedListEntry entry = (LRULinkedListEntry) hash.get (key);
if (entry != null)
{
// It's there. It's just been accessed, so move it to the
// top of the linked list.
assert (entry.key.equals (key)) :
"entry.key=" + entry.key + ", key=" + key;
lruQueue.moveToHead (entry);
value = entry.value;
}
return value;
}
/**
* Get the initial capacity of this LRUMap.
*
* @return the initial capacity, as passed to the constructor
*
* @see #getLoadFactor
* @see #getMaximumCapacity
*/
public int getInitialCapacity()
{
return initialCapacity;
}
/**
* Get the load factor for this LRUMap.
*
* @return the load factor, as passed to the constructor
*
* @see #getInitialCapacity
* @see #getMaximumCapacity
*/
public float getLoadFactor()
{
return loadFactor;
}
/**
* Get the maximum capacity of this LRUMap.
*
* @return the maximum capacity, as passed to the constructor
*
* @see #setMaximumCapacity
* @see #getLoadFactor
* @see #getInitialCapacity
*/
public int getMaximumCapacity()
{
return maxCapacity;
}
/**
* Determine whether this map is empty or not.
*
* @return true if the map has no mappings, false
* otherwise
*/
public boolean isEmpty()
{
return hash.isEmpty();
}
/**
* Return a Set view of the keys in the map. The set is
* backed by the map, so changes to the map are reflected in the set,
* and vice-versa. The set does supports element removal, which removes
* the corresponding mapping from this map; however, the
* Iterator returned by the set currently does not
* support element removal. The set does not support the add
* or addAll operations.
*
* @return the set of keys in this map
*/
public Set keySet()
{
return new KeySet();
}
/**
* Associates the specified value with the specified key in this map.
* If the key already has a value in this map, the existing value is
* replaced by the new value, and the old value is replaced. If the key
* already exists in the map, it is moved to the end of the key
* insertion order list.
*
* @param key the key with which the specified value is to be associated
* @param value the value to associate with the specified key
*
* @return the previous value associated with the key, or null if (a) there
* was no previous value, or (b) the previous value was a null
*/
public V put (K key, V value)
{
return doPut (key, value);
}
/**
* Copies all of the mappings from a specified map to this one. These
* mappings replace any mappings that this map had for any of the keys.
*
* @param map the map whose mappings are to be copied
*/
public void putAll (Map map)
{
doPutAll(map);
}
/**
* Removes the mapping for a key, if there is one.
*
* @param key the key to remove
*
* @return the previous value associated with the key, or null if (a) there
* was no previous value, or (b) the previous value was a null
*/
public V remove (Object key)
{
V value = null;
LRULinkedListEntry entry = (LRULinkedListEntry) hash.remove (key);
if (entry != null)
{
value = entry.value;
lruQueue.remove (entry);
callRemovalListeners (key, value, false);
}
assert (hash.size() == lruQueue.size);
return value;
}
/**
* Set or change the maximum capacity of this LRUMap. If the
* maximum capacity is reduced to less than the map's current size,
* then the map is reduced in size by discarding the oldest entries.
*
* @param newCapacity the new maximum capacity
*
* @return the old maximum capacity
*
* @see #getMaximumCapacity
*/
public int setMaximumCapacity (int newCapacity)
{
assert (newCapacity > 0);
int oldCapacity = this.maxCapacity;
clearTo (newCapacity);
this.maxCapacity = newCapacity;
return oldCapacity;
}
/**
* Get the number of entries in the map. Note that this value can
* temporarily exceed the maximum capacity of the map. See the class
* documentation for details.
*
* @return the number of entries in the map
*/
public int size()
{
return lruQueue.size;
}
/**
* Returns a collection view of the values contained in this map. The
* returned collection is a "thin" view of the values contained in
* this map. The collection contains proxies for the actual disk-resident
* values; the values themselves are not loaded until a
* Collection method such as contains() is called.
*
* The collection is backed by the map, so changes to the map are
* reflected in the set. If the map is modified while an iteration over
* the set is in progress, the results of the iteration are undefined.
* The set does not support any of the add() methods.
*
* Warning:: The toArray() methods can be dangerous,
* since they will attempt to load every value from the data file into
* an in-memory array.
*
* @return a collection view of the values contained in this map.
*
* @see #keySet
* @see #values
*/
public Collection values()
{
return new ValueSet();
}
/*----------------------------------------------------------------------*\
Protected Methods
\*----------------------------------------------------------------------*/
/**
* Returns a shallow copy of this instance. The keys and values themselves
* are not cloned.
*
* @return a shallow copy of this map
*
* @throws CloneNotSupportedException not cloneable
*/
protected Object clone()
throws CloneNotSupportedException
{
return new LRUMap (this);
}
/*----------------------------------------------------------------------*\
Private Methods
\*----------------------------------------------------------------------*/
private LRULinkedListEntry clearTo (int size)
{
assert (hash.size() == lruQueue.size);
LRULinkedListEntry oldTail = null;
while (lruQueue.size > size)
{
oldTail = lruQueue.removeTail();
assert (oldTail != null);
Object key = oldTail.key;
LRULinkedListEntry rem = (LRULinkedListEntry) hash.remove (key);
assert (rem != null);
assert (rem.key == key);
callRemovalListeners (key, rem.value, true);
}
assert (lruQueue.size <= size);
assert (hash.size() == lruQueue.size);
return oldTail;
}
private synchronized void callRemovalListeners (final Object key,
final Object value,
boolean automatic)
{
if (removalListeners != null)
{
for (Iterator it = removalListeners.values().iterator();
it.hasNext(); )
{
RemovalListenerWrapper l = (RemovalListenerWrapper) it.next();
if ((! automatic) && (l.automaticOnly))
continue;
Map.Entry entry = new Map.Entry()
{
public boolean equals (Object o)
{
return false;
}
public Object getKey()
{
return key;
}
public Object getValue()
{
return value;
}
public int hashCode()
{
return key.hashCode();
}
public Object setValue (Object val)
{
return null;
}
};
l.objectRemoved (new ObjectRemovalEvent (entry));
}
}
}
/**
* Actual implementation of putAll(). Extracted to a private method
* so it can be called from the constructor.
*
* @param map the map from which to extract values
*/
private void doPutAll(final Map map)
{
for (Iterator it = map.keySet().iterator();
it.hasNext(); )
{
K key = it.next();
V value = map.get (key);
doPut (key, value);
}
}
private V doPut(final K key, final V value)
{
// If the total number of entries is at capacity, then we need to
// remove one of them to make room. The linked list is a priority
// queue, of sorts, with least recently used items at the end. So
// remove the tail entries.
V oldValue = null;
LRULinkedListEntry entry = (LRULinkedListEntry) hash.get (key);
if (entry == null)
{
// Must add a new one. Clear out the cruft. Reuse the last
// cleared entry, though, rather than allocate a new object.
entry = clearTo (this.maxCapacity - 1);
if (entry == null)
entry = new LRULinkedListEntry (key, value);
else
entry.setKeyValue (key, value);
lruQueue.addToHead (entry);
hash.put (key, entry);
}
else
{
// We're replacing the value with a new one. Move the entry to
// the head of the list.
oldValue = entry.value;
entry.value = value;
lruQueue.moveToHead (entry);
}
return oldValue;
}
}
Ads help maintain this website.