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