Class Cache<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
org.apache.sis.util.collection.Cache<K,V>
Type Parameters:
K - the type of key objects.
V - the type of value objects.
All Implemented Interfaces:
ConcurrentMap<K,V>, Map<K,V>
Direct Known Subclasses:
TileCache

public class Cache<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>
A concurrent map capable to locks entries for which the value is in process of being computed. This map is intended for use as a cache, with a goal of avoiding to compute the same values twice. This implementation is thread-safe and supports concurrency. Cache is based on ConcurrentHashMap with the addition of three main capabilities:
  • Lock an entry when its value is under computation in a thread.
  • Block other threads requesting the value of that particular entry until computation is completed.
  • Retain oldest values by soft or weak references instead of strong references.
The easiest way to use this class is to invoke computeIfAbsent(…) or getOrCreate(…) with lambda functions as below: Alternatively, one can handle explicitly the locks. This alternative sometimes provides more flexibility, for example in exception handling. The steps are as below:
  1. Check if the value is already available in the map. If it is, return it immediately and we are done.
  2. Otherwise, get a lock and check again if the value is already available in the map (because the value could have been computed by another thread between step 1 and the obtention of the lock). If it is, release the lock and we are done.
  3. Otherwise compute the value, store the result and release the lock.
Code example is shown below. Note that the call to putAndUnlock(…) must be inside the finally block of a try block beginning immediately after the call to lock(…), no matter what the result of the computation is (including null).

Eviction of eldest values

  • The cost of a value is the value returned by cost(V). The default implementation returns 1 in all cases, but subclasses can override this method for more elaborated cost computation.
  • The total cost is the sum of the cost of all values held by strong reference in this cache. The total cost does not include the cost of values held by weak or soft reference.
  • The cost limit is the maximal value allowed for the total cost. If the total cost exceed this value, then strong references to the eldest values are replaced by weak or soft references until the total cost become equals or lower than the cost limit.
The total cost is given at construction time. If the cost(V) method has not been overridden, then the total cost is the maximal amount of values to keep by strong references.

Circular dependencies

