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</code> 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 * A somewhat subtle ramification of the least recently used
037 * algorithm is that calls to {@link #get(Object)} stand a very good chance
038 * of modifying the map's iteration order and thus invalidating any
039 * iterators currently in use.  It is therefore suggested that iterations
040 * over an {@link LRUMap} instance access entry values only through a
041 * {@link org.apache.commons.collections4.MapIterator MapIterator} or {@link #entrySet()} iterator.
042 * <p>
043 * The map implements <code>OrderedMap</code> and entries may be queried using
044 * the bidirectional <code>OrderedMapIterator</code>. The order returned is
045 * least recently used to most recently used. Iterators from map views can
046 * also be cast to <code>OrderedIterator</code> if required.
047 * <p>
048 * All the available iterators can be reset back to the start by casting to
049 * <code>ResettableIterator</code> and calling <code>reset()</code>.
050 * <p>
051 * <strong>Note that LRUMap is not synchronized and is not thread-safe.</strong>
052 * If you wish to use this map from multiple threads concurrently, you must use
053 * appropriate synchronization. The simplest approach is to wrap this map
054 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
055 * <code>NullPointerException</code>'s when accessed by concurrent threads.
056 *
057 * @since 3.0 (previously in main package v1.0)
058 * @version $Id: LRUMap.html 887892 2013-11-24 13:43:45Z tn $
059 */
060public class LRUMap<K, V>
061        extends AbstractLinkedMap<K, V> implements BoundedMap<K, V>, Serializable, Cloneable {
062
063    /** Serialisation version */
064    private static final long serialVersionUID = -612114643488955218L;
065    /** Default maximum size */
066    protected static final int DEFAULT_MAX_SIZE = 100;
067
068    /** Maximum size */
069    private transient int maxSize;
070    /** Scan behaviour */
071    private boolean scanUntilRemovable;
072
073    /**
074     * Constructs a new empty map with a maximum size of 100.
075     */
076    public LRUMap() {
077        this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
078    }
079
080    /**
081     * Constructs a new, empty map with the specified maximum size.
082     *
083     * @param maxSize  the maximum size of the map
084     * @throws IllegalArgumentException if the maximum size is less than one
085     */
086    public LRUMap(final int maxSize) {
087        this(maxSize, DEFAULT_LOAD_FACTOR);
088    }
089
090    /**
091     * Constructs a new, empty map with the specified maximum size.
092     *
093     * @param maxSize  the maximum size of the map
094     * @param scanUntilRemovable  scan until a removeable entry is found, default false
095     * @throws IllegalArgumentException if the maximum size is less than one
096     * @since 3.1
097     */
098    public LRUMap(final int maxSize, final boolean scanUntilRemovable) {
099        this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
100    }
101
102    /**
103     * Constructs a new, empty map with the specified initial capacity and
104     * load factor.
105     *
106     * @param maxSize  the maximum size of the map
107     * @param loadFactor  the load factor
108     * @throws IllegalArgumentException if the maximum size is less than one
109     * @throws IllegalArgumentException if the load factor is less than zero
110     */
111    public LRUMap(final int maxSize, final float loadFactor) {
112        this(maxSize, loadFactor, false);
113    }
114
115    /**
116     * Constructs a new, empty map with the specified initial capacity and
117     * load factor.
118     *
119     * @param maxSize  the maximum size of the ma
120     * @param loadFactor  the load factor
121     * @param scanUntilRemovable  scan until a removeable entry is found, default false
122     * @throws IllegalArgumentException if the maximum size is less than one
123     * @throws IllegalArgumentException if the load factor is less than zero
124     * @since 3.1
125     */
126    public LRUMap(final int maxSize, final float loadFactor, final boolean scanUntilRemovable) {
127        super(maxSize < 1 ? DEFAULT_CAPACITY : maxSize, loadFactor);
128        if (maxSize < 1) {
129            throw new IllegalArgumentException("LRUMap max size must be greater than 0");
130        }
131        this.maxSize = maxSize;
132        this.scanUntilRemovable = scanUntilRemovable;
133    }
134
135    /**
136     * Constructor copying elements from another map.
137     * <p>
138     * The maximum size is set from the map's size.
139     *
140     * @param map  the map to copy
141     * @throws NullPointerException if the map is null
142     * @throws IllegalArgumentException if the map is empty
143     */
144    public LRUMap(final Map<? extends K, ? extends V> map) {
145        this(map, false);
146    }
147
148    /**
149     * Constructor copying elements from another map.
150     * <p/>
151     * The maximum size is set from the map's size.
152     *
153     * @param map  the map to copy
154     * @param scanUntilRemovable  scan until a removeable entry is found, default false
155     * @throws NullPointerException if the map is null
156     * @throws IllegalArgumentException if the map is empty
157     * @since 3.1
158     */
159    public LRUMap(final Map<? extends K, ? extends V> map, final boolean scanUntilRemovable) {
160        this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
161        putAll(map);
162    }
163
164    //-----------------------------------------------------------------------
165    /**
166     * Gets the value mapped to the key specified.
167     * <p>
168     * This operation changes the position of the key in the map to the
169     * most recently used position (first).
170     *
171     * @param key  the key
172     * @return the mapped value, null if no match
173     */
174    @Override
175    public V get(final Object key) {
176        final LinkEntry<K, V> entry = getEntry(key);
177        if (entry == null) {
178            return null;
179        }
180        moveToMRU(entry);
181        return entry.getValue();
182    }
183
184    //-----------------------------------------------------------------------
185    /**
186     * Moves an entry to the MRU position at the end of the list.
187     * <p>
188     * This implementation moves the updated entry to the end of the list.
189     *
190     * @param entry  the entry to update
191     */
192    protected void moveToMRU(final LinkEntry<K, V> entry) {
193        if (entry.after != header) {
194            modCount++;
195            // remove
196            if(entry.before == null) {
197                throw new IllegalStateException("Entry.before is null." +
198                    " Please check that your keys are immutable, and that you have used synchronization properly." +
199                    " If so, then please report this to dev@commons.apache.org as a bug.");
200            }
201            entry.before.after = entry.after;
202            entry.after.before = entry.before;
203            // add first
204            entry.after = header;
205            entry.before = header.before;
206            header.before.after = entry;
207            header.before = entry;
208        } else if (entry == header) {
209            throw new IllegalStateException("Can't move header to MRU" +
210                " (please report this to dev@commons.apache.org)");
211        }
212    }
213
214    /**
215     * Updates an existing key-value mapping.
216     * <p>
217     * This implementation moves the updated entry to the top of the list
218     * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}.
219     *
220     * @param entry  the entry to update
221     * @param newValue  the new value to store
222     */
223    @Override
224    protected void updateEntry(final HashEntry<K, V> entry, final V newValue) {
225        moveToMRU((LinkEntry<K, V>) entry);  // handles modCount
226        entry.setValue(newValue);
227    }
228
229    /**
230     * Adds a new key-value mapping into this map.
231     * <p>
232     * This implementation checks the LRU size and determines whether to
233     * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}.
234     * <p>
235     * From Commons Collections 3.1 this method uses {@link #isFull()} rather
236     * than accessing <code>size</code> and <code>maxSize</code> directly.
237     * It also handles the scanUntilRemovable functionality.
238     *
239     * @param hashIndex  the index into the data array to store at
240     * @param hashCode  the hash code of the key to add
241     * @param key  the key to add
242     * @param value  the value to add
243     */
244    @Override
245    protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) {
246        if (isFull()) {
247            LinkEntry<K, V> reuse = header.after;
248            boolean removeLRUEntry = false;
249            if (scanUntilRemovable) {
250                while (reuse != header && reuse != null) {
251                    if (removeLRU(reuse)) {
252                        removeLRUEntry = true;
253                        break;
254                    }
255                    reuse = reuse.after;
256                }
257                if (reuse == null) {
258                    throw new IllegalStateException(
259                        "Entry.after=null, header.after" + header.after + " header.before" + header.before +
260                        " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
261                        " Please check that your keys are immutable, and that you have used synchronization properly." +
262                        " If so, then please report this to dev@commons.apache.org as a bug.");
263                }
264            } else {
265                removeLRUEntry = removeLRU(reuse);
266            }
267
268            if (removeLRUEntry) {
269                if (reuse == null) {
270                    throw new IllegalStateException(
271                        "reuse=null, header.after=" + header.after + " header.before" + header.before +
272                        " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
273                        " Please check that your keys are immutable, and that you have used synchronization properly." +
274                        " If so, then please report this to dev@commons.apache.org as a bug.");
275                }
276                reuseMapping(reuse, hashIndex, hashCode, key, value);
277            } else {
278                super.addMapping(hashIndex, hashCode, key, value);
279            }
280        } else {
281            super.addMapping(hashIndex, hashCode, key, value);
282        }
283    }
284
285    /**
286     * Reuses an entry by removing it and moving it to a new place in the map.
287     * <p>
288     * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}.
289     *
290     * @param entry  the entry to reuse
291     * @param hashIndex  the index into the data array to store at
292     * @param hashCode  the hash code of the key to add
293     * @param key  the key to add
294     * @param value  the value to add
295     */
296    protected void reuseMapping(final LinkEntry<K, V> entry, final int hashIndex, final int hashCode,
297                                final K key, final V value) {
298        // find the entry before the entry specified in the hash table
299        // remember that the parameters (except the first) refer to the new entry,
300        // not the old one
301        try {
302            final int removeIndex = hashIndex(entry.hashCode, data.length);
303            final HashEntry<K, V>[] tmp = data;  // may protect against some sync issues
304            HashEntry<K, V> loop = tmp[removeIndex];
305            HashEntry<K, V> previous = null;
306            while (loop != entry && loop != null) {
307                previous = loop;
308                loop = loop.next;
309            }
310            if (loop == null) {
311                throw new IllegalStateException(
312                    "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous +
313                    " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
314                    " Please check that your keys are immutable, and that you have used synchronization properly." +
315                    " If so, then please report this to dev@commons.apache.org as a bug.");
316            }
317
318            // reuse the entry
319            modCount++;
320            removeEntry(entry, removeIndex, previous);
321            reuseEntry(entry, hashIndex, hashCode, key, value);
322            addEntry(entry, hashIndex);
323        } catch (final NullPointerException ex) {
324            throw new IllegalStateException(
325                    "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) +
326                    " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
327                    " Please check that your keys are immutable, and that you have used synchronization properly." +
328                    " If so, then please report this to dev@commons.apache.org as a bug.");
329        }
330    }
331
332    /**
333     * Subclass method to control removal of the least recently used entry from the map.
334     * <p>
335     * This method exists for subclasses to override. A subclass may wish to
336     * provide cleanup of resources when an entry is removed. For example:
337     * <pre>
338     * protected boolean removeLRU(LinkEntry entry) {
339     *   releaseResources(entry.getValue());  // release resources held by entry
340     *   return true;  // actually delete entry
341     * }
342     * </pre>
343     * <p>
344     * Alternatively, a subclass may choose to not remove the entry or selectively
345     * keep certain LRU entries. For example:
346     * <pre>
347     * protected boolean removeLRU(LinkEntry entry) {
348     *   if (entry.getKey().toString().startsWith("System.")) {
349     *     return false;  // entry not removed from LRUMap
350     *   } else {
351     *     return true;  // actually delete entry
352     *   }
353     * }
354     * </pre>
355     * The effect of returning false is dependent on the scanUntilRemovable flag.
356     * If the flag is true, the next LRU entry will be passed to this method and so on
357     * until one returns false and is removed, or every entry in the map has been passed.
358     * If the scanUntilRemovable flag is false, the map will exceed the maximum size.
359     * <p>
360     * NOTE: Commons Collections 3.0 passed the wrong entry to this method.
361     * This is fixed in version 3.1 onwards.
362     *
363     * @param entry  the entry to be removed
364     * @return {@code true}
365     */
366    protected boolean removeLRU(final LinkEntry<K, V> entry) {
367        return true;
368    }
369
370    //-----------------------------------------------------------------------
371    /**
372     * Returns true if this map is full and no new mappings can be added.
373     *
374     * @return <code>true</code> if the map is full
375     */
376    public boolean isFull() {
377        return size >= maxSize;
378    }
379
380    /**
381     * Gets the maximum size of the map (the bound).
382     *
383     * @return the maximum number of elements the map can hold
384     */
385    public int maxSize() {
386        return maxSize;
387    }
388
389    /**
390     * Whether this LRUMap will scan until a removable entry is found when the
391     * map is full.
392     *
393     * @return true if this map scans
394     * @since 3.1
395     */
396    public boolean isScanUntilRemovable() {
397        return scanUntilRemovable;
398    }
399
400    //-----------------------------------------------------------------------
401    /**
402     * Clones the map without cloning the keys or values.
403     *
404     * @return a shallow clone
405     */
406    @Override
407    public LRUMap<K, V> clone() {
408        return (LRUMap<K, V>) super.clone();
409    }
410
411    /**
412     * Write the map out using a custom routine.
413     */
414    private void writeObject(final ObjectOutputStream out) throws IOException {
415        out.defaultWriteObject();
416        doWriteObject(out);
417    }
418
419    /**
420     * Read the map in using a custom routine.
421     */
422    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
423        in.defaultReadObject();
424        doReadObject(in);
425    }
426
427    /**
428     * Writes the data necessary for <code>put()</code> to work in deserialization.
429     *
430     * @param out  the output stream
431     * @throws IOException if an error occurs while writing to the stream
432     */
433    @Override
434    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
435        out.writeInt(maxSize);
436        super.doWriteObject(out);
437    }
438
439    /**
440     * Reads the data necessary for <code>put()</code> to work in the superclass.
441     *
442     * @param in  the input stream
443     * @throws IOException if an error occurs while reading from the stream
444     * @throws ClassNotFoundException if an object read from the stream can not be loaded
445     */
446    @Override
447    protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
448        maxSize = in.readInt();
449        super.doReadObject(in);
450    }
451
452}