Cache.java
/*
* $Source$
* $Revision$
*
* Copyright (C) 2000 William Chesters
*
* Part of Melati (http://melati.org), a framework for the rapid
* development of clean, maintainable web applications.
*
* Melati is free software; Permission is granted to copy, distribute
* and/or modify this software under the terms either:
*
* a) the GNU General Public License as published by the Free Software
* Foundation; either version 2 of the License, or (at your option)
* any later version,
*
* or
*
* b) any version of the Melati Software License, as published
* at http://melati.org
*
* You should have received a copy of the GNU General Public License and
* the Melati Software License along with this program;
* if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA to obtain the
* GNU General Public License and visit http://melati.org to obtain the
* Melati Software License.
*
* Feel free to contact the Developers of Melati (http://melati.org),
* if you would like to work out a different arrangement than the options
* outlined here. It is our intention to allow Melati to be used by as
* wide an audience as possible.
*
* This program 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 General Public License for more details.
*
* Contact details for copyright holder:
*
* William Chesters <williamc At paneris.org>
* http://paneris.org/~williamc
* Obrechtstraat 114, 2517VX Den Haag, The Netherlands
*/
package org.melati.poem.util;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;
import org.melati.poem.PoemException;
/**
* A store whose capacity has a guaranteed lower limit but whose upper limit
* is bounded by the amount of memory available to the JVM.
* The lower limit can be adjusted after cache creation.
*
* Elements added to the cache once the cache size exceeds the lower limit
* (the cache is full) force the least recently used (LRU) item off the held list.
* Items which are removed from the held list are not deleted but
* converted to soft references: available to be retrieved if they
* are not garbage collected first.
*
* The cache cannot contain nulls, as there would be no mechanism to
* distinguish between a held null value and an unheld value.
*
* There is no mechanism for invalidating the cache, reducing its size
* to zero mearly allows all its members to be garbage collected.
*
* Ideally, having been created, objects remain in the cache; however this
* is impracticable when the possible size of the sum of cached objects
* exceeds available memory.
*
* The performance of the cache depends upon the pattern of accesses to it.
* An LRU cache such as this assumes a normal distribution of accesses.
*
* The state of the cache can be monitored by using the reporting
* objects, see for example org.melati.admin.Status.
*
*/
public final class Cache {
/** A <code>key:value</code> pair. */
private interface Node {
/** The key. */
Object key();
/** The value. */
Object value();
}
/** A <code>node</code> in the cache, which is guaranteed to be there. */
private static class HeldNode implements Node {
Object key;
Object value;
HeldNode nextMRU = null; // Next Most Recently Used node
HeldNode prevMRU = null; // Previous Most Recently Used node
HeldNode(Object key, Object value) {
this.key = key;
this.value = value;
}
synchronized void putBefore(HeldNode nextMRU_P) {
//
// Before:
//
// 11 -A-> 00 -B-> 22 33 -E-> 44
// 11 <-C- 00 <-D- 22 33 <-F- 44
//
// After:
//
// 11 -G-> 22 33 -I-> 00 -J-> 44
// 11 <-H- 22 33 <-K- 00 <-L- 44
//
// What has to happen:
//
// A => G if 1 exists
// B => J
// C => K
// D => H if 2 exists
// E => I if 3 exists
// F => L if 4 exists
//
if (this.nextMRU != null) // 2 exists
this.nextMRU.prevMRU = prevMRU; // D => H using C
if (prevMRU != null) // 1 exists
prevMRU.nextMRU = this.nextMRU; // A => G using B
if (nextMRU_P != null) { // 4 exists
if (nextMRU_P.prevMRU != null) // 3 exists
// this should never happen as nextMRU_P is always null or
// theMRU which always has a null prevMRU
nextMRU_P.prevMRU.nextMRU = this; // E => I
prevMRU = nextMRU_P.prevMRU; // C => K using F
nextMRU_P.prevMRU = this; // F => L
}
else
prevMRU = null; // C => K
this.nextMRU = nextMRU_P; // B => J
}
/**
* {@inheritDoc}
* @see org.melati.poem.util.Cache.Node#key()
*/
public Object key() {
return key;
}
/**
* {@inheritDoc}
* @see org.melati.poem.util.Cache.Node#value()
*/
public Object value() {
return value;
}
/**
* {@inheritDoc}
* @see java.lang.Object#toString()
*/
public String toString() {
StringBuffer ret = new StringBuffer();
if(prevMRU == null)
ret.append("null");
else
ret.append(prevMRU.key());
ret.append(">>"+ key + "=" + value + ">>");
if(nextMRU == null)
ret.append("null");
else
ret.append(nextMRU.key());
return ret.toString();
}
}
/** A {@link SoftReference} node; that is one which can be reclaimed
* by the Garbage Collector before it throws an out of memory error.
*/
private static class DroppedNode extends SoftReference<Object> implements Node {
Object key;
/**
* Constructor.
* @param key cache key
* @param value Cache object
* @param queue reference queue
*/
DroppedNode(Object key, Object value, ReferenceQueue<Object> queue) {
super(value, queue);
this.key = key;
}
/**
* {@inheritDoc}
* @see org.melati.poem.util.Cache.Node#key()
*/
public Object key() {
return key;
}
/**
* {@inheritDoc}
* @see org.melati.poem.util.Cache.Node#value()
*/
public Object value() {
return this.get();
}
}
private Hashtable<Object, Object> table = new Hashtable<Object, Object>();
private HeldNode theMRU = null, theLRU = null;
private int heldNodes = 0;
private int maxSize;
private int collectedEver = 0;
private ReferenceQueue<Object> collectedValuesQueue = new ReferenceQueue<Object>();
// invariants:
// if theMRU != null, theMRU.prevMRU == null
// if theLRU != null, theLRU.nextMRU == null
// following theMRU gives you the same elements as following theLRU
// in the opposite order
// everything in the[ML]RU is in table as a HeldNode, and visa versa.
// heldNodes == length of the[ML]RU
/**
* Thrown if one or more problems are discovered with cache consistency.
*/
public class InconsistencyException extends PoemException {
/**serialVersionUID */
private static final long serialVersionUID = 1832694552964508864L;
public Vector<Object> problems;
/** Constructor. */
public InconsistencyException(Vector<Object> probs) {
this.problems = probs;
}
/**
* {@inheritDoc}
*/
public String getMessage() {
return EnumUtils.concatenated("\n", problems.elements());
}
}
/**
* @return a Vector of problematic nodes
*/
private Vector<Object> invariantBreaches() {
Vector<Object> probs = new Vector<Object>();
if (theMRU != null && theMRU.prevMRU != null)
probs.addElement("theMRU.prevMRU == " + theMRU.prevMRU);
if (theLRU != null && theLRU.nextMRU != null)
probs.addElement("theLRU.nextMRU == " + theLRU.nextMRU);
Object[] held = new Object[heldNodes];
Hashtable<HeldNode, Boolean> heldHash = new Hashtable<HeldNode, Boolean>();
int countML = 0;
for (HeldNode n = theMRU; n != null; n = n.nextMRU, ++countML) {
if (table.get(n.key()) != n)
probs.addElement("MRU list check: table.get(" + n + ".key()) == " + table.get(n.key()));
if (countML < heldNodes)
held[countML] = n;
heldHash.put(n, Boolean.TRUE);
}
if (countML != heldNodes)
probs.addElement(countML + " nodes in MRU->LRU not " + heldNodes);
Hashtable<Object,HeldNode> keys = new Hashtable<Object,HeldNode>();
int countLM = 0;
for (HeldNode n = theLRU; n != null; n = n.prevMRU, ++countLM) {
HeldNode oldn = (HeldNode)keys.get(n.key());
if (oldn != null)
probs.addElement("key " + n.key() + " duplicated in " + n + " and " +
oldn);
keys.put(n.key(), n);
if (table.get(n.key()) != n)
probs.addElement("LRU list check: table.get(" + n + ".key()) == " + table.get(n.key()));
if (countLM < heldNodes) {
int o = heldNodes - (1 + countLM);
if (n != held[o])
probs.addElement("lm[" + countLM + "] == " + n + " != ml[" +
o + "] == " + held[o]);
}
}
for (Enumeration<Object> nodes = table.elements(); nodes.hasMoreElements();) {
Node n = (Node)nodes.nextElement();
if (n instanceof HeldNode && !heldHash.containsKey(n))
probs.addElement(n + " in table but not MRU->LRU");
}
if (countLM != heldNodes)
probs.addElement(countLM + " nodes in LRU->MRU not " + heldNodes);
return probs;
}
/**
* This is too costly to run in production.
*/
private void assertInvariant() {
boolean debug = false;
if (debug) {
Vector<Object> probs = invariantBreaches();
if (probs.size() != 0) {
throw new InconsistencyException(probs);
}
}
}
/**
* Constructor with maximum size.
* @param maxSize maximum size cache may grow to
*/
public Cache(int maxSize) {
setSize(maxSize);
}
/**
* Set maximum size of Cache.
* @param maxSize maximum size cache may grow to
*/
public void setSize(int maxSize) {
if (maxSize < 0)
throw new IllegalArgumentException();
this.maxSize = maxSize;
}
/**
* Get maximum size of Cache.
*/
public int getSize() {
return maxSize;
}
/**
* Check whether the garbage collector has actually reclaimed any of
* our {@link SoftReference}s, should it have done so it will have
* placed the reference on the collected queue, this entry is then
* removed from the backing store.
*/
private synchronized void checkForGarbageCollection() {
DroppedNode collected;
while ((collected = (DroppedNode)collectedValuesQueue.poll()) != null) {
table.remove(collected.key());
++collectedEver;
}
}
/**
* Reduce number of units held in the cache, without changing
* its size.
*
* This is intended for cache maintenance, enabling only the
* most frequently used items to remain in the cache, whilst
* the others are dropped; where dropped means converted to a soft reference.
*
* @param maxSize_P maximum number of units to hold
*/
public synchronized void trim(int maxSize_P) {
checkForGarbageCollection();
HeldNode n = theLRU;
while (n != null && heldNodes > maxSize_P) {
HeldNode nn = n.prevMRU;
n.putBefore(null);
table.put(n.key, new DroppedNode(n.key, n.value, collectedValuesQueue));
--heldNodes;
n = nn;
}
if (n == null) {
theLRU = null;
theMRU = null;
} else
theLRU = n;
assertInvariant();
}
/**
* Remove from cache.
*
* If key is not in the cache as a HeldNode then does nothing.
*
* @param key cache key field
*/
public synchronized void delete(Object key) {
Node n = (Node)table.get(key);
if (n == null)
return;
if (n instanceof HeldNode) {
HeldNode h = (HeldNode)n;
if (theLRU == h)
theLRU = h.prevMRU;
if (theMRU == h)
theMRU = h.nextMRU;
h.putBefore(null);
--heldNodes;
}
table.remove(key);
assertInvariant();
}
/**
* Add an Object to the cache.
*
* @param key the Object to use as a lookup
* @param value the Object to put in the cache
*/
public synchronized void put(Object key, Object value) {
if (key == null || value == null)
throw new NullPointerException();
trim(maxSize);
if (maxSize == 0) {
table.put(key, new DroppedNode(key, value, collectedValuesQueue));
} else {
HeldNode node = new HeldNode(key, value);
Object previous = table.put(key, node);
if (previous != null) {
// Return cache to previous state
table.put(key, previous);
throw new CacheDuplicationException("Key already in cache for key=" + key + ", value="+value);
}
node.putBefore(theMRU);
theMRU = node;
if (theLRU == null) theLRU = node;
++heldNodes;
assertInvariant();
}
}
/**
* Return an object from the Cache, null if not found.
* @param key the cache key
* @return the object or null if not in cache
*/
public synchronized Object get(Object key) {
checkForGarbageCollection();
Node node = (Node)table.get(key);
if (node == null)
return null;
else {
HeldNode held;
if (node instanceof HeldNode) {
held = (HeldNode)node;
if (held != theMRU) {
if (held == theLRU)
theLRU = held.prevMRU;
held.putBefore(theMRU);
theMRU = held;
}
} else { // It is a DroppedNode ie SoftReference - which may be mangled
if (node.value() == null)
// This seems actually to happen
// which means that the value has been collected since
// the call to checkForGarbageCollection() above
return null;
held = new HeldNode(key, node.value());
table.put(key, held);
++heldNodes;
held.putBefore(theMRU);
theMRU = held;
if (theLRU == null)
theLRU = held;
trim(maxSize);
}
assertInvariant();
return held.value;
}
}
/**
* Apply function to all items in cache, only ignoring items
* where the value has been garbage collected.
*
* @param f Procedure to apply to all members of cache
*/
public synchronized void iterate(Procedure f) {
checkForGarbageCollection();
for (Enumeration<Object> n = table.elements(); n.hasMoreElements();) {
Object value = ((Node)n.nextElement()).value();
if (value != null)
// Value could conceivably have been nulled since call to checkForGarbageCollection above
f.apply(value);
}
}
/**
* Report on the status of the cache.
* @return an Enumeration of report lines
*/
public Enumeration<Object> getReport() {
return new ConsEnumeration<Object>("" +
maxSize + " maxSize, " +
theMRU + " theMRU, " +
theLRU + " theLRU, " +
collectedEver + " collectedEver",
new ConsEnumeration<Object>(
heldNodes + " held, " + table.size() + " total ",
invariantBreaches().elements()));
}
/**
* A class which enables reporting upon the state of the <code>Cache</code>.
*/
public final class Info {
private Info() {}
/**
* @return an Enumeration of objects held
*/
public Enumeration<Object> getHeldElements() {
checkForGarbageCollection();
return new MappedEnumeration<Object, Object>(
new FilteredEnumeration<Object>(table.elements()) {
public boolean isIncluded(Object o) {
return o instanceof HeldNode;
}
}) {
public Object mapped(Object o) {
return ((Node)o).value();
}
};
}
/**
* @return an Enumeration of elements dropped from the cache
*/
public Enumeration<Object> getDroppedElements() {
checkForGarbageCollection();
return new MappedEnumeration<Object, Object>(
new FilteredEnumeration<Object>(table.elements()) {
public boolean isIncluded(Object o) {
return o instanceof DroppedNode;
}
}) {
public Object mapped(Object o) {
return ((Node)o).value();
}
};
}
/**
* @return the report
*/
public Enumeration<Object> getReport() {
return Cache.this.getReport();
}
}
/**
* @return a new Info object
*/
public Info getInfo() {
return new Info();
}
/**
* Dump to Syserr.
*/
public void dumpAnalysis() {
for (Enumeration<Object> l = getReport(); l.hasMoreElements();)
System.err.println(l.nextElement());
}
/**
* Output to syserr.
*/
public void dump() {
System.err.println("Keys: " + table.size());
System.err.println("maxSize: " + maxSize);
System.err.println("theMRU: " + theMRU);
System.err.println("theLRU: " + theLRU);
System.err.println("heldNodes: " + heldNodes);
System.err.println("collectedEver: " + collectedEver);
Enumeration<Object> e = table.keys();
while(e.hasMoreElements()) {
Object k = e.nextElement();
System.err.print(k );
System.err.print(" : ");
System.err.println(table.get(k) );
}
}
}