LRUCachePolicy


1   package com.knowgate.cache;
2   
3   import java.util.HashMap  ;
4   import com.knowgate.debug.DebugFile;
5   
6   /**
7    * <p>LRU Cache Policy</p>
8    * <p>Implementation of a Least Recently Used cache policy.</p>
9    * @author Simone Bordet &lt;simone.bordet@compaq.com&gt;
10   * @version 1.3.2.1
11   */
12  
13  public final class LRUCachePolicy {
14  
15    // Attributes ----------------------------------------------------
16  
17    /**
18     * The map holding the cached objects
19     */
20  
21    protected HashMap   m_map;
22  
23    /**
24     * The linked list used to implement the LRU algorithm
25     */
26  
27    protected LRUList m_list;
28  
29    /**
30     * The maximum capacity of this cache
31     */
32  
33    protected int m_maxCapacity;
34  
35    /**
36     * The minimum capacity of this cache
37     */
38  
39    protected int m_minCapacity;
40  
41    // Constructors --------------------------------------------------
42  
43    /**
44     * Creates a LRU cache policy object with zero cache capacity.
45     *
46     * @see #create
47     */
48  
49    public LRUCachePolicy() {}
50  
51    /**
52     * Creates a LRU cache policy object with the specified minimum and maximum capacity.
53     *
54     * @see #create
55     */
56  
57    public LRUCachePolicy(int min, int max) {
58      if (min < 2 || min > max) {
59        throw new IllegalArgumentException  ("Illegal cache capacities");
60      }
61      m_minCapacity = min;
62      m_maxCapacity = max;
63  
64      create();
65    }
66  
67    // Service implementation ----------------------------------------------
68  
69    /**
70         * Initializes the cache, creating all required objects and initializing their
71     * values.
72     * @see #start
73     * @see #destroy
74     */
75  
76    private void create() {
77  
78      m_map = new HashMap  (211);
79      m_list = createList();
80      m_list.m_maxCapacity = m_maxCapacity;
81      m_list.m_minCapacity = m_minCapacity;
82      m_list.m_capacity = m_maxCapacity;
83    }
84  
85    /**
86     * Starts this cache that is now ready to be used.
87     * @see #create
88     * @see #stop
89     */
90  
91    public void start() {}
92  
93    /**
94     * Stops this cache thus {@link #flush}ing all cached objects. <br>
95         * After this method is called, a call to {@link #start} will restart the cache.
96     * @see #start
97     * @see #destroy
98     */
99  
100   public void stop() {
101     if (m_list != null) {
102       flush();
103     }
104   }
105 
106   /**
107    * Destroys the cache that is now unusable. <br>
108    * To have it working again it must be re-{@link #create}ed and re-{@link #start}ed.
109    *
110    * @see #create
111    */
112 
113   public void destroy() {
114 
115     if (m_map != null) {
116       m_map.clear();
117 
118     }
119     if (m_list != null) {
120       m_list.clear();
121     }
122   }
123 
124   public java.util.Set   keySet() {
125     return m_map.keySet();
126   }
127 
128   public long last(Object   key) {
129     LRUCacheEntry value = (LRUCacheEntry) m_map.get(key);
130     return value.m_last;
131   }
132 
133   public Object   get(Object   key) {
134     Object   oRetVal;
135 
136     if (DebugFile.trace) {
137       DebugFile.writeln("Begin LRUCachePolicy.get(" + key + ")");
138       DebugFile.incIdent();
139     }
140 
141     if (key == null) {
142       throw new IllegalArgumentException  (
143           "Requesting an object using a null key");
144     }
145 
146     Object   value = m_map.get(key);
147     LRUCacheEntry entry;
148 
149     if (value != null) {
150       entry = (LRUCacheEntry)value;
151       m_list.promote(entry);
152       oRetVal = entry.m_object;
153     }
154     else {
155       if (DebugFile.trace) DebugFile.writeln("LRUCachePolicy.cacheMiss()");
156       cacheMiss();
157       oRetVal = null;
158     }
159 
160     if (DebugFile.trace) {
161       DebugFile.decIdent();
162       DebugFile.writeln("End LRUCachePolicy.get() : " + (oRetVal!=null ? "[Object]" : "null") );
163     }
164     return oRetVal;
165   } // get
166 
167   public Object   peek(Object   key) {
168     if (key == null)
169       throw new IllegalArgumentException  ("Requesting an object using a null key");
170 
171 
172     LRUCacheEntry value = (LRUCacheEntry) m_map.get(key);
173 
174     if (value == null)
175       return null;
176     else
177       return value.m_object;
178   } // peek
179 
180   public void insert(Object   key, Object   o, long t) {
181 
182     if (o == null)
183       throw new IllegalArgumentException  ("Cannot insert a null object in the cache");
184 
185     if (key == null)
186       throw new IllegalArgumentException  ("Cannot insert an object in the cache with null key");
187 
188     Object   obj = m_map.get(key);
189 
190     if (obj == null) {
191       m_list.demote();
192       LRUCacheEntry entry = createCacheEntry(key, o, t);
193       m_list.promote(entry);
194       m_map.put(key, entry);
195     }
196     else
197     {
198       throw new IllegalStateException  ("Attempt to put in the cache an object that is already there");
199     }
200   } // insert
201 
202   public void remove(Object   key) {
203 
204     if (key == null)
205       throw new IllegalArgumentException  ("Removing an object using a null key");
206 
207     Object   value = m_map.get(key);
208 
209     if (value != null) {
210       m_list.remove( (LRUCacheEntry) value);
211       m_map.remove(key);
212     }
213 
214   } // remove
215 
216   public void flush() {
217 
218     LRUCacheEntry entry = null;
219 
220     while ( (entry = m_list.m_tail) != null)
221       ageOut(entry);
222   } // flush
223 
224   public int size() {
225     return m_list.m_count;
226   } // size
227 
228 
229   // Protected -----------------------------------------------------
230 
231   /**
232    * Factory method for the linked list used by this cache implementation.
233    */
234 
235   protected LRUList createList() {
236     return new LRUList();
237   }
238 
239   /**
240    * Callback method called when the cache algorithm ages out of the cache
241    * the given entry. <br>
242    * The implementation here is removing the given entry from the cache.
243    */
244 
245   protected void ageOut(LRUCacheEntry entry) {
246     remove(entry.m_key);
247   }
248 
249   /**
250    * Callback method called when a cache miss happens.
251    */
252 
253   protected void cacheMiss() {
254   }
255 
256   /**
257    * Factory method for cache entries
258    */
259 
260   protected LRUCacheEntry createCacheEntry(Object   key, Object   value, long t) {
261 
262     return new LRUCacheEntry(key, value, t);
263   }
264 
265   // Private -------------------------------------------------------
266 
267   // Inner classes -------------------------------------------------
268 
269   /**
270    * Double queued list used to store cache entries.
271    */
272 
273   public class LRUList {
274 
275     /** The maximum capacity of the cache list */
276 
277     public int m_maxCapacity;
278 
279     /** The minimum capacity of the cache list */
280 
281     public int m_minCapacity;
282 
283     /** The current capacity of the cache list */
284 
285     public int m_capacity;
286 
287     /** The number of cached objects */
288 
289     public int m_count;
290 
291     /** The head of the double linked list */
292 
293     public LRUCacheEntry m_head;
294 
295     /** The tail of the double linked list */
296 
297     public LRUCacheEntry m_tail;
298 
299     /** The cache misses happened */
300 
301     public int m_cacheMiss;
302 
303     /**
304      * Creates a new double queued list.
305      */
306 
307     protected LRUList() {
308 
309       m_head = null;
310 
311       m_tail = null;
312 
313       m_count = 0;
314     }
315 
316     /**
317      * Promotes the cache entry <code>entry</code> to the last used position
318      * of the list. <br>
319      * If the object is already there, does nothing.
320      * @param entry the object to be promoted, cannot be null
321      * @see #demote
322      * @throws IllegalStateException if this method is called with a full cache
323      */
324 
325     protected void promote(LRUCacheEntry entry) {
326 
327       if (entry == null) {
328         throw new IllegalArgumentException  ("Trying to promote a null object");
329       }
330 
331       if (m_capacity < 1) {
332         throw new IllegalStateException  ("Can't work with capacity < 1");
333       }
334 
335       entry.m_time = System.currentTimeMillis();
336 
337       if (entry.m_prev == null)
338 
339       {
340 
341         if (entry.m_next == null)
342 
343         {
344 
345           // entry is new or there is only the head
346 
347           if (m_count == 0) // cache is empty
348 
349           {
350 
351             m_head = entry;
352 
353             m_tail = entry;
354 
355             ++m_count;
356 
357             entryAdded(entry);
358 
359           }
360 
361           else if (m_count == 1 && m_head == entry) {} // there is only the head and I want to promote it, do nothing
362 
363           else if (m_count < m_capacity)
364 
365           {
366 
367             entry.m_prev = null;
368 
369             entry.m_next = m_head;
370 
371             m_head.m_prev = entry;
372 
373             m_head = entry;
374 
375             ++m_count;
376 
377             entryAdded(entry);
378 
379           }
380 
381           else if (m_count < m_maxCapacity)
382 
383           {
384 
385             entry.m_prev = null;
386 
387             entry.m_next = m_head;
388 
389             m_head.m_prev = entry;
390 
391             m_head = entry;
392 
393             ++m_count;
394 
395             int oldCapacity = m_capacity;
396 
397             ++m_capacity;
398 
399             entryAdded(entry);
400 
401             capacityChanged(oldCapacity);
402 
403           }
404 
405           else {
406             throw new IllegalStateException  (
407                 "Attempt to put a new cache entry on a full cache");
408           }
409 
410         }
411 
412         else {} // entry is the head, do nothing
413 
414       }
415 
416       else
417 
418       {
419 
420         if (entry.m_next == null) // entry is the tail
421 
422         {
423 
424           LRUCacheEntry beforeLast = entry.m_prev;
425 
426           beforeLast.m_next = null;
427 
428           entry.m_prev = null;
429 
430           entry.m_next = m_head;
431 
432           m_head.m_prev = entry;
433 
434           m_head = entry;
435 
436           m_tail = beforeLast;
437 
438         }
439 
440         else // entry is in the middle of the list
441 
442         {
443 
444           LRUCacheEntry previous = entry.m_prev;
445 
446           previous.m_next = entry.m_next;
447 
448           entry.m_next.m_prev = previous;
449 
450           entry.m_prev = null;
451 
452           entry.m_next = m_head;
453 
454           m_head.m_prev = entry;
455 
456           m_head = entry;
457 
458         }
459 
460       }
461     }
462 
463     /**
464      * Demotes from the cache the least used entry. <br>
465      * If the cache is not full, does nothing.
466      * @see #promote
467      */
468 
469     protected void demote() {
470 
471       if (m_capacity < 1)
472         throw new IllegalStateException  ("Can't work with capacity < 1");
473 
474       if (m_count > m_maxCapacity)
475         throw new IllegalStateException  ("Cache list entries number (" + m_count +
476                                         ") > than the maximum allowed (" +
477                                         m_maxCapacity + ")");
478 
479       if (m_count == m_maxCapacity) {
480 
481         LRUCacheEntry entry = m_tail;
482 
483         // the entry will be removed by ageOut
484 
485         ageOut(entry);
486       }
487     }
488 
489     /**
490      * Removes from the cache list the specified entry.
491      */
492 
493     protected void remove(LRUCacheEntry entry) throws IllegalArgumentException  ,IllegalStateException   {
494 
495       if (entry == null)
496         throw new IllegalArgumentException  ("LRUList.remove() Cannot remove a null entry from the cache");
497 
498       if (m_count < 1)
499         throw new IllegalStateException  ("LRUList.remove() Trying to remove an entry from an empty cache");
500 
501       entry.m_key = entry.m_object = null;
502 
503       if (m_count == 1) {
504 
505         m_head = m_tail = null;
506       }
507       else {
508         if (entry.m_prev == null)  { // the head
509 
510           m_head = entry.m_next;
511 
512           if (null!=m_head) m_head.m_prev = null;
513 
514           entry.m_next = null;
515         }
516         else if (entry.m_next == null) { // the tail
517 
518           m_tail = entry.m_prev;
519 
520           m_tail.m_next = null;
521 
522           entry.m_prev = null;
523         }
524         else { // in the middle
525 
526           entry.m_next.m_prev = entry.m_prev;
527 
528           entry.m_prev.m_next = entry.m_next;
529 
530           entry.m_prev = null;
531 
532           entry.m_next = null;
533         }
534       }
535 
536       --m_count;
537 
538       entryRemoved(entry);
539     } // remove
540 
541     /**
542      * Callback that signals that the given entry has been added to the cache.
543      */
544 
545     protected void entryAdded(LRUCacheEntry entry) {}
546 
547     /**
548          * Callback that signals that the given entry has been removed from the cache.
549      */
550 
551     protected void entryRemoved(LRUCacheEntry entry) {}
552 
553     /**
554      * Callback that signals that the capacity of the cache is changed.
555      * @param oldCapacity the capacity before the change happened
556      */
557 
558     protected void capacityChanged(int oldCapacity) {}
559 
560     protected void clear() {
561 
562       m_head = null;
563 
564       m_tail = null;
565 
566       m_count = 0;
567     }
568 
569     public String   toString() {
570 
571       String   s = Integer.toHexString(super.hashCode());
572 
573       s += " size: " + m_count;
574 
575       for (LRUCacheEntry entry = m_head; entry != null; entry = entry.m_next)
576         s += "\n" + entry;
577 
578       return s;
579     }
580   }
581 
582   /**
583    * Double linked cell used as entry in the cache list.
584    */
585 
586   public final class LRUCacheEntry {
587 
588     /** Reference to the next cell in the list */
589 
590     public LRUCacheEntry m_next;
591 
592     /** Reference to the previous cell in the list */
593 
594     public LRUCacheEntry m_prev;
595 
596     /** The key used to retrieve the cached object */
597 
598     public Object   m_key;
599 
600     /** The cached object */
601 
602     public Object   m_object;
603 
604     /** The timestamp of the creation */
605 
606     public long m_time;
607 
608     /** The timestamp of last modification */
609 
610     public long m_last;
611 
612     /**
613      * Creates a new double linked cell, storing the object we
614      * want to cache and the key that is used to retrieve it.
615      */
616 
617     protected LRUCacheEntry(Object   key, Object   object, long t) {
618 
619       m_key = key;
620 
621       m_object = object;
622 
623       m_next = null;
624 
625       m_prev = null;
626 
627       m_time = 0; // Set when inserted in the list.
628 
629       m_last = t;
630     }
631 
632     public String   toString() {
633       return "key: " + m_key + ", object: " +
634           (m_object == null ? "null" : Integer.toHexString(m_object.hashCode())) +
635           ", entry: " + Integer.toHexString(super.hashCode());
636     }
637   } // LRUCacheEntry
638 } // LRUCachePolicy
639
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags