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 @Override 195 public Object get( Object key ) 196 { 197 int index = key.hashCode() & _mask; 198 return key.equals( _keys[index] ) ? _values[index] : getCacheMissed( key, index ); 199 } 200 201 private Object getCacheMissed( Object key, int index ) 202 { 203 if ( _backingFastMap != null ) 204 { 205 Map.Entry entry = _backingFastMap.getEntry( key ); 206 if ( entry != null ) 207 { 208 _keys[index] = entry.getKey(); 209 Object value = entry.getValue(); 210 _values[index] = value; 211 return value; 212 } 213 else 214 { 215 return null; 216 } 217 } 218 else 219 { // Generic backing map. 220 Object mapKey = _keysMap.get( key ); 221 if ( mapKey != null ) 222 { 223 _keys[index] = mapKey; 224 Object value = _backingMap.get( key ); 225 _values[index] = value; 226 return value; 227 } 228 else 229 { 230 return null; 231 } 232 } 233 } 234 235 /** 236 * Associates the specified value with the specified key in this map. 237 * 238 * @param key the key with which the specified value is to be associated. 239 * @param value the value to be associated with the specified key. 240 * @return the previous value associated with specified key, or <code>null</code> if there was no mapping for the 241 * key. 242 * @throws UnsupportedOperationException if the <code>put</code> operation is not supported by the backing map. 243 * @throws ClassCastException if the class of the specified key or value prevents it from being stored in this map. 244 * @throws IllegalArgumentException if some aspect of this key or value prevents it from being stored in this map. 245 * @throws NullPointerException if the key is <code>null</code>. 246 */ 247 @Override 248 public Object put( Object key, Object value ) 249 { 250 // Updates the cache. 251 int index = key.hashCode() & _mask; 252 if ( key.equals( _keys[index] ) ) 253 { 254 _values[index] = value; 255 } 256 else if ( _keysMap != null ) 257 { // Possibly a new key. 258 _keysMap.put( key, key ); 259 } 260 261 // Updates the backing map. 262 return _backingMap.put( key, value ); 263 } 264 265 /** 266 * Removes the mapping for this key from this map if it is present. 267 * 268 * @param key key whose mapping is to be removed from the map. 269 * @return previous value associated with specified key, or <code>null</code> if there was no mapping for key. 270 * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional). 271 * @throws NullPointerException if the key is <code>null</code>. 272 * @throws UnsupportedOperationException if the <code>remove</code> method is not supported by the backing map. 273 */ 274 @Override 275 public Object remove( Object key ) 276 { 277 // Removes from cache. 278 int index = key.hashCode() & _mask; 279 if ( key.equals( _keys[index] ) ) 280 { 281 _keys[index] = null; 282 } 283 // Removes from key map. 284 if ( _keysMap != null ) 285 { 286 _keysMap.remove( key ); 287 } 288 // Removes from backing map. 289 return _backingMap.remove( key ); 290 } 291 292 /** 293 * Indicates if this map contains a mapping for the specified key. 294 * 295 * @param key the key whose presence in this map is to be tested. 296 * @return <code>true</code> if this map contains a mapping for the specified key; <code>false</code> otherwise. 297 */ 298 @Override 299 public boolean containsKey( Object key ) 300 { 301 // Checks the cache. 302 int index = key.hashCode() & _mask; 303 if ( key.equals( _keys[index] ) ) 304 { 305 return true; 306 } 307 else 308 { // Checks the backing map. 309 return _backingMap.containsKey( key ); 310 } 311 } 312 313 /** 314 * Returns the number of key-value mappings in this map. If the map contains more than 315 * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>. 316 * 317 * @return the number of key-value mappings in this map. 318 */ 319 @Override 320 public int size() 321 { 322 return _backingMap.size(); 323 } 324 325 /** 326 * Returns <code>true</code> if this map contains no key-value mappings. 327 * 328 * @return <code>true</code> if this map contains no key-value mappings. 329 */ 330 @Override 331 public boolean isEmpty() 332 { 333 return _backingMap.isEmpty(); 334 } 335 336 /** 337 * Returns <code>true</code> if this map maps one or more keys to the specified value. 338 * 339 * @param value value whose presence in this map is to be tested. 340 * @return <code>true</code> if this map maps one or more keys to the specified value. 341 * @throws ClassCastException if the value is of an inappropriate type for the backing map (optional). 342 * @throws NullPointerException if the value is <code>null</code> and the backing map does not not permit 343 * <code>null</code> values. 344 */ 345 @Override 346 public boolean containsValue( Object value ) 347 { 348 return _backingMap.containsValue( value ); 349 } 350 351 /** 352 * Copies all of the mappings from the specified map to this map (optional operation). This method automatically 353 * flushes the cache. 354 * 355 * @param map the mappings to be stored in this map. 356 * @throws UnsupportedOperationException if the <code>putAll</code> method is not supported by the backing map. 357 * @throws ClassCastException if the class of a key or value in the specified map prevents it from being stored in 358 * this map. 359 * @throws IllegalArgumentException some aspect of a key or value in the specified map prevents it from being stored 360 * in this map. 361 * @throws NullPointerException the specified map is <code>null</code>, or if the backing map does not permit 362 * <code>null</code> keys or values, and the specified map contains <code>null</code> keys or values. 363 */ 364 @Override 365 public void putAll( Map map ) 366 { 367 _backingMap.putAll( map ); 368 flush(); 369 } 370 371 /** 372 * Removes all mappings from this map (optional operation). This method automatically flushes the cache. 373 * 374 * @throws UnsupportedOperationException if clear is not supported by the backing map. 375 */ 376 @Override 377 public void clear() 378 { 379 _backingMap.clear(); 380 flush(); 381 } 382 383 /** 384 * Returns an <b>unmodifiable</b> view of the keys contained in this map. 385 * 386 * @return an unmodifiable view of the keys contained in this map. 387 */ 388 @Override 389 public Set keySet() 390 { 391 return Collections.unmodifiableSet( _backingMap.keySet() ); 392 } 393 394 /** 395 * Returns an <b>unmodifiable</b> view of the values contained in this map. 396 * 397 * @return an unmodifiable view of the values contained in this map. 398 */ 399 @Override 400 public Collection values() 401 { 402 return Collections.unmodifiableCollection( _backingMap.values() ); 403 } 404 405 /** 406 * Returns an <b>unmodifiable</b> view of the mappings contained in this map. Each element in the returned set is a 407 * <code>Map.Entry</code>. 408 * 409 * @return an unmodifiable view of the mappings contained in this map. 410 */ 411 @Override 412 public Set entrySet() 413 { 414 return Collections.unmodifiableSet( _backingMap.entrySet() ); 415 } 416 417 /** 418 * Compares the specified object with this map for equality. Returns <code>true</code> if the given object is also a map 419 * and the two Maps represent the same mappings. 420 * 421 * @param o object to be compared for equality with this map. 422 * @return <code>true</code> if the specified object is equal to this map. 423 */ 424 @Override 425 public boolean equals( Object o ) 426 { 427 return _backingMap.equals( o ); 428 } 429 430 /** 431 * Returns the hash code value for this map. 432 * 433 * @return the hash code value for this map. 434 */ 435 @Override 436 public int hashCode() 437 { 438 return _backingMap.hashCode(); 439 } 440 }