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