LongKeyLruCache


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   *
23   *   Free Software Foundation, Inc.
24   *   59 Temple Place, Suite 330
25   *   Boston, MA 02111-1307  USA
26   *
27   * @author Scott Ferguson
28   */
29  
30  package com.caucho.util;
31  
32  import java.util.ArrayList  ;
33  import java.util.Iterator  ;
34  import java.util.logging.Logger  ;
35  
36  /**
37   * Fixed length cache with a LRU replacement policy.  If cache items
38   * implement CacheListener, they will be informed when they're removed
39   * from the cache.
40   *
41   * <p>LongKeyLruCache is synchronized.
42   */
43  public class LongKeyLruCache<V> {
44    private static final Logger   log
45      = Logger.getLogger(LongKeyLruCache.class.getName());
46    private static final Integer   NULL = new Integer  (0);
47    
48    // hash table containing the entries.  Its size is twice the capacity
49    // so it will always remain at least half empty
50    private CacheItem<V> []_entries;
51    
52    // maximum allowed entries
53    private int _capacity;
54    // size 1 capacity is half the actual capacity
55    private int _capacity1;
56    
57    // mask for hash mapping
58    private int _mask;
59    
60    // number of items in the cache seen once
61    private int _size1;
62  
63    // head of the LRU list
64    private CacheItem<V> _head1;
65    // tail of the LRU list
66    private CacheItem<V> _tail1;
67    
68    // number of items in the cache seen more than once
69    private int _size2;
70  
71    // head of the LRU list
72    private CacheItem<V> _head2;
73    // tail of the LRU list
74    private CacheItem<V> _tail2;
75  
76    // hit count statistics
77    private volatile long _hitCount;
78    // miss count statistics
79    private volatile long _missCount;
80    
81    /**
82     * Create the LRU cache with a specific capacity.
83     *
84     * @param initialCapacity minimum capacity of the cache
85     */
86    public LongKeyLruCache(int initialCapacity)
87    {
88      int capacity;
89  
90      for (capacity = 16; capacity < 8 * initialCapacity; capacity *= 2) {
91      }
92  
93      _entries = new CacheItem[capacity];
94      _mask = capacity - 1;
95  
96      _capacity = initialCapacity;
97      _capacity1 = _capacity / 2;
98    }
99  
100   /**
101    * Returns the current number of entries in the cache.
102    */
103   public int size()
104   {
105     return _size1 + _size2;
106   }
107 
108   /**
109    * Returns the capacity.
110    */
111   public int getCapacity()
112   {
113     return _capacity;
114   }
115 
116   /**
117    * Ensure the cache can contain the given value.
118    */
119   public void ensureCapacity(int newCapacity)
120   {
121     synchronized (this) {
122       int capacity;
123 
124       for (capacity = _entries.length;
125        capacity < 8 * newCapacity;
126        capacity *= 2) {
127       }
128 
129       if (capacity == _entries.length)
130     return;
131 
132       CacheItem []oldEntries = _entries;
133       
134       _entries = new CacheItem[capacity];
135       _mask = capacity - 1;
136       
137       _capacity = newCapacity;
138       _capacity1 = _capacity / 2;
139 
140       for (int i = 0; i < oldEntries.length; i++) {
141     if (oldEntries[i] != null)
142       refillEntry(oldEntries[i]);
143       }
144     }
145   }
146 
147   /**
148    * Clears the cache
149    */
150   public void clear()
151   {
152     ArrayList  <CacheListener> listeners = null;
153     ArrayList  <SyncCacheListener> syncListeners = null;
154 
155     synchronized (this) {
156       for (int i = _entries.length - 1; i >= 0; i--) {
157         CacheItem<V> item = _entries[i];
158 
159         if (item != null) {
160           if (item._value instanceof CacheListener) {
161             if (listeners == null)
162               listeners = new ArrayList  <CacheListener>();
163             listeners.add((CacheListener) item._value);
164           }
165       
166           if (item._value instanceof SyncCacheListener) {
167             if (syncListeners == null)
168               syncListeners = new ArrayList  <SyncCacheListener>();
169             syncListeners.add((SyncCacheListener) item._value);
170           }
171         }
172         
173         _entries[i] = null;
174       }
175 
176       _size1 = 0;
177       _head1 = null;
178       _tail1 = null;
179       _size2 = 0;
180       _head2 = null;
181       _tail2 = null;
182     }
183 
184     for (int i = listeners == null ? -1 : listeners.size() - 1; i >= 0; i--) {
185       CacheListener listener = listeners.get(i);
186       listener.removeEvent();
187     }
188 
189     for (int i = syncListeners == null ? -1 : syncListeners.size() - 1; i >= 0; i--) {
190       SyncCacheListener listener = syncListeners.get(i);
191       listener.syncRemoveEvent();
192     }
193   }
194 
195   /**
196    * Get an item from the cache and make it most recently used.
197    *
198    * @param key key to lookup the item
199    * @return the matching object in the cache
200    */
201   public V get(long key)
202   {
203     int hash = hash(key) & _mask;
204     int count = _size1 + _size2 + 1;
205 
206     synchronized (this) {
207       for (; count >= 0; count--) {
208         CacheItem<V> item = _entries[hash];
209 
210         if (item == null) {
211       _missCount++;
212           return null;
213     }
214 
215         if (item._key == key) {
216           updateLru(item);
217 
218       _hitCount++;
219 
220           return item._value;
221         }
222 
223         hash = (hash + 1) & _mask;
224       }
225       
226       _missCount++;
227     }
228 
229     return null;
230   }
231 
232   /**
233    * Puts a new item in the cache.  If the cache is full, remove the
234    * LRU item.
235    *
236    * @param key key to store data
237    * @param value value to be stored
238    *
239    * @return old value stored under the key
240    */
241   public V put(long key, V value)
242   {
243     V oldValue = put(key, value, true);
244 
245     if (oldValue instanceof CacheListener)
246       ((CacheListener) oldValue).removeEvent();
247 
248     return oldValue;
249   }
250 
251   /**
252    * Puts a new item in the cache.  If the cache is full, remove the
253    * LRU item.
254    *
255    * @param key key to store data
256    * @param value value to be stored
257    *
258    * @return the value actually stored
259    */
260   public V putIfNew(long key, V value)
261   {
262     V oldValue = put(key, value, false);
263 
264     if (oldValue != null)
265       return oldValue;
266     else
267       return value;
268   }
269 
270   /**
271    * Puts a new item in the cache.  If the cache is full, remove the
272    * LRU item.
273    *
274    * @param key key to store data
275    * @param value value to be stored
276    *
277    * @return old value stored under the key
278    */
279   private V put(long key, V value, boolean replace)
280   {
281     // remove LRU items until we're below capacity
282     for (int max = 32;
283      max > 0 && _capacity <= _size1 + _size2 && removeTail();
284      max--) {
285     }
286 
287     int hash = hash(key) & _mask;
288     int count = _size1 + _size2 + 1;
289 
290     V oldValue = null;
291 
292     synchronized (this) {
293       for (; count > 0; count--) {
294     CacheItem<V> item = _entries[hash];
295 
296     // No matching item, so create one
297     if (item == null) {
298       item = new CacheItem<V>(key, value);
299       _entries[hash] = item;
300       _size1++;
301       
302       item._next = _head1;
303       if (_head1 != null)
304         _head1._prev = item;
305           else
306             _tail1 = item;
307       _head1 = item;
308 
309       return null;
310     }
311 
312     // matching item gets replaced
313     if (item._key == key) {
314       updateLru(item);
315 
316       oldValue = item._value;
317 
318       if (replace)
319         item._value = value;
320 
321       break;
322     }
323 
324     hash = (hash + 1) & _mask;
325       }
326 
327       if (replace && oldValue instanceof SyncCacheListener)
328     ((SyncCacheListener) oldValue).syncRemoveEvent();
329     }
330 
331     if (replace && oldValue instanceof CacheListener)
332       ((CacheListener) oldValue).removeEvent();
333 
334     return oldValue;
335   }
336 
337   /**
338    * Put item at the head of the used-twice lru list.
339    * This is always called while synchronized.
340    */
341   private void updateLru(CacheItem<V> item)
342   {
343     CacheItem<V> prev = item._prev;
344     CacheItem<V> next = item._next;
345 
346     if (item._isOnce) {
347       item._isOnce = false;
348 
349       if (prev != null)
350     prev._next = next;
351       else
352     _head1 = next;
353 
354       if (next != null)
355     next._prev = prev;
356       else
357     _tail1 = prev;
358 
359       item._prev = null;
360       if (_head2 != null)
361     _head2._prev = item;
362       else
363     _tail2 = item;
364       
365       item._next = _head2;
366       _head2 = item;
367 
368       _size1--;
369       _size2++;
370     }
371     else {
372       if (prev == null)
373     return;
374       
375       prev._next = next;
376 
377       item._prev = null;
378       item._next = _head2;
379       
380       _head2._prev = item;
381       _head2 = item;
382       
383       if (next != null)
384     next._prev = prev;
385       else
386     _tail2 = prev;
387     }
388   }
389 
390   /**
391    * Remove the last item in the LRU
392    */
393   public boolean removeTail()
394   {
395     CacheItem<V> tail;
396 
397     if (_capacity1 <= _size1)
398       tail = _tail1;
399     else
400       tail = _tail2;
401 
402     for (int max = 32; max > 0; max--) {
403       if (tail == null)
404     return false;
405 
406       Object   value = tail._value;
407 
408       synchronized (this) {
409     // check the item for its use
410     if (value instanceof ClockCacheItem) {
411       ClockCacheItem item = (ClockCacheItem) value;
412       item.clearUsed();
413 
414       if (item.isUsed()) {
415         tail = tail._prev;
416         continue;
417       }
418     }
419       
420     value = removeImpl(tail._key);
421 
422     if (value instanceof SyncCacheListener)
423       ((SyncCacheListener) value).syncRemoveEvent();
424       }
425 
426       if (value instanceof CacheListener)
427     ((CacheListener) value).removeEvent();
428     
429       return true;
430     }
431 
432     log.fine("LRU-Cache can't remove tail because the tail values are busy.");
433 
434     return false;
435   }
436 
437   /**
438    * Removes an item from the cache
439    *
440    * @param key the key to remove
441    *
442    * @return the value removed
443    */
444   public V remove(long key)
445   {
446     V value = null;
447 
448     synchronized (this) {
449       value = removeImpl(key);
450 
451       if (value instanceof SyncCacheListener)
452     ((SyncCacheListener) value).syncRemoveEvent();
453     }
454 
455     if (value instanceof CacheListener)
456       ((CacheListener) value).removeEvent();
457 
458     return value;
459   }
460 
461   /**
462    * Removes an item from the cache.  Must be called from a synchronized block.
463    *
464    * @param key the key to remove
465    *
466    * @return the value removed
467    */
468   private V removeImpl(long key)
469   {
470     int hash = hash(key) & _mask;
471     int count = _size1 + _size2 + 1;
472 
473     V value = null;
474 
475     for (; count > 0; count--) {
476       CacheItem<V> item = _entries[hash];
477 
478       if (item == null)
479     return null;
480 
481       if (item._key == key) {
482     _entries[hash] = null;
483 
484     CacheItem<V> prev = item._prev;
485     CacheItem<V> next = item._next;
486 
487     if (item._isOnce) {
488       _size1--; 
489 
490       if (prev != null)
491         prev._next = next;
492       else
493         _head1 = next;
494 
495       if (next != null)
496         next._prev = prev;
497       else
498         _tail1 = prev;
499     }
500     else {
501       _size2--; 
502 
503       if (prev != null)
504         prev._next = next;
505       else
506         _head2 = next;
507 
508       if (next != null)
509         next._prev = prev;
510       else
511         _tail2 = prev;
512     }
513 
514     value = item._value;
515 
516     // Shift colliding entries down
517     for (int i = 1; i <= count; i++) {
518       int nextHash = (hash + i) & _mask;
519       CacheItem<V> nextItem = _entries[nextHash];
520       if (nextItem == null)
521         break;
522 
523       _entries[nextHash] = null;
524       refillEntry(nextItem);
525     }
526     break;
527       }
528 
529       hash = (hash + 1) & _mask;
530     }
531 
532     if (count < 0)
533       throw new RuntimeException  ("internal cache error");
534 
535     return value;
536   }
537 
538   /**
539    * Put the item in the best location available in the hash table.
540    */
541   private void refillEntry(CacheItem<V> item)
542   {
543     int baseHash = hash(item._key);
544 
545     for (int count = 0; count < _size1 + _size2 + 1; count++) {
546       int hash = (baseHash + count) & _mask;
547 
548       if (_entries[hash] == null) {
549     _entries[hash] = item;
550     return;
551       }
552     }
553   }
554 
555   private static int hash(long key)
556   {
557     long hash = key;
558     
559     hash = 65537 * hash + (key >>> 8);
560     hash = 65537 * hash + (key >>> 16);
561     hash = 65537 * hash + (key >>> 32);
562     hash = 65537 * hash + (key >>> 48);
563 
564     return (int) hash;
565   }
566 
567   /**
568    * Returns the values in the cache
569    */
570   public Iterator  <V> values()
571   {
572     ValueIterator iter = new ValueIterator<V>(this);
573     iter.init(this);
574     return iter;
575   }
576 
577   public Iterator  <V> values(Iterator  <V> oldIter)
578   {
579     ValueIterator iter = (ValueIterator) oldIter;
580     iter.init(this);
581     return oldIter;
582   }
583 
584   /**
585    * Returns the hit count.
586    */
587   public long getHitCount()
588   {
589     return _hitCount;
590   }
591 
592   /**
593    * Returns the miss count.
594    */
595   public long getMissCount()
596   {
597     return _missCount;
598   }
599 
600   /**
601    * A cache item
602    */
603   static class CacheItem<V> {
604     CacheItem<V> _prev;
605     CacheItem<V> _next;
606     long _key;
607     V _value;
608     int _index;
609     boolean _isOnce;
610 
611     CacheItem(long key, V value)
612     {
613       _key = key;
614       _value = value;
615       _isOnce = true;
616     }
617   }
618 
619   /**
620    * Iterator of cache values
621    */
622   static class ValueIterator<V> implements Iterator  <V> {
623     private LongKeyLruCache<V> _cache;
624     private int _i = -1;
625 
626     ValueIterator(LongKeyLruCache<V> cache)
627     {
628       init(cache);
629     }
630 
631     void init(LongKeyLruCache<V> cache)
632     {
633       _cache = cache;
634       _i = -1;
635     }
636 
637     /**
638      * Returns the next entry in the cache.
639      */
640     public boolean hasNext()
641     {
642       CacheItem<V> []entries = _cache._entries;
643       int length = entries.length;
644 
645       int i = _i + 1;
646       for (; i < length; i++) {
647     if (entries[i] != null) {
648       _i = i - 1;
649       
650       return true;
651     }
652       }
653       _i = i;
654       
655       return false;
656     }
657 
658     /**
659      * Returns the next value.
660      */
661     public V next()
662     {
663       CacheItem<V> []entries = _cache._entries;
664       int length = entries.length;
665 
666       int i = _i + 1;
667       for (; i < length; i++) {
668     CacheItem<V> entry = entries[i];
669     
670     if (entry != null) {
671       _i = i;
672       return entry._value;
673     }
674       }
675       _i = i;
676 
677       return null;
678     }
679 
680     public void remove()
681     {
682       throw new UnsupportedOperationException  ();
683     }
684   }
685 }
686
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags