Coverage Report - org.codehaus.plexus.util.CachedMap
 
Classes in this File Line Coverage Branch Coverage Complexity
CachedMap
0%
0/79
0%
0/32
1.952
 
 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  0
         this( 256, new FastMap() );
 86  0
     }
 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  0
         this( cacheSize, new FastMap( cacheSize ) );
 97  0
     }
 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  0
     {
 110  
 
 111  
         // Find a power of 2 >= minimalCache
 112  0
         int actualCacheSize = 1;
 113  0
         while ( actualCacheSize < cacheSize )
 114  
         {
 115  0
             actualCacheSize <<= 1;
 116  
         }
 117  
 
 118  
         // Sets up cache.
 119  0
         _keys = new Object[actualCacheSize];
 120  0
         _values = new Object[actualCacheSize];
 121  0
         _mask = actualCacheSize - 1;
 122  
 
 123  
         // Sets backing map references.
 124  0
         if ( backingMap instanceof FastMap )
 125  
         {
 126  0
             _backingFastMap = (FastMap) backingMap;
 127  0
             _backingMap = _backingFastMap;
 128  0
             _keysMap = null;
 129  
         }
 130  
         else
 131  
         {
 132  0
             _backingFastMap = null;
 133  0
             _backingMap = backingMap;
 134  0
             _keysMap = new FastMap( backingMap.size() );
 135  0
             for ( Object key : backingMap.keySet() )
 136  
             {
 137  0
                 _keysMap.put( key, key );
 138  0
             }
 139  
         }
 140  0
     }
 141  
 
 142  
     /**
 143  
      * Returns the actual cache size.
 144  
      *
 145  
      * @return the cache size (power of 2).
 146  
      */
 147  
     public int getCacheSize()
 148  
     {
 149  0
         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  0
         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  0
         for ( int i = 0; i < _keys.length; i++ )
 169  
         {
 170  0
             _keys[i] = null;
 171  0
             _values[i] = null;
 172  
         }
 173  
 
 174  0
         if ( _keysMap != null )
 175  
         {
 176  
             // Re-populates keys from backing map.
 177  0
             for ( Object key : _backingMap.keySet() )
 178  
             {
 179  0
                 _keysMap.put( key, key );
 180  0
             }
 181  
         }
 182  0
     }
 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  0
         int index = key.hashCode() & _mask;
 197  0
         return key.equals( _keys[index] ) ? _values[index] : getCacheMissed( key, index );
 198  
     }
 199  
 
 200  
     private Object getCacheMissed( Object key, int index )
 201  
     {
 202  0
         if ( _backingFastMap != null )
 203  
         {
 204  0
             Map.Entry entry = _backingFastMap.getEntry( key );
 205  0
             if ( entry != null )
 206  
             {
 207  0
                 _keys[index] = entry.getKey();
 208  0
                 Object value = entry.getValue();
 209  0
                 _values[index] = value;
 210  0
                 return value;
 211  
             }
 212  
             else
 213  
             {
 214  0
                 return null;
 215  
             }
 216  
         }
 217  
         else
 218  
         { // Generic backing map.
 219  0
             Object mapKey = _keysMap.get( key );
 220  0
             if ( mapKey != null )
 221  
             {
 222  0
                 _keys[index] = mapKey;
 223  0
                 Object value = _backingMap.get( key );
 224  0
                 _values[index] = value;
 225  0
                 return value;
 226  
             }
 227  
             else
 228  
             {
 229  0
                 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  0
         int index = key.hashCode() & _mask;
 250  0
         if ( key.equals( _keys[index] ) )
 251  
         {
 252  0
             _values[index] = value;
 253  
         }
 254  0
         else if ( _keysMap != null )
 255  
         { // Possibly a new key.
 256  0
             _keysMap.put( key, key );
 257  
         }
 258  
 
 259  
         // Updates the backing map.
 260  0
         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  0
         int index = key.hashCode() & _mask;
 276  0
         if ( key.equals( _keys[index] ) )
 277  
         {
 278  0
             _keys[index] = null;
 279  
         }
 280  
         // Removes from key map.
 281  0
         if ( _keysMap != null )
 282  
         {
 283  0
             _keysMap.remove( key );
 284  
         }
 285  
         // Removes from backing map.
 286  0
         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  0
         int index = key.hashCode() & _mask;
 299  0
         if ( key.equals( _keys[index] ) )
 300  
         {
 301  0
             return true;
 302  
         }
 303  
         else
 304  
         { // Checks the backing map.
 305  0
             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  0
         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  0
         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  0
         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  0
         _backingMap.putAll( map );
 360  0
         flush();
 361  0
     }
 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  0
         _backingMap.clear();
 371  0
         flush();
 372  0
     }
 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  0
         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  0
         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  0
         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  0
         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  0
         return _backingMap.hashCode();
 425  
     }
 426  
 }