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