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}