LruCache


1   /*
2    * Copyright (c) 1998-2006 Caucho Technology -- all rights reserved
3    *
4    * This file is part of Resin(R) Open Source
5    *
6    * Each copy or derived work must preserve the copyright notice and this
7    * notice unmodified.
8    *
9    * Resin Open Source is free software; you can redistribute it and/or modify
10   * it under the terms of the GNU General Public License as published by
11   * the Free Software Foundation; either version 2 of the License, or
12   * (at your option) any later version.
13   *
14   * Resin Open Source is distributed in the hope that it will be useful,
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
17   * of NON-INFRINGEMENT.  See the GNU General Public License for more
18   * details.
19   *
20   * You should have received a copy of the GNU General Public License
21   * along with Resin Open Source; if not, write to the
22   *   Free Software Foundation, Inc.
23   *   59 Temple Place, Suite 330
24   *   Boston, MA 02111-1307  USA
25   *
26   * @author Scott Ferguson
27   */
28  
29  package com.caucho.util;
30  
31  import java.util.ArrayList  ;
32  import java.util.Iterator  ;
33  
34  /**
35   * Fixed length cache with a LRU replacement policy.  If cache items
36   * implement CacheListener, they will be informed when they're removed
37   * from the cache.
38   *
39   * <p>Null keys are not allowed.  LruCache is synchronized.
40   */
41  public class LruCache<K,V> {
42    private static final Integer   NULL = new Integer  (0);
43    
44    // hash table containing the entries.  Its size is twice the capacity
45    // so it will always remain at least half empty
46    private CacheItem []_entries;
47    
48    // maximum allowed entries
49    private int _capacity;
50    // size 1 capacity is half the actual capacity
51    private int _capacity1;
52    
53    // mask for hash mapping
54    private int _mask;
55    
56    // number of items in the cache seen once
57    private int _size1;
58  
59    // head of the LRU list
60    private CacheItem<K,V> _head1;
61    // tail of the LRU list
62    private CacheItem<K,V> _tail1;
63    
64    // number of items in the cache seen more than once
65    private int _size2;
66  
67    // head of the LRU list
68    private CacheItem<K,V> _head2;
69    // tail of the LRU list
70    private CacheItem<K,V> _tail2;
71  
72    // hit count statistics
73    private volatile long _hitCount;
74    // miss count statistics
75    private volatile long _missCount;
76    
77    /**
78     * Create the LRU cache with a specific capacity.
79     *
80     * @param initialCapacity minimum capacity of the cache
81     */
82    public LruCache(int initialCapacity)
83    {
84      int capacity;
85  
86      for (capacity = 16; capacity < 2 * initialCapacity; capacity *= 2) {
87      }
88  
89      _entries = new CacheItem[capacity];
90      _mask = capacity - 1;
91  
92      _capacity = initialCapacity;
93      _capacity1 = _capacity / 2;
94    }
95  
96    /**
97     * Returns the current number of entries in the cache.
98     */
99    public int size()
100   {
101     return _size1 + _size2;
102   }
103 
104   /**
105    * Clears the cache
106    */
107   public void clear()
108   {
109     ArrayList  <CacheListener> listeners = null;
110 
111     synchronized (this) {
112       for (int i = _entries.length - 1; i >= 0; i--) {
113         CacheItem<K,V> item = _entries[i];
114 
115         if (item != null) {
116           if (item._value instanceof CacheListener) {
117             if (listeners == null)
118               listeners = new ArrayList  <CacheListener>();
119             listeners.add((CacheListener) item._value);
120           }
121         }
122         
123         _entries[i] = null;
124       }
125 
126       _size1 = 0;
127       _head1 = null;
128       _tail1 = null;
129       _size2 = 0;
130       _head2 = null;
131       _tail2 = null;
132     }
133 
134     for (int i = listeners != null ? listeners.size() - 1 : -1;
135      i >= 0;
136      i--) {
137       CacheListener listener = listeners.get(i);
138       listener.removeEvent();
139     }
140   }
141 
142   /**
143    * Get an item from the cache and make it most recently used.
144    *
145    * @param key key to lookup the item
146    * @return the matching object in the cache
147    */
148   public V get(K key)
149   {
150     Object   okey = key;
151     if (okey == null)
152       okey = NULL;
153     
154     int hash = okey.hashCode() & _mask;
155     int count = _size1 + _size2 + 1;
156 
157     synchronized (this) {
158       for (; count >= 0; count--) {
159         CacheItem<K,V> item = _entries[hash];
160 
161         if (item == null) {
162       _missCount++;
163           return null;
164     }
165 
166         if (item._key == key || item._key.equals(key)) {
167           updateLru(item);
168 
169       _hitCount++;
170 
171           return item._value;
172         }
173 
174         hash = (hash + 1) & _mask;
175       }
176       
177       _missCount++;
178     }
179 
180     return null;
181   }
182 
183   /**
184    * Puts a new item in the cache.  If the cache is full, remove the
185    * LRU item.
186    *
187    * @param key key to store data
188    * @param value value to be stored
189    *
190    * @return old value stored under the key
191    */
192   public V put(K key, V value)
193   {
194     V oldValue = put(key, value, true);
195 
196     if (oldValue instanceof CacheListener)
197       ((CacheListener) oldValue).removeEvent();
198 
199     return oldValue;
200   }
201 
202   /**
203    * Puts a new item in the cache.  If the cache is full, remove the
204    * LRU item.
205    *
206    * @param key key to store data
207    * @param value value to be stored
208    *
209    * @return the value actually stored
210    */
211   public V putIfNew(K key, V value)
212   {
213     V oldValue = put(key, value, false);
214 
215     if (oldValue != null)
216       return oldValue;
217     else
218       return value;
219   }
220 
221   /**
222    * Puts a new item in the cache.  If the cache is full, remove the
223    * LRU item.
224    *
225    * @param key key to store data
226    * @param value value to be stored
227    *
228    * @return old value stored under the key
229    */
230   private V put(K key, V value, boolean replace)
231   {
232     Object   okey = key;
233     
234     if (okey == null)
235       okey = NULL;
236 
237     // remove LRU items until we're below capacity
238     while (_capacity <= _size1 + _size2) {
239       removeTail();
240     }
241 
242     int hash = key.hashCode() & _mask;
243     int count = _size1 + _size2 + 1;
244 
245     V oldValue = null;
246 
247     synchronized (this) {
248       for (; count > 0; count--) {
249     CacheItem<K,V> item = _entries[hash];
250 
251     // No matching item, so create one
252     if (item == null) {
253       item = new CacheItem<K,V>(key, value);
254       _entries[hash] = item;
255       _size1++;
256       
257       item._next = _head1;
258       if (_head1 != null)
259         _head1._prev = item;
260           else
261             _tail1 = item;
262       _head1 = item;
263 
264       return null;
265     }
266 
267     // matching item gets replaced
268     if (item._key == okey || item._key.equals(okey)) {
269       updateLru(item);
270 
271       oldValue = item._value;
272 
273       if (replace)
274         item._value = value;
275       
276       if (value == oldValue)
277         oldValue = null;
278 
279       break;
280     }
281 
282     hash = (hash + 1) & _mask;
283       }
284 
285       if (replace && oldValue instanceof SyncCacheListener)
286     ((SyncCacheListener) oldValue).syncRemoveEvent();
287     }
288 
289     if (replace && oldValue instanceof CacheListener)
290       ((CacheListener) oldValue).removeEvent();
291 
292     return oldValue;
293   }
294 
295   /**
296    * Put item at the head of the used-twice lru list.
297    * This is always called while synchronized.
298    */
299   private void updateLru(CacheItem<K,V> item)
300   {
301     CacheItem<K,V> prev = item._prev;
302     CacheItem<K,V> next = item._next;
303 
304     if (item._isOnce) {
305       item._isOnce = false;
306 
307       if (prev != null)
308     prev._next = next;
309       else
310     _head1 = next;
311 
312       if (next != null)
313     next._prev = prev;
314       else
315     _tail1 = prev;
316 
317       item._prev = null;
318       if (_head2 != null)
319     _head2._prev = item;
320       else
321     _tail2 = item;
322       
323       item._next = _head2;
324       _head2 = item;
325 
326       _size1--;
327       _size2++;
328     }
329     else {
330       if (prev == null)
331     return;
332       
333       prev._next = next;
334 
335       item._prev = null;
336       item._next = _head2;
337       
338       _head2._prev = item;
339       _head2 = item;
340       
341       if (next != null)
342     next._prev = prev;
343       else
344     _tail2 = prev;
345     }
346   }
347 
348   /**
349    * Remove the last item in the LRU
350    */
351   public boolean removeTail()
352   {
353     CacheItem<K,V> tail;
354 
355     if (_capacity1 <= _size1)
356       tail = _tail1 != null ? _tail1 : _tail2;
357     else
358       tail = _tail2 != null ? _tail2 : _tail1;
359 
360     if (tail == null)
361       return false;
362       
363     remove(tail._key);
364     
365     return true;
366   }
367 
368   /**
369    * Remove the last item in the LRU.  In this case, remove from the
370    * list with the longest length.
371    *
372    * For functions like Cache disk space, this is a better solution
373    * than the struct LRU removal.
374    */
375   public boolean removeLongestTail()
376   {
377     CacheItem<K,V> tail;
378 
379     if (_size1 <= _size2)
380       tail = _tail2 != null ? _tail2 : _tail1;
381     else
382       tail = _tail1 != null ? _tail1 : _tail2;
383 
384     if (tail == null)
385       return false;
386       
387     remove(tail._key);
388     
389     return true;
390   }
391 
392   /**
393    * Removes an item from the cache
394    *
395    * @param key the key to remove
396    *
397    * @return the value removed
398    */
399   public V remove(K key)
400   {
401     Object   okey = key;
402     if (okey == null)
403       okey = NULL;
404     
405     int hash = key.hashCode() & _mask;
406     int count = _size1 + _size2 + 1;
407 
408     V value = null;
409 
410     synchronized (this) {
411       for (; count > 0; count--) {
412     CacheItem<K,V> item = _entries[hash];
413 
414     if (item == null)
415       return null;
416 
417     if (item._key == okey || item._key.equals(okey)) {
418       _entries[hash] = null;
419 
420       CacheItem<K,V> prev = item._prev;
421       CacheItem<K,V> next = item._next;
422 
423       if (item._isOnce) {
424         _size1--; 
425 
426         if (prev != null)
427           prev._next = next;
428         else
429           _head1 = next;
430 
431         if (next != null)
432           next._prev = prev;
433         else
434           _tail1 = prev;
435       }
436       else {
437         _size2--; 
438 
439         if (prev != null)
440           prev._next = next;
441         else
442           _head2 = next;
443 
444         if (next != null)
445           next._prev = prev;
446         else
447           _tail2 = prev;
448       }
449 
450       value = item._value;
451 
452       // Shift colliding entries down
453       for (int i = 1; i <= count; i++) {
454         int nextHash = (hash + i) & _mask;
455         CacheItem<K,V> nextItem = _entries[nextHash];
456         if (nextItem == null)
457           break;
458 
459         _entries[nextHash] = null;
460         refillEntry(nextItem);
461       }
462       break;
463     }
464 
465     hash = (hash + 1) & _mask;
466       }
467 
468       if (value instanceof SyncCacheListener)
469     ((SyncCacheListener) value).syncRemoveEvent();
470     }
471 
472     if (count < 0)
473       throw new RuntimeException  ("internal cache error");
474 
475     if (value instanceof CacheListener)
476       ((CacheListener) value).removeEvent();
477 
478     return value;
479   }
480 
481   /**
482    * Put the item in the best location available in the hash table.
483    */
484   private void refillEntry(CacheItem<K,V> item)
485   {
486     int baseHash = item._key.hashCode();
487 
488     for (int count = 0; count < _size1 + _size2 + 1; count++) {
489       int hash = (baseHash + count) & _mask;
490 
491       if (_entries[hash] == null) {
492     _entries[hash] = item;
493     return;
494       }
495     }
496   }
497 
498   /**
499    * Returns the keys stored in the cache
500    */
501   public Iterator  <K> keys()
502   {
503     KeyIterator iter = new KeyIterator<K,V>(this);
504     iter.init(this);
505     return iter;
506   }
507 
508   /**
509    * Returns keys stored in the cache using an old iterator
510    */
511   public Iterator  <K> keys(Iterator  <K> oldIter)
512   {
513     KeyIterator iter = (KeyIterator) oldIter;
514     iter.init(this);
515     return oldIter;
516   }
517 
518   /**
519    * Returns the values in the cache
520    */
521   public Iterator  <V> values()
522   {
523     ValueIterator iter = new ValueIterator<K,V>(this);
524     iter.init(this);
525     return iter;
526   }
527 
528   public Iterator  <V> values(Iterator  <V> oldIter)
529   {
530     ValueIterator iter = (ValueIterator) oldIter;
531     iter.init(this);
532     return oldIter;
533   }
534 
535   /**
536    * Returns the entries
537    */
538   public Iterator  <Entry<K,V>> iterator()
539   {
540     return new EntryIterator();
541   }
542 
543   /**
544    * Returns the hit count.
545    */
546   public long getHitCount()
547   {
548     return _hitCount;
549   }
550 
551   /**
552    * Returns the miss count.
553    */
554   public long getMissCount()
555   {
556     return _missCount;
557   }
558 
559   /**
560    * A cache item
561    */
562   static class CacheItem<K,V> {
563     CacheItem<K,V> _prev;
564     CacheItem<K,V> _next;
565     K _key;
566     V _value;
567     int _index;
568     boolean _isOnce;
569 
570     CacheItem(K key, V value)
571     {
572       _key = key;
573       _value = value;
574       _isOnce = true;
575     }
576   }
577 
578   /**
579    * Iterator of cache keys
580    */
581   static class KeyIterator<K,V> implements Iterator  <K> {
582     private LruCache<K,V> _cache;
583     private int _i = -1;
584 
585     KeyIterator(LruCache<K,V> cache)
586     {
587       _cache = cache;
588     }
589 
590     void init(LruCache<K,V> cache)
591     {
592       _cache = cache;
593       _i = -1;
594     }
595 
596     /**
597      * Returns the next entry in the cache.
598      */
599     public boolean hasNext()
600     {
601       CacheItem<K,V> []entries = _cache._entries;
602       int length = entries.length;
603       
604       for (_i++; _i < length; _i++) {
605     if (entries[_i] != null) {
606       _i--;
607       return true;
608     }
609       }
610       
611       return false;
612     }
613 
614     /**
615      * Returns the next value.
616      */
617     public K next()
618     {
619       CacheItem<K,V> []entries = _cache._entries;
620       int length = entries.length;
621       
622       for (_i++; _i < length; _i++) {
623     CacheItem<K,V> entry = entries[_i];
624     
625     if (entry != null)
626       return entry._key;
627       }
628 
629       return null;
630     }
631 
632     public void remove()
633     {
634       throw new UnsupportedOperationException  ();
635     }
636   }
637 
638   /**
639    * Iterator of cache values
640    */
641   static class ValueIterator<K,V> implements Iterator  <V> {
642     private LruCache<K,V> _cache;
643     private int _i = -1;
644 
645     ValueIterator(LruCache<K,V> cache)
646     {
647       init(cache);
648     }
649 
650     void init(LruCache<K,V> cache)
651     {
652       _cache = cache;
653       _i = -1;
654     }
655 
656     /**
657      * Returns the next entry in the cache.
658      */
659     public boolean hasNext()
660     {
661       CacheItem<K,V> []entries = _cache._entries;
662       int length = entries.length;
663 
664       int i = _i + 1;
665       for (; i < length; i++) {
666     if (entries[i] != null) {
667       _i = i - 1;
668       
669       return true;
670     }
671       }
672       _i = i;
673       
674       return false;
675     }
676 
677     /**
678      * Returns the next value.
679      */
680     public V next()
681     {
682       CacheItem<K,V> []entries = _cache._entries;
683       int length = entries.length;
684 
685       int i = _i + 1;
686       for (; i < length; i++) {
687     CacheItem<K,V> entry = entries[i];
688     
689     if (entry != null) {
690       _i = i;
691       return entry._value;
692     }
693       }
694       _i = i;
695 
696       return null;
697     }
698 
699     public void remove()
700     {
701       throw new UnsupportedOperationException  ();
702     }
703   }
704 
705   /**
706    * Interface for entry iterator;
707    */
708   public interface Entry<K,V> {
709     /**
710      * Returns the key.
711      */
712     public K getKey();
713     
714     /**
715      * Returns the value.
716      */
717     public V getValue();
718   }
719 
720   /**
721    * Iterator of cache values
722    */
723   class EntryIterator implements Iterator  <Entry<K,V>>, Entry<K,V> {
724     private int _i = -1;
725 
726     public boolean hasNext()
727     {
728       int i = _i + 1;
729       CacheItem<K,V> []entries = _entries;
730       int length = entries.length;
731 
732       for (; i < length && entries[i] == null; i++) {
733       }
734 
735       _i = i - 1;
736       
737       return i < length;
738     }
739 
740     public Entry<K,V> next()
741     {
742       int i = _i + 1;
743       CacheItem<K,V> []entries = _entries;
744       int length = entries.length;
745 
746       for (; i < length && entries[i] == null; i++) {
747       }
748 
749       _i = i;
750       
751       if (_i < length) {
752     return this;
753       }
754       else
755     return null;
756     }
757 
758     /**
759      * Returns the key.
760      */
761     public K getKey()
762     {
763       if (_i < _entries.length) {
764     CacheItem<K,V> entry = _entries[_i];
765     
766     return entry != null ? entry._key : null;
767       }
768 
769       return null;
770     }
771 
772     /**
773      * Returns the value.
774      */
775     public V getValue()
776     {
777       if (_i < _entries.length) {
778     CacheItem<K,V> entry = _entries[_i];
779     
780     return entry != null ? entry._value : null;
781       }
782 
783       return null;
784     }
785 
786     public void remove()
787     {
788       if (_i < _entries.length) {
789     CacheItem<K,V> entry = _entries[_i];
790 
791     if (entry != null)
792       LruCache.this.remove(entry._key);
793       }
794     }
795   }
796 }
797
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags