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 887892 2013-11-24 13:43:45Z 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 887892 2013-11-24 13:43:45Z 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 IllegalArgumentException 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 887892 2013-11-24 13:43:45Z 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. If the parameters are invalid, an
185     * {@link IllegalArgumentException} is thrown.
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 IllegalArgumentException 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 IllegalArgumentException("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     */
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 IllegalArgumentException if the map 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 IllegalArgumentException("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 IllegalArgumentException 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 IllegalArgumentException 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 IllegalArgumentException if the time unit is null.
312     * @throws IllegalArgumentException if the map 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 IllegalArgumentException 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    @Override
429    public V put(final K key, final V value) {
430        return put(key, value, now());
431    }
432
433    /**
434     * Add the given key-value pair to this map as well as recording the entry's expiration time based on
435     * the current time in milliseconds, <code>now</code> and this map's {@link #expiringPolicy}.
436     */
437    private V put(final K key, final V value, final long now) {
438        // record expiration time of new entry
439        final long expirationTime = expiringPolicy.expirationTime(key, value);
440        expirationMap.put(key, Long.valueOf(expirationTime));
441
442        return super.put(key, value);
443    }
444
445    @Override
446    public void putAll(final Map<? extends K, ? extends V> mapToCopy) {
447        for (final Map.Entry<? extends K, ? extends V> entry : mapToCopy.entrySet()) {
448            put(entry.getKey(), entry.getValue());
449        }
450    }
451
452    /**
453     * Normal {@link Map#remove(Object)} behavior with the addition of removing
454     * any expiration entry as well.
455     * {@inheritDoc}
456     */
457    @Override
458    public V remove(final Object key) {
459        expirationMap.remove(key);
460        return super.remove(key);
461    }
462
463    /**
464     * Removes all entries in the map whose expiration time is less than
465     * <code>now</code>. The exceptions are entries with negative expiration
466     * times; those entries are never removed.
467     *
468     * @see #isExpired(long, Long)
469     */
470    private void removeAllExpired(final long now) {
471        final Iterator<Map.Entry<Object, Long>> iter = expirationMap.entrySet().iterator();
472        while (iter.hasNext()) {
473            final Map.Entry<Object, Long> expirationEntry = iter.next();
474            if (isExpired(now, expirationEntry.getValue())) {
475                // remove entry from collection
476                super.remove(expirationEntry.getKey());
477                // remove entry from expiration map
478                iter.remove();
479            }
480        }
481    }
482
483    /**
484     * Removes the entry with the given key if the entry's expiration time is
485     * less than <code>now</code>. If the entry has a negative expiration time,
486     * the entry is never removed.
487     */
488    private void removeIfExpired(final Object key, final long now) {
489        final Long expirationTimeObject = expirationMap.get(key);
490        if (isExpired(now, expirationTimeObject)) {
491            remove(key);
492        }
493    }
494
495    /**
496     * All expired entries are removed from the map prior to returning the size.
497     * {@inheritDoc}
498     */
499    @Override
500    public int size() {
501        removeAllExpired(now());
502        return super.size();
503    }
504
505    /**
506     * Read the map in using a custom routine.
507     *
508     * @param in the input stream
509     * @throws IOException
510     * @throws ClassNotFoundException
511     */
512    @SuppressWarnings("unchecked")
513    // (1) should only fail if input stream is incorrect
514    private void readObject(final ObjectInputStream in)
515        throws IOException, ClassNotFoundException {
516        in.defaultReadObject();
517        map = (Map<K, V>) in.readObject(); // (1)
518    }
519
520    /**
521     * Write the map out using a custom routine.
522     *
523     * @param out the output stream
524     * @throws IOException
525     */
526    private void writeObject(final ObjectOutputStream out)
527        throws IOException {
528        out.defaultWriteObject();
529        out.writeObject(map);
530    }
531
532    /**
533     * All expired entries are removed from the map prior to returning the value collection.
534     * {@inheritDoc}
535     */
536    @Override
537    public Collection<V> values() {
538        removeAllExpired(now());
539        return super.values();
540    }
541}