Cache


1   /*
2    * Cache.java
3    *
4    * Created: Fri Dec 21 11:38:14 2001
5    * Author : Ole Arndt
6    */
7   package org.enhydra.xml.xmlc.deferredparsing;
8   
9   import java.lang.ref.ReferenceQueue  ;
10  import java.lang.ref.WeakReference  ;
11  import java.util.AbstractCollection  ;
12  import java.util.Collection  ;
13  import java.util.HashMap  ;
14  import java.util.Iterator  ;
15  import java.util.Map  ;
16  import java.util.Set  ;
17  
18  /**
19   * A Cache for arbitrary objects. It holds its objects with soft
20   * references. Because broken handling of soft references in
21   * current JVM implementations, we also hold additional hard
22   * references to the most recently used entries.
23   *
24   * @author  <a HREF="mailto:arndt@tivano.de">Ole Arndt</a>
25   * @version $Id: Cache.java,v 1.3 2005/01/26 08:29:24 jkjome Exp $
26   */
27  public class Cache implements Map   {
28      
29      /**
30       * A simple class for holding references to
31       * the most recently used entries.
32       */
33      protected static class MRUCache {
34          
35          private static final class Entry {
36              public Object   ref;
37              public Cache.MRUCache.Entry prev;
38              public Cache.MRUCache.Entry next;
39          }
40          
41              
42          /** an array to hold the references. */
43          private Entry[] cache;
44  
45          /** list of free entries */
46          private Entry freelist;
47          
48          /** Current index into ref array. */
49          private Entry header;
50  
51          /**
52           * Creates a new <code>MRUCache</code> instance.
53           *
54           * @param num an <code>int</code> value
55           */
56          MRUCache(int num) {
57              cache = new Entry[num];
58              for (int i = 0; i < cache.length; ++i)
59                  cache[i] = new Entry();
60              
61              header = new Entry();
62              this.clear();
63          }
64  
65          /**
66           * Describe <code>getCapacity</code> method here.
67           *
68           * @return an <code>int</code> value
69           */
70          int getCapacity() {
71              return cache.length;
72          }
73  
74          /**
75           * Describe <code>add</code> method here.
76           *
77           * @param obj an <code>Object</code> value
78           * @return an <code>Object</code> value
79           */
80           synchronized Object   add(Object   obj) {
81              // if object is already at front of cache
82              // return immediately
83              if (obj == null || obj == header.next.ref)
84                  return obj;
85              
86              Entry entry = null;
87  
88              if ((entry = find(obj)) != null) {
89                  extractEntry(entry);
90              } else if (freelist != null) {
91                  entry = freelist;
92                  freelist = entry.next;
93              } else {
94                  // remove from back
95                  entry = header.prev;
96                  extractEntry(entry);
97              }
98  
99              entry.ref = obj;
100 
101             // insert to front
102             entry.next = header.next;
103             entry.prev = header;
104             entry.next.prev = entry;
105             header.next = entry;
106             
107             return obj;
108         }
109 
110         
111         /**
112          * Remove an object from the cache.
113          *
114          * @param obj an <code>Object</code> value
115          */
116         synchronized void remove(Object   obj) {
117             Entry entry = null;
118             if (obj != null && (entry = find(obj)) != null) {
119                 extractEntry(entry);
120 
121                 entry.ref = null;
122                 entry.next = freelist;
123                 freelist = entry;
124             }
125         }
126         
127         /**
128          * Clear the MRU cache.
129          */
130          synchronized void clear() {
131             header.next = header.prev = header;
132             
133             for (int i = 0; i < (cache.length - 1); ++i) {
134                 cache[i].next = cache[i + 1];
135                 cache[i].ref = null;
136             }
137             
138             freelist = cache[0];
139             cache[cache.length - 1].next = null;
140             cache[cache.length - 1].ref  = null;
141         }
142 
143         /**
144          * Find an entry by object.
145          *
146          * @param obj an <code>Object</code> value
147          * @return an <code>Object</code> value
148          */
149         private Entry find(Object   obj) {
150             for (Entry e = header.next; e != header; e = e.next) {
151                 if (e.ref == obj)
152                     return e;
153             }
154             return null;
155         }
156 
157 
158         /**
159          * Extract an entry.
160          *
161          * @param e an <code>Entry</code> value
162          */
163         private void extractEntry(Entry entry) {
164             entry.next.prev = entry.prev;
165             entry.prev.next = entry.next;
166         }
167         
168     }
169 
170     /**
171      * An inner class to hold the mappings.
172      */
173     private class MapEntry extends WeakReference   implements Map.Entry   {
174         /** the key */
175         private Object   key;
176         
177         /**
178          * Creates a new <code>MapEntry</code> instance.
179          *
180          * @param key an <code>Object</code> value
181          * @param value an <code>Object</code> value
182          * @param queue the reference queue this entry will be enqueued on.
183          */
184         MapEntry(Object   key, Object   value, ReferenceQueue   queue) {
185             super(value, queue);
186             this.key = key;
187         }
188 
189         /**
190          * Get the Key value.
191          * @return the Key value.
192          */
193         public Object   getKey() {
194             return key;
195         }
196 
197         /**
198          * Get the Value value.
199          * @return the Value value.
200          */
201         public Object   getValue() {
202             return this.get();
203         }
204 
205         /**
206          * Set the Value value.
207          * @param value The new Value value.
208          */
209         public Object   setValue(Object   value) {
210             return Cache.this.put(key, value);
211         }
212 
213         public boolean equals(Object   o) {
214             return (o!=null) &&
215                 (o instanceof MapEntry) &&
216                 (key.equals(((MapEntry)o).getKey()));
217         }
218 
219         public int hashCode() {
220             return key.hashCode();
221         }
222     }
223     
224     /**
225      * An iterator for the entry set.
226      */
227     private class ValueIterator implements Iterator   {
228         Iterator   it;
229 
230         public ValueIterator(Iterator   it) {
231             this.it = it;
232         }
233         
234         public boolean hasNext() {
235             return it.hasNext();
236         }
237 
238         public Object   next() {
239             return mru.add(((MapEntry) it.next()).getValue());
240         }
241 
242         public void remove() {
243             it.remove();
244         }
245     }
246 
247     /** the default size for the MRU cache */
248     public static final int DEFAULT_NUM_MRU_ENTRIES = 64;
249     
250     /** the reference queue for collecting old references */
251     private ReferenceQueue   queue = new ReferenceQueue  ();
252 
253     /** the underlying map */
254     private HashMap   map = new HashMap  ();
255 
256     /** the  MRU cache */
257     private MRUCache mru;
258 
259     /**
260      * Creates a new <code>Cache</code> instance with the
261      * default value for most recently used entries.
262      *
263      */
264     public Cache () {
265         this(DEFAULT_NUM_MRU_ENTRIES);
266     }
267 
268     /**
269      * Creates a new <code>Cache</code> instance with an
270      * explicit value for most recently used entries cache.
271      *
272      * @param numMRUEntries an <code>int</code> value
273      */
274     public Cache (int numMRUEntries) {
275         mru = new MRUCache(numMRUEntries);
276     }
277 
278     /**
279      * Creates a new <code>Cache</code> instance.
280      * The give <code>Map</code> will be copied.
281      * 
282      * @param other a <code>Map</code> value
283      */
284     public Cache (Map   other) { 
285         this();
286         putAll(other);
287     }
288     
289     /**
290      * Creates a new <code>Cache</code> instance.
291      * The give <code>Map</code> will be copied.
292      * 
293      * @param other a <code>Map</code> value
294      */
295     public Cache (int numMRUEntries, Map   other) { 
296         this(numMRUEntries);
297         putAll(other);
298     }
299 
300     /**
301      * Get hash code of map.
302      *
303      * @return an <code>int</code> value
304      */
305     public int hashCode() {
306         return map.hashCode();
307     }
308 
309     /**
310      * Compare two <code>Cache</code> instances.
311      *
312      * @param cache other cache to compare to.
313      * @return true if caches are equal, false otherwise.
314      */
315     public boolean equals(Object   cache) {
316         return (cache instanceof Cache) && map.equals(((Cache)cache).map);
317     }
318 
319     /**
320      * Get the current size of the cache.
321      *
322      * @return the size of the cache.
323      */
324     public int size() {
325         return map.size();
326     }
327 
328     /**
329      * Describe <code>clear</code> method here.
330      *
331      */
332     public void clear() {
333         mru.clear();
334         map.clear();
335     }
336 
337     /**
338      * Associates the specified value with the specified key in this cache.
339      * If the cache previously contained a mapping for this key, the old value is replaced.
340      * Note that this cache can not map <code>null</code> values.
341      * 
342      * @param key key with which the specified value is to be associated.
343      * @param value value to be associated with the specified key.
344      * @return previous value associated with specified key, or null if there was no mapping for key.
345      * @throws NullPointerException if <code>value</code> is <code>null</code>.
346      */
347     public synchronized Object   put(Object   key, Object   value) {
348 
349         // cannot map null values, they do not differ from
350         // cleared soft references.
351         if (value == null)
352             return new UnsupportedOperationException  ("Cache does not support null values");
353 
354         // clean up before us, so we don't fill the memory
355         // with keys if user calls only #put and never #get
356         cleanup();
357 
358         MapEntry entry = (MapEntry) map.put(key, new MapEntry(key, value, queue));
359 
360         return (entry != null) ? entry.getValue() : null;
361     }
362 
363     /**
364      * Returns the value to which this cache maps the specified key.
365      * If the value is not found, returns <code>null</code>
366      *
367      * @param key key whose associated value is to be returned.
368      * @return the value to which this cache maps the specified key,
369      * or <code>null</code> if the cache contains no mapping for
370      * this key.
371      */
372     public synchronized Object   get(Object   key) {
373         Object   value = null;
374         MapEntry entry = null;
375 
376         cleanup();
377 
378         if ((entry = (MapEntry) map.get(key)) != null)
379             value = entry.getValue();
380 
381         return mru.add(value);
382     }
383 
384     /**
385      * Return a collection of all values this cache contains.
386      * It is not guaranteed, that an iterator from the collection
387      * will return only non null values. It is likely some soft (weak) references
388      * will go away while traversing the Collection. The iterator will return
389      * <code>null</code> in this case.
390      * 
391      * @return a <code>Collection</code> containing a values of the cache.
392      */
393     public Collection   values() {
394         return new AbstractCollection  () {
395                 public int size() {
396                     return Cache.this.size();
397                 }
398 
399                 public Iterator   iterator() {
400                     return getValueIterator();
401                 }
402             };
403     }
404 
405     /**
406      * Removes the mapping for this key from this cache.
407      *
408      * @param key key whose mapping is to be removed from the cache.
409      * @return previous value associated with specified key, or null if there was no mapping for key.
410      */
411     public synchronized Object   remove(Object   key) {
412         cleanup();
413         mru.remove(key);
414         MapEntry entry = (MapEntry) map.remove(key);
415         return (entry != null) ? entry.getValue() : null;
416     }
417 
418     /**
419      * Return a <code>Set</code> of all keys.
420      *
421      * @return a <code>Set</code> of all keys.
422      */
423     public Set   keySet() {
424         cleanup();
425         return map.keySet();
426     }
427 
428     /**
429      * Returns a set view of the mappings contained in this cache.
430      * Each element in the returned set is a Map.Entry. The set is backed by the cache,
431      * so changes to the cache are reflected in the set, and vice-versa.
432      * If the map is modified while an iteration over the set is in progress,
433      * the results of the iteration are undefined.
434      * The set supports element removal, which removes the corresponding mapping from the map,
435      * via the Iterator.remove, Set.remove, removeAll, retainAll and clear operations.
436      * It does not support the add or addAll operations.
437      *
438      * @return a <code>Set</code> view of all values.
439      */
440     public Set   entrySet() {
441         cleanup();
442         return map.entrySet();
443     }
444 
445     /**
446      * Map interface, <code>isEmpty</code> method.
447      *
448      * @return true if map is empty, false otherwise
449      * @see java.util.Map#isEmpty
450      */
451     public boolean isEmpty() {
452         cleanup();
453         return map.isEmpty();
454     }
455 
456     /**
457      * Describe <code>containsValue</code> method here.
458      *
459      * @param obj an <code>Object</code> value
460      * @return a <code>boolean</code> value
461      */
462     public boolean containsValue(Object   obj) {
463         for (Iterator   it = map.entrySet().iterator(); it.hasNext(); ) {
464             MapEntry entry  = (MapEntry) it.next();
465             Object   value = entry.getValue();
466             if (value != null && value.equals(obj))
467                 return true;
468         }
469         
470         return false;
471     }
472 
473     /**
474      * Describe <code>containsKey</code> method here.
475      *
476      * @param key an <code>Object</code> value
477      * @return a <code>boolean</code> value
478      */
479     public boolean containsKey(Object   key) {
480         return map.containsKey(key);
481     }
482 
483     /**
484      * Describe <code>putAll</code> method here.
485      *
486      * @param cache a <code>Map</code> value
487      */
488     public void putAll(Map   cache) {
489         for (Iterator   it = cache.keySet().iterator(); it.hasNext(); ) {
490             Object   key = it.next(); 
491             put(key, cache.get(key));
492         }
493     }
494 
495     /**
496      * Clean up the expired references from the reference queue.
497      */
498     private synchronized void cleanup() {
499         MapEntry entry;
500         while ((entry = (MapEntry)queue.poll()) != null) {
501             map.remove(entry.getKey());
502     }
503     }
504     
505     private Iterator   getValueIterator() {
506         cleanup();
507         return new ValueIterator(map.entrySet().iterator());
508     }
509     
510 } // Cache
511
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags