Coverage Report

 /*
  * $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) );
     }
   }
 }
 
 
 
 

1		/*
2		* $Source$
3		* $Revision$
4		*
5		* Copyright (C) 2000 William Chesters
6		*
7		* Part of Melati (http://melati.org), a framework for the rapid
8		* development of clean, maintainable web applications.
9		*
10		* Melati is free software; Permission is granted to copy, distribute
11		* and/or modify this software under the terms either:
12		*
13		* a) the GNU General Public License as published by the Free Software
14		* Foundation; either version 2 of the License, or (at your option)
15		* any later version,
16		*
17		* or
18		*
19		* b) any version of the Melati Software License, as published
20		* at http://melati.org
21		*
22		* You should have received a copy of the GNU General Public License and
23		* the Melati Software License along with this program;
24		* if not, write to the Free Software Foundation, Inc.,
25		* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA to obtain the
26		* GNU General Public License and visit http://melati.org to obtain the
27		* Melati Software License.
28		*
29		* Feel free to contact the Developers of Melati (http://melati.org),
30		* if you would like to work out a different arrangement than the options
31		* outlined here. It is our intention to allow Melati to be used by as
32		* wide an audience as possible.
33		*
34		* This program is distributed in the hope that it will be useful,
35		* but WITHOUT ANY WARRANTY; without even the implied warranty of
36		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
37		* GNU General Public License for more details.
38		*
39		* Contact details for copyright holder:
40		*
41		* William Chesters <williamc At paneris.org>
42		* http://paneris.org/~williamc
43		* Obrechtstraat 114, 2517VX Den Haag, The Netherlands
44		*/
45
46		package org.melati.poem.util;
47
48		import java.lang.ref.ReferenceQueue;
49		import java.lang.ref.SoftReference;
50		import java.util.Enumeration;
51		import java.util.Hashtable;
52		import java.util.Vector;
53
54		import org.melati.poem.PoemException;
55
56		/**
57		* A store whose capacity has a guaranteed lower limit but whose upper limit
58		* is bounded by the amount of memory available to the JVM.
59		* The lower limit can be adjusted after cache creation.
60		*
61		* Elements added to the cache once the cache size exceeds the lower limit
62		* (the cache is full) force the least recently used (LRU) item off the held list.
63		* Items which are removed from the held list are not deleted but
64		* converted to soft references: available to be retrieved if they
65		* are not garbage collected first.
66		*
67		* The cache cannot contain nulls, as there would be no mechanism to
68		* distinguish between a held null value and an unheld value.
69		*
70		* There is no mechanism for invalidating the cache, reducing its size
71		* to zero mearly allows all its members to be garbage collected.
72		*
73		* Ideally, having been created, objects remain in the cache; however this
74		* is impracticable when the possible size of the sum of cached objects
75		* exceeds available memory.
76		*
77		* The performance of the cache depends upon the pattern of accesses to it.
78		* An LRU cache such as this assumes a normal distribution of accesses.
79		*
80		* The state of the cache can be monitored by using the reporting
81		* objects, see for example org.melati.admin.Status.
82		*
83		*/
84	6	public final class Cache {
85
86		/** A <code>key:value</code> pair. */
87		private interface Node {
88		/** The key. */
89		Object key();
90		/** The value. */
91		Object value();
92		}
93
94		/** A <code>node</code> in the cache, which is guaranteed to be there. */
95		private static class HeldNode implements Node {
96		Object key;
97		Object value;
98	6261	HeldNode nextMRU = null; // Next Most Recently Used node
99	6261	HeldNode prevMRU = null; // Previous Most Recently Used node
100
101	6261	HeldNode(Object key, Object value) {
102	6261	this.key = key;
103	6261	this.value = value;
104	6261	}
105
106		synchronized void putBefore(HeldNode nextMRU_P) {
107
108		//
109		// Before:
110		//
111		// 11 -A-> 00 -B-> 22 33 -E-> 44
112		// 11 <-C- 00 <-D- 22 33 <-F- 44
113		//
114		// After:
115		//
116		// 11 -G-> 22 33 -I-> 00 -J-> 44
117		// 11 <-H- 22 33 <-K- 00 <-L- 44
118		//
119		// What has to happen:
120		//
121		// A => G if 1 exists
122		// B => J
123		// C => K
124		// D => H if 2 exists
125		// E => I if 3 exists
126		// F => L if 4 exists
127		//
128
129	7507	if (this.nextMRU != null) // 2 exists
130	203	this.nextMRU.prevMRU = prevMRU; // D => H using C
131
132	7507	if (prevMRU != null) // 1 exists
133	1146	prevMRU.nextMRU = this.nextMRU; // A => G using B
134
135	7507	if (nextMRU_P != null) { // 4 exists
136	6991	if (nextMRU_P.prevMRU != null) // 3 exists
137		// this should never happen as nextMRU_P is always null or
138		// theMRU which always has a null prevMRU
139	0	nextMRU_P.prevMRU.nextMRU = this; // E => I
140	6991	prevMRU = nextMRU_P.prevMRU; // C => K using F
141	6991	nextMRU_P.prevMRU = this; // F => L
142		}
143		else
144	516	prevMRU = null; // C => K
145	7507	this.nextMRU = nextMRU_P; // B => J
146	7507	}
147
148		/**
149		* {@inheritDoc}
150		* @see org.melati.poem.util.Cache.Node#key()
151		*/
152		public Object key() {
153	146	return key;
154		}
155
156		/**
157		* {@inheritDoc}
158		* @see org.melati.poem.util.Cache.Node#value()
159		*/
160		public Object value() {
161	14197	return value;
162		}
163
164		/**
165		* {@inheritDoc}
166		* @see java.lang.Object#toString()
167		*/
168		public String toString() {
169	16	StringBuffer ret = new StringBuffer();
170	16	if(prevMRU == null)
171	11	ret.append("null");
172		else
173	5	ret.append(prevMRU.key());
174	16	ret.append(">>"+ key + "=" + value + ">>");
175	16	if(nextMRU == null)
176	11	ret.append("null");
177		else
178	5	ret.append(nextMRU.key());
179	16	return ret.toString();
180		}
181
182
183		}
184
185		/** A {@link SoftReference} node; that is one which can be reclaimed
186		* by the Garbage Collector before it throws an out of memory error.
187		*/
188		private static class DroppedNode extends SoftReference<Object> implements Node {
189
190		Object key;
191
192		/**
193		* Constructor.
194		* @param key cache key
195		* @param value Cache object
196		* @param queue reference queue
197		*/
198		DroppedNode(Object key, Object value, ReferenceQueue<Object> queue) {
199	59	super(value, queue);
200	59	this.key = key;
201	59	}
202
203		/**
204		* {@inheritDoc}
205		* @see org.melati.poem.util.Cache.Node#key()
206		*/
207		public Object key() {
208	0	return key;
209		}
210
211		/**
212		* {@inheritDoc}
213		* @see org.melati.poem.util.Cache.Node#value()
214		*/
215		public Object value() {
216	171	return this.get();
217		}
218		}
219
220	932	private Hashtable<Object, Object> table = new Hashtable<Object, Object>();
221	932	private HeldNode theMRU = null, theLRU = null;
222	932	private int heldNodes = 0;
223		private int maxSize;
224	932	private int collectedEver = 0;
225
226	932	private ReferenceQueue<Object> collectedValuesQueue = new ReferenceQueue<Object>();
227
228		// invariants:
229		// if theMRU != null, theMRU.prevMRU == null
230		// if theLRU != null, theLRU.nextMRU == null
231		// following theMRU gives you the same elements as following theLRU
232		// in the opposite order
233		// everything in the[ML]RU is in table as a HeldNode, and visa versa.
234		// heldNodes == length of the[ML]RU
235
236		/**
237		* Thrown if one or more problems are discovered with cache consistency.
238		*/
239		public class InconsistencyException extends PoemException {
240
241		/*serialVersionUID /
242		private static final long serialVersionUID = 1832694552964508864L;
243
244		public Vector<Object> problems;
245
246		/** Constructor. */
247		public InconsistencyException(Vector<Object> probs) {
248		this.problems = probs;
249		}
250
251		/**
252		* {@inheritDoc}
253		*/
254		public String getMessage() {
255		return EnumUtils.concatenated("\n", problems.elements());
256		}
257		}
258
259		/**
260		* @return a Vector of problematic nodes
261		*/
262		private Vector<Object> invariantBreaches() {
263	9	Vector<Object> probs = new Vector<Object>();
264
265	9	if (theMRU != null && theMRU.prevMRU != null)
266	0	probs.addElement("theMRU.prevMRU == " + theMRU.prevMRU);
267	9	if (theLRU != null && theLRU.nextMRU != null)
268	0	probs.addElement("theLRU.nextMRU == " + theLRU.nextMRU);
269
270	9	Object[] held = new Object[heldNodes];
271	9	Hashtable<HeldNode, Boolean> heldHash = new Hashtable<HeldNode, Boolean>();
272
273	9	int countML = 0;
274	43	for (HeldNode n = theMRU; n != null; n = n.nextMRU, ++countML) {
275	34	if (table.get(n.key()) != n)
276	0	probs.addElement("MRU list check: table.get(" + n + ".key()) == " + table.get(n.key()));
277	34	if (countML < heldNodes)
278	34	held[countML] = n;
279	34	heldHash.put(n, Boolean.TRUE);
280		}
281
282	9	if (countML != heldNodes)
283	0	probs.addElement(countML + " nodes in MRU->LRU not " + heldNodes);
284
285	9	Hashtable<Object,HeldNode> keys = new Hashtable<Object,HeldNode>();
286	9	int countLM = 0;
287	43	for (HeldNode n = theLRU; n != null; n = n.prevMRU, ++countLM) {
288	34	HeldNode oldn = (HeldNode)keys.get(n.key());
289	34	if (oldn != null)
290	0	probs.addElement("key " + n.key() + " duplicated in " + n + " and " +
291		oldn);
292	34	keys.put(n.key(), n);
293
294	34	if (table.get(n.key()) != n)
295	0	probs.addElement("LRU list check: table.get(" + n + ".key()) == " + table.get(n.key()));
296	34	if (countLM < heldNodes) {
297	34	int o = heldNodes - (1 + countLM);
298	34	if (n != held[o])
299	0	probs.addElement("lm[" + countLM + "] == " + n + " != ml[" +
300		o + "] == " + held[o]);
301		}
302		}
303
304	9	for (Enumeration<Object> nodes = table.elements(); nodes.hasMoreElements();) {
305	91	Node n = (Node)nodes.nextElement();
306	91	if (n instanceof HeldNode && !heldHash.containsKey(n))
307	0	probs.addElement(n + " in table but not MRU->LRU");
308	91	}
309
310	9	if (countLM != heldNodes)
311	0	probs.addElement(countLM + " nodes in LRU->MRU not " + heldNodes);
312
313	9	return probs;
314		}
315
316		/**
317		* This is too costly to run in production.
318		*/
319		private void assertInvariant() {
320	19004	boolean debug = false;
321	19004	if (debug) {
322	0	Vector<Object> probs = invariantBreaches();
323	0	if (probs.size() != 0) {
324	0	throw new InconsistencyException(probs);
325		}
326		}
327	19004	}
328
329		/**
330		* Constructor with maximum size.
331		* @param maxSize maximum size cache may grow to
332		*/
333	932	public Cache(int maxSize) {
334	932	setSize(maxSize);
335	932	}
336
337		/**
338		* Set maximum size of Cache.
339		* @param maxSize maximum size cache may grow to
340		*/
341		public void setSize(int maxSize) {
342	1657	if (maxSize < 0)
343	0	throw new IllegalArgumentException();
344	1657	this.maxSize = maxSize;
345	1657	}
346
347		/**
348		* Get maximum size of Cache.
349		*/
350		public int getSize() {
351	0	return maxSize;
352		}
353
354		/**
355		* Check whether the garbage collector has actually reclaimed any of
356		* our {@link SoftReference}s, should it have done so it will have
357		* placed the reference on the collected queue, this entry is then
358		* removed from the backing store.
359		*/
360		private synchronized void checkForGarbageCollection() {
361		DroppedNode collected;
362	23706	while ((collected = (DroppedNode)collectedValuesQueue.poll()) != null) {
363	0	table.remove(collected.key());
364	0	++collectedEver;
365		}
366	23706	}
367
368		/**
369		* Reduce number of units held in the cache, without changing
370		* its size.
371		*
372		* This is intended for cache maintenance, enabling only the
373		* most frequently used items to remain in the cache, whilst
374		* the others are dropped; where dropped means converted to a soft reference.
375		*
376		* @param maxSize_P maximum number of units to hold
377		*/
378		public synchronized void trim(int maxSize_P) {
379	6272	checkForGarbageCollection();
380
381	6272	HeldNode n = theLRU;
382	6329	while (n != null && heldNodes > maxSize_P) {
383	57	HeldNode nn = n.prevMRU;
384	57	n.putBefore(null);
385	57	table.put(n.key, new DroppedNode(n.key, n.value, collectedValuesQueue));
386	57	--heldNodes;
387	57	n = nn;
388	57	}
389
390	6272	if (n == null) {
391	344	theLRU = null;
392	344	theMRU = null;
393		} else
394	5928	theLRU = n;
395
396	6272	assertInvariant();
397	6272	}
398
399		/**
400		* Remove from cache.
401		*
402		* If key is not in the cache as a HeldNode then does nothing.
403		*
404		* @param key cache key field
405		*/
406		public synchronized void delete(Object key) {
407	118	Node n = (Node)table.get(key);
408	118	if (n == null)
409	0	return;
410
411	118	if (n instanceof HeldNode) {
412	118	HeldNode h = (HeldNode)n;
413
414	118	if (theLRU == h)
415	29	theLRU = h.prevMRU;
416	118	if (theMRU == h)
417	100	theMRU = h.nextMRU;
418
419	118	h.putBefore(null);
420
421	118	--heldNodes;
422		}
423
424	118	table.remove(key);
425
426	118	assertInvariant();
427	118	}
428
429		/**
430		* Add an Object to the cache.
431		*
432		* @param key the Object to use as a lookup
433		* @param value the Object to put in the cache
434		*/
435		public synchronized void put(Object key, Object value) {
436	6263	if (key == null \|\| value == null)
437	0	throw new NullPointerException();
438
439	6263	trim(maxSize);
440
441	6263	if (maxSize == 0) {
442	2	table.put(key, new DroppedNode(key, value, collectedValuesQueue));
443		} else {
444	6261	HeldNode node = new HeldNode(key, value);
445
446	6261	Object previous = table.put(key, node);
447	6261	if (previous != null) {
448		// Return cache to previous state
449	0	table.put(key, previous);
450	0	throw new CacheDuplicationException("Key already in cache for key=" + key + ", value="+value);
451		}
452
453	6261	node.putBefore(theMRU);
454	6261	theMRU = node;
455	6261	if (theLRU == null) theLRU = node;
456
457	6261	++heldNodes;
458
459	6261	assertInvariant();
460		}
461	6263	}
462
463		/**
464		* Return an object from the Cache, null if not found.
465		* @param key the cache key
466		* @return the object or null if not in cache
467		*/
468		public synchronized Object get(Object key) {
469
470	15761	checkForGarbageCollection();
471
472	15761	Node node = (Node)table.get(key);
473	15761	if (node == null)
474	9408	return null;
475		else {
476		HeldNode held;
477	6353	if (node instanceof HeldNode) {
478	6353	held = (HeldNode)node;
479	6353	if (held != theMRU) {
480	1071	if (held == theLRU)
481	957	theLRU = held.prevMRU;
482	1071	held.putBefore(theMRU);
483	1071	theMRU = held;
484		}
485		} else { // It is a DroppedNode ie SoftReference - which may be mangled
486	0	if (node.value() == null)
487		// This seems actually to happen
488		// which means that the value has been collected since
489		// the call to checkForGarbageCollection() above
490	0	return null;
491	0	held = new HeldNode(key, node.value());
492	0	table.put(key, held);
493	0	++heldNodes;
494	0	held.putBefore(theMRU);
495	0	theMRU = held;
496	0	if (theLRU == null)
497	0	theLRU = held;
498	0	trim(maxSize);
499		}
500
501	6353	assertInvariant();
502	6353	return held.value;
503		}
504		}
505
506		/**
507		* Apply function to all items in cache, only ignoring items
508		* where the value has been garbage collected.
509		*
510		* @param f Procedure to apply to all members of cache
511		*/
512		public synchronized void iterate(Procedure f) {
513	1670	checkForGarbageCollection();
514	1670	for (Enumeration<Object> n = table.elements(); n.hasMoreElements();) {
515	14356	Object value = ((Node)n.nextElement()).value();
516	14356	if (value != null)
517		// Value could conceivably have been nulled since call to checkForGarbageCollection above
518	14356	f.apply(value);
519	14356	}
520	1670	}
521
522		/**
523		* Report on the status of the cache.
524		* @return an Enumeration of report lines
525		*/
526		public Enumeration<Object> getReport() {
527	9	return new ConsEnumeration<Object>("" +
528		maxSize + " maxSize, " +
529		theMRU + " theMRU, " +
530		theLRU + " theLRU, " +
531		collectedEver + " collectedEver",
532		new ConsEnumeration<Object>(
533	9	heldNodes + " held, " + table.size() + " total ",
534	9	invariantBreaches().elements()));
535		}
536
537		/**
538		* A class which enables reporting upon the state of the <code>Cache</code>.
539		*/
540	3	public final class Info {
541
542	3	private Info() {}
543
544		/**
545		* @return an Enumeration of objects held
546		*/
547		public Enumeration<Object> getHeldElements() {
548	3	checkForGarbageCollection();
549	3	return new MappedEnumeration<Object, Object>(
550	3	new FilteredEnumeration<Object>(table.elements()) {
551		public boolean isIncluded(Object o) {
552	12	return o instanceof HeldNode;
553		}
554	3	}) {
555		public Object mapped(Object o) {
556	12	return ((Node)o).value();
557		}
558		};
559		}
560
561		/**
562		* @return an Enumeration of elements dropped from the cache
563		*/
564		public Enumeration<Object> getDroppedElements() {
565	0	checkForGarbageCollection();
566	0	return new MappedEnumeration<Object, Object>(
567	0	new FilteredEnumeration<Object>(table.elements()) {
568		public boolean isIncluded(Object o) {
569	0	return o instanceof DroppedNode;
570		}
571	0	}) {
572		public Object mapped(Object o) {
573	0	return ((Node)o).value();
574		}
575		};
576		}
577
578		/**
579		* @return the report
580		*/
581		public Enumeration<Object> getReport() {
582	0	return Cache.this.getReport();
583		}
584
585
586		}
587
588		/**
589		* @return a new Info object
590		*/
591		public Info getInfo() {
592	3	return new Info();
593		}
594
595		/**
596		* Dump to Syserr.
597		*/
598		public void dumpAnalysis() {
599	9	for (Enumeration<Object> l = getReport(); l.hasMoreElements();)
600	18	System.err.println(l.nextElement());
601	9	}
602
603		/**
604		* Output to syserr.
605		*/
606		public void dump() {
607	0	System.err.println("Keys: " + table.size());
608	0	System.err.println("maxSize: " + maxSize);
609	0	System.err.println("theMRU: " + theMRU);
610	0	System.err.println("theLRU: " + theLRU);
611	0	System.err.println("heldNodes: " + heldNodes);
612	0	System.err.println("collectedEver: " + collectedEver);
613	0	Enumeration<Object> e = table.keys();
614	0	while(e.hasMoreElements()) {
615	0	Object k = e.nextElement();
616	0	System.err.print(k );
617	0	System.err.print(" : ");
618	0	System.err.println(table.get(k) );
619	0	}
620	0	}
621		}
622
623
624
625