1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.collections4.map; 18 19 import java.io.IOException; 20 import java.io.ObjectInputStream; 21 import java.io.ObjectOutputStream; 22 import java.io.Serializable; 23 import java.util.Collection; 24 import java.util.HashMap; 25 import java.util.Iterator; 26 import java.util.Map; 27 import java.util.Objects; 28 import java.util.Set; 29 import java.util.concurrent.TimeUnit; 30 31 /** 32 * Decorates a {@code Map} to evict expired entries once their expiration 33 * time has been reached. 34 * <p> 35 * When putting a key-value pair in the map this decorator uses a 36 * {@link ExpirationPolicy} to determine how long the entry should remain alive 37 * as defined by an expiration time value. 38 * </p> 39 * <p> 40 * When accessing the mapped value for a key, its expiration time is checked, 41 * and if it is a negative value or if it is greater than the current time, the 42 * mapped value is returned. Otherwise, the key is removed from the decorated 43 * map, and {@code null} is returned. 44 * </p> 45 * <p> 46 * When invoking methods that involve accessing the entire map contents (i.e 47 * {@link #containsValue(Object)}, {@link #entrySet()}, etc.) this decorator 48 * removes all expired entries prior to actually completing the invocation. 49 * </p> 50 * <p> 51 * <strong>Note that {@link PassiveExpiringMap} is not synchronized and is not 52 * thread-safe.</strong> If you wish to use this map from multiple threads 53 * concurrently, you must use appropriate synchronization. The simplest approach 54 * is to wrap this map using {@link java.util.Collections#synchronizedMap(Map)}. 55 * This class may throw exceptions when accessed by concurrent threads without 56 * synchronization. 57 * </p> 58 * 59 * @param <K> the type of the keys in this map 60 * @param <V> the type of the values in this map 61 * @since 4.0 62 */ 63 public class PassiveExpiringMap<K, V> 64 extends AbstractMapDecorator<K, V> 65 implements Serializable { 66 67 /** 68 * A {@link org.apache.commons.collections4.map.PassiveExpiringMap.ExpirationPolicy ExpirationPolicy} 69 * that returns an expiration time that is a 70 * constant about of time in the future from the current time. 71 * 72 * @param <K> the type of the keys in the map 73 * @param <V> the type of the values in the map 74 * @since 4.0 75 */ 76 public static class ConstantTimeToLiveExpirationPolicy<K, V> 77 implements ExpirationPolicy<K, V> { 78 79 /** Serialization version */ 80 private static final long serialVersionUID = 1L; 81 82 /** The constant time-to-live value measured in milliseconds. */ 83 private final long timeToLiveMillis; 84 85 /** 86 * Default constructor. Constructs a policy using a negative 87 * time-to-live value that results in entries never expiring. 88 */ 89 public ConstantTimeToLiveExpirationPolicy() { 90 this(-1L); 91 } 92 93 /** 94 * Constructs a policy with the given time-to-live constant measured in 95 * milliseconds. A negative time-to-live value indicates entries never 96 * expire. A zero time-to-live value indicates entries expire (nearly) 97 * immediately. 98 * 99 * @param timeToLiveMillis the constant amount of time (in milliseconds) 100 * an entry is available before it expires. A negative value 101 * results in entries that NEVER expire. A zero value results in 102 * entries that ALWAYS expire. 103 */ 104 public ConstantTimeToLiveExpirationPolicy(final long timeToLiveMillis) { 105 this.timeToLiveMillis = timeToLiveMillis; 106 } 107 108 /** 109 * Constructs 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} 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} ≥ 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 nowMillis = System.currentTimeMillis(); 140 if (nowMillis > 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 nowMillis + 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} 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 Objects.requireNonNull(timeUnit, "timeUnit"); 195 return TimeUnit.MILLISECONDS.convert(timeToLive, timeUnit); 196 } 197 198 /** Map used to manage expiration times for the actual map entries. */ 199 private final Map<Object, Long> expirationMap = new HashMap<>(); 200 201 /** The policy used to determine time-to-live values for map entries. */ 202 private final ExpirationPolicy<K, V> expiringPolicy; 203 204 /** 205 * Default constructor. Constructs a map decorator that results in entries 206 * NEVER expiring. 207 */ 208 public PassiveExpiringMap() { 209 this(-1L); 210 } 211 212 /** 213 * Constructs a map decorator using the given expiration policy to determine 214 * expiration times. 215 * 216 * @param expiringPolicy the policy used to determine expiration times of 217 * entries as they are added. 218 * @throws NullPointerException if expiringPolicy is null 219 */ 220 public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy) { 221 this(expiringPolicy, new HashMap<>()); 222 } 223 224 /** 225 * Constructs a map decorator that decorates the given map and uses the given 226 * expiration policy to determine expiration times. If there are any 227 * elements already in the map being decorated, they will NEVER expire 228 * unless they are replaced. 229 * 230 * @param expiringPolicy the policy used to determine expiration times of 231 * entries as they are added. 232 * @param map the map to decorate, must not be null. 233 * @throws NullPointerException if the map or expiringPolicy is null. 234 */ 235 public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy, 236 final Map<K, V> map) { 237 super(map); 238 this.expiringPolicy = Objects.requireNonNull(expiringPolicy, "expiringPolicy"); 239 } 240 241 /** 242 * Constructs a map decorator that decorates the given map using the given 243 * time-to-live value measured in milliseconds to create and use a 244 * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. 245 * 246 * @param timeToLiveMillis the constant amount of time (in milliseconds) an 247 * entry is available before it expires. A negative value results in 248 * entries that NEVER expire. A zero value results in entries that 249 * ALWAYS expire. 250 */ 251 public PassiveExpiringMap(final long timeToLiveMillis) { 252 this(new ConstantTimeToLiveExpirationPolicy<>(timeToLiveMillis), 253 new HashMap<>()); 254 } 255 256 /** 257 * Constructs a map decorator using the given time-to-live value measured in 258 * milliseconds to create and use a 259 * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. If there 260 * are any elements already in the map being decorated, they will NEVER 261 * expire unless they are replaced. 262 * 263 * @param timeToLiveMillis the constant amount of time (in milliseconds) an 264 * entry is available before it expires. A negative value results in 265 * entries that NEVER expire. A zero value results in entries that 266 * ALWAYS expire. 267 * @param map the map to decorate, must not be null. 268 * @throws NullPointerException if the map is null. 269 */ 270 public PassiveExpiringMap(final long timeToLiveMillis, final Map<K, V> map) { 271 this(new ConstantTimeToLiveExpirationPolicy<>(timeToLiveMillis), 272 map); 273 } 274 275 /** 276 * Constructs a map decorator using the given time-to-live value measured in 277 * the given time units of measure to create and use a 278 * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. 279 * 280 * @param timeToLive the constant amount of time an entry is available 281 * before it expires. A negative value results in entries that NEVER 282 * expire. A zero value results in entries that ALWAYS expire. 283 * @param timeUnit the unit of time for the {@code timeToLive} 284 * parameter, must not be null. 285 * @throws NullPointerException if the time unit is null. 286 */ 287 public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit) { 288 this(validateAndConvertToMillis(timeToLive, timeUnit)); 289 } 290 291 /** 292 * Constructs a map decorator that decorates the given map using the given 293 * time-to-live value measured in the given time units of measure to create 294 * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. This policy 295 * is used to determine expiration times. If there are any elements already 296 * in the map being decorated, they will NEVER expire unless they are 297 * replaced. 298 * 299 * @param timeToLive the constant amount of time an entry is available 300 * before it expires. A negative value results in entries that NEVER 301 * expire. A zero value results in entries that ALWAYS expire. 302 * @param timeUnit the unit of time for the {@code timeToLive} 303 * parameter, must not be null. 304 * @param map the map to decorate, must not be null. 305 * @throws NullPointerException if the map or time unit is null. 306 */ 307 public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit, final Map<K, V> map) { 308 this(validateAndConvertToMillis(timeToLive, timeUnit), map); 309 } 310 311 /** 312 * Constructs a map decorator that decorates the given map and results in 313 * entries NEVER expiring. If there are any elements already in the map 314 * being decorated, they also will NEVER expire. 315 * 316 * @param map the map to decorate, must not be null. 317 * @throws NullPointerException if the map is null. 318 */ 319 public PassiveExpiringMap(final Map<K, V> map) { 320 this(-1L, map); 321 } 322 323 /** 324 * Normal {@link Map#clear()} behavior with the addition of clearing all 325 * expiration entries as well. 326 */ 327 @Override 328 public void clear() { 329 super.clear(); 330 expirationMap.clear(); 331 } 332 333 /** 334 * All expired entries are removed from the map prior to determining the 335 * contains result. 336 * {@inheritDoc} 337 */ 338 @Override 339 public boolean containsKey(final Object key) { 340 removeIfExpired(key, now()); 341 return super.containsKey(key); 342 } 343 344 /** 345 * All expired entries are removed from the map prior to determining the 346 * contains result. 347 * {@inheritDoc} 348 */ 349 @Override 350 public boolean containsValue(final Object value) { 351 removeAllExpired(now()); 352 return super.containsValue(value); 353 } 354 355 /** 356 * All expired entries are removed from the map prior to returning the entry set. 357 * {@inheritDoc} 358 */ 359 @Override 360 public Set<Entry<K, V>> entrySet() { 361 removeAllExpired(now()); 362 return super.entrySet(); 363 } 364 365 /** 366 * All expired entries are removed from the map prior to returning the entry value. 367 * {@inheritDoc} 368 */ 369 @Override 370 public V get(final Object key) { 371 removeIfExpired(key, now()); 372 return super.get(key); 373 } 374 375 /** 376 * All expired entries are removed from the map prior to determining if it is empty. 377 * {@inheritDoc} 378 */ 379 @Override 380 public boolean isEmpty() { 381 removeAllExpired(now()); 382 return super.isEmpty(); 383 } 384 385 /** 386 * Determines if the given expiration time is less than {@code now}. 387 * 388 * @param now the time in milliseconds used to compare against the 389 * expiration time. 390 * @param expirationTimeObject the expiration time value retrieved from 391 * {@link #expirationMap}, can be null. 392 * @return {@code true} if {@code expirationTimeObject} is ≥ 0 393 * and {@code expirationTimeObject} < {@code now}. 394 * {@code false} otherwise. 395 */ 396 private boolean isExpired(final long now, final Long expirationTimeObject) { 397 if (expirationTimeObject != null) { 398 final long expirationTime = expirationTimeObject.longValue(); 399 return expirationTime >= 0 && now >= expirationTime; 400 } 401 return false; 402 } 403 404 /** 405 * All expired entries are removed from the map prior to returning the key set. 406 * {@inheritDoc} 407 */ 408 @Override 409 public Set<K> keySet() { 410 removeAllExpired(now()); 411 return super.keySet(); 412 } 413 414 /** 415 * The current time in milliseconds. 416 */ 417 private long now() { 418 return System.currentTimeMillis(); 419 } 420 421 /** 422 * Add the given key-value pair to this map as well as recording the entry's expiration time based on 423 * the current time in milliseconds and this map's {@link #expiringPolicy}. 424 * <p> 425 * {@inheritDoc} 426 */ 427 @Override 428 public V put(final K key, final V value) { 429 // remove the previous record 430 removeIfExpired(key, now()); 431 432 // record expiration time of new entry 433 final long expirationTime = expiringPolicy.expirationTime(key, value); 434 expirationMap.put(key, Long.valueOf(expirationTime)); 435 436 return super.put(key, value); 437 } 438 439 @Override 440 public void putAll(final Map<? extends K, ? extends V> mapToCopy) { 441 for (final Map.Entry<? extends K, ? extends V> entry : mapToCopy.entrySet()) { 442 put(entry.getKey(), entry.getValue()); 443 } 444 } 445 446 /** 447 * Read the map in using a custom routine. 448 * 449 * @param in the input stream 450 * @throws IOException if an error occurs while reading from the stream 451 * @throws ClassNotFoundException if an object read from the stream can not be loaded 452 */ 453 @SuppressWarnings("unchecked") 454 // (1) should only fail if input stream is incorrect 455 private void readObject(final ObjectInputStream in) 456 throws IOException, ClassNotFoundException { 457 in.defaultReadObject(); 458 map = (Map<K, V>) in.readObject(); // (1) 459 } 460 461 /** 462 * Normal {@link Map#remove(Object)} behavior with the addition of removing 463 * any expiration entry as well. 464 * {@inheritDoc} 465 */ 466 @Override 467 public V remove(final Object key) { 468 expirationMap.remove(key); 469 return super.remove(key); 470 } 471 472 /** 473 * Removes all entries in the map whose expiration time is less than 474 * {@code now}. The exceptions are entries with negative expiration 475 * times; those entries are never removed. 476 * 477 * @see #isExpired(long, Long) 478 */ 479 private void removeAllExpired(final long nowMillis) { 480 final Iterator<Map.Entry<Object, Long>> iter = expirationMap.entrySet().iterator(); 481 while (iter.hasNext()) { 482 final Map.Entry<Object, Long> expirationEntry = iter.next(); 483 if (isExpired(nowMillis, expirationEntry.getValue())) { 484 // remove entry from collection 485 super.remove(expirationEntry.getKey()); 486 // remove entry from expiration map 487 iter.remove(); 488 } 489 } 490 } 491 492 /** 493 * Removes the entry with the given key if the entry's expiration time is 494 * less than {@code now}. If the entry has a negative expiration time, 495 * the entry is never removed. 496 */ 497 private void removeIfExpired(final Object key, final long nowMillis) { 498 final Long expirationTimeObject = expirationMap.get(key); 499 if (isExpired(nowMillis, expirationTimeObject)) { 500 remove(key); 501 } 502 } 503 504 /** 505 * All expired entries are removed from the map prior to returning the size. 506 * {@inheritDoc} 507 */ 508 @Override 509 public int size() { 510 removeAllExpired(now()); 511 return super.size(); 512 } 513 514 /** 515 * All expired entries are removed from the map prior to returning the value collection. 516 * {@inheritDoc} 517 */ 518 @Override 519 public Collection<V> values() { 520 removeAllExpired(now()); 521 return super.values(); 522 } 523 524 /** 525 * Write the map out using a custom routine. 526 * 527 * @param out the output stream 528 * @throws IOException if an error occurs while writing to the stream 529 */ 530 private void writeObject(final ObjectOutputStream out) 531 throws IOException { 532 out.defaultWriteObject(); 533 out.writeObject(map); 534 } 535 }