    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.Collection;
    024import java.util.HashMap;
    025import java.util.Iterator;
    026import java.util.Map;
    027import java.util.Set;
    028import java.util.concurrent.TimeUnit;
    029
    030/**
    031 * Decorates a <code>Map</code> to evict expired entries once their expiration
    032 * time has been reached.
    033 * <p>
    034 * When putting a key-value pair in the map this decorator uses a
    035 * {@link ExpirationPolicy} to determine how long the entry should remain alive
    036 * as defined by an expiration time value.
    037 * </p>
    038 * <p>
    039 * When accessing the mapped value for a key, its expiration time is checked,
    040 * and if it is a negative value or if it is greater than the current time, the
    041 * mapped value is returned. Otherwise, the key is removed from the decorated
    042 * map, and <code>null</code> is returned.
    043 * </p>
    044 * <p>
    045 * When invoking methods that involve accessing the entire map contents (i.e
    046 * {@link #containsKey(Object)}, {@link #entrySet()}, etc.) this decorator
    047 * removes all expired entries prior to actually completing the invocation.
    048 * </p>
    049 * <p>
    050 * <strong>Note that {@link PassiveExpiringMap} is not synchronized and is not
    051 * thread-safe.</strong> If you wish to use this map from multiple threads
    052 * concurrently, you must use appropriate synchronization. The simplest approach
    053 * is to wrap this map using {@link java.util.Collections#synchronizedMap(Map)}.
    054 * This class may throw exceptions when accessed by concurrent threads without
    055 * synchronization.
    056 * </p>
    057 *
    058 * @param <K> the type of the keys in this map
    059 * @param <V> the type of the values in this map
    060 * @since 4.0
    061 */
    062public class PassiveExpiringMap<K, V>
    063    extends AbstractMapDecorator<K, V>
    064    implements Serializable {
    065
    066    /**
    067     * A {@link org.apache.commons.collections4.map.PassiveExpiringMap.ExpirationPolicy ExpirationPolicy}
    068     * that returns a expiration time that is a
    069     * constant about of time in the future from the current time.
    070     *
    071     * @param <K> the type of the keys in the map
    072     * @param <V> the type of the values in the map
    073     * @since 4.0
    074     */
    075    public static class ConstantTimeToLiveExpirationPolicy<K, V>
    076        implements ExpirationPolicy<K, V> {
    077
    078        /** Serialization version */
    079        private static final long serialVersionUID = 1L;
    080
    081        /** the constant time-to-live value measured in milliseconds. */
    082        private final long timeToLiveMillis;
    083
    084        /**
    085         * Default constructor. Constructs a policy using a negative
    086         * time-to-live value that results in entries never expiring.
    087         */
    088        public ConstantTimeToLiveExpirationPolicy() {
    089            this(-1L);
    090        }
    091
    092        /**
    093         * Construct a policy with the given time-to-live constant measured in
    094         * milliseconds. A negative time-to-live value indicates entries never
    095         * expire. A zero time-to-live value indicates entries expire (nearly)
    096         * immediately.
    097         *
    098         * @param timeToLiveMillis the constant amount of time (in milliseconds)
    099         *        an entry is available before it expires. A negative value
    100         *        results in entries that NEVER expire. A zero value results in
    101         *        entries that ALWAYS expire.
    102         */
    103        public ConstantTimeToLiveExpirationPolicy(final long timeToLiveMillis) {
    104            super();
    105            this.timeToLiveMillis = timeToLiveMillis;
    106        }
    107
    108        /**
    109         * Construct a policy with the given time-to-live constant measured in
    110         * the given time unit of measure.
    111         *
    112         * @param timeToLive the constant amount of time an entry is available
    113         *        before it expires. A negative value results in entries that
    114         *        NEVER expire. A zero value results in entries that ALWAYS
    115         *        expire.
    116         * @param timeUnit the unit of time for the <code>timeToLive</code>
    117         *        parameter, must not be null.
    118         * @throws NullPointerException if the time unit is null.
    119         */
    120        public ConstantTimeToLiveExpirationPolicy(final long timeToLive,
    121                                                  final TimeUnit timeUnit) {
    122            this(validateAndConvertToMillis(timeToLive, timeUnit));
    123        }
    124
    125        /**
    126         * Determine the expiration time for the given key-value entry.
    127         *
    128         * @param key the key for the entry (ignored).
    129         * @param value the value for the entry (ignored).
    130         * @return if {@link #timeToLiveMillis} &ge; 0, an expiration time of
    131         *         {@link #timeToLiveMillis} +
    132         *         {@link System#currentTimeMillis()} is returned. Otherwise, -1
    133         *         is returned indicating the entry never expires.
    134         */
    135        @Override
    136        public long expirationTime(final K key, final V value) {
    137            if (timeToLiveMillis >= 0L) {
    138                // avoid numerical overflow
    139                final long now = System.currentTimeMillis();
    140                if (now > Long.MAX_VALUE - timeToLiveMillis) {
    141                    // expiration would be greater than Long.MAX_VALUE
    142                    // never expire
    143                    return -1;
    144                }
    145
    146                // timeToLiveMillis in the future
    147                return now + timeToLiveMillis;
    148            }
    149
    150            // never expire
    151            return -1L;
    152        }
    153    }
    154
    155    /**
    156     * A policy to determine the expiration time for key-value entries.
    157     *
    158     * @param <K> the key object type.
    159     * @param <V> the value object type
    160     * @since 4.0
    161     */
    162    @FunctionalInterface
    163    public interface ExpirationPolicy<K, V>
    164        extends Serializable {
    165
    166        /**
    167         * Determine the expiration time for the given key-value entry.
    168         *
    169         * @param key the key for the entry.
    170         * @param value the value for the entry.
    171         * @return the expiration time value measured in milliseconds. A
    172         *         negative return value indicates the entry never expires.
    173         */
    174        long expirationTime(K key, V value);
    175    }
    176
    177    /** Serialization version */
    178    private static final long serialVersionUID = 1L;
    179
    180    /**
    181     * First validate the input parameters. If the parameters are valid, convert
    182     * the given time measured in the given units to the same time measured in
    183     * milliseconds.
    184     *
    185     * @param timeToLive the constant amount of time an entry is available
    186     *        before it expires. A negative value results in entries that NEVER
    187     *        expire. A zero value results in entries that ALWAYS expire.
    188     * @param timeUnit the unit of time for the <code>timeToLive</code>
    189     *        parameter, must not be null.
    190     * @throws NullPointerException if the time unit is null.
    191     */
    192    private static long validateAndConvertToMillis(final long timeToLive,
    193                                                   final TimeUnit timeUnit) {
    194        if (timeUnit == null) {
    195            throw new NullPointerException("Time unit must not be null");
    196        }
    197        return TimeUnit.MILLISECONDS.convert(timeToLive, timeUnit);
    198    }
    199
    200    /** map used to manage expiration times for the actual map entries. */
    201    private final Map<Object, Long> expirationMap = new HashMap<>();
    202
    203    /** the policy used to determine time-to-live values for map entries. */
    204    private final ExpirationPolicy<K, V> expiringPolicy;
    205
    206    /**
    207     * Default constructor. Constructs a map decorator that results in entries
    208     * NEVER expiring.
    209     */
    210    public PassiveExpiringMap() {
    211        this(-1L);
    212    }
    213
    214    /**
    215     * Construct a map decorator using the given expiration policy to determine
    216     * expiration times.
    217     *
    218     * @param expiringPolicy the policy used to determine expiration times of
    219     *        entries as they are added.
    220     * @throws NullPointerException if expiringPolicy is null
    221     */
    222    public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy) {
    223        this(expiringPolicy, new HashMap<K, V>());
    224    }
    225
    226    /**
    227     * Construct a map decorator that decorates the given map and uses the given
    228     * expiration policy to determine expiration times. If there are any
    229     * elements already in the map being decorated, they will NEVER expire
    230     * unless they are replaced.
    231     *
    232     * @param expiringPolicy the policy used to determine expiration times of
    233     *        entries as they are added.
    234     * @param map the map to decorate, must not be null.
    235     * @throws NullPointerException if the map or expiringPolicy is null.
    236     */
    237    public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy,
    238                              final Map<K, V> map) {
    239        super(map);
    240        if (expiringPolicy == null) {
    241            throw new NullPointerException("Policy must not be null.");
    242        }
    243        this.expiringPolicy = expiringPolicy;
    244    }
    245
    246    /**
    247     * Construct a map decorator that decorates the given map using the given
    248     * time-to-live value measured in milliseconds to create and use a
    249     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy.
    250     *
    251     * @param timeToLiveMillis the constant amount of time (in milliseconds) an
    252     *        entry is available before it expires. A negative value results in
    253     *        entries that NEVER expire. A zero value results in entries that
    254     *        ALWAYS expire.
    255     */
    256    public PassiveExpiringMap(final long timeToLiveMillis) {
    257        this(new ConstantTimeToLiveExpirationPolicy<K, V>(timeToLiveMillis),
    258             new HashMap<K, V>());
    259    }
    260
    261    /**
    262     * Construct a map decorator using the given time-to-live value measured in
    263     * milliseconds to create and use a
    264     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. If there
    265     * are any elements already in the map being decorated, they will NEVER
    266     * expire unless they are replaced.
    267     *
    268     * @param timeToLiveMillis the constant amount of time (in milliseconds) an
    269     *        entry is available before it expires. A negative value results in
    270     *        entries that NEVER expire. A zero value results in entries that
    271     *        ALWAYS expire.
    272     * @param map the map to decorate, must not be null.
    273     * @throws NullPointerException if the map is null.
    274     */
    275    public PassiveExpiringMap(final long timeToLiveMillis, final Map<K, V> map) {
    276        this(new ConstantTimeToLiveExpirationPolicy<K, V>(timeToLiveMillis),
    277             map);
    278    }
    279
    280    /**
    281     * Construct a map decorator using the given time-to-live value measured in
    282     * the given time units of measure to create and use a
    283     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy.
    284     *
    285     * @param timeToLive the constant amount of time an entry is available
    286     *        before it expires. A negative value results in entries that NEVER
    287     *        expire. A zero value results in entries that ALWAYS expire.
    288     * @param timeUnit the unit of time for the <code>timeToLive</code>
    289     *        parameter, must not be null.
    290     * @throws NullPointerException if the time unit is null.
    291     */
    292    public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit) {
    293        this(validateAndConvertToMillis(timeToLive, timeUnit));
    294    }
    295
    296    /**
    297     * Construct a map decorator that decorates the given map using the given
    298     * time-to-live value measured in the given time units of measure to create
    299     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. This policy
    300     * is used to determine expiration times. If there are any elements already
    301     * in the map being decorated, they will NEVER expire unless they are
    302     * replaced.
    303     *
    304     * @param timeToLive the constant amount of time an entry is available
    305     *        before it expires. A negative value results in entries that NEVER
    306     *        expire. A zero value results in entries that ALWAYS expire.
    307     * @param timeUnit the unit of time for the <code>timeToLive</code>
    308     *        parameter, must not be null.
    309     * @param map the map to decorate, must not be null.
    310     * @throws NullPointerException if the map or time unit is null.
    311     */
    312    public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit, final Map<K, V> map) {
    313        this(validateAndConvertToMillis(timeToLive, timeUnit), map);
    314    }
    315
    316    /**
    317     * Constructs a map decorator that decorates the given map and results in
    318     * entries NEVER expiring. If there are any elements already in the map
    319     * being decorated, they also will NEVER expire.
    320     *
    321     * @param map the map to decorate, must not be null.
    322     * @throws NullPointerException if the map is null.
    323     */
    324    public PassiveExpiringMap(final Map<K, V> map) {
    325        this(-1L, map);
    326    }
    327
    328    /**
    329     * Normal {@link Map#clear()} behavior with the addition of clearing all
    330     * expiration entries as well.
    331     */
    332    @Override
    333    public void clear() {
    334        super.clear();
    335        expirationMap.clear();
    336    }
    337
    338    /**
    339     * All expired entries are removed from the map prior to determining the
    340     * contains result.
    341     * {@inheritDoc}
    342     */
    343    @Override
    344    public boolean containsKey(final Object key) {
    345        removeIfExpired(key, now());
    346        return super.containsKey(key);
    347    }
    348
    349    /**
    350     * All expired entries are removed from the map prior to determining the
    351     * contains result.
    352     * {@inheritDoc}
    353     */
    354    @Override
    355    public boolean containsValue(final Object value) {
    356        removeAllExpired(now());
    357        return super.containsValue(value);
    358    }
    359
    360    /**
    361     * All expired entries are removed from the map prior to returning the entry set.
    362     * {@inheritDoc}
    363     */
    364    @Override
    365    public Set<Entry<K, V>> entrySet() {
    366        removeAllExpired(now());
    367        return super.entrySet();
    368    }
    369
    370    /**
    371     * All expired entries are removed from the map prior to returning the entry value.
    372     * {@inheritDoc}
    373     */
    374    @Override
    375    public V get(final Object key) {
    376        removeIfExpired(key, now());
    377        return super.get(key);
    378    }
    379
    380    /**
    381     * All expired entries are removed from the map prior to determining if it is empty.
    382     * {@inheritDoc}
    383     */
    384    @Override
    385    public boolean isEmpty() {
    386        removeAllExpired(now());
    387        return super.isEmpty();
    388    }
    389
    390    /**
    391     * Determines if the given expiration time is less than <code>now</code>.
    392     *
    393     * @param now the time in milliseconds used to compare against the
    394     *        expiration time.
    395     * @param expirationTimeObject the expiration time value retrieved from
    396     *        {@link #expirationMap}, can be null.
    397     * @return <code>true</code> if <code>expirationTimeObject</code> is &ge; 0
    398     *         and <code>expirationTimeObject</code> &lt; <code>now</code>.
    399     *         <code>false</code> otherwise.
    400     */
    401    private boolean isExpired(final long now, final Long expirationTimeObject) {
    402        if (expirationTimeObject != null) {
    403            final long expirationTime = expirationTimeObject.longValue();
    404            return expirationTime >= 0 && now >= expirationTime;
    405        }
    406        return false;
    407    }
    408
    409    /**
    410     * All expired entries are removed from the map prior to returning the key set.
    411     * {@inheritDoc}
    412     */
    413    @Override
    414    public Set<K> keySet() {
    415        removeAllExpired(now());
    416        return super.keySet();
    417    }
    418
    419    /**
    420     * The current time in milliseconds.
    421     */
    422    private long now() {
    423        return System.currentTimeMillis();
    424    }
    425
    426    /**
    427    * Add the given key-value pair to this map as well as recording the entry's expiration time based on
    428    * the current time in milliseconds and this map's {@link #expiringPolicy}.
    429    * <p>
    430    * {@inheritDoc}
    431    */
    432    @Override
    433    public V put(final K key, final V value) {
    434        // remove the previous record
    435        removeIfExpired(key, now());
    436
    437        // record expiration time of new entry
    438        final long expirationTime = expiringPolicy.expirationTime(key, value);
    439        expirationMap.put(key, Long.valueOf(expirationTime));
    440
    441        return super.put(key, value);
    442    }
    443
    444    @Override
    445    public void putAll(final Map<? extends K, ? extends V> mapToCopy) {
    446        for (final Map.Entry<? extends K, ? extends V> entry : mapToCopy.entrySet()) {
    447            put(entry.getKey(), entry.getValue());
    448        }
    449    }
    450
    451    /**
    452     * Normal {@link Map#remove(Object)} behavior with the addition of removing
    453     * any expiration entry as well.
    454     * {@inheritDoc}
    455     */
    456    @Override
    457    public V remove(final Object key) {
    458        expirationMap.remove(key);
    459        return super.remove(key);
    460    }
    461
    462    /**
    463     * Removes all entries in the map whose expiration time is less than
    464     * <code>now</code>. The exceptions are entries with negative expiration
    465     * times; those entries are never removed.
    466     *
    467     * @see #isExpired(long, Long)
    468     */
    469    private void removeAllExpired(final long now) {
    470        final Iterator<Map.Entry<Object, Long>> iter = expirationMap.entrySet().iterator();
    471        while (iter.hasNext()) {
    472            final Map.Entry<Object, Long> expirationEntry = iter.next();
    473            if (isExpired(now, expirationEntry.getValue())) {
    474                // remove entry from collection
    475                super.remove(expirationEntry.getKey());
    476                // remove entry from expiration map
    477                iter.remove();
    478            }
    479        }
    480    }
    481
    482    /**
    483     * Removes the entry with the given key if the entry's expiration time is
    484     * less than <code>now</code>. If the entry has a negative expiration time,
    485     * the entry is never removed.
    486     */
    487    private void removeIfExpired(final Object key, final long now) {
    488        final Long expirationTimeObject = expirationMap.get(key);
    489        if (isExpired(now, expirationTimeObject)) {
    490            remove(key);
    491        }
    492    }
    493
    494    /**
    495     * All expired entries are removed from the map prior to returning the size.
    496     * {@inheritDoc}
    497     */
    498    @Override
    499    public int size() {
    500        removeAllExpired(now());
    501        return super.size();
    502    }
    503
    504    /**
    505     * Read the map in using a custom routine.
    506     *
    507     * @param in the input stream
    508     * @throws IOException if an error occurs while reading from the stream
    509     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    510     */
    511    @SuppressWarnings("unchecked")
    512    // (1) should only fail if input stream is incorrect
    513    private void readObject(final ObjectInputStream in)
    514        throws IOException, ClassNotFoundException {
    515        in.defaultReadObject();
    516        map = (Map<K, V>) in.readObject(); // (1)
    517    }
    518
    519    /**
    520     * Write the map out using a custom routine.
    521     *
    522     * @param out the output stream
    523     * @throws IOException if an error occurs while writing to the stream
    524     */
    525    private void writeObject(final ObjectOutputStream out)
    526        throws IOException {
    527        out.defaultWriteObject();
    528        out.writeObject(map);
    529    }
    530
    531    /**
    532     * All expired entries are removed from the map prior to returning the value collection.
    533     * {@inheritDoc}
    534     */
    535    @Override
    536    public Collection<V> values() {
    537        removeAllExpired(now());
    538        return super.values();
    539    }
    540}