WeakLruCache


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 SoftwareFoundation, 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.lang.ref.WeakReference  ;
32  import java.util.ArrayList  ;
33  import java.util.Iterator  ;
34  
35  /**
36   * Fixed length cache with a LRU replacement policy.  If cache items
37   * implement CacheListener, they will be informed when they're removed
38   * from the cache.
39   *
40   * <p>Null keys are not allowed.  LruCache is synchronized.
41   */
42  public class WeakLruCache<K,V> {
43    // hash table containing the entries.  Its size is twice the capacity
44    // so it will always remain at least half empty
45    private CacheItem []_entries;
46    // maximum allowed entries
47    private int _capacity;
48    // number of items in the cache
49    private int _size;
50    private int _mask;
51  
52    // head of the LRU list
53    private CacheItem<K,V> _head;
54    // tail of the LRU list
55    private CacheItem<K,V> _tail;
56    
57    private static Integer   NULL = new Integer  (0);
58    
59    /**
60     * Create the LRU cache with a specific capacity.
61     *
62     * @param initialCapacity minimum capacity of the cache
63     */
64    public WeakLruCache(int initialCapacity)
65    {
66      int capacity;
67  
68      for (capacity = 16; capacity < 2 * initialCapacity; capacity *= 2) {
69      }
70  
71      _entries = new CacheItem[capacity];
72      _mask = capacity - 1;
73  
74      _capacity = initialCapacity;
75    }
76  
77    /**
78     * Returns the current number of entries in the cache.
79     */
80    public int size()
81    {
82      return _size;
83    }
84  
85    /**
86     * Clears the cache
87     */
88    public void clear()
89    {
90      ArrayList  <CacheListener> listeners = null;
91  
92      synchronized (this) {
93        for (int i = 0; i < _entries.length; i++) {
94          CacheItem<K,V> item = _entries[i];
95  
96          if (item != null) {
97            V value = item.getValue();
98            
99            if (value instanceof CacheListener) {
100             if (listeners == null)
101               listeners = new ArrayList  <CacheListener>();
102             listeners.add((CacheListener) value);
103           }
104         }
105         
106         _entries[i] = null;
107       }
108 
109       _size = 0;
110       _head = null;
111       _tail = null;
112     }
113 
114     for (int i = listeners == null ? -1 : listeners.size() - 1; i >= 0; i--) {
115       CacheListener listener = listeners.get(i);
116       listener.removeEvent();
117     }
118   }
119 
120   /**
121    * Get an item from the cache and make it most recently used.
122    *
123    * @param key key to lookup the item
124    * @return the matching object in the cache
125    */
126   public V get(K key)
127   {
128     Object   okey = key;
129     if (okey == null)
130       okey = NULL;
131     
132     int hash = okey.hashCode() & _mask;
133     int count = _size + 1;
134 
135     synchronized (this) {
136       for (; count > 0; count--) {
137         CacheItem<K,V> item = _entries[hash];
138 
139         if (item == null)
140           return null;
141 
142         if (item._key == key || item._key.equals(key)) {
143           updateLru(item);
144 
145           return item.getValue();
146         }
147 
148         hash = (hash + 1) & _mask;
149       }
150     }
151 
152     return null;
153   }
154 
155   /**
156    * Puts a new item in the cache.  If the cache is full, remove the
157    * LRU item.
158    *
159    * @param key key to store data
160    * @param value value to be stored
161    *
162    * @return old value stored under the key
163    */
164   public V put(K key, V value)
165   {
166     Object   okey = key;
167     
168     if (okey == null)
169       okey = NULL;
170 
171     // remove LRU items until we're below capacity
172     while (_capacity <= _size) {
173       remove(_tail._key);
174     }
175 
176     V oldValue = null;
177 
178     int hash = key.hashCode() & _mask;
179     int count = _size + 1;
180 
181     synchronized (this) {
182       for (; count > 0; count--) {
183     CacheItem<K,V> item = _entries[hash];
184 
185     // No matching item, so create one
186     if (item == null) {
187       item = new CacheItem<K,V>(key, value);
188       _entries[hash] = item;
189       _size++;
190       item._next = _head;
191       if (_head != null)
192         _head._prev = item;
193           else
194             _tail = item;
195       _head = item;
196 
197       return null;
198     }
199 
200     // matching item gets replaced
201     if (item._key == okey || item._key.equals(okey)) {
202       updateLru(item);
203 
204       oldValue = item.getValue();
205       item.setValue(value);
206       break;
207     }
208 
209     hash = (hash + 1) & _mask;
210       }
211     }
212     
213     if (oldValue instanceof CacheListener && oldValue != value)
214       ((CacheListener) oldValue).removeEvent();
215 
216     return oldValue;
217   }
218 
219   /**
220    * Put item at the head of the lru list.  This is always called while
221    * synchronized.
222    */
223   private void updateLru(CacheItem<K,V> item)
224   {
225     CacheItem<K,V> prev = item._prev;
226     CacheItem<K,V> next = item._next;
227 
228     if (prev != null) {
229       prev._next = next;
230 
231       item._prev = null;
232       item._next = _head;
233       _head._prev = item;
234       _head = item;
235 
236       if (next != null)
237     next._prev = prev;
238       else
239     _tail = prev;
240     }
241   }
242 
243   /**
244    * Remove the last item in the LRU
245    */
246   public boolean removeTail()
247   {
248     CacheItem<K,V> last = _tail;
249 
250     if (last == null)
251       return false;
252     else {
253       remove(last._key);
254       return true;
255     }
256   }
257 
258   /**
259    * Removes an item from the cache
260    *
261    * @param key the key to remove
262    *
263    * @return the value removed
264    */
265   public V remove(K key)
266   {
267     Object   okey = key;
268     if (okey == null)
269       okey = NULL;
270     
271     int hash = key.hashCode() & _mask;
272     int count = _size + 1;
273 
274     V value = null;
275 
276     synchronized (this) {
277       for (; count > 0; count--) {
278     CacheItem<K,V> item = _entries[hash];
279 
280     if (item == null)
281       return null;
282 
283     if (item._key == okey || item._key.equals(okey)) {
284       _entries[hash] = null;
285       _size--; 
286 
287       CacheItem<K,V> prev = item._prev;
288       CacheItem<K,V> next = item._next;
289 
290       if (prev != null)
291         prev._next = next;
292       else
293         _head = next;
294 
295       if (next != null)
296         next._prev = prev;
297       else
298         _tail = prev;
299 
300       // Shift colliding entries down
301       for (int i = 1; i <= count; i++) {
302         int nextHash = (hash + i) & _mask;
303         CacheItem<K,V> nextItem = _entries[nextHash];
304         if (nextItem == null)
305           break;
306 
307         _entries[nextHash] = null;
308         refillEntry(nextItem);
309       }
310 
311       value = item.getValue();
312       break;
313     }
314 
315     hash = (hash + 1) & _mask;
316       }
317     }
318 
319     if (count < 0)
320       throw new RuntimeException  ("internal cache error");
321 
322     if (value instanceof CacheListener)
323       ((CacheListener) value).removeEvent();
324 
325     return value;
326   }
327 
328   /**
329    * Put the item in the best location available in the hash table.
330    */
331   private void refillEntry(CacheItem<K,V> item)
332   {
333     int baseHash = item._key.hashCode();
334 
335     for (int count = 0; count < _size + 1; count++) {
336       int hash = (baseHash + count) & _mask;
337 
338       if (_entries[hash] == null) {
339     _entries[hash] = item;
340     return;
341       }
342     }
343   }
344 
345   /**
346    * Returns the keys stored in the cache
347    */
348   public Iterator  <K> keys()
349   {
350     KeyIterator<K,V> iter = new KeyIterator<K,V>();
351     iter.init(this);
352     return iter;
353   }
354 
355   /**
356    * Returns keys stored in the cache using an old iterator
357    */
358   public Iterator  <K> keys(Iterator  <K> oldIter)
359   {
360     KeyIterator iter = (KeyIterator) oldIter;
361     iter.init(this);
362     return oldIter;
363   }
364 
365   /**
366    * Returns the values in the cache
367    */
368   public Iterator  <V> values()
369   {
370     ValueIterator<K,V> iter = new ValueIterator<K,V>();
371     iter.init(this);
372     return iter;
373   }
374 
375   public Iterator  <V> values(Iterator  <V> oldIter)
376   {
377     ValueIterator iter = (ValueIterator) oldIter;
378     iter.init(this);
379     return oldIter;
380   }
381 
382   /**
383    * A cache item
384    */
385   static class CacheItem<K,V> {
386     CacheItem<K,V> _prev;
387     CacheItem<K,V> _next;
388     K _key;
389     private WeakReference  <V> _value;
390     int _index;
391 
392     CacheItem(K key, V value)
393     {
394       _key = key;
395       
396       if (value == null)
397         _value = null;
398       else
399         _value = new WeakReference  <V>(value);
400     }
401 
402     public final V getValue()
403     {
404       WeakReference  <V> ref = _value;
405 
406       if (ref == null)
407         return null;
408       else
409         return ref.get();
410     }
411 
412     public final void setValue(V value)
413     {
414       if (value == null)
415         _value = null;
416       else
417         _value = new WeakReference  <V>(value);
418     }
419   }
420 
421   /**
422    * Iterator of cache keys
423    */
424   static class KeyIterator<K,V> implements Iterator  <K> {
425     CacheItem<K,V> _item;
426 
427     void init(WeakLruCache<K,V> cache)
428     {
429       _item = cache._head;
430     }
431 
432     public boolean hasNext()
433     {
434       return _item != null;
435     }
436 
437     public K next()
438     {
439       K key = _item._key;
440 
441       _item = _item._next;
442 
443       return key;
444     }
445 
446     public void remove()
447     {
448       throw new UnsupportedOperationException  ();
449     }
450   }
451 
452   /**
453    * Iterator of cache values
454    */
455   static class ValueIterator<K,V> implements Iterator  <V> {
456     CacheItem<K,V> _item;
457 
458     void init(WeakLruCache<K,V> cache)
459     {
460       _item = cache._head;
461     }
462 
463     public boolean hasNext()
464     {
465       return _item != null;
466     }
467 
468     public V next()
469     {
470       V value = _item.getValue();
471 
472       _item = _item._next;
473 
474       return value;
475     }
476 
477     public void remove()
478     {
479       throw new UnsupportedOperationException  ();
480     }
481   }
482 }
483
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags