Java > Open Source Codes > pt > waveweb > util > LruCache


1 // From http://sourceforge.net/projects/tktk/
2
3 /*
4  * Class LRUCache
5  * --------------
6  *
7  * $Author: dhiren $
8  * $Revision: 1.8 $
9  * $Name: $
10  *
11  * Copyright 2001 Triple Kona Software, Inc.
12  *
13  * This library is free software; you can redistribute it and/or
14  * modify it under the terms of the GNU Lesser General Public
15  * License as published by the Free Software Foundation; either
16  * version 2.1 of the License, or (at your option) any later version.
17  *
18  * This library is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21  * Lesser General Public License for more details.
22  *
23  * You should have received a copy of the GNU Lesser General Public
24  * License along with this library; if not, write to the Free Software
25  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
26  */
27 package pt.waveweb.util;
28
29 import java.util.ArrayList ;
30 import java.util.Collection ;
31 import java.util.Collections ;
32 import java.util.HashMap ;
33 import java.util.HashSet ;
34 import java.util.Iterator ;
35 import java.util.Map ;
36 import java.util.Set ;
37 import java.util.TreeMap ;
38
39 /**
40  * This class implements a simple, thread-safe LRU cache. The size of
41  * the cache is specifed in terms of the number of objects that the
42  * cache can hold. In addition to an LRU algorithm, each entry in the
43  * cache has a timeout value. When the entry expires, it is evicted
44  * from the cache.
45  *
46  * @author Dhiren Patel, Triple Kona Software, Inc.
47  */
48 public class LruCache implements Map
49 {
50     private int _maxCapacity = 32768;
51     private long _lifespan;
52     private long _timeout;
53     private TreeMap _timeOrder;
54     private HashMap _keyOrder;
55     private ArrayList _entryPool;
56
57     /**
58      * Create a cache with the given timeout and with an infinite default timeout
59      * for entries; this will create a true LRU cache, i.e. the expiration will
60      * be based only on the last accessed time and not the lifespan of the
61      * entry. The initial capacity of the cache will be zero.
62      *
63      * @see LRUCache(long timeout, long lifespan, int initialCapacity, int maxCapacity)
64      * @see LRUCache(long timeout,long lifespan, int maxCapacity)
65      */
66     public LruCache(long timeout, int maxCapacity)
67     {
68         this(timeout, Long.MAX_VALUE, 0, maxCapacity);
69     }
70
71     /**
72      * timeout and lifespan in milliseconds. intial capacity = zero
73      *
74      * @see LruCache(long timeout,int maxCapacity)
75      * @see LruCache(long timeout, long lifespan, int initialCapacity, int maxCapacity)
76      */
77     public LruCache(long timeout, long lifespan, int maxCapacity)
78     {
79         this(timeout, lifespan, 0, maxCapacity);
80     }
81
82     /**
83      * Create an LruCache with a given default timeout and lifespan
84      * for each entry. If <code>lifespan < timeout</code> then
85      * this will be a timeout only cache, i.e. entries will be evicted from
86      * the cache when they have lived longer than <code>lifespan</code>.
87      * You can get a LRU only cache by setting lifespan to Long.MAX_VALUE.
88      *
89      * @see LruCache(long timeout,int maxCapacity)
90      * @see LruCache(long timeout,long lifespan, int maxCapacity)
91      */
92     public LruCache(long timeout, long lifespan, int initialCapacity, int maxCapacity)
93     {
94         if (timeout < 0)
95         {
96             throw new IllegalArgumentException ("timeout < 0");
97         }
98
99         _timeout = timeout;
100
101         if (lifespan < 0)
102         {
103             throw new IllegalArgumentException ("lifespan < 0");
104         }
105
106         _lifespan = lifespan;
107
108         if (initialCapacity < 0)
109         {
110             throw new IllegalArgumentException ("initialCapacity < 0");
111         }
112
113         if (maxCapacity < 0)
114         {
115             throw new IllegalArgumentException ("maxCapacity < 0");
116         }
117
118         _timeOrder = new TreeMap ();
119         _keyOrder = new HashMap (initialCapacity);
120         _maxCapacity = maxCapacity;
121         _entryPool = new ArrayList (initialCapacity);
122     }
123
124     /* Implement the Map method */
125     public synchronized boolean containsKey(Object key)
126     {
127         return (get(key) != null);
128     }
129
130     public synchronized boolean containsValue(Object value)
131     {
132         // We have to enumerate all of the entries because
133 // the value is actually contained in the cache entry.
134 Iterator i = _timeOrder.values().iterator();
135
136         while (i.hasNext())
137         {
138             Entry ent = (Entry) i.next();
139
140             if (ent.getValue().equals(value))
141             {
142                 return true;
143             }
144         }
145
146         return false;
147     }
148
149     /**
150      * Returns an <i>unmodifiable and unsynchronized</i>
151      * <code>Set</code> of the
152      * <code>Entry</code> elements in the cache. Note
153      * that the underlying cache may change after this method
154      * returns. This method may return some expired entries
155      * if they have not yet been removed from the cache.
156      */
157     public synchronized Set entrySet()
158     {
159         Iterator entries = _timeOrder.entrySet().iterator();
160         HashSet hs = new HashSet (_timeOrder.size());
161         Map.Entry ent;
162
163         while (entries.hasNext())
164         {
165             ent = (Entry) ((Map.Entry ) entries.next()).getValue();
166             hs.add(ent);
167         }
168
169         return Collections.unmodifiableSet(hs);
170     }
171
172     public synchronized boolean equals(Object o)
173     {
174         LruCache c = (LruCache) o;
175
176         return _timeOrder.equals(c._timeOrder) && _keyOrder.equals(c._keyOrder);
177     }
178
179     public synchronized int hashCode()
180     {
181         return _timeOrder.hashCode() ^ _keyOrder.hashCode();
182     }
183
184     public boolean isEmpty()
185     {
186         return _timeOrder.isEmpty();
187     }
188
189     /**
190      * Returns an <i>unmodifiable</i> <code>Set</code> of the
191      * keys elements in the cache.
192      */
193     public synchronized Set keySet()
194     {
195         return Collections.unmodifiableSet(_keyOrder.keySet());
196     }
197
198     public synchronized Object get(Object key)
199     {
200         //System.out.println("Getting " + key);
201 Entry ent = (Entry) _keyOrder.get(key);
202
203         if (ent == null)
204         {
205             //System.out.println("Trying to get() null entry for key " + key);
206 return null;
207         }
208
209         // If the entry is expired, update() will remove
210 // it and return false. We do _not_ return the value
211 // in this case because the caller may then assume
212 // that the value is in the cache, even though it
213 // has been removed.
214 if (!update(ent))
215         {
216             return null;
217         }
218         else
219         {
220             return ent.getValue();
221         }
222     }
223
224     /**
225      * Put a mapping in the cache with the default
226      * expiration time and lifespan.
227      */
228     public synchronized Object put(Object key, Object val)
229     {
230         return put(key, val, _timeout);
231     }
232
233     /**
234      * Put a mapping in the cache using the given expiration
235      * time and the default lifespan (passed into the
236      * constructor).
237      */
238     public synchronized Object put(Object key, Object val, long expirationTime)
239     {
240         while (_keyOrder.size() >= _maxCapacity)
241         {
242             remove(((Entry) _timeOrder.lastKey()).getKey());
243         }
244
245         Entry ent = getEntryFromPool(key, val, expirationTime, _lifespan);
246
247         Entry retVal = add(ent);
248
249         if (retVal != null)
250         {
251             return retVal.getValue();
252         }
253
254         return retVal;
255     }
256
257     private synchronized Entry add(Entry ent)
258     {
259         _keyOrder.put(ent.getKey(), ent);
260
261         return (Entry) _timeOrder.put(ent, ent);
262     }
263
264     /**
265      * This will put all of the elements of <code>t</code>
266      * into the cache in a <i>linear</i> fashion.
267      */
268     public synchronized void putAll(Map t)
269     {
270         Iterator i = t.keySet().iterator();
271         Object key;
272
273         while (i.hasNext())
274         {
275             key = i.next();
276             put(key, t.get(key));
277         }
278     }
279
280     public synchronized Object remove(Object key)
281     {
282         //System.out.println("Removing " + key);
283 Entry ent = (Entry) _keyOrder.remove(key);
284
285         if (ent == null)
286         {
287             return null;
288         }
289
290         _timeOrder.remove(ent);
291
292         Object retVal = ent.getValue();
293         returnEntryToPool(ent);
294
295         return retVal;
296     }
297
298     public synchronized int size()
299     {
300         return _keyOrder.size();
301     }
302
303     /**
304      * Returns an <i>unmodifiable</i> <code>Collection</code>
305      * of the values held in the cache.
306      */
307     public synchronized Collection values()
308     {
309         return Collections.unmodifiableCollection(_timeOrder.values());
310     }
311
312     public synchronized void prune()
313     {
314         Iterator vals = _timeOrder.values().iterator();
315
316         Entry ent = null;
317
318         while (vals.hasNext())
319         {
320             ent = (Entry) vals.next();
321
322             if (ent.expired())
323             {
324                 remove(ent.getKey());
325             }
326         }
327     }
328
329     public synchronized void clear()
330     {
331         _keyOrder.clear();
332         _timeOrder.clear();
333     }
334
335     public synchronized boolean contains(Object key)
336     {
337         if (_keyOrder.get(key) != null)
338         {
339             return true;
340         }
341
342         return false;
343     }
344
345     public long getTimeout()
346     {
347         return _timeout;
348     }
349
350     public void setTimeout(long millis)
351     {
352         _timeout = millis;
353     }
354
355     public int getMaxCapacity()
356     {
357         return _maxCapacity;
358     }
359
360     public void setMaxCapacity(int max)
361     {
362         _maxCapacity = max;
363     }
364
365     /* package private members */
366
367     /**
368      * If an entry exists in the cache, retrieve it regardless of
369      * whether it is expired. The caller should not modify the
370      * returned object.
371      */
372     synchronized Entry getEntry(Object key)
373     {
374         return (Entry) _keyOrder.get(key);
375     }
376
377     /* privates */
378
379     /**
380      * If an entry is expired, remove it from internal data structures, otherwise
381      * update the entry's timestamp and put it back in the LRU list. This method
382      * returns <code>true</code> if the entry was updated, or <code>false</code>
383      * if the entry was removed from the cache.
384      */
385     private synchronized boolean update(Entry ent)
386     {
387         if (ent.expired())
388         {
389             remove(ent.getKey());
390
391             return false; // the entry was not updated
392 }
393
394         _timeOrder.remove(ent);
395         ent.touch();
396         _timeOrder.put(ent, ent);
397
398         return true; // the entry was updated
399 }
400
401     /**
402      * Get an entry from the free entry pool and set the values. If the free
403      * entry pool is empty, a new entry will be created and returned.
404      *
405      * @see returnEntryToPool(Entry ent)
406      */
407     private Entry getEntryFromPool(Object key, Object obj, long expirationTime, long lifespan)
408     {
409         int last = _entryPool.size() - 1;
410
411         if (last >= 0)
412         {
413             Entry ent = (Entry) _entryPool.remove(last);
414             ent.set(key, obj, expirationTime, lifespan);
415
416             return ent;
417         }
418
419         return new Entry(key, obj, expirationTime, lifespan);
420     }
421
422     /**
423      * Return an entry back into the free entry pool.
424      *
425      * @see getEntryFromPool(Object key, Object obj, long expirationTime, long lifespan)
426      */
427     private void returnEntryToPool(Entry ent)
428     {
429         ent.reset();
430         _entryPool.add(ent);
431     }
432
433     //private static final long _DEFAULT_TIMEOUT = 1000; // 1-sec minimum timeout
434 //private static final long _DEFAULT_LIFESPAN = 1000; // 1-sec minimum lifespan
435
436     /**
437      * Inner class for Cache entries. This Comparable class is
438      * consistent with equals.
439      */
440     public class Entry implements Map.Entry , Comparable
441     {
442         /* privates */
443         private Object _key;
444         private Object _obj;
445         private long _created;
446         private long _expirationTimeout;
447         private long _lifespan;
448         private long _lastAccessed;
449
450         /**
451          * Create an entry. The timestamp for this entry is set at the
452          * time of creation. The exiprationTime is the duration after
453          * which this entry will expire, and the lifespan is the maximum
454          * lifespan in the cache.
455          */
456         protected Entry(Object key, Object obj, long expirationTimeout, long lifespan)
457         {
458             set(key, obj, expirationTimeout, lifespan);
459         }
460
461         protected void set(Object key, Object obj, long expirationTimeout, long lifespan)
462         {
463             _key = key;
464             _obj = obj;
465             _created = System.currentTimeMillis();
466             _lastAccessed = _created;
467             _expirationTimeout = expirationTimeout;
468             _lifespan = lifespan;
469         }
470
471         /**
472          * Returns <code>true</code> if the entry is expired. An
473          * entry is considered to be expired if it hasn't been
474          * accessed for the duration of the <code>expirationTime</code>
475          * or if it has existed longer than its <code>lifespan</code>.
476          */
477         public boolean expired()
478         {
479             long currentTime = System.currentTimeMillis();
480
481             long expirationTime = _lastAccessed + _expirationTimeout;
482             long deathTime = _created + _lifespan;
483
484             boolean expired = false;
485
486             // If there is no overflow
487 if (expirationTime > 0)
488             {
489                 expired = currentTime >= expirationTime;
490             }
491             else
492             {
493                 // If we overlow, the expiration time is an extremely large number
494 // that the current time will never reach, so the entry cannot
495 // be expired.
496 }
497
498             boolean dead = false;
499
500             // If there is no overflow
501 if (deathTime > 0)
502             {
503                 dead = currentTime >= deathTime;
504             }
505             else
506             {
507                 // If we overlow, the death time is an extremely large number
508 // that the current time will never reach, so the entry cannot
509 // be expired.
510 }
511
512             // if we're expired or dead, we call
513 // that expired.
514 if (expired || dead)
515             {
516                 //System.out.println("Entry " + getKey() + " EXPIRED");
517 return true;
518             }
519
520             return false;
521         }
522
523         /**
524          * Update this entry's last accessed time so that
525          * it does not get evicted from the cache. This
526          * has to be done each time the object is updated
527          * in the cache.
528          */
529         protected void touch()
530         {
531             _lastAccessed = System.currentTimeMillis();
532         }
533
534         /**
535          * Reset this entry's object references so that the contained
536          * values can get garbage collected.
537          */
538         public void reset()
539         {
540             _key = "";
541             _obj = "";
542         }
543
544         /**
545          * Get the key associated with this Entry. The <code>Object</code>
546          * returned is a <code>String</code>.
547          */
548         public Object getKey()
549         {
550             return _key;
551         }
552
553         /**
554          * Get the object stored in this Entry.
555          */
556         public Object getValue()
557         {
558             return _obj;
559         }
560
561         /**
562          * Set the object stored in this Entry.
563          */
564         public Object setValue(Object obj)
565         {
566             Object tmp = _obj;
567             _obj = obj;
568
569             return tmp;
570         }
571
572         /**
573          * Returns the <code>hashCode</code> for this object as
574          * described in {@link java.util.Map.Entry#hashCode
575          * Map.Entry.hashCode()}
576          *
577          * @see Map.Entry#hashCode()
578          */
579         public int hashCode()
580         {
581             return getKey().hashCode();
582         }
583
584         /**
585          * Get the last accessed timestamp for this object.
586          * The time is represented
587          * as the number of milliseconds since January 1, 1970,
588          * 00:00:00 GMT, the same as System.currentTimeMillis().
589          */
590         protected long getLastAccessed()
591         {
592             return _lastAccessed;
593         }
594
595         private long getCreationTime()
596         {
597             return _created;
598         }
599
600         /**
601          * Return a key=value string for this entry.
602          */
603         public String toString()
604         {
605             StringBuffer buf = new StringBuffer ();
606             buf.append(getKey() + "=" + getValue());
607
608             return buf.toString();
609         }
610
611         /**
612          * Tests for equality of this object and <code>entry</code>
613          * This function implements as described in
614          * {@link java.util.Map.Entry#equals Map.Entry.equals()}
615          *
616          * @throws ClassCastException if <code>entry</code> is not
617          * an <code>Entry</code> object.
618          */
619         public boolean equals(Object entry)
620         {
621             Entry ent = (Entry) entry;
622
623             if (getKey().equals(ent.getKey()))
624             {
625                 return true;
626             }
627
628             return false;
629         }
630
631         /**
632          * Implement Comparable so we can sort entries. This function
633          * compares the last access times of the entries and imposes a total
634          * ordering on all entries. If two entries have the same timestamps,
635          * the entries' creation timestamps are compared, and if those
636          * are equal, the key's <code>hashCode()</code>
637          * values are compared to determine a total order.
638          */
639         public int compareTo(Object obj)
640         {
641             // If the keys are the same, we assume the entries are equal.
642 if (equals(obj))
643             {
644                 return 0;
645             }
646
647             Entry ent = (Entry) obj;
648             long _ts = ent.getLastAccessed();
649
650             // This object is fresher than obj
651 if (_lastAccessed > _ts)
652             {
653                 return -1;
654             }
655
656             // This object is not as fresh than obj
657 if (_lastAccessed < _ts)
658             {
659                 return 1;
660             }
661
662             long _creation = ent.getCreationTime();
663
664             // This object is younger than obj
665 if (_creation > _ts)
666             {
667                 return -1;
668             }
669
670             // This object is older than obj
671 if (_creation < _ts)
672             {
673                 return 1;
674             }
675
676             // If the timestamps are the same, we compare the
677 // hash codes of the keys.
678 int mine = _key.hashCode();
679             int other = ent.getKey().hashCode();
680
681             if (mine > other)
682             {
683                 return -1;
684             }
685             else
686                 if (mine < other)
687                 {
688                     return 1;
689                 }
690
691             // In this most exceedingly rare occurance, we must ensure that
692 // we impose a total ordering.
693 return 1;
694         }
695     }
696 }
697

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags