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 implements Map { 46 47 /** 48 * Holds the FastMap backing this collection (<code>null</code> if generic backing map). 49 */ 50 private final FastMap _backingFastMap; 51 52 /** 53 * Holds the generic map backing this collection. 54 */ 55 private final Map _backingMap; 56 57 /** 58 * Holds the keys of the backing map (key-to-key mapping). (<code>null</code> if FastMap backing map). 59 */ 60 private final FastMap _keysMap; 61 62 /** 63 * Holds the cache's mask (capacity - 1). 64 */ 65 private final int _mask; 66 67 /** 68 * Holds the keys being cached. 69 */ 70 private final Object[] _keys; 71 72 /** 73 * Holds the values being cached. 74 */ 75 private final Object[] _values; 76 77 /** 78 * Creates a cached map backed by a {@link FastMap}. The default cache size and map capacity is set to 79 * <code>256</code> entries. 80 */ 81 public CachedMap() { 82 this(256, new FastMap()); 83 } 84 85 /** 86 * Creates a cached map backed by a {@link FastMap} and having the specified cache size. 87 * 88 * @param cacheSize the cache size, the actual cache size is the first power of 2 greater or equal to 89 * <code>cacheSize</code>. This is also the initial capacity of the backing map. 90 */ 91 public CachedMap(int cacheSize) { 92 this(cacheSize, new FastMap(cacheSize)); 93 } 94 95 /** 96 * Creates a cached map backed by the specified map and having the specified cache size. In order to maintain cache 97 * veracity, it is critical that <b>all</b> update to the backing map is accomplished through the {@link CachedMap} 98 * instance; otherwise {@link #flush} has to be called. 99 * 100 * @param cacheSize the cache size, the actual cache size is the first power of 2 greater or equal to 101 * <code>cacheSize</code>. 102 * @param backingMap the backing map to be "wrapped" in a cached map. 103 */ 104 public CachedMap(int cacheSize, Map backingMap) { 105 106 // Find a power of 2 >= minimalCache 107 int actualCacheSize = 1; 108 while (actualCacheSize < cacheSize) { 109 actualCacheSize <<= 1; 110 } 111 112 // Sets up cache. 113 _keys = new Object[actualCacheSize]; 114 _values = new Object[actualCacheSize]; 115 _mask = actualCacheSize - 1; 116 117 // Sets backing map references. 118 if (backingMap instanceof FastMap) { 119 _backingFastMap = (FastMap) backingMap; 120 _backingMap = _backingFastMap; 121 _keysMap = null; 122 } else { 123 _backingFastMap = null; 124 _backingMap = backingMap; 125 _keysMap = new FastMap(backingMap.size()); 126 for (Object key : backingMap.keySet()) { 127 _keysMap.put(key, key); 128 } 129 } 130 } 131 132 /** 133 * Returns the actual cache size. 134 * 135 * @return the cache size (power of 2). 136 */ 137 public int getCacheSize() { 138 return _keys.length; 139 } 140 141 /** 142 * Returns the backing map. If the backing map is modified directly, this {@link CachedMap} has to be flushed. 143 * 144 * @return the backing map. 145 * @see #flush 146 */ 147 public Map getBackingMap() { 148 return (_backingFastMap != null) ? _backingFastMap : _backingMap; 149 } 150 151 /** 152 * Flushes the key/value pairs being cached. This method should be called if the backing map is externally modified. 153 */ 154 public void flush() { 155 for (int i = 0; i < _keys.length; i++) { 156 _keys[i] = null; 157 _values[i] = null; 158 } 159 160 if (_keysMap != null) { 161 // Re-populates keys from backing map. 162 for (Object key : _backingMap.keySet()) { 163 _keysMap.put(key, key); 164 } 165 } 166 } 167 168 /** 169 * Returns the value to which this map maps the specified key. First, the cache is being checked, then if the cache 170 * does not contains the specified key, the backing map is accessed and the key/value pair is stored in the cache. 171 * 172 * @param key the key whose associated value is to be returned. 173 * @return the value to which this map maps the specified key, or <code>null</code> if the map contains no mapping 174 * for this key. 175 * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional). 176 * @throws NullPointerException if the key is <code>null</code>. 177 */ 178 @Override 179 public Object get(Object key) { 180 int index = key.hashCode() & _mask; 181 return key.equals(_keys[index]) ? _values[index] : getCacheMissed(key, index); 182 } 183 184 private Object getCacheMissed(Object key, int index) { 185 if (_backingFastMap != null) { 186 Map.Entry entry = _backingFastMap.getEntry(key); 187 if (entry != null) { 188 _keys[index] = entry.getKey(); 189 Object value = entry.getValue(); 190 _values[index] = value; 191 return value; 192 } else { 193 return null; 194 } 195 } else { // Generic backing map. 196 Object mapKey = _keysMap.get(key); 197 if (mapKey != null) { 198 _keys[index] = mapKey; 199 Object value = _backingMap.get(key); 200 _values[index] = value; 201 return value; 202 } else { 203 return null; 204 } 205 } 206 } 207 208 /** 209 * Associates the specified value with the specified key in this map. 210 * 211 * @param key the key with which the specified value is to be associated. 212 * @param value the value to be associated with the specified key. 213 * @return the previous value associated with specified key, or <code>null</code> if there was no mapping for the 214 * key. 215 * @throws UnsupportedOperationException if the <code>put</code> operation is not supported by the backing map. 216 * @throws ClassCastException if the class of the specified key or value prevents it from being stored in this map. 217 * @throws IllegalArgumentException if some aspect of this key or value prevents it from being stored in this map. 218 * @throws NullPointerException if the key is <code>null</code>. 219 */ 220 @Override 221 public Object put(Object key, Object value) { 222 // Updates the cache. 223 int index = key.hashCode() & _mask; 224 if (key.equals(_keys[index])) { 225 _values[index] = value; 226 } else if (_keysMap != null) { // Possibly a new key. 227 _keysMap.put(key, key); 228 } 229 230 // Updates the backing map. 231 return _backingMap.put(key, value); 232 } 233 234 /** 235 * Removes the mapping for this key from this map if it is present. 236 * 237 * @param key key whose mapping is to be removed from the map. 238 * @return previous value associated with specified key, or <code>null</code> if there was no mapping for key. 239 * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional). 240 * @throws NullPointerException if the key is <code>null</code>. 241 * @throws UnsupportedOperationException if the <code>remove</code> method is not supported by the backing map. 242 */ 243 @Override 244 public Object remove(Object key) { 245 // Removes from cache. 246 int index = key.hashCode() & _mask; 247 if (key.equals(_keys[index])) { 248 _keys[index] = null; 249 } 250 // Removes from key map. 251 if (_keysMap != null) { 252 _keysMap.remove(key); 253 } 254 // Removes from backing map. 255 return _backingMap.remove(key); 256 } 257 258 /** 259 * Indicates if this map contains a mapping for the specified key. 260 * 261 * @param key the key whose presence in this map is to be tested. 262 * @return <code>true</code> if this map contains a mapping for the specified key; <code>false</code> otherwise. 263 */ 264 @Override 265 public boolean containsKey(Object key) { 266 // Checks the cache. 267 int index = key.hashCode() & _mask; 268 if (key.equals(_keys[index])) { 269 return true; 270 } else { // Checks the backing map. 271 return _backingMap.containsKey(key); 272 } 273 } 274 275 /** 276 * Returns the number of key-value mappings in this map. If the map contains more than 277 * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>. 278 * 279 * @return the number of key-value mappings in this map. 280 */ 281 @Override 282 public int size() { 283 return _backingMap.size(); 284 } 285 286 /** 287 * Returns <code>true</code> if this map contains no key-value mappings. 288 * 289 * @return <code>true</code> if this map contains no key-value mappings. 290 */ 291 @Override 292 public boolean isEmpty() { 293 return _backingMap.isEmpty(); 294 } 295 296 /** 297 * Returns <code>true</code> if this map maps one or more keys to the specified value. 298 * 299 * @param value value whose presence in this map is to be tested. 300 * @return <code>true</code> if this map maps one or more keys to the specified value. 301 * @throws ClassCastException if the value is of an inappropriate type for the backing map (optional). 302 * @throws NullPointerException if the value is <code>null</code> and the backing map does not not permit 303 * <code>null</code> values. 304 */ 305 @Override 306 public boolean containsValue(Object value) { 307 return _backingMap.containsValue(value); 308 } 309 310 /** 311 * Copies all of the mappings from the specified map to this map (optional operation). This method automatically 312 * flushes the cache. 313 * 314 * @param map the mappings to be stored in this map. 315 * @throws UnsupportedOperationException if the <code>putAll</code> method is not supported by the backing map. 316 * @throws ClassCastException if the class of a key or value in the specified map prevents it from being stored in 317 * this map. 318 * @throws IllegalArgumentException some aspect of a key or value in the specified map prevents it from being stored 319 * in this map. 320 * @throws NullPointerException the specified map is <code>null</code>, or if the backing map does not permit 321 * <code>null</code> keys or values, and the specified map contains <code>null</code> keys or values. 322 */ 323 @Override 324 public void putAll(Map map) { 325 _backingMap.putAll(map); 326 flush(); 327 } 328 329 /** 330 * Removes all mappings from this map (optional operation). This method automatically flushes the cache. 331 * 332 * @throws UnsupportedOperationException if clear is not supported by the backing map. 333 */ 334 @Override 335 public void clear() { 336 _backingMap.clear(); 337 flush(); 338 } 339 340 /** 341 * Returns an <b>unmodifiable</b> view of the keys contained in this map. 342 * 343 * @return an unmodifiable view of the keys contained in this map. 344 */ 345 @Override 346 public Set keySet() { 347 return Collections.unmodifiableSet(_backingMap.keySet()); 348 } 349 350 /** 351 * Returns an <b>unmodifiable</b> view of the values contained in this map. 352 * 353 * @return an unmodifiable view of the values contained in this map. 354 */ 355 @Override 356 public Collection values() { 357 return Collections.unmodifiableCollection(_backingMap.values()); 358 } 359 360 /** 361 * Returns an <b>unmodifiable</b> view of the mappings contained in this map. Each element in the returned set is a 362 * <code>Map.Entry</code>. 363 * 364 * @return an unmodifiable view of the mappings contained in this map. 365 */ 366 @Override 367 public Set entrySet() { 368 return Collections.unmodifiableSet(_backingMap.entrySet()); 369 } 370 371 /** 372 * Compares the specified object with this map for equality. Returns <code>true</code> if the given object is also a map 373 * and the two Maps represent the same mappings. 374 * 375 * @param o object to be compared for equality with this map. 376 * @return <code>true</code> if the specified object is equal to this map. 377 */ 378 @Override 379 public boolean equals(Object o) { 380 return _backingMap.equals(o); 381 } 382 383 /** 384 * Returns the hash code value for this map. 385 * 386 * @return the hash code value for this map. 387 */ 388 @Override 389 public int hashCode() { 390 return _backingMap.hashCode(); 391 } 392 }