View Javadoc
1   package org.codehaus.plexus.util;
2   
3   /*
4    * J.A.D.E. Java(TM) Addition to Default Environment.
5    * Latest release available at http://jade.dautelle.com/
6    * This class is public domain (not copyrighted).
7    */
8   
9   import java.util.Collection;
10  import java.util.Collections;
11  import java.util.Map;
12  import java.util.Set;
13  
14  /**
15   * <p>
16   * This class provides cache access to <code>Map</code> collections.
17   * </p>
18   * <p>
19   * Instance of this class can be used as "proxy" for any collection implementing the <code>java.util.Map</code>
20   * interface.
21   * </p>
22   * <p>
23   * Typically, {@link CachedMap} are used to accelerate access to large collections when the access to the collection is
24   * not evenly distributed (associative cache). The performance gain is about 50% for the fastest hash map collections
25   * (e.g. {@link FastMap}). For slower collections such as <code>java.util.TreeMap</code>, non-resizable {@link FastMap}
26   * (real-time) or database access, performance can be of several orders of magnitude.
27   * </p>
28   * <p>
29   * <b>Note:</b> The keys used to access elements of a {@link CachedMap} do not need to be immutable as they are not
30   * stored in the cache (only keys specified by the {@link #put} method are). In other words, access can be performed
31   * using mutable keys as long as these keys can be compared for equality with the real map's keys (e.g. same
32   * <code>hashCode</code> values).
33   * </p>
34   * <p>
35   * This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized
36   * externally.
37   * </p>
38   * <p>
39   * <i> This class is <b>public domain</b> (not copyrighted).</i>
40   * </p>
41   * 
42   * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
43   * @version 5.3, October 30, 2003
44   */
45  public final class CachedMap
46      implements Map
47  {
48  
49      /**
50       * Holds the FastMap backing this collection (<code>null</code> if generic backing map).
51       */
52      private final FastMap _backingFastMap;
53  
54      /**
55       * Holds the generic map backing this collection.
56       */
57      private final Map _backingMap;
58  
59      /**
60       * Holds the keys of the backing map (key-to-key mapping). (<code>null</code> if FastMap backing map).
61       */
62      private final FastMap _keysMap;
63  
64      /**
65       * Holds the cache's mask (capacity - 1).
66       */
67      private final int _mask;
68  
69      /**
70       * Holds the keys being cached.
71       */
72      private final Object[] _keys;
73  
74      /**
75       * Holds the values being cached.
76       */
77      private final Object[] _values;
78  
79      /**
80       * Creates a cached map backed by a {@link FastMap}. The default cache size and map capacity is set to
81       * <code>256</code> entries.
82       */
83      public CachedMap()
84      {
85          this( 256, new FastMap() );
86      }
87  
88      /**
89       * Creates a cached map backed by a {@link FastMap} and having the specified cache size.
90       *
91       * @param cacheSize the cache size, the actual cache size is the first power of 2 greater or equal to
92       *            <code>cacheSize</code>. This is also the initial capacity of the backing map.
93       */
94      public CachedMap( int cacheSize )
95      {
96          this( cacheSize, new FastMap( cacheSize ) );
97      }
98  
99      /**
100      * Creates a cached map backed by the specified map and having the specified cache size. In order to maintain cache
101      * veracity, it is critical that <b>all</b> update to the backing map is accomplished through the {@link CachedMap}
102      * instance; otherwise {@link #flush} has to be called.
103      *
104      * @param cacheSize the cache size, the actual cache size is the first power of 2 greater or equal to
105      *            <code>cacheSize</code>.
106      * @param backingMap the backing map to be "wrapped" in a cached map.
107      */
108     public CachedMap( int cacheSize, Map backingMap )
109     {
110 
111         // Find a power of 2 >= minimalCache
112         int actualCacheSize = 1;
113         while ( actualCacheSize < cacheSize )
114         {
115             actualCacheSize <<= 1;
116         }
117 
118         // Sets up cache.
119         _keys = new Object[actualCacheSize];
120         _values = new Object[actualCacheSize];
121         _mask = actualCacheSize - 1;
122 
123         // Sets backing map references.
124         if ( backingMap instanceof FastMap )
125         {
126             _backingFastMap = (FastMap) backingMap;
127             _backingMap = _backingFastMap;
128             _keysMap = null;
129         }
130         else
131         {
132             _backingFastMap = null;
133             _backingMap = backingMap;
134             _keysMap = new FastMap( backingMap.size() );
135             for ( Object key : backingMap.keySet() )
136             {
137                 _keysMap.put( key, key );
138             }
139         }
140     }
141 
142     /**
143      * Returns the actual cache size.
144      *
145      * @return the cache size (power of 2).
146      */
147     public int getCacheSize()
148     {
149         return _keys.length;
150     }
151 
152     /**
153      * Returns the backing map. If the backing map is modified directly, this {@link CachedMap} has to be flushed.
154      *
155      * @return the backing map.
156      * @see #flush
157      */
158     public Map getBackingMap()
159     {
160         return ( _backingFastMap != null ) ? _backingFastMap : _backingMap;
161     }
162 
163     /**
164      * Flushes the key/value pairs being cached. This method should be called if the backing map is externally modified.
165      */
166     public void flush()
167     {
168         for ( int i = 0; i < _keys.length; i++ )
169         {
170             _keys[i] = null;
171             _values[i] = null;
172         }
173 
174         if ( _keysMap != null )
175         {
176             // Re-populates keys from backing map.
177             for ( Object key : _backingMap.keySet() )
178             {
179                 _keysMap.put( key, key );
180             }
181         }
182     }
183 
184     /**
185      * Returns the value to which this map maps the specified key. First, the cache is being checked, then if the cache
186      * does not contains the specified key, the backing map is accessed and the key/value pair is stored in the cache.
187      *
188      * @param key the key whose associated value is to be returned.
189      * @return the value to which this map maps the specified key, or <code>null</code> if the map contains no mapping
190      *         for this key.
191      * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional).
192      * @throws NullPointerException if the key is <code>null</code>.
193      */
194     public Object get( Object key )
195     {
196         int index = key.hashCode() & _mask;
197         return key.equals( _keys[index] ) ? _values[index] : getCacheMissed( key, index );
198     }
199 
200     private Object getCacheMissed( Object key, int index )
201     {
202         if ( _backingFastMap != null )
203         {
204             Map.Entry entry = _backingFastMap.getEntry( key );
205             if ( entry != null )
206             {
207                 _keys[index] = entry.getKey();
208                 Object value = entry.getValue();
209                 _values[index] = value;
210                 return value;
211             }
212             else
213             {
214                 return null;
215             }
216         }
217         else
218         { // Generic backing map.
219             Object mapKey = _keysMap.get( key );
220             if ( mapKey != null )
221             {
222                 _keys[index] = mapKey;
223                 Object value = _backingMap.get( key );
224                 _values[index] = value;
225                 return value;
226             }
227             else
228             {
229                 return null;
230             }
231         }
232     }
233 
234     /**
235      * Associates the specified value with the specified key in this map.
236      *
237      * @param key the key with which the specified value is to be associated.
238      * @param value the value to be associated with the specified key.
239      * @return the previous value associated with specified key, or <code>null</code> if there was no mapping for the
240      *         key.
241      * @throws UnsupportedOperationException if the <code>put</code> operation is not supported by the backing map.
242      * @throws ClassCastException if the class of the specified key or value prevents it from being stored in this map.
243      * @throws IllegalArgumentException if some aspect of this key or value prevents it from being stored in this map.
244      * @throws NullPointerException if the key is <code>null</code>.
245      */
246     public Object put( Object key, Object value )
247     {
248         // Updates the cache.
249         int index = key.hashCode() & _mask;
250         if ( key.equals( _keys[index] ) )
251         {
252             _values[index] = value;
253         }
254         else if ( _keysMap != null )
255         { // Possibly a new key.
256             _keysMap.put( key, key );
257         }
258 
259         // Updates the backing map.
260         return _backingMap.put( key, value );
261     }
262 
263     /**
264      * Removes the mapping for this key from this map if it is present.
265      *
266      * @param key key whose mapping is to be removed from the map.
267      * @return previous value associated with specified key, or <code>null</code> if there was no mapping for key.
268      * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional).
269      * @throws NullPointerException if the key is <code>null</code>.
270      * @throws UnsupportedOperationException if the <code>remove</code> method is not supported by the backing map.
271      */
272     public Object remove( Object key )
273     {
274         // Removes from cache.
275         int index = key.hashCode() & _mask;
276         if ( key.equals( _keys[index] ) )
277         {
278             _keys[index] = null;
279         }
280         // Removes from key map.
281         if ( _keysMap != null )
282         {
283             _keysMap.remove( key );
284         }
285         // Removes from backing map.
286         return _backingMap.remove( key );
287     }
288 
289     /**
290      * Indicates if this map contains a mapping for the specified key.
291      *
292      * @param key the key whose presence in this map is to be tested.
293      * @return <code>true</code> if this map contains a mapping for the specified key; <code>false</code> otherwise.
294      */
295     public boolean containsKey( Object key )
296     {
297         // Checks the cache.
298         int index = key.hashCode() & _mask;
299         if ( key.equals( _keys[index] ) )
300         {
301             return true;
302         }
303         else
304         { // Checks the backing map.
305             return _backingMap.containsKey( key );
306         }
307     }
308 
309     /**
310      * Returns the number of key-value mappings in this map. If the map contains more than
311      * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>.
312      *
313      * @return the number of key-value mappings in this map.
314      */
315     public int size()
316     {
317         return _backingMap.size();
318     }
319 
320     /**
321      * Returns <code>true</code> if this map contains no key-value mappings.
322      *
323      * @return <code>true</code> if this map contains no key-value mappings.
324      */
325     public boolean isEmpty()
326     {
327         return _backingMap.isEmpty();
328     }
329 
330     /**
331      * Returns <code>true</code> if this map maps one or more keys to the specified value.
332      *
333      * @param value value whose presence in this map is to be tested.
334      * @return <code>true</code> if this map maps one or more keys to the specified value.
335      * @throws ClassCastException if the value is of an inappropriate type for the backing map (optional).
336      * @throws NullPointerException if the value is <code>null</code> and the backing map does not not permit
337      *             <code>null</code> values.
338      */
339     public boolean containsValue( Object value )
340     {
341         return _backingMap.containsValue( value );
342     }
343 
344     /**
345      * Copies all of the mappings from the specified map to this map (optional operation). This method automatically
346      * flushes the cache.
347      *
348      * @param map the mappings to be stored in this map.
349      * @throws UnsupportedOperationException if the <code>putAll</code> method is not supported by the backing map.
350      * @throws ClassCastException if the class of a key or value in the specified map prevents it from being stored in
351      *             this map.
352      * @throws IllegalArgumentException some aspect of a key or value in the specified map prevents it from being stored
353      *             in this map.
354      * @throws NullPointerException the specified map is <code>null</code>, or if the backing map does not permit
355      *             <code>null</code> keys or values, and the specified map contains <code>null</code> keys or values.
356      */
357     public void putAll( Map map )
358     {
359         _backingMap.putAll( map );
360         flush();
361     }
362 
363     /**
364      * Removes all mappings from this map (optional operation). This method automatically flushes the cache.
365      *
366      * @throws UnsupportedOperationException if clear is not supported by the backing map.
367      */
368     public void clear()
369     {
370         _backingMap.clear();
371         flush();
372     }
373 
374     /**
375      * Returns an <b>unmodifiable</b> view of the keys contained in this map.
376      *
377      * @return an unmodifiable view of the keys contained in this map.
378      */
379     public Set keySet()
380     {
381         return Collections.unmodifiableSet( _backingMap.keySet() );
382     }
383 
384     /**
385      * Returns an <b>unmodifiable</b> view of the values contained in this map.
386      *
387      * @return an unmodifiable view of the values contained in this map.
388      */
389     public Collection values()
390     {
391         return Collections.unmodifiableCollection( _backingMap.values() );
392     }
393 
394     /**
395      * Returns an <b>unmodifiable</b> view of the mappings contained in this map. Each element in the returned set is a
396      * <code>Map.Entry</code>.
397      *
398      * @return an unmodifiable view of the mappings contained in this map.
399      */
400     public Set entrySet()
401     {
402         return Collections.unmodifiableSet( _backingMap.entrySet() );
403     }
404 
405     /**
406      * Compares the specified object with this map for equality. Returns <tt>true</tt> if the given object is also a map
407      * and the two Maps represent the same mappings.
408      *
409      * @param o object to be compared for equality with this map.
410      * @return <code>true</code> if the specified object is equal to this map.
411      */
412     public boolean equals( Object o )
413     {
414         return _backingMap.equals( o );
415     }
416 
417     /**
418      * Returns the hash code value for this map.
419      *
420      * @return the hash code value for this map.
421      */
422     public int hashCode()
423     {
424         return _backingMap.hashCode();
425     }
426 }