This implementation assumes that there are no circular dependencies (or cyclic graph) between the values in the cache. For example if creating A implies creating B, then creating B is not allowed to implies (directly or indirectly) the creation of A. If this condition is not met, deadlock may occur randomly.
Since:
0.3
Version:
1.3
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private static final class 
    Key-value pairs of new entries created during Cache.ReplaceAdapter execution, as a chained list.
    static interface 
    The handler returned by lock(K), to be used for unlocking and storing the result.
    private final class 
    A callback for map which forwards the calls to the remapping function provided by user.
    private final class 
    A simple handler implementation wrapping an existing value.
    private final class 
    A soft reference which removes itself from the cache when the reference is garbage-collected.
    private final class 
    Invoked from the a background thread after a weak or soft reference has been replaced by a strong one.
    private final class 
    A weak reference which removes itself from the cache when the reference is garbage-collected.
    (package private) final class 
    A handler implementation used for telling to other threads that the current thread is computing a value.

    Nested classes/interfaces inherited from class java.util.AbstractMap

    AbstractMap.SimpleEntry<K extends Object,V extends Object>, AbstractMap.SimpleImmutableEntry<K extends Object,V extends Object>

    Nested classes/interfaces inherited from interface java.util.Map

    Map.Entry<K extends Object,V extends Object>
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final long
    The maximal cost allowed.
    private final Map<K,Integer>
    The keys of values that are retained in the map by strong references, together with an estimation of their cost.
    private Set<Map.Entry<K,V>>
    A view over the entries in the cache.
    private boolean
    true if different values may be assigned to the same key.
    private final ConcurrentMap<K,Object>
    The map that contains the cached values.
    private final boolean
    If true, use SoftReference instead of WeakReference.
    private long
    The sum of all values in the costs map.
  • Constructor Summary

    Constructors
    Constructor
    Description
    Creates a new cache with a default initial capacity and cost limit of 100.
    Cache(int initialCapacity, long costLimit, boolean soft)
    Creates a new cache using the given initial capacity and cost limit.
  • Method Summary

    Modifier and Type
    Method
    Description
    private void
    adjustReferences(K key, V value)
    Invoked in a background thread after a value has been set in the map.
    void
    Clears the content of this cache.
    compute(K key, BiFunction<? super K,? super V,? extends V> remapping)
    Replaces the value mapped to the given key by a new value computed from the old value.
    computeIfAbsent(K key, Function<? super K,? extends V> creator)
    Returns the value for the given key if it exists, or computes it otherwise.
    computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remapping)
    Replaces the value mapped to the given key by a new value computed from the old value.
    boolean
    Returns true if this map contains the specified key.
    protected int
    cost(V value)
    Computes an estimation of the cost of the given value.
    private static void
    Ensures that the given value is not an instance of a reserved type.
    Returns the set of entries in this cache.
    boolean
    Forces the removal of all garbage collected values in the map.
    get(Object key)
    Returns the value mapped to the given key in the cache, potentially waiting for computation to complete.
    getOrCreate(K key, Callable<? extends V> creator)
    Returns the value for the given key if it exists, or computes it otherwise.
    private static <V> V
    Returns the value of the given object if it is not under computation.
    boolean
    Returns true if this cache is empty.
    boolean
    Returns true if different values may be assigned to the same key.
    private static boolean
    isNull(Object value)
    Returns true if the given value is null or a cleared reference.
    private static boolean
    Returns true if the given value is an instance of one of the reserved types used internally by this class.
    Returns the set of keys in this cache.
    lock(K key)
    Gets a lock for the entry at the given key and returns a handler to be used by the caller for unlocking and storing the result.
    merge(K key, V value, BiFunction<? super V,? super V,? extends V> remapping)
    Maps the given value to the given key if no mapping existed before this method call, or computes a new value otherwise.
    private void
    notifyChange(K key, V value)
    Notifies this Cache instance that an entry has changed.
    peek(K key)
    If a value is already cached for the given key, returns it.
    put(K key, V value)
    Puts the given value in cache and immediately returns the old value.
    putIfAbsent(K key, V value)
    If no value is already mapped and no value is under computation for the given key, puts the given value in the cache.
    Removes the value mapped to the given key in the cache.
    boolean
    remove(Object key, Object oldValue)
    If the given key is mapped to the given old value, removes that value.
    private void
    removeKey(K key, Reference<V> value)
    Removes the given key from the map if it is associated to the given value, otherwise do nothing.
    replace(K key, V value)
    If the given key is mapped to any value, replaces that value with the given new value.
    boolean
    replace(K key, V oldValue, V newValue)
    If the given key is mapped to the given old value, replaces that value with the given new value.
    void
    replaceAll(BiFunction<? super K,? super V,? extends V> remapping)
    Iterates over all entries in the cache and replaces their value with the one provided by the given function.
    void
    setKeyCollisionAllowed(boolean allowed)
    If set to true, different values may be assigned to the same key.
    int
    Returns the number of elements in this cache.
    private static <V> V
    valueOf(Object value)
    Returns the value of the given object, unwrapping it if possible.

    Methods inherited from class java.util.AbstractMap

    clone, containsValue, equals, hashCode, putAll, toString, values

    Methods inherited from class java.lang.Object

    finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.util.concurrent.ConcurrentMap

    forEach, getOrDefault

    Methods inherited from interface java.util.Map

    containsValue, equals, hashCode, putAll, values
  • Field Details

    • map

      private final ConcurrentMap<K,Object> map
      The map that contains the cached values. If a value is in the process of being computed, then the value is a temporary instance of Cache.Handler. Otherwise the value is a weak or soft Reference objects, or otherwise a strong <V> reference.
      See Also:
    • costs

      private final Map<K,Integer> costs
      The keys of values that are retained in the map by strong references, together with an estimation of their cost. This map is not thread safe; it shall be used by a single thread at any given time, even for read-only operations.

      Entries in this map are ordered from least-recently accessed to most-recently accessed.

    • totalCost

      private long totalCost
      The sum of all values in the costs map. This field shall be read and updated in the same thread than costs.
    • costLimit

      private final long costLimit
      The maximal cost allowed. If the totalCost is above that limit, then the eldest strong references will be replaced by weak or soft references.
    • soft

      private final boolean soft
      If true, use SoftReference instead of WeakReference.
    • isKeyCollisionAllowed

      private volatile boolean isKeyCollisionAllowed
      true if different values may be assigned to the same key. This is usually an error, so the default Cache behavior is to throw an exception in such cases.
      See Also:
    • entries

      private transient volatile Set<Map.Entry<K,V>> entries
      A view over the entries in the cache.
      See Also:
  • Constructor Details

    • Cache

      public Cache()
      Creates a new cache with a default initial capacity and cost limit of 100. The oldest objects will be hold by weak references.
    • Cache

      public Cache(int initialCapacity, long costLimit, boolean soft)
      Creates a new cache using the given initial capacity and cost limit. The initial capacity is the expected number of values to be stored in this cache. More values are allowed, but a little bit of CPU time may be saved if the expected capacity is known before the cache is created.

      The cost limit is the maximal value of the total cost (the sum of the cost of all values) before to replace eldest strong references by weak or soft references.

      Parameters:
      initialCapacity - the initial capacity.
      costLimit - the maximum cost of objects to keep by strong reference.
      soft - if true, use SoftReference instead of WeakReference.
  • Method Details

    • clear

      public void clear()
      Clears the content of this cache.
      Specified by:
      clear in interface Map<K,V>
      Overrides:
      clear in class AbstractMap<K,V>
    • isEmpty

      public boolean isEmpty()
      Returns true if this cache is empty.
      Specified by:
      isEmpty in interface Map<K,V>
      Overrides:
      isEmpty in class AbstractMap<K,V>
      Returns:
      true if this cache do not contains any element.
    • size

      public int size()
      Returns the number of elements in this cache. The count includes values keep by strong, soft or weak references, and the values under computation at the time this method is invoked.
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size in class AbstractMap<K,V>
      Returns:
      the number of elements currently cached.
    • get

      public V get(Object key)
      Returns the value mapped to the given key in the cache, potentially waiting for computation to complete. This method is similar to peek(Object) except that it blocks if the value is currently under computation in another thread.
      Specified by:
      get in interface Map<K,V>
      Overrides:
      get in class AbstractMap<K,V>
      Parameters:
      key - the key of the value to get.
      Returns:
      the value mapped to the given key, or null if none.
      See Also:
    • getOrCreate

      public V getOrCreate(K key, Callable<? extends V> creator) throws Exception
      Returns the value for the given key if it exists, or computes it otherwise. If a value already exists in the cache, then it is returned immediately. Otherwise the creator.call() method is invoked and its result is saved in this cache for future reuse.
      Example: the following example shows how this method can be used. In particular, it shows how to propagate MyCheckedException:
      This method is similar to computeIfAbsent(Object, Function) except that it can propagate checked exceptions. If the creator function does not throw any checked exception, then invoking computeIfAbsent(…) is simpler.
      Parameters:
      key - the key for which to get the cached or created value.
      creator - a method for creating a value, to be invoked only if no value are cached for the given key.
      Returns:
      the value for the given key, which may have been created as a result of this method call.
      Throws:
      Exception - if an exception occurred during the execution of creator.call().
      See Also:
    • computeIfAbsent

      public V computeIfAbsent(K key, Function<? super K,? extends V> creator)
      Returns the value for the given key if it exists, or computes it otherwise. If a value already exists in the cache, then it is returned immediately. Otherwise the creator.apply(Object) method is invoked and its result is saved in this cache for future reuse.
      Example: below is the same code than getOrCreate(Object, Callable) example, but without the need for any checked exception handling:
      This method is similar to getOrCreate(Object, Callable), but without checked exceptions.
      Specified by:
      computeIfAbsent in interface ConcurrentMap<K,V>
      Specified by:
      computeIfAbsent in interface Map<K,V>
      Parameters:
      key - the key for which to get the cached or created value.
      creator - a method for creating a value, to be invoked only if no value are cached for the given key.
      Returns:
      the value already mapped to the key, or the newly computed value.
      Since:
      1.0
      See Also:
    • isNull

      private static boolean isNull(Object value)
      Returns true if the given value is null or a cleared reference.
      Parameters:
      value - the value to test.
      Returns:
      whether the given value is null or a cleared reference.
    • isReservedType

      private static boolean isReservedType(Object value)
      Returns true if the given value is an instance of one of the reserved types used internally by this class.
    • ensureValidType

      private static void ensureValidType(Object value) throws IllegalArgumentException
      Ensures that the given value is not an instance of a reserved type.
      Throws:
      IllegalArgumentException
    • valueOf

      private static <V> V valueOf(Object value)
      Returns the value of the given object, unwrapping it if possible. If the value is under computation in another thread, this method will block until the computation is completed.
    • immediateValueOf

      private static <V> V immediateValueOf(Object value)
      Returns the value of the given object if it is not under computation. This method is similar to valueOf(Object) except that it does not block if the value is under computation.
    • notifyChange

      private void notifyChange(K key, V value)
      Notifies this Cache instance that an entry has changed. This method is invoked after put(…), replace(…) and remove(…) operations. It does not need to be atomic with above-cited operations because this method performs its work in a background thread anyway. If the value for the specified key was retained by weak reference, it become a value retained by strong reference. Conversely some values previously retained by strong references may be retained by weak references after the cost adjustment performed by this method.
      Parameters:
      key - key of the entry that changed.
      value - the new value. May be null.
    • putIfAbsent

      public V putIfAbsent(K key, V value)
      If no value is already mapped and no value is under computation for the given key, puts the given value in the cache. Otherwise returns the current value (potentially blocking until the computation finishes). A null value argument is equivalent to a no-op. Otherwise a null return value means that the given value has been stored in the Cache.
      Specified by:
      putIfAbsent in interface ConcurrentMap<K,V>
      Specified by:
      putIfAbsent in interface Map<K,V>
      Parameters:
      key - the key to associate with a value.
      value - the value to associate with the given key if no value already exists, or null.
      Returns:
      the existing value mapped to the given key, or null if none existed before this method call.
      Since:
      1.0
      See Also:
    • put

      public V put(K key, V value)
      Puts the given value in cache and immediately returns the old value. A null value argument removes the entry. If a different value is under computation in another thread, then the other thread may fail with an IllegalStateException unless isKeyCollisionAllowed() returns true. For more safety, consider using putIfAbsent(…) instead.
      Specified by:
      put in interface Map<K,V>
      Overrides:
      put in class AbstractMap<K,V>
      Parameters:
      key - the key to associate with a value.
      value - the value to associate with the given key, or null for removing the mapping.
      Returns:
      the value previously mapped to the given key, or null if no value existed before this method call or if the value was under computation in another thread.
      See Also:
    • replace

      public V replace(K key, V value)
      If the given key is mapped to any value, replaces that value with the given new value. Otherwise does nothing. A null value argument removes the entry. If a different value is under computation in another thread, then the other thread may fail with an IllegalStateException unless isKeyCollisionAllowed() returns true.
      Specified by:
      replace in interface ConcurrentMap<K,V>
      Specified by:
      replace in interface Map<K,V>
      Parameters:
      key - key of the value to replace.
      value - the new value to use in replacement of the previous one, or null for removing the mapping.
      Returns:
      the value previously mapped to the given key, or null if no value existed before this method call or if the value was under computation in another thread.
      Since:
      1.0
      See Also:
    • replace

      public boolean replace(K key, V oldValue, V newValue)
      If the given key is mapped to the given old value, replaces that value with the given new value. Otherwise does nothing. A null value argument removes the entry if the condition matches. If a value is under computation in another thread, then this method unconditionally returns false.
      Specified by:
      replace in interface ConcurrentMap<K,V>
      Specified by:
      replace in interface Map<K,V>
      Parameters:
      key - key of the value to replace.
      oldValue - previous value expected to be mapped to the given key.
      newValue - the new value to put if the condition matches, or null for removing the mapping.
      Returns:
      true if the value has been replaced, false otherwise.
      Since:
      1.0
    • replaceAll

      public void replaceAll(BiFunction<? super K,? super V,? extends V> remapping)
      Iterates over all entries in the cache and replaces their value with the one provided by the given function. If the function throws an exception, the iteration is stopped and the exception is propagated. If any value is under computation in other threads, then the iteration will block on that entry until its computation is completed.
      Specified by:
      replaceAll in interface ConcurrentMap<K,V>
      Specified by:
      replaceAll in interface Map<K,V>
      Parameters:
      remapping - the function computing new values from the old ones.
      Since:
      1.0
    • computeIfPresent

      public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remapping)
      Replaces the value mapped to the given key by a new value computed from the old value. If a value for the given key is under computation in another thread, then this method blocks until that computation is completed. This is equivalent to the work performed by replaceAll(…) but on a single entry.
      Specified by:
      computeIfPresent in interface ConcurrentMap<K,V>
      Specified by:
      computeIfPresent in interface Map<K,V>
      Parameters:
      key - key of the value to replace.
      remapping - the function computing new values from the old ones.
      Returns:
      the new value associated with the given key.
      Since:
      1.0
      See Also:
    • compute

      public V compute(K key, BiFunction<? super K,? super V,? extends V> remapping)
      Replaces the value mapped to the given key by a new value computed from the old value. If there is no value for the given key, then the "old value" is taken as null. If a value for the given key is under computation in another thread, then this method blocks until that computation is completed. This method is equivalent to computeIfPresent(…) except that a new value will be computed even if no value existed for the key before this method call.
      Specified by:
      compute in interface ConcurrentMap<K,V>
      Specified by:
      compute in interface Map<K,V>
      Parameters:
      key - key of the value to replace.
      remapping - the function computing new values from the old ones, or from a null value.
      Returns:
      the new value associated with the given key.
      Since:
      1.0
      See Also:
    • merge

      public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remapping)
      Maps the given value to the given key if no mapping existed before this method call, or computes a new value otherwise. If a value for the given key is under computation in another thread, then this method blocks until that computation is completed.
      Specified by:
      merge in interface ConcurrentMap<K,V>
      Specified by:
      merge in interface Map<K,V>
      Parameters:
      key - key of the value to replace.
      value - the value to associate with the given key if no value already exists, or null.
      remapping - the function computing a new value by merging the exiting value with the value argument given to this method.
      Returns:
      the new value associated with the given key.
      Since:
      1.0
    • remove

      public V remove(Object key)
      Removes the value mapped to the given key in the cache. If a value is under computation in another thread, then the other thread may fail with an IllegalStateException unless isKeyCollisionAllowed() returns true. For more safety, consider using remove(Object, Object) instead.
      Specified by:
      remove in interface Map<K,V>
      Overrides:
      remove in class AbstractMap<K,V>
      Parameters:
      key - the key of the value to removed.
      Returns:
      the value previously mapped to the given key, or null if no value existed before this method call or if the value was under computation in another thread.
      See Also:
    • remove

      public boolean remove(Object key, Object oldValue)
      If the given key is mapped to the given old value, removes that value. Otherwise does nothing. If a value is under computation in another thread, then this method unconditionally returns false.
      Specified by:
      remove in interface ConcurrentMap<K,V>
      Specified by:
      remove in interface Map<K,V>
      Parameters:
      key - key of the value to remove.
      oldValue - previous value expected to be mapped to the given key.
      Returns:
      true if the value has been removed, false otherwise.
      Since:
      1.0
      See Also:
    • containsKey

      public boolean containsKey(Object key)
      Returns true if this map contains the specified key. If the value is under computation in another thread, this method returns true without waiting for the computation result. This behavior is consistent with other Map methods in the following ways:
      • get(Object) blocks until the computation is completed.
      • put(Object, Object) returns null for values under computation, i.e. behaves as if keys are temporarily mapped to the null value until the computation is completed.
      Specified by:
      containsKey in interface Map<K,V>
      Overrides:
      containsKey in class AbstractMap<K,V>
      Parameters:
      key - the key to check for existence.
      Returns:
      true if the given key is mapped to an existing value or a value under computation.
      See Also:
    • peek

      public V peek(K key)
      If a value is already cached for the given key, returns it. Otherwise returns null. This method is similar to get(Object) except that it doesn't block if the value is in process of being computed in another thread; it returns null in such case.
      Parameters:
      key - the key for which to get the cached value.
      Returns:
      the cached value for the given key, or null if there is none.
      See Also:
    • lock

      public Cache.Handler<V> lock(K key)
      Gets a lock for the entry at the given key and returns a handler to be used by the caller for unlocking and storing the result. This method must be used together with a putAndUnlock call in trycatch blocks as in the example below:
      Parameters:
      key - the key for the entry to lock.
      Returns:
      a handler to use for unlocking and storing the result.
    • adjustReferences

      private void adjustReferences(K key, V value)
      Invoked in a background thread after a value has been set in the map. This method computes a cost estimation of the new value. If the total cost is greater than the cost limit, then oldest strong references are replaced by weak references until the cost of entries kept by strong references become lower than the threshold.
    • removeKey

      private void removeKey(K key, Reference<V> value)
      Removes the given key from the map if it is associated to the given value, otherwise do nothing. This method is invoked when the value of a weak or soft reference has been cleared. Theoretically no entry for that key should exist in the costs map because that map contains only the keys of objects hold by strong references. But we check anyway for reducing the risk of memory leaks. It may happen if some keys are removed from keySet() instead of using Cache API.
      Parameters:
      key - key of the entry to remove.
      value - expected value associated to the given entry.
    • keySet

      public Set<K> keySet()
      Returns the set of keys in this cache. The returned set is subjects to the same caution than the ones documented in the ConcurrentHashMap.keySet() method.

      If some elements are removed from the key set, then flush() should be invoked after removals. This is not done automatically by the returned set. For safety, the remove(Object) methods defined in the Cache class should be used instead.

      Specified by:
      keySet in interface Map<K,V>
      Overrides:
      keySet in class AbstractMap<K,V>
      Returns:
      the set of keys in this cache.
      See Also:
    • entrySet

      public Set<Map.Entry<K,V>> entrySet()
      Returns the set of entries in this cache. The returned set is subjects to the same caution than the ones documented in the ConcurrentHashMap.entrySet() method, except that it does not support removal of elements (including through the Iterator.remove() method call).
      Specified by:
      entrySet in interface Map<K,V>
      Specified by:
      entrySet in class AbstractMap<K,V>
      Returns:
      a view of the entries contained in this map.
    • isKeyCollisionAllowed

      public boolean isKeyCollisionAllowed()
      Returns true if different values may be assigned to the same key. The default value is false.
      Returns:
      true if key collisions are allowed.
    • setKeyCollisionAllowed

      public void setKeyCollisionAllowed(boolean allowed)
      If set to true, different values may be assigned to the same key. This is usually an error, so the default Cache behavior is to thrown an IllegalStateException in such cases, typically when Cache.Handler.putAndUnlock(Object) is invoked. However, in some cases we may want to relax this check. For example, the EPSG database sometimes assigns the same key to different kinds of objects.

      If key collisions are allowed and two threads invoke lock(Object) concurrently for the same key, then the value to be stored in the map will be the one computed by the first thread who got the lock. The value computed by any other concurrent thread will be ignored by this Cache class. However, those threads still return their computed values to their callers.

      This property can also be set in order to allow some recursivity. If during the creation of an object, the program asks to this Cache for the same object (using the same key), then the default Cache implementation will consider this situation as a key collision unless this property has been set to true.

      Parameters:
      allowed - true if key collisions should be allowed.
    • cost

      protected int cost(V value)
      Computes an estimation of the cost of the given value. The default implementation returns 1 in all cases. Subclasses should override this method if they have some easy way to measure the relative cost of value objects.
      Parameters:
      value - the object for which to get an estimation of its cost.
      Returns:
      the estimated cost of the given object.
      See Also:
    • flush

      public boolean flush()
      Forces the removal of all garbage collected values in the map. This method should not need to be invoked when using Cache API. It is provided as a debugging tools when suspecting a memory leak.
      Returns:
      true if some entries have been removed as a result of this method call.
      Since:
      1.3
      See Also: