1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.map;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.io.Serializable;
23 import java.util.Map;
24
25 import org.apache.commons.collections4.BoundedMap;
26
27 /**
28 * A {@code Map} implementation with a fixed maximum size which removes
29 * the least recently used entry if an entry is added when full.
30 * <p>
31 * The least recently used algorithm works on the get and put operations only.
32 * Iteration of any kind, including setting the value by iteration, does not
33 * change the order. Queries such as containsKey and containsValue or access
34 * via views also do not change the order.
35 * </p>
36 * <p>
37 * A somewhat subtle ramification of the least recently used
38 * algorithm is that calls to {@link #get(Object)} stand a very good chance
39 * of modifying the map's iteration order and thus invalidating any
40 * iterators currently in use. It is therefore suggested that iterations
41 * over an {@link LRUMap} instance access entry values only through a
42 * {@link org.apache.commons.collections4.MapIterator MapIterator} or {@link #entrySet()} iterator.
43 * </p>
44 * <p>
45 * The map implements {@code OrderedMap} and entries may be queried using
46 * the bidirectional {@code OrderedMapIterator}. The order returned is
47 * least recently used to most recently used. Iterators from map views can
48 * also be cast to {@code OrderedIterator} if required.
49 * </p>
50 * <p>
51 * All the available iterators can be reset back to the start by casting to
52 * {@code ResettableIterator} and calling {@code reset()}.
53 * </p>
54 * <p>
55 * <strong>Note that LRUMap is not synchronized and is not thread-safe.</strong>
56 * If you wish to use this map from multiple threads concurrently, you must use
57 * appropriate synchronization. The simplest approach is to wrap this map
58 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
59 * {@code NullPointerException}'s when accessed by concurrent threads.
60 * </p>
61 *
62 * @param <K> the type of the keys in this map
63 * @param <V> the type of the values in this map
64 * @since 3.0 (previously in main package v1.0)
65 */
66 public class LRUMap<K, V>
67 extends AbstractLinkedMap<K, V> implements BoundedMap<K, V>, Serializable, Cloneable {
68
69 /** Serialisation version */
70 private static final long serialVersionUID = -612114643488955218L;
71 /** Default maximum size */
72 protected static final int DEFAULT_MAX_SIZE = 100;
73
74 /** Maximum size */
75 private transient int maxSize;
76 /** Scan behavior */
77 private final boolean scanUntilRemovable;
78
79 /**
80 * Constructs a new empty map with a maximum size of 100.
81 */
82 public LRUMap() {
83 this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
84 }
85
86 /**
87 * Constructs a new, empty map with the specified maximum size.
88 *
89 * @param maxSize the maximum size of the map
90 * @throws IllegalArgumentException if the maximum size is less than one
91 */
92 public LRUMap(final int maxSize) {
93 this(maxSize, DEFAULT_LOAD_FACTOR);
94 }
95
96 /**
97 * Constructs a new, empty map with the specified maximum size.
98 *
99 * @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 * </p>
197 *
198 * @param map the map to copy
199 * @throws NullPointerException if the map is null
200 * @throws IllegalArgumentException if the map is empty
201 */
202 public LRUMap(final Map<? extends K, ? extends V> map) {
203 this(map, false);
204 }
205
206 /**
207 * Constructor copying elements from another map.
208 *
209 * <p>The maximum size is set from the map's size.</p>
210 *
211 * @param map the map to copy
212 * @param scanUntilRemovable scan until a removable entry is found, default false
213 * @throws NullPointerException if the map is null
214 * @throws IllegalArgumentException if the map is empty
215 * @since 3.1
216 */
217 public LRUMap(final Map<? extends K, ? extends V> map, final boolean scanUntilRemovable) {
218 this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
219 putAll(map);
220 }
221
222 /**
223 * Adds a new key-value mapping into this map.
224 * <p>
225 * This implementation checks the LRU size and determines whether to
226 * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}.
227 * </p>
228 * <p>
229 * From Commons Collections 3.1 this method uses {@link #isFull()} rather
230 * than accessing {@code size} and {@code maxSize} directly.
231 * It also handles the scanUntilRemovable functionality.
232 * </p>
233 *
234 * @param hashIndex the index into the data array to store at
235 * @param hashCode the hash code of the key to add
236 * @param key the key to add
237 * @param value the value to add
238 */
239 @Override
240 protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) {
241 if (isFull()) {
242 LinkEntry<K, V> reuse = header.after;
243 boolean removeLRUEntry = false;
244 if (scanUntilRemovable) {
245 while (reuse != header && reuse != null) {
246 if (removeLRU(reuse)) {
247 removeLRUEntry = true;
248 break;
249 }
250 reuse = reuse.after;
251 }
252 if (reuse == null) {
253 throw new IllegalStateException(
254 "Entry.after=null, header.after=" + header.after + " header.before=" + header.before +
255 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
256 " This should not occur if your keys are immutable and you used synchronization properly.");
257 }
258 } else {
259 removeLRUEntry = removeLRU(reuse);
260 }
261
262 if (removeLRUEntry) {
263 if (reuse == null) {
264 throw new IllegalStateException(
265 "reuse=null, header.after=" + header.after + " header.before=" + header.before +
266 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
267 " This should not occur if your keys are immutable and you used synchronization properly.");
268 }
269 reuseMapping(reuse, hashIndex, hashCode, key, value);
270 } else {
271 super.addMapping(hashIndex, hashCode, key, value);
272 }
273 } else {
274 super.addMapping(hashIndex, hashCode, key, value);
275 }
276 }
277
278 /**
279 * Clones the map without cloning the keys or values.
280 *
281 * @return a shallow clone
282 */
283 @Override
284 public LRUMap<K, V> clone() {
285 return (LRUMap<K, V>) super.clone();
286 }
287
288 /**
289 * Reads the data necessary for {@code put()} to work in the superclass.
290 *
291 * @param in the input stream
292 * @throws IOException if an error occurs while reading from the stream
293 * @throws ClassNotFoundException if an object read from the stream cannot be loaded
294 */
295 @Override
296 protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
297 maxSize = in.readInt();
298 super.doReadObject(in);
299 }
300
301 /**
302 * Writes the data necessary for {@code put()} to work in deserialization.
303 *
304 * @param out the output stream
305 * @throws IOException if an error occurs while writing to the stream
306 */
307 @Override
308 protected void doWriteObject(final ObjectOutputStream out) throws IOException {
309 out.writeInt(maxSize);
310 super.doWriteObject(out);
311 }
312
313 /**
314 * Gets the value mapped to the key specified.
315 * <p>
316 * This operation changes the position of the key in the map to the
317 * most recently used position (last).
318 *
319 * @param key the key
320 * @return the mapped value, null if no match
321 */
322 @Override
323 public V get(final Object key) {
324 return get(key, true);
325 }
326
327 /**
328 * Gets the value mapped to the key specified.
329 * <p>
330 * If {@code updateToMRU} is {@code true}, the position of the key in the map
331 * is changed to the most recently used position (last), otherwise the iteration
332 * order is not changed by this operation.
333 * </p>
334 *
335 * @param key the key
336 * @param updateToMRU whether the key shall be updated to the
337 * most recently used position
338 * @return the mapped value, null if no match
339 * @since 4.1
340 */
341 public V get(final Object key, final boolean updateToMRU) {
342 final LinkEntry<K, V> entry = getEntry(key);
343 if (entry == null) {
344 return null;
345 }
346 if (updateToMRU) {
347 moveToMRU(entry);
348 }
349 return entry.getValue();
350 }
351
352 /**
353 * Returns true if this map is full and no new mappings can be added.
354 *
355 * @return {@code true} if the map is full
356 */
357 @Override
358 public boolean isFull() {
359 return size >= maxSize;
360 }
361
362 /**
363 * Whether this LRUMap will scan until a removable entry is found when the
364 * map is full.
365 *
366 * @return true if this map scans
367 * @since 3.1
368 */
369 public boolean isScanUntilRemovable() {
370 return scanUntilRemovable;
371 }
372
373 /**
374 * Gets the maximum size of the map (the bound).
375 *
376 * @return the maximum number of elements the map can hold
377 */
378 @Override
379 public int maxSize() {
380 return maxSize;
381 }
382
383 /**
384 * Moves an entry to the MRU position at the end of the list.
385 * <p>
386 * This implementation moves the updated entry to the end of the list.
387 * </p>
388 *
389 * @param entry the entry to update
390 */
391 protected void moveToMRU(final LinkEntry<K, V> entry) {
392 if (entry.after != header) {
393 modCount++;
394 // remove
395 if (entry.before == null) {
396 throw new IllegalStateException("Entry.before is null." +
397 " This should not occur if your keys are immutable, and you have used synchronization properly.");
398 }
399 entry.before.after = entry.after;
400 entry.after.before = entry.before;
401 // add first
402 entry.after = header;
403 entry.before = header.before;
404 header.before.after = entry;
405 header.before = entry;
406 } else if (entry == header) {
407 throw new IllegalStateException("Can't move header to MRU" +
408 " This should not occur if your keys are immutable, and you have used synchronization properly.");
409 }
410 }
411
412 /**
413 * Deserializes the map in using a custom routine.
414 *
415 * @param in the input stream
416 * @throws IOException if an error occurs while reading from the stream
417 * @throws ClassNotFoundException if an object read from the stream cannot be loaded
418 */
419 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
420 in.defaultReadObject();
421 doReadObject(in);
422 }
423
424 /**
425 * Subclass method to control removal of the least recently used entry from the map.
426 * <p>
427 * This method exists for subclasses to override. A subclass may wish to
428 * provide cleanup of resources when an entry is removed. For example:
429 * </p>
430 * <pre>
431 * protected boolean removeLRU(LinkEntry entry) {
432 * releaseResources(entry.getValue()); // release resources held by entry
433 * return true; // actually delete entry
434 * }
435 * </pre>
436 * <p>
437 * Alternatively, a subclass may choose to not remove the entry or selectively
438 * keep certain LRU entries. For example:
439 * </p>
440 * <pre>
441 * protected boolean removeLRU(LinkEntry entry) {
442 * if (entry.getKey().toString().startsWith("System.")) {
443 * return false; // entry not removed from LRUMap
444 * } else {
445 * return true; // actually delete entry
446 * }
447 * }
448 * </pre>
449 * <p>
450 * The effect of returning false is dependent on the scanUntilRemovable flag.
451 * If the flag is true, the next LRU entry will be passed to this method and so on
452 * until one returns false and is removed, or every entry in the map has been passed.
453 * If the scanUntilRemovable flag is false, the map will exceed the maximum size.
454 * </p>
455 * <p>
456 * Note: Commons Collections 3.0 passed the wrong entry to this method.
457 * This is fixed in version 3.1 onwards.
458 * </p>
459 *
460 * @param entry the entry to be removed
461 * @return {@code true}
462 */
463 protected boolean removeLRU(final LinkEntry<K, V> entry) {
464 return true;
465 }
466
467 /**
468 * Reuses an entry by removing it and moving it to a new place in the map.
469 * <p>
470 * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}.
471 *
472 * @param entry the entry to reuse
473 * @param hashIndex the index into the data array to store at
474 * @param hashCode the hash code of the key to add
475 * @param key the key to add
476 * @param value the value to add
477 */
478 protected void reuseMapping(final LinkEntry<K, V> entry, final int hashIndex, final int hashCode,
479 final K key, final V value) {
480 // find the entry before the entry specified in the hash table
481 // remember that the parameters (except the first) refer to the new entry,
482 // not the old one
483 try {
484 final int removeIndex = hashIndex(entry.hashCode, data.length);
485 final HashEntry<K, V>[] tmp = data; // may protect against some sync issues
486 HashEntry<K, V> loop = tmp[removeIndex];
487 HashEntry<K, V> previous = null;
488 while (loop != entry && loop != null) {
489 previous = loop;
490 loop = loop.next;
491 }
492 if (loop == null) {
493 throw new IllegalStateException(
494 "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous +
495 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
496 " This should not occur if your keys are immutable, and you have used synchronization properly.");
497 }
498
499 // reuse the entry
500 modCount++;
501 removeEntry(entry, removeIndex, previous);
502 reuseEntry(entry, hashIndex, hashCode, key, value);
503 addEntry(entry, hashIndex);
504 } catch (final NullPointerException ex) {
505 throw new IllegalStateException("NPE, entry=" + entry + " entryIsHeader=" + (entry == header) + " key=" + key + " value=" + value + " size=" + size
506 + " maxSize=" + maxSize + " This should not occur if your keys are immutable, and you have used synchronization properly.");
507 }
508 }
509
510 /**
511 * Updates an existing key-value mapping.
512 * <p>
513 * This implementation moves the updated entry to the end of the list
514 * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}.
515 * </p>
516 *
517 * @param entry the entry to update
518 * @param newValue the new value to store
519 */
520 @Override
521 protected void updateEntry(final HashEntry<K, V> entry, final V newValue) {
522 moveToMRU((LinkEntry<K, V>) entry); // handles modCount
523 entry.setValue(newValue);
524 }
525
526 /**
527 * Serializes this object to an ObjectOutputStream.
528 *
529 * @param out the target ObjectOutputStream.
530 * @throws IOException thrown when an I/O errors occur writing to the target stream.
531 */
532 private void writeObject(final ObjectOutputStream out) throws IOException {
533 out.defaultWriteObject();
534 doWriteObject(out);
535 }
536
537 }