001: /**********************************************************************************
002: * $URL: https://source.sakaiproject.org/svn/presentation/tags/sakai_2-4-1/api-impl/src/java/org/sakaiproject/component/app/presentation/CacheMap.java $
003: * $Id: CacheMap.java 8654 2006-05-02 01:40:40Z ggolden@umich.edu $
004: ***********************************************************************************
005: *
006: * Copyright (c) 2004, 2005, 2006 The Sakai Foundation.
007: *
008: * Licensed under the Educational Community License, Version 1.0 (the "License");
009: * you may not use this file except in compliance with the License.
010: * You may obtain a copy of the License at
011: *
012: * http://www.opensource.org/licenses/ecl1.php
013: *
014: * Unless required by applicable law or agreed to in writing, software
015: * distributed under the License is distributed on an "AS IS" BASIS,
016: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: * See the License for the specific language governing permissions and
018: * limitations under the License.
019: *
020: **********************************************************************************/package org.sakaiproject.component.app.presentation;
021:
022: import java.util.Hashtable;
023: import java.util.Iterator;
024: import java.util.LinkedList;
025:
026: public class CacheMap {
027: /** A Hash Table to store the actual proxies */
028: private Hashtable m_map = null;
029:
030: /** A linked list to store the IDs in a "FIFO" queue */
031: private LinkedList m_queue = null;
032:
033: /** The time to cache the objects (seconds) */
034: private int m_cacheTime = 300;
035:
036: /** The maximum size of the cachemap */
037: private int m_cacheSize = 20;
038:
039: /** The title for this Cache */
040: private String m_title = null;
041:
042: /** Whether or not we log debug messages */
043: private boolean m_debug = false;
044:
045: /** The count between status messages */
046: private long m_messageCount = -1;
047:
048: /** Used to record the recent activity */
049: private long totalHits = 0;
050: private long totalGets = 0;
051: private long totalPuts = 0;
052: private final long TRY_HISTORY = 1000000; // Avoid overflow
053:
054: public CacheMap(int cacheTime, int cacheSize, String title,
055: int messageCount, boolean debug) {
056: // Create the data structures
057: if (cacheSize < 10)
058: cacheSize = 10;
059: m_map = new Hashtable(cacheSize);
060: m_queue = new LinkedList();
061:
062: if (cacheTime < 1)
063: cacheTime = 1;
064: m_cacheTime = cacheTime;
065: m_cacheSize = cacheSize;
066: m_title = title;
067: m_debug = debug;
068: if (messageCount <= 0)
069: m_messageCount = -1;
070: else
071: m_messageCount = messageCount;
072: }
073:
074: public CacheMap(int cacheTime, int cacheSize, String title) {
075: this (cacheTime, cacheSize, title, -1, false);
076: }
077:
078: private class CacheMapEntry {
079: private Object obj;
080: private long time;
081: private int hits;
082:
083: CacheMapEntry(Object obj) {
084: this .obj = obj;
085: this .time = System.currentTimeMillis() / 1000;
086: hits = 0;
087: }
088:
089: public long getTime() {
090: return time;
091: }
092:
093: public Object getObject() {
094: return obj;
095: }
096:
097: public int getHits() {
098: return hits;
099: }
100:
101: public void recordHit() {
102: hits++;
103: }
104: }
105:
106: private boolean checkAndExpire(Object key, CacheMapEntry entry) {
107: // Check to see if it is old
108: long starttime = (System.currentTimeMillis() / 1000);
109: long timeDifference = Math.abs(entry.getTime() - starttime);
110:
111: boolean expired = (timeDifference > m_cacheTime);
112:
113: /*
114: System.out.println("Found id="+key+" time="+entry.getTime()+" hits="+entry.getHits()+
115: " starttime="+starttime+" diff="+timeDifference+" expired="+expired);
116: */
117:
118: if (expired) {
119: Object removed = m_map.remove(key);
120: m_queue.remove(key);
121: }
122: return expired;
123: }
124:
125: private void sanityCheck() {
126: if (m_map.isEmpty() == true)
127: return;
128: if (m_queue.isEmpty() == true)
129: return;
130:
131: if (m_map.size() != m_queue.size()) {
132: System.out.println(toString()
133: + " Error: FIFO/Hash length mis-match");
134: clear();
135: }
136:
137: // Extreme sanity check - only run in test mode and on small Caches
138: if (!m_debug)
139: return;
140:
141: if (m_cacheSize > 200)
142: return;
143:
144: for (Iterator i = m_queue.iterator(); i.hasNext();) {
145: Object key = i.next();
146:
147: if (!m_map.containsKey(key)) {
148: System.out.println(toString());
149: System.out
150: .println("**** ERROR **** Missing key:" + key);
151: }
152: }
153:
154: }
155:
156: /**
157: * Retrieve an element
158: */
159: private CacheMapEntry internalGet(Object key) {
160: if (m_map.isEmpty() == true)
161: return null;
162:
163: if (m_map.containsKey(key) == false) {
164: return null;
165: } else {
166: CacheMapEntry entry = (CacheMapEntry) m_map.get(key);
167: entry.recordHit();
168: return entry;
169: }
170: }
171:
172: private void doStatus() {
173: if (m_messageCount != -1
174: && ((totalGets + totalPuts) % m_messageCount) == 0) {
175: System.out.println(toString());
176: }
177:
178: if (totalGets >= TRY_HISTORY || totalPuts >= TRY_HISTORY) {
179: totalGets = 0;
180: totalPuts = 0;
181: totalHits = 0;
182: }
183: }
184:
185: public String toString() {
186: long hits;
187: if (totalGets == 0)
188: hits = 0;
189: else
190: hits = (totalHits * 100) / totalGets;
191:
192: return "CacheMap:" + m_title + " Put/Get/Hit=" + totalPuts
193: + "/" + totalGets + "/" + totalHits + " " + hits
194: + "% size=" + m_map.size() + "/" + m_queue.size();
195: }
196:
197: /**
198: * Check to see if the oldest entry in the table needs to expire.
199: */
200: public void expireTop() {
201: if (m_map.isEmpty() == true)
202: return;
203: if (m_queue.isEmpty() == true)
204: return;
205:
206: // Check the first entry in the FIFO list
207: Object topEntry = m_queue.getFirst();
208:
209: // If we are too large, simply expire the top entry
210: if (m_queue.size() >= m_cacheSize) {
211: Object entry = m_map.remove(topEntry);
212: m_queue.remove(topEntry);
213: // if ( m_debug ) System.out.println(toString()+" List length exceeded "+m_cacheSize);
214: }
215:
216: // Retrieve it from the cache to check expiration time
217: CacheMapEntry entry = (CacheMapEntry) internalGet(topEntry);
218: if (entry == null) {
219: System.out.println(toString()
220: + " Top FIFO entry not in Hash:" + topEntry);
221: topEntry = m_queue.removeFirst();
222: return;
223: }
224:
225: if (checkAndExpire(topEntry, entry))
226: return;
227: }
228:
229: /*
230: * Run through all entries and expire the entries - probably not a good idea
231: *
232: * In general this should not be needed as the structures are self-maintaining in the
233: * normal get and put methods, but for a large cache where the application knows that it
234: * will not be using the contents for a while, this may be useful.
235: *
236: * The performance of this method is O(N ** 2) because it copies and then loops through
237: * the LinkedList O(N) and then potentially deletes every expired item
238: * separately (each O(N))
239: *
240: * Another option is just use clear() or throw the cache away and re-create it - other than
241: * garbage collection issues, throwing the structure away and re-creating it is
242: * nominally O(1) - but with GC factored should be thought of as O(N) - which is still
243: * better than O(N ** 2).
244: */
245:
246: public void expireAll() {
247: if (m_map.isEmpty() == true)
248: return;
249: if (m_queue.isEmpty() == true)
250: return;
251:
252: // Make copy of linked list so as we clean up, we can safely continue to iterate
253: LinkedList localList = new LinkedList(m_queue);
254:
255: for (Iterator i = localList.iterator(); i.hasNext();) {
256: Object key = i.next();
257:
258: CacheMapEntry entry = (CacheMapEntry) internalGet(key);
259: if (entry == null) {
260: System.out.println(toString()
261: + " expireAll() Not in Hash:" + key);
262: m_queue.remove(key);
263: continue;
264: }
265: checkAndExpire(key, entry);
266: }
267:
268: }
269:
270: /*
271: * Clear the underlying structures
272: */
273:
274: public void clear() {
275: m_queue.clear();
276: m_map.clear();
277:
278: totalGets = 0;
279: totalPuts = 0;
280: totalHits = 0;
281: }
282:
283: public void put(Object key, Object value) {
284: if (m_debug)
285: System.out.println("Adding key=" + key);
286: doStatus();
287: sanityCheck();
288: expireTop(); // Expire top on gets and puts to "catch up"
289:
290: totalPuts++;
291: m_queue.remove(key);
292: m_map.put(key, new CacheMapEntry(value)); // Replaces if already there
293: m_queue.add(key);
294: }
295:
296: /**
297: * Retrieve an element
298: */
299: public Object get(Object key) {
300: if (m_debug)
301: System.out.println(" Getting key=" + key);
302: doStatus();
303: sanityCheck();
304: expireTop(); // First, expire the latest entry, if it exists
305:
306: totalGets++;
307: CacheMapEntry entry = internalGet(key);
308:
309: if (entry == null)
310: return null;
311: if (checkAndExpire(key, entry))
312: return null;
313:
314: totalHits++;
315: return entry.getObject();
316: }
317: }
|