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 *
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(
496 "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) +
497 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
498 " This should not occur if your keys are immutable, and you have used synchronization properly.");
499 }
500 }
501
502 /**
503 * Updates an existing key-value mapping.
504 * <p>
505 * This implementation moves the updated entry to the end of the list
506 * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}.
507 *
508 * @param entry the entry to update
509 * @param newValue the new value to store
510 */
511 @Override
512 protected void updateEntry(final HashEntry<K, V> entry, final V newValue) {
513 moveToMRU((LinkEntry<K, V>) entry); // handles modCount
514 entry.setValue(newValue);
515 }
516
517 /**
518 * Write the map out using a custom routine.
519 *
520 * @param out the output stream
521 * @throws IOException if an error occurs while writing to the stream
522 */
523 private void writeObject(final ObjectOutputStream out) throws IOException {
524 out.defaultWriteObject();
525 doWriteObject(out);
526 }
527
528 }