001: package com.knowgate.cache;
002:
003: import java.util.HashMap;
004: import com.knowgate.debug.DebugFile;
005:
006: /**
007: * <p>LRU Cache Policy</p>
008: * <p>Implementation of a Least Recently Used cache policy.</p>
009: * @author Simone Bordet <simone.bordet@compaq.com>
010: * @version 1.3.2.1
011: */
012:
013: public final class LRUCachePolicy {
014:
015: // Attributes ----------------------------------------------------
016:
017: /**
018: * The map holding the cached objects
019: */
020:
021: protected HashMap m_map;
022:
023: /**
024: * The linked list used to implement the LRU algorithm
025: */
026:
027: protected LRUList m_list;
028:
029: /**
030: * The maximum capacity of this cache
031: */
032:
033: protected int m_maxCapacity;
034:
035: /**
036: * The minimum capacity of this cache
037: */
038:
039: protected int m_minCapacity;
040:
041: // Constructors --------------------------------------------------
042:
043: /**
044: * Creates a LRU cache policy object with zero cache capacity.
045: *
046: * @see #create
047: */
048:
049: public LRUCachePolicy() {
050: }
051:
052: /**
053: * Creates a LRU cache policy object with the specified minimum and maximum capacity.
054: *
055: * @see #create
056: */
057:
058: public LRUCachePolicy(int min, int max) {
059: if (min < 2 || min > max) {
060: throw new IllegalArgumentException(
061: "Illegal cache capacities");
062: }
063: m_minCapacity = min;
064: m_maxCapacity = max;
065:
066: create();
067: }
068:
069: // Service implementation ----------------------------------------------
070:
071: /**
072: * Initializes the cache, creating all required objects and initializing their
073: * values.
074: * @see #start
075: * @see #destroy
076: */
077:
078: private void create() {
079:
080: m_map = new HashMap(211);
081: m_list = createList();
082: m_list.m_maxCapacity = m_maxCapacity;
083: m_list.m_minCapacity = m_minCapacity;
084: m_list.m_capacity = m_maxCapacity;
085: }
086:
087: /**
088: * Starts this cache that is now ready to be used.
089: * @see #create
090: * @see #stop
091: */
092:
093: public void start() {
094: }
095:
096: /**
097: * Stops this cache thus {@link #flush}ing all cached objects. <br>
098: * After this method is called, a call to {@link #start} will restart the cache.
099: * @see #start
100: * @see #destroy
101: */
102:
103: public void stop() {
104: if (m_list != null) {
105: flush();
106: }
107: }
108:
109: /**
110: * Destroys the cache that is now unusable. <br>
111: * To have it working again it must be re-{@link #create}ed and re-{@link #start}ed.
112: *
113: * @see #create
114: */
115:
116: public void destroy() {
117:
118: if (m_map != null) {
119: m_map.clear();
120:
121: }
122: if (m_list != null) {
123: m_list.clear();
124: }
125: }
126:
127: public java.util.Set keySet() {
128: return m_map.keySet();
129: }
130:
131: public long last(Object key) {
132: LRUCacheEntry value = (LRUCacheEntry) m_map.get(key);
133: return value.m_last;
134: }
135:
136: public Object get(Object key) {
137: Object oRetVal;
138:
139: if (DebugFile.trace) {
140: DebugFile.writeln("Begin LRUCachePolicy.get(" + key + ")");
141: DebugFile.incIdent();
142: }
143:
144: if (key == null) {
145: throw new IllegalArgumentException(
146: "Requesting an object using a null key");
147: }
148:
149: Object value = m_map.get(key);
150: LRUCacheEntry entry;
151:
152: if (value != null) {
153: entry = (LRUCacheEntry) value;
154: m_list.promote(entry);
155: oRetVal = entry.m_object;
156: } else {
157: if (DebugFile.trace)
158: DebugFile.writeln("LRUCachePolicy.cacheMiss()");
159: cacheMiss();
160: oRetVal = null;
161: }
162:
163: if (DebugFile.trace) {
164: DebugFile.decIdent();
165: DebugFile.writeln("End LRUCachePolicy.get() : "
166: + (oRetVal != null ? "[Object]" : "null"));
167: }
168: return oRetVal;
169: } // get
170:
171: public Object peek(Object key) {
172: if (key == null)
173: throw new IllegalArgumentException(
174: "Requesting an object using a null key");
175:
176: LRUCacheEntry value = (LRUCacheEntry) m_map.get(key);
177:
178: if (value == null)
179: return null;
180: else
181: return value.m_object;
182: } // peek
183:
184: public void insert(Object key, Object o, long t) {
185:
186: if (o == null)
187: throw new IllegalArgumentException(
188: "Cannot insert a null object in the cache");
189:
190: if (key == null)
191: throw new IllegalArgumentException(
192: "Cannot insert an object in the cache with null key");
193:
194: Object obj = m_map.get(key);
195:
196: if (obj == null) {
197: m_list.demote();
198: LRUCacheEntry entry = createCacheEntry(key, o, t);
199: m_list.promote(entry);
200: m_map.put(key, entry);
201: } else {
202: throw new IllegalStateException(
203: "Attempt to put in the cache an object that is already there");
204: }
205: } // insert
206:
207: public void remove(Object key) {
208:
209: if (key == null)
210: throw new IllegalArgumentException(
211: "Removing an object using a null key");
212:
213: Object value = m_map.get(key);
214:
215: if (value != null) {
216: m_list.remove((LRUCacheEntry) value);
217: m_map.remove(key);
218: }
219:
220: } // remove
221:
222: public void flush() {
223:
224: LRUCacheEntry entry = null;
225:
226: while ((entry = m_list.m_tail) != null)
227: ageOut(entry);
228: } // flush
229:
230: public int size() {
231: return m_list.m_count;
232: } // size
233:
234: // Protected -----------------------------------------------------
235:
236: /**
237: * Factory method for the linked list used by this cache implementation.
238: */
239:
240: protected LRUList createList() {
241: return new LRUList();
242: }
243:
244: /**
245: * Callback method called when the cache algorithm ages out of the cache
246: * the given entry. <br>
247: * The implementation here is removing the given entry from the cache.
248: */
249:
250: protected void ageOut(LRUCacheEntry entry) {
251: remove(entry.m_key);
252: }
253:
254: /**
255: * Callback method called when a cache miss happens.
256: */
257:
258: protected void cacheMiss() {
259: }
260:
261: /**
262: * Factory method for cache entries
263: */
264:
265: protected LRUCacheEntry createCacheEntry(Object key, Object value,
266: long t) {
267:
268: return new LRUCacheEntry(key, value, t);
269: }
270:
271: // Private -------------------------------------------------------
272:
273: // Inner classes -------------------------------------------------
274:
275: /**
276: * Double queued list used to store cache entries.
277: */
278:
279: public class LRUList {
280:
281: /** The maximum capacity of the cache list */
282:
283: public int m_maxCapacity;
284:
285: /** The minimum capacity of the cache list */
286:
287: public int m_minCapacity;
288:
289: /** The current capacity of the cache list */
290:
291: public int m_capacity;
292:
293: /** The number of cached objects */
294:
295: public int m_count;
296:
297: /** The head of the double linked list */
298:
299: public LRUCacheEntry m_head;
300:
301: /** The tail of the double linked list */
302:
303: public LRUCacheEntry m_tail;
304:
305: /** The cache misses happened */
306:
307: public int m_cacheMiss;
308:
309: /**
310: * Creates a new double queued list.
311: */
312:
313: protected LRUList() {
314:
315: m_head = null;
316:
317: m_tail = null;
318:
319: m_count = 0;
320: }
321:
322: /**
323: * Promotes the cache entry <code>entry</code> to the last used position
324: * of the list. <br>
325: * If the object is already there, does nothing.
326: * @param entry the object to be promoted, cannot be null
327: * @see #demote
328: * @throws IllegalStateException if this method is called with a full cache
329: */
330:
331: protected void promote(LRUCacheEntry entry) {
332:
333: if (entry == null) {
334: throw new IllegalArgumentException(
335: "Trying to promote a null object");
336: }
337:
338: if (m_capacity < 1) {
339: throw new IllegalStateException(
340: "Can't work with capacity < 1");
341: }
342:
343: entry.m_time = System.currentTimeMillis();
344:
345: if (entry.m_prev == null)
346:
347: {
348:
349: if (entry.m_next == null)
350:
351: {
352:
353: // entry is new or there is only the head
354:
355: if (m_count == 0) // cache is empty
356:
357: {
358:
359: m_head = entry;
360:
361: m_tail = entry;
362:
363: ++m_count;
364:
365: entryAdded(entry);
366:
367: }
368:
369: else if (m_count == 1 && m_head == entry) {
370: } // there is only the head and I want to promote it, do nothing
371:
372: else if (m_count < m_capacity)
373:
374: {
375:
376: entry.m_prev = null;
377:
378: entry.m_next = m_head;
379:
380: m_head.m_prev = entry;
381:
382: m_head = entry;
383:
384: ++m_count;
385:
386: entryAdded(entry);
387:
388: }
389:
390: else if (m_count < m_maxCapacity)
391:
392: {
393:
394: entry.m_prev = null;
395:
396: entry.m_next = m_head;
397:
398: m_head.m_prev = entry;
399:
400: m_head = entry;
401:
402: ++m_count;
403:
404: int oldCapacity = m_capacity;
405:
406: ++m_capacity;
407:
408: entryAdded(entry);
409:
410: capacityChanged(oldCapacity);
411:
412: }
413:
414: else {
415: throw new IllegalStateException(
416: "Attempt to put a new cache entry on a full cache");
417: }
418:
419: }
420:
421: else {
422: } // entry is the head, do nothing
423:
424: }
425:
426: else
427:
428: {
429:
430: if (entry.m_next == null) // entry is the tail
431:
432: {
433:
434: LRUCacheEntry beforeLast = entry.m_prev;
435:
436: beforeLast.m_next = null;
437:
438: entry.m_prev = null;
439:
440: entry.m_next = m_head;
441:
442: m_head.m_prev = entry;
443:
444: m_head = entry;
445:
446: m_tail = beforeLast;
447:
448: }
449:
450: else // entry is in the middle of the list
451:
452: {
453:
454: LRUCacheEntry previous = entry.m_prev;
455:
456: previous.m_next = entry.m_next;
457:
458: entry.m_next.m_prev = previous;
459:
460: entry.m_prev = null;
461:
462: entry.m_next = m_head;
463:
464: m_head.m_prev = entry;
465:
466: m_head = entry;
467:
468: }
469:
470: }
471: }
472:
473: /**
474: * Demotes from the cache the least used entry. <br>
475: * If the cache is not full, does nothing.
476: * @see #promote
477: */
478:
479: protected void demote() {
480:
481: if (m_capacity < 1)
482: throw new IllegalStateException(
483: "Can't work with capacity < 1");
484:
485: if (m_count > m_maxCapacity)
486: throw new IllegalStateException(
487: "Cache list entries number (" + m_count
488: + ") > than the maximum allowed ("
489: + m_maxCapacity + ")");
490:
491: if (m_count == m_maxCapacity) {
492:
493: LRUCacheEntry entry = m_tail;
494:
495: // the entry will be removed by ageOut
496:
497: ageOut(entry);
498: }
499: }
500:
501: /**
502: * Removes from the cache list the specified entry.
503: */
504:
505: protected void remove(LRUCacheEntry entry)
506: throws IllegalArgumentException, IllegalStateException {
507:
508: if (entry == null)
509: throw new IllegalArgumentException(
510: "LRUList.remove() Cannot remove a null entry from the cache");
511:
512: if (m_count < 1)
513: throw new IllegalStateException(
514: "LRUList.remove() Trying to remove an entry from an empty cache");
515:
516: entry.m_key = entry.m_object = null;
517:
518: if (m_count == 1) {
519:
520: m_head = m_tail = null;
521: } else {
522: if (entry.m_prev == null) { // the head
523:
524: m_head = entry.m_next;
525:
526: if (null != m_head)
527: m_head.m_prev = null;
528:
529: entry.m_next = null;
530: } else if (entry.m_next == null) { // the tail
531:
532: m_tail = entry.m_prev;
533:
534: m_tail.m_next = null;
535:
536: entry.m_prev = null;
537: } else { // in the middle
538:
539: entry.m_next.m_prev = entry.m_prev;
540:
541: entry.m_prev.m_next = entry.m_next;
542:
543: entry.m_prev = null;
544:
545: entry.m_next = null;
546: }
547: }
548:
549: --m_count;
550:
551: entryRemoved(entry);
552: } // remove
553:
554: /**
555: * Callback that signals that the given entry has been added to the cache.
556: */
557:
558: protected void entryAdded(LRUCacheEntry entry) {
559: }
560:
561: /**
562: * Callback that signals that the given entry has been removed from the cache.
563: */
564:
565: protected void entryRemoved(LRUCacheEntry entry) {
566: }
567:
568: /**
569: * Callback that signals that the capacity of the cache is changed.
570: * @param oldCapacity the capacity before the change happened
571: */
572:
573: protected void capacityChanged(int oldCapacity) {
574: }
575:
576: protected void clear() {
577:
578: m_head = null;
579:
580: m_tail = null;
581:
582: m_count = 0;
583: }
584:
585: public String toString() {
586:
587: String s = Integer.toHexString(super .hashCode());
588:
589: s += " size: " + m_count;
590:
591: for (LRUCacheEntry entry = m_head; entry != null; entry = entry.m_next)
592: s += "\n" + entry;
593:
594: return s;
595: }
596: }
597:
598: /**
599: * Double linked cell used as entry in the cache list.
600: */
601:
602: public final class LRUCacheEntry {
603:
604: /** Reference to the next cell in the list */
605:
606: public LRUCacheEntry m_next;
607:
608: /** Reference to the previous cell in the list */
609:
610: public LRUCacheEntry m_prev;
611:
612: /** The key used to retrieve the cached object */
613:
614: public Object m_key;
615:
616: /** The cached object */
617:
618: public Object m_object;
619:
620: /** The timestamp of the creation */
621:
622: public long m_time;
623:
624: /** The timestamp of last modification */
625:
626: public long m_last;
627:
628: /**
629: * Creates a new double linked cell, storing the object we
630: * want to cache and the key that is used to retrieve it.
631: */
632:
633: protected LRUCacheEntry(Object key, Object object, long t) {
634:
635: m_key = key;
636:
637: m_object = object;
638:
639: m_next = null;
640:
641: m_prev = null;
642:
643: m_time = 0; // Set when inserted in the list.
644:
645: m_last = t;
646: }
647:
648: public String toString() {
649: return "key: "
650: + m_key
651: + ", object: "
652: + (m_object == null ? "null" : Integer
653: .toHexString(m_object.hashCode()))
654: + ", entry: "
655: + Integer.toHexString(super .hashCode());
656: }
657: } // LRUCacheEntry
658: } // LRUCachePolicy
|