001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.map; 018 019import java.io.IOException; 020import java.io.ObjectInputStream; 021import java.io.ObjectOutputStream; 022import java.io.Serializable; 023import java.util.Map; 024 025import org.apache.commons.collections4.BoundedMap; 026 027/** 028 * A {@code Map} implementation with a fixed maximum size which removes 029 * the least recently used entry if an entry is added when full. 030 * <p> 031 * The least recently used algorithm works on the get and put operations only. 032 * Iteration of any kind, including setting the value by iteration, does not 033 * change the order. Queries such as containsKey and containsValue or access 034 * via views also do not change the order. 035 * </p> 036 * <p> 037 * A somewhat subtle ramification of the least recently used 038 * algorithm is that calls to {@link #get(Object)} stand a very good chance 039 * of modifying the map's iteration order and thus invalidating any 040 * iterators currently in use. It is therefore suggested that iterations 041 * over an {@link LRUMap} instance access entry values only through a 042 * {@link org.apache.commons.collections4.MapIterator MapIterator} or {@link #entrySet()} iterator. 043 * </p> 044 * <p> 045 * The map implements {@code OrderedMap} and entries may be queried using 046 * the bidirectional {@code OrderedMapIterator}. The order returned is 047 * least recently used to most recently used. Iterators from map views can 048 * also be cast to {@code OrderedIterator} if required. 049 * </p> 050 * <p> 051 * All the available iterators can be reset back to the start by casting to 052 * {@code ResettableIterator} and calling {@code reset()}. 053 * </p> 054 * <p> 055 * <strong>Note that LRUMap is not synchronized and is not thread-safe.</strong> 056 * If you wish to use this map from multiple threads concurrently, you must use 057 * appropriate synchronization. The simplest approach is to wrap this map 058 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 059 * {@code NullPointerException}'s when accessed by concurrent threads. 060 * </p> 061 * 062 * @param <K> the type of the keys in this map 063 * @param <V> the type of the values in this map 064 * @since 3.0 (previously in main package v1.0) 065 */ 066public class LRUMap<K, V> 067 extends AbstractLinkedMap<K, V> implements BoundedMap<K, V>, Serializable, Cloneable { 068 069 /** Serialisation version */ 070 private static final long serialVersionUID = -612114643488955218L; 071 /** Default maximum size */ 072 protected static final int DEFAULT_MAX_SIZE = 100; 073 074 /** Maximum size */ 075 private transient int maxSize; 076 /** Scan behavior */ 077 private final boolean scanUntilRemovable; 078 079 /** 080 * Constructs a new empty map with a maximum size of 100. 081 */ 082 public LRUMap() { 083 this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false); 084 } 085 086 /** 087 * Constructs a new, empty map with the specified maximum size. 088 * 089 * @param maxSize the maximum size of the map 090 * @throws IllegalArgumentException if the maximum size is less than one 091 */ 092 public LRUMap(final int maxSize) { 093 this(maxSize, DEFAULT_LOAD_FACTOR); 094 } 095 096 /** 097 * Constructs a new, empty map with the specified maximum size. 098 * 099 * @param maxSize the maximum size of the map 100 * @param scanUntilRemovable scan until a removable entry is found, default false 101 * @throws IllegalArgumentException if the maximum size is less than one 102 * @since 3.1 103 */ 104 public LRUMap(final int maxSize, final boolean scanUntilRemovable) { 105 this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable); 106 } 107 108 /** 109 * Constructs a new, empty map with the specified max capacity and 110 * load factor. 111 * 112 * @param maxSize the maximum size of the map 113 * @param loadFactor the load factor 114 * @throws IllegalArgumentException if the maximum size is less than one 115 * @throws IllegalArgumentException if the load factor is less than zero 116 */ 117 public LRUMap(final int maxSize, final float loadFactor) { 118 this(maxSize, loadFactor, false); 119 } 120 121 /** 122 * Constructs a new, empty map with the specified max capacity and load factor. 123 * 124 * @param maxSize the maximum size of the map 125 * @param loadFactor the load factor 126 * @param scanUntilRemovable scan until a removable entry is found, default false 127 * @throws IllegalArgumentException if the maximum size is less than one 128 * @throws IllegalArgumentException if the load factor is less than zero 129 * @since 3.1 130 */ 131 public LRUMap(final int maxSize, final float loadFactor, final boolean scanUntilRemovable) { 132 this(maxSize, maxSize, loadFactor, scanUntilRemovable); 133 } 134 135 /** 136 * Constructs a new, empty map with the specified maximum size. 137 * 138 * @param maxSize the maximum size of the map 139 * @param initialSize the initial size of the map 140 * @throws IllegalArgumentException if the maximum size is less than one 141 * @throws IllegalArgumentException if the initial size is negative or larger than the maximum size 142 * @since 4.1 143 */ 144 public LRUMap(final int maxSize, final int initialSize) { 145 this(maxSize, initialSize, DEFAULT_LOAD_FACTOR); 146 } 147 148 /** 149 * Constructs a new, empty map with the specified max / initial capacity and 150 * load factor. 151 * 152 * @param maxSize the maximum size of the map 153 * @param initialSize the initial size of the map 154 * @param loadFactor the load factor 155 * @throws IllegalArgumentException if the maximum size is less than one 156 * @throws IllegalArgumentException if the initial size is negative or larger than the maximum size 157 * @throws IllegalArgumentException if the load factor is less than zero 158 * @since 4.1 159 */ 160 public LRUMap(final int maxSize, final int initialSize, final float loadFactor) { 161 this(maxSize, initialSize, loadFactor, false); 162 } 163 164 /** 165 * Constructs a new, empty map with the specified max / initial capacity and load factor. 166 * 167 * @param maxSize the maximum size of the map 168 * @param initialSize the initial size of the map 169 * @param loadFactor the load factor 170 * @param scanUntilRemovable scan until a removable entry is found, default false 171 * @throws IllegalArgumentException if the maximum size is less than one 172 * @throws IllegalArgumentException if the initial size is negative or larger than the maximum size 173 * @throws IllegalArgumentException if the load factor is less than zero 174 * @since 4.1 175 */ 176 public LRUMap(final int maxSize, 177 final int initialSize, 178 final float loadFactor, 179 final boolean scanUntilRemovable) { 180 181 super(initialSize, loadFactor); 182 if (maxSize < 1) { 183 throw new IllegalArgumentException("LRUMap max size must be greater than 0"); 184 } 185 if (initialSize > maxSize) { 186 throw new IllegalArgumentException("LRUMap initial size must not be greater than max size"); 187 } 188 this.maxSize = maxSize; 189 this.scanUntilRemovable = scanUntilRemovable; 190 } 191 192 /** 193 * Constructor copying elements from another map. 194 * <p> 195 * The maximum size is set from the map's size. 196 * 197 * @param map the map to copy 198 * @throws NullPointerException if the map is null 199 * @throws IllegalArgumentException if the map is empty 200 */ 201 public LRUMap(final Map<? extends K, ? extends V> map) { 202 this(map, false); 203 } 204 205 /** 206 * Constructor copying elements from another map. 207 * 208 * <p>The maximum size is set from the map's size.</p> 209 * 210 * @param map the map to copy 211 * @param scanUntilRemovable scan until a removable entry is found, default false 212 * @throws NullPointerException if the map is null 213 * @throws IllegalArgumentException if the map is empty 214 * @since 3.1 215 */ 216 public LRUMap(final Map<? extends K, ? extends V> map, final boolean scanUntilRemovable) { 217 this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable); 218 putAll(map); 219 } 220 221 /** 222 * Adds a new key-value mapping into this map. 223 * <p> 224 * This implementation checks the LRU size and determines whether to 225 * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}. 226 * <p> 227 * From Commons Collections 3.1 this method uses {@link #isFull()} rather 228 * than accessing {@code size} and {@code maxSize} directly. 229 * It also handles the scanUntilRemovable functionality. 230 * 231 * @param hashIndex the index into the data array to store at 232 * @param hashCode the hash code of the key to add 233 * @param key the key to add 234 * @param value the value to add 235 */ 236 @Override 237 protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) { 238 if (isFull()) { 239 LinkEntry<K, V> reuse = header.after; 240 boolean removeLRUEntry = false; 241 if (scanUntilRemovable) { 242 while (reuse != header && reuse != null) { 243 if (removeLRU(reuse)) { 244 removeLRUEntry = true; 245 break; 246 } 247 reuse = reuse.after; 248 } 249 if (reuse == null) { 250 throw new IllegalStateException( 251 "Entry.after=null, header.after=" + header.after + " header.before=" + header.before + 252 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 253 " This should not occur if your keys are immutable and you used synchronization properly."); 254 } 255 } else { 256 removeLRUEntry = removeLRU(reuse); 257 } 258 259 if (removeLRUEntry) { 260 if (reuse == null) { 261 throw new IllegalStateException( 262 "reuse=null, header.after=" + header.after + " header.before=" + header.before + 263 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 264 " This should not occur if your keys are immutable and you used synchronization properly."); 265 } 266 reuseMapping(reuse, hashIndex, hashCode, key, value); 267 } else { 268 super.addMapping(hashIndex, hashCode, key, value); 269 } 270 } else { 271 super.addMapping(hashIndex, hashCode, key, value); 272 } 273 } 274 275 /** 276 * Clones the map without cloning the keys or values. 277 * 278 * @return a shallow clone 279 */ 280 @Override 281 public LRUMap<K, V> clone() { 282 return (LRUMap<K, V>) super.clone(); 283 } 284 285 /** 286 * Reads the data necessary for {@code put()} to work in the superclass. 287 * 288 * @param in the input stream 289 * @throws IOException if an error occurs while reading from the stream 290 * @throws ClassNotFoundException if an object read from the stream can not be loaded 291 */ 292 @Override 293 protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 294 maxSize = in.readInt(); 295 super.doReadObject(in); 296 } 297 298 /** 299 * Writes the data necessary for {@code put()} to work in deserialization. 300 * 301 * @param out the output stream 302 * @throws IOException if an error occurs while writing to the stream 303 */ 304 @Override 305 protected void doWriteObject(final ObjectOutputStream out) throws IOException { 306 out.writeInt(maxSize); 307 super.doWriteObject(out); 308 } 309 310 /** 311 * Gets the value mapped to the key specified. 312 * <p> 313 * This operation changes the position of the key in the map to the 314 * most recently used position (last). 315 * 316 * @param key the key 317 * @return the mapped value, null if no match 318 */ 319 @Override 320 public V get(final Object key) { 321 return get(key, true); 322 } 323 324 /** 325 * Gets the value mapped to the key specified. 326 * <p> 327 * If {@code updateToMRU} is {@code true}, the position of the key in the map 328 * is changed to the most recently used position (last), otherwise the iteration 329 * order is not changed by this operation. 330 * 331 * @param key the key 332 * @param updateToMRU whether the key shall be updated to the 333 * most recently used position 334 * @return the mapped value, null if no match 335 * @since 4.1 336 */ 337 public V get(final Object key, final boolean updateToMRU) { 338 final LinkEntry<K, V> entry = getEntry(key); 339 if (entry == null) { 340 return null; 341 } 342 if (updateToMRU) { 343 moveToMRU(entry); 344 } 345 return entry.getValue(); 346 } 347 348 /** 349 * Returns true if this map is full and no new mappings can be added. 350 * 351 * @return {@code true} if the map is full 352 */ 353 @Override 354 public boolean isFull() { 355 return size >= maxSize; 356 } 357 358 /** 359 * Whether this LRUMap will scan until a removable entry is found when the 360 * map is full. 361 * 362 * @return true if this map scans 363 * @since 3.1 364 */ 365 public boolean isScanUntilRemovable() { 366 return scanUntilRemovable; 367 } 368 369 /** 370 * Gets the maximum size of the map (the bound). 371 * 372 * @return the maximum number of elements the map can hold 373 */ 374 @Override 375 public int maxSize() { 376 return maxSize; 377 } 378 379 /** 380 * Moves an entry to the MRU position at the end of the list. 381 * <p> 382 * This implementation moves the updated entry to the end of the list. 383 * 384 * @param entry the entry to update 385 */ 386 protected void moveToMRU(final LinkEntry<K, V> entry) { 387 if (entry.after != header) { 388 modCount++; 389 // remove 390 if (entry.before == null) { 391 throw new IllegalStateException("Entry.before is null." + 392 " This should not occur if your keys are immutable, and you have used synchronization properly."); 393 } 394 entry.before.after = entry.after; 395 entry.after.before = entry.before; 396 // add first 397 entry.after = header; 398 entry.before = header.before; 399 header.before.after = entry; 400 header.before = entry; 401 } else if (entry == header) { 402 throw new IllegalStateException("Can't move header to MRU" + 403 " This should not occur if your keys are immutable, and you have used synchronization properly."); 404 } 405 } 406 407 /** 408 * Read the map in using a custom routine. 409 * 410 * @param in the input stream 411 * @throws IOException if an error occurs while reading from the stream 412 * @throws ClassNotFoundException if an object read from the stream can not be loaded 413 */ 414 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 415 in.defaultReadObject(); 416 doReadObject(in); 417 } 418 419 /** 420 * Subclass method to control removal of the least recently used entry from the map. 421 * <p> 422 * This method exists for subclasses to override. A subclass may wish to 423 * provide cleanup of resources when an entry is removed. For example: 424 * <pre> 425 * protected boolean removeLRU(LinkEntry entry) { 426 * releaseResources(entry.getValue()); // release resources held by entry 427 * return true; // actually delete entry 428 * } 429 * </pre> 430 * <p> 431 * Alternatively, a subclass may choose to not remove the entry or selectively 432 * keep certain LRU entries. For example: 433 * <pre> 434 * protected boolean removeLRU(LinkEntry entry) { 435 * if (entry.getKey().toString().startsWith("System.")) { 436 * return false; // entry not removed from LRUMap 437 * } else { 438 * return true; // actually delete entry 439 * } 440 * } 441 * </pre> 442 * The effect of returning false is dependent on the scanUntilRemovable flag. 443 * If the flag is true, the next LRU entry will be passed to this method and so on 444 * until one returns false and is removed, or every entry in the map has been passed. 445 * If the scanUntilRemovable flag is false, the map will exceed the maximum size. 446 * <p> 447 * NOTE: Commons Collections 3.0 passed the wrong entry to this method. 448 * This is fixed in version 3.1 onwards. 449 * 450 * @param entry the entry to be removed 451 * @return {@code true} 452 */ 453 protected boolean removeLRU(final LinkEntry<K, V> entry) { 454 return true; 455 } 456 457 /** 458 * Reuses an entry by removing it and moving it to a new place in the map. 459 * <p> 460 * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}. 461 * 462 * @param entry the entry to reuse 463 * @param hashIndex the index into the data array to store at 464 * @param hashCode the hash code of the key to add 465 * @param key the key to add 466 * @param value the value to add 467 */ 468 protected void reuseMapping(final LinkEntry<K, V> entry, final int hashIndex, final int hashCode, 469 final K key, final V value) { 470 // find the entry before the entry specified in the hash table 471 // remember that the parameters (except the first) refer to the new entry, 472 // not the old one 473 try { 474 final int removeIndex = hashIndex(entry.hashCode, data.length); 475 final HashEntry<K, V>[] tmp = data; // may protect against some sync issues 476 HashEntry<K, V> loop = tmp[removeIndex]; 477 HashEntry<K, V> previous = null; 478 while (loop != entry && loop != null) { 479 previous = loop; 480 loop = loop.next; 481 } 482 if (loop == null) { 483 throw new IllegalStateException( 484 "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous + 485 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 486 " This should not occur if your keys are immutable, and you have used synchronization properly."); 487 } 488 489 // reuse the entry 490 modCount++; 491 removeEntry(entry, removeIndex, previous); 492 reuseEntry(entry, hashIndex, hashCode, key, value); 493 addEntry(entry, hashIndex); 494 } catch (final NullPointerException ex) { 495 throw new IllegalStateException("NPE, entry=" + entry + " entryIsHeader=" + (entry == header) + " key=" + key + " value=" + value + " size=" + size 496 + " maxSize=" + maxSize + " This should not occur if your keys are immutable, and you have used synchronization properly."); 497 } 498 } 499 500 /** 501 * Updates an existing key-value mapping. 502 * <p> 503 * This implementation moves the updated entry to the end of the list 504 * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}. 505 * 506 * @param entry the entry to update 507 * @param newValue the new value to store 508 */ 509 @Override 510 protected void updateEntry(final HashEntry<K, V> entry, final V newValue) { 511 moveToMRU((LinkEntry<K, V>) entry); // handles modCount 512 entry.setValue(newValue); 513 } 514 515 /** 516 * Write the map out using a custom routine. 517 * 518 * @param out the output stream 519 * @throws IOException if an error occurs while writing to the stream 520 */ 521 private void writeObject(final ObjectOutputStream out) throws IOException { 522 out.defaultWriteObject(); 523 doWriteObject(out); 524 } 525 526}