Package org.apache.sis.util.collection

# Class Cache<K,V>

Object
AbstractMap<K,V>
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>`

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:

>     private final Cache<String,MyObject> cache = new Cache<String,MyObject>();

>     public MyObject getMyObject(String key) {
>         return cache.computeIfAbsent(key, (k) -> createMyObject(k));
>     }

Alternatively, one can handle explicitly the locks. This alternative sometime 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`).

>     private final Cache<String,MyObject> cache = new Cache<String,MyObject>();

>     public MyObject getMyObject(final String key) throws MyCheckedException {
>         MyObject value = cache.peek(key);
>         if (value == null) {
>             final Cache.Handler<MyObject> handler = cache.lock(key);
>             try {
>                 value = handler.peek();
>                 if (value == null) {
>                     value = createMyObject(key);
>                 }
>             } finally {
>                 handler.putAndUnlock(value);
>             }
>         }
>         return value;
>     }

## 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 is 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

Defined in the `sis-utility` module

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `static interface`
  `Cache​.Handler<V>`
  The handler returned by `lock(K)`, to be used for unlocking and storing the result.

  ## Nested classes/interfaces inherited from class AbstractMap

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

  ## Nested classes/interfaces inherited from interface Map

  `Map​.Entry<K extends Object,V extends Object>`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `Cache()`
  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
  `void`
  `clear()`
  Clears the content of this cache.
  `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.
  `V`
  `computeIfAbsent(K key, Function<? super K,? extends V> creator)`
  Returns the value for the given key if it exists, or computes it otherwise.
  `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.
  `boolean`
  `containsKey(Object key)`
  Returns `true` if this map contains the specified key.
  `protected int`
  `cost(V value)`
  Computes an estimation of the cost of the given value.
  `Set<Map​.Entry<K,V>>`
  `entrySet()`
  Returns the set of entries in this cache.
  `V`
  `get(Object key)`
  Returns the value mapped to the given key in the cache, potentially waiting for computation to complete.
  `V`
  `getOrCreate(K key, Callable<? extends V> creator)`
  Returns the value for the given key if it exists, or computes it otherwise.
  `boolean`
  `isEmpty()`
  Returns `true` if this cache is empty.
  `boolean`
  `isKeyCollisionAllowed()`
  Returns `true` if different values may be assigned to the same key.
  `Set<K>`
  `keySet()`
  Returns the set of keys in this cache.
  `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.
  `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.
  `V`
  `peek(K key)`
  If a value is already cached for the given key, returns it.
  `V`
  `put(K key, V value)`
  Puts the given value in cache and immediately returns the old value.
  `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.
  `V`
  `remove(Object key)`
  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.
  `V`
  `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`
  `size()`
  Returns the number of elements in this cache.

  ### Methods inherited from class AbstractMap

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

  ### Methods inherited from class Object

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

  ### Methods inherited from interface ConcurrentMap

  `forEach, getOrDefault`

  ### Methods inherited from interface Map

  `containsValue, equals, hashCode, putAll, values`

- ## 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:
      - `peek(Object)`
      - `containsKey(Object)`
      - `computeIfAbsent(Object, Function)`

  - ### 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`:

    >     private final Cache<String,MyObject> cache = new Cache<String,MyObject>();

    >     public MyObject getMyObject(final String key) throws MyCheckedException {
    >         try {
    >             return cache.getOrCreate(key, new Callable<MyObject>() {
    >                 public MyObject call() throws MyCheckedException {
    >                     return createMyObject(key);
    >                 }
    >             });
    >         } catch (MyCheckedException | RuntimeException e) {
    >             throw e;
    >         } catch (Exception e) {
    >             throw new UndeclaredThrowableException(e);
    >         }
    >     }

    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:
      - `get(Object)`
      - `peek(Object)`
      - `computeIfAbsent(Object, Function)`

  - ### 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:

    >     private final Cache<String,MyObject> cache = new Cache<String,MyObject>();

    >     public MyObject getMyObject(final String key) {
    >         return cache.computeIfAbsent(key, (k) -> createMyObject(k));
    >     }

    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:
      - `peek(Object)`
      - `containsKey(Object)`
      - `getOrCreate(Object, Callable)`
      - `computeIfPresent(Object, BiFunction)`

  - ### 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:
      - `get(Object)`
      - `computeIfAbsent(Object, Function)`

  - ### 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:
      - `get(Object)`
      - `putIfAbsent(Object, Object)`

  - ### 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(Object, Object, Object)`

  - ### 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:
      - `computeIfAbsent(Object, Function)`

  - ### 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:
      - `computeIfAbsent(Object, Function)`

  - ### 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:
      - `get(Object)`
      - `remove(Object, Object)`

  - ### 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:
      - `get(Object)`

  - ### 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:
      - `get(Object)`
      - `peek(Object)`

  - ### 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:
      - `get(Object)`
      - `lock(Object)`

  - ### 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 `try` … `catch` blocks as in the example below:

    >     Cache.Handler handler = cache.lock();
    >     try {
    >         // Compute the result...
    >     } finally {
    >         handler.putAndUnlock(result);
    >     }

    Parameters:
      `key` - the key for the entry to lock.
    Returns:
      a handler to use for unlocking and storing the result.

  - ### 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.
    Specified by:
      `keySet` in interface `Map<K,V>`
    Overrides:
      `keySet` in class `AbstractMap<K,V>`
    Returns:
      the set of keys in this cache.

  - ### 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 sometime 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:
      - `Instrumentation​.getObjectSize(Object)`