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