    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    public interface ExpirationPolicy<K, V>
    163        extends Serializable {
    164
    165        /**
    166         * Determine the expiration time for the given key-value entry.
    167         *
    168         * @param key the key for the entry.
    169         * @param value the value for the entry.
    170         * @return the expiration time value measured in milliseconds. A
    171         *         negative return value indicates the entry never expires.
    172         */
    173        long expirationTime(K key, V value);
    174    }
    175
    176    /** Serialization version */
    177    private static final long serialVersionUID = 1L;
    178
    179    /**
    180     * First validate the input parameters. If the parameters are valid, convert
    181     * the given time measured in the given units to the same time measured in
    182     * milliseconds.
    183     *
    184     * @param timeToLive the constant amount of time an entry is available
    185     *        before it expires. A negative value results in entries that NEVER
    186     *        expire. A zero value results in entries that ALWAYS expire.
    187     * @param timeUnit the unit of time for the <code>timeToLive</code>
    188     *        parameter, must not be null.
    189     * @throws NullPointerException if the time unit is null.
    190     */
    191    private static long validateAndConvertToMillis(final long timeToLive,
    192                                                   final TimeUnit timeUnit) {
    193        if (timeUnit == null) {
    194            throw new NullPointerException("Time unit must not be null");
    195        }
    196        return TimeUnit.MILLISECONDS.convert(timeToLive, timeUnit);
    197    }
    198
    199    /** map used to manage expiration times for the actual map entries. */
    200    private final Map<Object, Long> expirationMap = new HashMap<>();
    201
    202    /** the policy used to determine time-to-live values for map entries. */
    203    private final ExpirationPolicy<K, V> expiringPolicy;
    204
    205    /**
    206     * Default constructor. Constructs a map decorator that results in entries
    207     * NEVER expiring.
    208     */
    209    public PassiveExpiringMap() {
    210        this(-1L);
    211    }
    212
    213    /**
    214     * Construct a map decorator using the given expiration policy to determine
    215     * expiration times.
    216     *
    217     * @param expiringPolicy the policy used to determine expiration times of
    218     *        entries as they are added.
    219     * @throws NullPointerException if expiringPolicy is null
    220     */
    221    public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy) {
    222        this(expiringPolicy, new HashMap<K, V>());
    223    }
    224
    225    /**
    226     * Construct a map decorator that decorates the given map and uses the given
    227     * expiration policy to determine expiration times. If there are any
    228     * elements already in the map being decorated, they will NEVER expire
    229     * unless they are replaced.
    230     *
    231     * @param expiringPolicy the policy used to determine expiration times of
    232     *        entries as they are added.
    233     * @param map the map to decorate, must not be null.
    234     * @throws NullPointerException if the map or expiringPolicy is null.
    235     */
    236    public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy,
    237                              final Map<K, V> map) {
    238        super(map);
    239        if (expiringPolicy == null) {
    240            throw new NullPointerException("Policy must not be null.");
    241        }
    242        this.expiringPolicy = expiringPolicy;
    243    }
    244
    245    /**
    246     * Construct a map decorator that decorates the given map using the given
    247     * time-to-live value measured in milliseconds to create and use a
    248     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy.
    249     *
    250     * @param timeToLiveMillis the constant amount of time (in milliseconds) an
    251     *        entry is available before it expires. A negative value results in
    252     *        entries that NEVER expire. A zero value results in entries that
    253     *        ALWAYS expire.
    254     */
    255    public PassiveExpiringMap(final long timeToLiveMillis) {
    256        this(new ConstantTimeToLiveExpirationPolicy<K, V>(timeToLiveMillis),
    257             new HashMap<K, V>());
    258    }
    259
    260    /**
    261     * Construct a map decorator using the given time-to-live value measured in
    262     * milliseconds to create and use a
    263     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. If there
    264     * are any elements already in the map being decorated, they will NEVER
    265     * expire unless they are replaced.
    266     *
    267     * @param timeToLiveMillis the constant amount of time (in milliseconds) an
    268     *        entry is available before it expires. A negative value results in
    269     *        entries that NEVER expire. A zero value results in entries that
    270     *        ALWAYS expire.
    271     * @param map the map to decorate, must not be null.
    272     * @throws NullPointerException if the map is null.
    273     */
    274    public PassiveExpiringMap(final long timeToLiveMillis, final Map<K, V> map) {
    275        this(new ConstantTimeToLiveExpirationPolicy<K, V>(timeToLiveMillis),
    276             map);
    277    }
    278
    279    /**
    280     * Construct a map decorator using the given time-to-live value measured in
    281     * the given time units of measure to create and use a
    282     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy.
    283     *
    284     * @param timeToLive the constant amount of time an entry is available
    285     *        before it expires. A negative value results in entries that NEVER
    286     *        expire. A zero value results in entries that ALWAYS expire.
    287     * @param timeUnit the unit of time for the <code>timeToLive</code>
    288     *        parameter, must not be null.
    289     * @throws NullPointerException if the time unit is null.
    290     */
    291    public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit) {
    292        this(validateAndConvertToMillis(timeToLive, timeUnit));
    293    }
    294
    295    /**
    296     * Construct a map decorator that decorates the given map using the given
    297     * time-to-live value measured in the given time units of measure to create
    298     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. This policy
    299     * is used to determine expiration times. If there are any elements already
    300     * in the map being decorated, they will NEVER expire unless they are
    301     * replaced.
    302     *
    303     * @param timeToLive the constant amount of time an entry is available
    304     *        before it expires. A negative value results in entries that NEVER
    305     *        expire. A zero value results in entries that ALWAYS expire.
    306     * @param timeUnit the unit of time for the <code>timeToLive</code>
    307     *        parameter, must not be null.
    308     * @param map the map to decorate, must not be null.
    309     * @throws NullPointerException if the map or time unit is null.
    310     */
    311    public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit, final Map<K, V> map) {
    312        this(validateAndConvertToMillis(timeToLive, timeUnit), map);
    313    }
    314
    315    /**
    316     * Constructs a map decorator that decorates the given map and results in
    317     * entries NEVER expiring. If there are any elements already in the map
    318     * being decorated, they also will NEVER expire.
    319     *
    320     * @param map the map to decorate, must not be null.
    321     * @throws NullPointerException if the map is null.
    322     */
    323    public PassiveExpiringMap(final Map<K, V> map) {
    324        this(-1L, map);
    325    }
    326
    327    /**
    328     * Normal {@link Map#clear()} behavior with the addition of clearing all
    329     * expiration entries as well.
    330     */
    331    @Override
    332    public void clear() {
    333        super.clear();
    334        expirationMap.clear();
    335    }
    336
    337    /**
    338     * All expired entries are removed from the map prior to determining the
    339     * contains result.
    340     * {@inheritDoc}
    341     */
    342    @Override
    343    public boolean containsKey(final Object key) {
    344        removeIfExpired(key, now());
    345        return super.containsKey(key);
    346    }
    347
    348    /**
    349     * All expired entries are removed from the map prior to determining the
    350     * contains result.
    351     * {@inheritDoc}
    352     */
    353    @Override
    354    public boolean containsValue(final Object value) {
    355        removeAllExpired(now());
    356        return super.containsValue(value);
    357    }
    358
    359    /**
    360     * All expired entries are removed from the map prior to returning the entry set.
    361     * {@inheritDoc}
    362     */
    363    @Override
    364    public Set<Entry<K, V>> entrySet() {
    365        removeAllExpired(now());
    366        return super.entrySet();
    367    }
    368
    369    /**
    370     * All expired entries are removed from the map prior to returning the entry value.
    371     * {@inheritDoc}
    372     */
    373    @Override
    374    public V get(final Object key) {
    375        removeIfExpired(key, now());
    376        return super.get(key);
    377    }
    378
    379    /**
    380     * All expired entries are removed from the map prior to determining if it is empty.
    381     * {@inheritDoc}
    382     */
    383    @Override
    384    public boolean isEmpty() {
    385        removeAllExpired(now());
    386        return super.isEmpty();
    387    }
    388
    389    /**
    390     * Determines if the given expiration time is less than <code>now</code>.
    391     *
    392     * @param now the time in milliseconds used to compare against the
    393     *        expiration time.
    394     * @param expirationTimeObject the expiration time value retrieved from
    395     *        {@link #expirationMap}, can be null.
    396     * @return <code>true</code> if <code>expirationTimeObject</code> is &ge; 0
    397     *         and <code>expirationTimeObject</code> &lt; <code>now</code>.
    398     *         <code>false</code> otherwise.
    399     */
    400    private boolean isExpired(final long now, final Long expirationTimeObject) {
    401        if (expirationTimeObject != null) {
    402            final long expirationTime = expirationTimeObject.longValue();
    403            return expirationTime >= 0 && now >= expirationTime;
    404        }
    405        return false;
    406    }
    407
    408    /**
    409     * All expired entries are removed from the map prior to returning the key set.
    410     * {@inheritDoc}
    411     */
    412    @Override
    413    public Set<K> keySet() {
    414        removeAllExpired(now());
    415        return super.keySet();
    416    }
    417
    418    /**
    419     * The current time in milliseconds.
    420     */
    421    private long now() {
    422        return System.currentTimeMillis();
    423    }
    424
    425    /**
    426    * Add the given key-value pair to this map as well as recording the entry's expiration time based on
    427    * the current time in milliseconds and this map's {@link #expiringPolicy}.
    428    * <p>
    429    * {@inheritDoc}
    430    */
    431    @Override
    432    public V put(final K key, final V value) {
    433        // record expiration time of new entry
    434        final long expirationTime = expiringPolicy.expirationTime(key, value);
    435        expirationMap.put(key, Long.valueOf(expirationTime));
    436
    437        return super.put(key, value);
    438    }
    439
    440    @Override
    441    public void putAll(final Map<? extends K, ? extends V> mapToCopy) {
    442        for (final Map.Entry<? extends K, ? extends V> entry : mapToCopy.entrySet()) {
    443            put(entry.getKey(), entry.getValue());
    444        }
    445    }
    446
    447    /**
    448     * Normal {@link Map#remove(Object)} behavior with the addition of removing
    449     * any expiration entry as well.
    450     * {@inheritDoc}
    451     */
    452    @Override
    453    public V remove(final Object key) {
    454        expirationMap.remove(key);
    455        return super.remove(key);
    456    }
    457
    458    /**
    459     * Removes all entries in the map whose expiration time is less than
    460     * <code>now</code>. The exceptions are entries with negative expiration
    461     * times; those entries are never removed.
    462     *
    463     * @see #isExpired(long, Long)
    464     */
    465    private void removeAllExpired(final long now) {
    466        final Iterator<Map.Entry<Object, Long>> iter = expirationMap.entrySet().iterator();
    467        while (iter.hasNext()) {
    468            final Map.Entry<Object, Long> expirationEntry = iter.next();
    469            if (isExpired(now, expirationEntry.getValue())) {
    470                // remove entry from collection
    471                super.remove(expirationEntry.getKey());
    472                // remove entry from expiration map
    473                iter.remove();
    474            }
    475        }
    476    }
    477
    478    /**
    479     * Removes the entry with the given key if the entry's expiration time is
    480     * less than <code>now</code>. If the entry has a negative expiration time,
    481     * the entry is never removed.
    482     */
    483    private void removeIfExpired(final Object key, final long now) {
    484        final Long expirationTimeObject = expirationMap.get(key);
    485        if (isExpired(now, expirationTimeObject)) {
    486            remove(key);
    487        }
    488    }
    489
    490    /**
    491     * All expired entries are removed from the map prior to returning the size.
    492     * {@inheritDoc}
    493     */
    494    @Override
    495    public int size() {
    496        removeAllExpired(now());
    497        return super.size();
    498    }
    499
    500    /**
    501     * Read the map in using a custom routine.
    502     *
    503     * @param in the input stream
    504     * @throws IOException if an error occurs while reading from the stream
    505     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    506     */
    507    @SuppressWarnings("unchecked")
    508    // (1) should only fail if input stream is incorrect
    509    private void readObject(final ObjectInputStream in)
    510        throws IOException, ClassNotFoundException {
    511        in.defaultReadObject();
    512        map = (Map<K, V>) in.readObject(); // (1)
    513    }
    514
    515    /**
    516     * Write the map out using a custom routine.
    517     *
    518     * @param out the output stream
    519     * @throws IOException if an error occurs while writing to the stream
    520     */
    521    private void writeObject(final ObjectOutputStream out)
    522        throws IOException {
    523        out.defaultWriteObject();
    524        out.writeObject(map);
    525    }
    526
    527    /**
    528     * All expired entries are removed from the map prior to returning the value collection.
    529     * {@inheritDoc}
    530     */
    531    @Override
    532    public Collection<V> values() {
    533        removeAllExpired(now());
    534        return super.values();
    535    }
    536}