PassiveExpiringMap.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.map;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.concurrent.TimeUnit;

/**
 * Decorates a {@code Map} to evict expired entries once their expiration
 * time has been reached.
 * <p>
 * When putting a key-value pair in the map this decorator uses a
 * {@link ExpirationPolicy} to determine how long the entry should remain alive
 * as defined by an expiration time value.
 * </p>
 * <p>
 * When accessing the mapped value for a key, its expiration time is checked,
 * and if it is a negative value or if it is greater than the current time, the
 * mapped value is returned. Otherwise, the key is removed from the decorated
 * map, and {@code null} is returned.
 * </p>
 * <p>
 * When invoking methods that involve accessing the entire map contents (i.e
 * {@link #containsValue(Object)}, {@link #entrySet()}, etc.) this decorator
 * removes all expired entries prior to actually completing the invocation.
 * </p>
 * <p>
 * <strong>Note that {@link PassiveExpiringMap} is not synchronized and is not
 * thread-safe.</strong> If you wish to use this map from multiple threads
 * concurrently, you must use appropriate synchronization. The simplest approach
 * is to wrap this map using {@link java.util.Collections#synchronizedMap(Map)}.
 * This class may throw exceptions when accessed by concurrent threads without
 * synchronization.
 * </p>
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 4.0
 */
public class PassiveExpiringMap<K, V>
    extends AbstractMapDecorator<K, V>
    implements Serializable {

    /**
     * A {@link org.apache.commons.collections4.map.PassiveExpiringMap.ExpirationPolicy ExpirationPolicy}
     * that returns an expiration time that is a
     * constant about of time in the future from the current time.
     *
     * @param <K> the type of the keys in the map
     * @param <V> the type of the values in the map
     * @since 4.0
     */
    public static class ConstantTimeToLiveExpirationPolicy<K, V>
        implements ExpirationPolicy<K, V> {

        /** Serialization version */
        private static final long serialVersionUID = 1L;

        /** The constant time-to-live value measured in milliseconds. */
        private final long timeToLiveMillis;

        /**
         * Default constructor. Constructs a policy using a negative
         * time-to-live value that results in entries never expiring.
         */
        public ConstantTimeToLiveExpirationPolicy() {
            this(-1L);
        }

        /**
         * Constructs a policy with the given time-to-live constant measured in
         * milliseconds. A negative time-to-live value indicates entries never
         * expire. A zero time-to-live value indicates entries expire (nearly)
         * immediately.
         *
         * @param timeToLiveMillis the constant amount of time (in milliseconds)
         *        an entry is available before it expires. A negative value
         *        results in entries that NEVER expire. A zero value results in
         *        entries that ALWAYS expire.
         */
        public ConstantTimeToLiveExpirationPolicy(final long timeToLiveMillis) {
            this.timeToLiveMillis = timeToLiveMillis;
        }

        /**
         * Constructs a policy with the given time-to-live constant measured in
         * the given time unit of measure.
         *
         * @param timeToLive the constant amount of time an entry is available
         *        before it expires. A negative value results in entries that
         *        NEVER expire. A zero value results in entries that ALWAYS
         *        expire.
         * @param timeUnit the unit of time for the {@code timeToLive}
         *        parameter, must not be null.
         * @throws NullPointerException if the time unit is null.
         */
        public ConstantTimeToLiveExpirationPolicy(final long timeToLive,
                                                  final TimeUnit timeUnit) {
            this(validateAndConvertToMillis(timeToLive, timeUnit));
        }

        /**
         * Determine the expiration time for the given key-value entry.
         *
         * @param key the key for the entry (ignored).
         * @param value the value for the entry (ignored).
         * @return if {@link #timeToLiveMillis} &ge; 0, an expiration time of
         *         {@link #timeToLiveMillis} +
         *         {@link System#currentTimeMillis()} is returned. Otherwise, -1
         *         is returned indicating the entry never expires.
         */
        @Override
        public long expirationTime(final K key, final V value) {
            if (timeToLiveMillis >= 0L) {
                // avoid numerical overflow
                final long nowMillis = System.currentTimeMillis();
                if (nowMillis > Long.MAX_VALUE - timeToLiveMillis) {
                    // expiration would be greater than Long.MAX_VALUE
                    // never expire
                    return -1;
                }

                // timeToLiveMillis in the future
                return nowMillis + timeToLiveMillis;
            }

            // never expire
            return -1L;
        }
    }

    /**
     * A policy to determine the expiration time for key-value entries.
     *
     * @param <K> the key object type.
     * @param <V> the value object type
     * @since 4.0
     */
    @FunctionalInterface
    public interface ExpirationPolicy<K, V>
        extends Serializable {

        /**
         * Determine the expiration time for the given key-value entry.
         *
         * @param key the key for the entry.
         * @param value the value for the entry.
         * @return the expiration time value measured in milliseconds. A
         *         negative return value indicates the entry never expires.
         */
        long expirationTime(K key, V value);
    }

    /** Serialization version */
    private static final long serialVersionUID = 1L;

    /**
     * First validate the input parameters. If the parameters are valid, convert
     * the given time measured in the given units to the same time measured in
     * milliseconds.
     *
     * @param timeToLive the constant amount of time an entry is available
     *        before it expires. A negative value results in entries that NEVER
     *        expire. A zero value results in entries that ALWAYS expire.
     * @param timeUnit the unit of time for the {@code timeToLive}
     *        parameter, must not be null.
     * @throws NullPointerException if the time unit is null.
     */
    private static long validateAndConvertToMillis(final long timeToLive,
                                                   final TimeUnit timeUnit) {
        Objects.requireNonNull(timeUnit, "timeUnit");
        return TimeUnit.MILLISECONDS.convert(timeToLive, timeUnit);
    }

    /** Map used to manage expiration times for the actual map entries. */
    private final Map<Object, Long> expirationMap = new HashMap<>();

    /** The policy used to determine time-to-live values for map entries. */
    private final ExpirationPolicy<K, V> expiringPolicy;

    /**
     * Default constructor. Constructs a map decorator that results in entries
     * NEVER expiring.
     */
    public PassiveExpiringMap() {
        this(-1L);
    }

    /**
     * Constructs a map decorator using the given expiration policy to determine
     * expiration times.
     *
     * @param expiringPolicy the policy used to determine expiration times of
     *        entries as they are added.
     * @throws NullPointerException if expiringPolicy is null
     */
    public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy) {
        this(expiringPolicy, new HashMap<>());
    }

    /**
     * Constructs a map decorator that decorates the given map and uses the given
     * expiration policy to determine expiration times. If there are any
     * elements already in the map being decorated, they will NEVER expire
     * unless they are replaced.
     *
     * @param expiringPolicy the policy used to determine expiration times of
     *        entries as they are added.
     * @param map the map to decorate, must not be null.
     * @throws NullPointerException if the map or expiringPolicy is null.
     */
    public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy,
                              final Map<K, V> map) {
        super(map);
        this.expiringPolicy = Objects.requireNonNull(expiringPolicy, "expiringPolicy");
    }

    /**
     * Constructs a map decorator that decorates the given map using the given
     * time-to-live value measured in milliseconds to create and use a
     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy.
     *
     * @param timeToLiveMillis the constant amount of time (in milliseconds) an
     *        entry is available before it expires. A negative value results in
     *        entries that NEVER expire. A zero value results in entries that
     *        ALWAYS expire.
     */
    public PassiveExpiringMap(final long timeToLiveMillis) {
        this(new ConstantTimeToLiveExpirationPolicy<>(timeToLiveMillis),
                new HashMap<>());
    }

    /**
     * Constructs a map decorator using the given time-to-live value measured in
     * milliseconds to create and use a
     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. If there
     * are any elements already in the map being decorated, they will NEVER
     * expire unless they are replaced.
     *
     * @param timeToLiveMillis the constant amount of time (in milliseconds) an
     *        entry is available before it expires. A negative value results in
     *        entries that NEVER expire. A zero value results in entries that
     *        ALWAYS expire.
     * @param map the map to decorate, must not be null.
     * @throws NullPointerException if the map is null.
     */
    public PassiveExpiringMap(final long timeToLiveMillis, final Map<K, V> map) {
        this(new ConstantTimeToLiveExpirationPolicy<>(timeToLiveMillis),
             map);
    }

    /**
     * Constructs a map decorator using the given time-to-live value measured in
     * the given time units of measure to create and use a
     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy.
     *
     * @param timeToLive the constant amount of time an entry is available
     *        before it expires. A negative value results in entries that NEVER
     *        expire. A zero value results in entries that ALWAYS expire.
     * @param timeUnit the unit of time for the {@code timeToLive}
     *        parameter, must not be null.
     * @throws NullPointerException if the time unit is null.
     */
    public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit) {
        this(validateAndConvertToMillis(timeToLive, timeUnit));
    }

    /**
     * Constructs a map decorator that decorates the given map using the given
     * time-to-live value measured in the given time units of measure to create
     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. This policy
     * is used to determine expiration times. If there are any elements already
     * in the map being decorated, they will NEVER expire unless they are
     * replaced.
     *
     * @param timeToLive the constant amount of time an entry is available
     *        before it expires. A negative value results in entries that NEVER
     *        expire. A zero value results in entries that ALWAYS expire.
     * @param timeUnit the unit of time for the {@code timeToLive}
     *        parameter, must not be null.
     * @param map the map to decorate, must not be null.
     * @throws NullPointerException if the map or time unit is null.
     */
    public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit, final Map<K, V> map) {
        this(validateAndConvertToMillis(timeToLive, timeUnit), map);
    }

    /**
     * Constructs a map decorator that decorates the given map and results in
     * entries NEVER expiring. If there are any elements already in the map
     * being decorated, they also will NEVER expire.
     *
     * @param map the map to decorate, must not be null.
     * @throws NullPointerException if the map is null.
     */
    public PassiveExpiringMap(final Map<K, V> map) {
        this(-1L, map);
    }

    /**
     * Normal {@link Map#clear()} behavior with the addition of clearing all
     * expiration entries as well.
     */
    @Override
    public void clear() {
        super.clear();
        expirationMap.clear();
    }

    /**
     * All expired entries are removed from the map prior to determining the
     * contains result.
     * {@inheritDoc}
     */
    @Override
    public boolean containsKey(final Object key) {
        removeIfExpired(key, now());
        return super.containsKey(key);
    }

    /**
     * All expired entries are removed from the map prior to determining the
     * contains result.
     * {@inheritDoc}
     */
    @Override
    public boolean containsValue(final Object value) {
        removeAllExpired(now());
        return super.containsValue(value);
    }

    /**
     * All expired entries are removed from the map prior to returning the entry set.
     * {@inheritDoc}
     */
    @Override
    public Set<Entry<K, V>> entrySet() {
        removeAllExpired(now());
        return super.entrySet();
    }

    /**
     * All expired entries are removed from the map prior to returning the entry value.
     * {@inheritDoc}
     */
    @Override
    public V get(final Object key) {
        removeIfExpired(key, now());
        return super.get(key);
    }

    /**
     * All expired entries are removed from the map prior to determining if it is empty.
     * {@inheritDoc}
     */
    @Override
    public boolean isEmpty() {
        removeAllExpired(now());
        return super.isEmpty();
    }

    /**
     * Determines if the given expiration time is less than {@code now}.
     *
     * @param now the time in milliseconds used to compare against the
     *        expiration time.
     * @param expirationTimeObject the expiration time value retrieved from
     *        {@link #expirationMap}, can be null.
     * @return {@code true} if {@code expirationTimeObject} is &ge; 0
     *         and {@code expirationTimeObject} &lt; {@code now}.
     *         {@code false} otherwise.
     */
    private boolean isExpired(final long now, final Long expirationTimeObject) {
        if (expirationTimeObject != null) {
            final long expirationTime = expirationTimeObject.longValue();
            return expirationTime >= 0 && now >= expirationTime;
        }
        return false;
    }

    /**
     * All expired entries are removed from the map prior to returning the key set.
     * {@inheritDoc}
     */
    @Override
    public Set<K> keySet() {
        removeAllExpired(now());
        return super.keySet();
    }

    /**
     * The current time in milliseconds.
     */
    private long now() {
        return System.currentTimeMillis();
    }

    /**
     * {@inheritDoc}
     * <p>
     * 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
     * {@link #expiringPolicy}.
     * </p>
     */
    @Override
    public V put(final K key, final V value) {
        // remove the previous record
        removeIfExpired(key, now());

        // record expiration time of new entry
        final long expirationTime = expiringPolicy.expirationTime(key, value);
        expirationMap.put(key, Long.valueOf(expirationTime));

        return super.put(key, value);
    }

    @Override
    public void putAll(final Map<? extends K, ? extends V> mapToCopy) {
        for (final Map.Entry<? extends K, ? extends V> entry : mapToCopy.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    /**
     * Deserializes the map in using a custom routine.
     *
     * @param in the input stream
     * @throws IOException if an error occurs while reading from the stream
     * @throws ClassNotFoundException if an object read from the stream cannot be loaded
     */
    @SuppressWarnings("unchecked")
    // (1) should only fail if input stream is incorrect
    private void readObject(final ObjectInputStream in)
        throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        map = (Map<K, V>) in.readObject(); // (1)
    }

    /**
     * Normal {@link Map#remove(Object)} behavior with the addition of removing
     * any expiration entry as well.
     * {@inheritDoc}
     */
    @Override
    public V remove(final Object key) {
        expirationMap.remove(key);
        return super.remove(key);
    }

    /**
     * Removes all entries in the map whose expiration time is less than
     * {@code now}. The exceptions are entries with negative expiration
     * times; those entries are never removed.
     *
     * @see #isExpired(long, Long)
     */
    private void removeAllExpired(final long nowMillis) {
        final Iterator<Map.Entry<Object, Long>> iter = expirationMap.entrySet().iterator();
        while (iter.hasNext()) {
            final Map.Entry<Object, Long> expirationEntry = iter.next();
            if (isExpired(nowMillis, expirationEntry.getValue())) {
                // remove entry from collection
                super.remove(expirationEntry.getKey());
                // remove entry from expiration map
                iter.remove();
            }
        }
    }

    /**
     * Removes the entry with the given key if the entry's expiration time is
     * less than {@code now}. If the entry has a negative expiration time,
     * the entry is never removed.
     */
    private void removeIfExpired(final Object key, final long nowMillis) {
        final Long expirationTimeObject = expirationMap.get(key);
        if (isExpired(nowMillis, expirationTimeObject)) {
            remove(key);
        }
    }

    /**
     * All expired entries are removed from the map prior to returning the size.
     * {@inheritDoc}
     */
    @Override
    public int size() {
        removeAllExpired(now());
        return super.size();
    }

    /**
     * All expired entries are removed from the map prior to returning the value collection.
     * {@inheritDoc}
     */
    @Override
    public Collection<V> values() {
        removeAllExpired(now());
        return super.values();
    }

    /**
     * Serializes this object to an ObjectOutputStream.
     *
     * @param out the target ObjectOutputStream.
     * @throws IOException thrown when an I/O errors occur writing to the target stream.
     */
    private void writeObject(final ObjectOutputStream out)
        throws IOException {
        out.defaultWriteObject();
        out.writeObject(map);
    }
}