SieveCache

Artifact: androidx.collection:collection

Kotlin |Java

Cmn
```
class SieveCache<K : Any, V : Any>
```

SieveCache is an in-memory cache that holds strong references to a limited number of values determined by the cache's maxSize and the size of each value. When a value is added to a full cache, one or more existing values are evicted from the cache using the SIEVE algorithm. Complete details about the algorithm can be found in Zhang et al., 2024, SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches, NSDI'24 (paper).

Contrary to LruCache, SieveCache does not maintain a list of entries based on their access order, but on their insertion order. Eviction candidates are found by keeping track of the "visited" status of each entry. This means that reading a value using get prevents that entry from becoming an eviction candidate. In practice, SieveCache offers better hit ratio compared to LruCache.

The underlying implementation is also designed to avoid all allocations on insertion, removal, retrieval, and iteration. Allocations may still happen on insertion when the underlying storage needs to grow to accommodate newly added entries to the table. In addition, this implementation minimizes memory usage by avoiding the use of separate objects to hold key/value pairs. The implementation follows the implementation of ScatterMap.

By default, the size of the cache is measured in number of entries. The caller can choose the size and size unit of the values by passing their own sizeOf lambda, invoked whenever the cache needs to query the size of a value.

The createValueFromKey lambda can be used to compute values on demand from a key when querying for an entry that does not exist in the cache.

When a cached value is removed, either directly by the caller or via the eviction mechanism, you can use the onEntryRemoved lambda to execute any side effect or perform any necessary cleanup.

This implementation is not thread-safe: if multiple threads access this container concurrently, and one or more threads modify the structure of the map (insertion or removal for instance), the calling code must provide the appropriate synchronization. Multiple threads are safe to read from this map concurrently if no write is happening.

A SieveCache can hold a maximum of Int.MAX_VALUE - 1 entries, independent of their computed size.

Summary

Public constructors
`<K : Any, V : Any> SieveCache( maxSize: @IntRange(from = 1, to = 2147483646) Int, initialCapacity: @IntRange(from = 0, to = 2147483646) Int, sizeOf: (key, value) -> Int, createValueFromKey: (key) -> V?, onEntryRemoved: (key, oldValue, newValue?, evicted: Boolean) -> Unit )` Creates a new `SieveCache`.	Cmn

Public functions
`inline Boolean`	`all(predicate: (K, V) -> Boolean)` Returns true if all entries match the given `predicate`.	Cmn
`Boolean`	`any()` Returns `true` if this cache has at least one entry.	Cmn
`inline Boolean`	`any(predicate: (K, V) -> Boolean)` Returns true if at least one entry matches the given `predicate`.	Cmn
`operator Boolean`	`contains(key: K)` Returns true if the specified `key` is present in this cache, false otherwise.	Cmn
`Boolean`	`containsKey(key: K)` Returns true if the specified `key` is present in this cache, false otherwise.	Cmn
`Boolean`	`containsValue(value: V)` Returns true if the specified `value` is present in this hash map, false otherwise.	Cmn
`Int`	`count()` Returns the number of entries in this cache.	Cmn
`inline Int`	`count(predicate: (K, V) -> Boolean)` Returns the number of entries matching the given `predicate`.	Cmn
`open operator Boolean`	`equals(other: Any?)` Compares the specified object `other` with this cache for equality.	Cmn
`Unit`	`evictAll()` Removes all the entries from this cache.	Cmn
`inline Unit`	`forEach(block: (key, value) -> Unit)` Iterates over every key/value pair stored in this cache by invoking the specified `block` lambda.	Cmn
`inline Unit`	`forEachKey(block: (key) -> Unit)` Iterates over every key stored in this cache by invoking the specified `block` lambda.	Cmn
`inline Unit`	`forEachValue(block: (value) -> Unit)` Iterates over every value stored in this cache by invoking the specified `block` lambda.	Cmn
`operator V?`	`get(key: K)` Returns the value for `key` if it exists in the cache or can be created by `createValueFromKey`.	Cmn
`open Int`	`hashCode()` Returns the hash code value for this cache.	Cmn
`Boolean`	`isEmpty()` Indicates whether this cache is empty.	Cmn
`Boolean`	`isNotEmpty()` Returns `true` if this cache is not empty.	Cmn
`inline operator Unit`	`minusAssign(key: K)` Removes the specified `key` and its associated value from the map.	Cmn
`inline operator Unit`	`minusAssign(keys: Array<K>)` Removes the specified `keys` and their associated value from the map.	Cmn
`inline operator Unit`	`minusAssign(keys: Iterable<K>)` Removes the specified `keys` and their associated value from the map.	Cmn
`inline operator Unit`	`minusAssign(keys: ObjectList<K>)` Removes the specified `keys` and their associated value from the map.	Cmn
`inline operator Unit`	`minusAssign(keys: ScatterSet<K>)` Removes the specified `keys` and their associated value from the map.	Cmn
`inline operator Unit`	`minusAssign(keys: Sequence<K>)` Removes the specified `keys` and their associated value from the map.	Cmn
`Boolean`	`none()` Returns `true` if this cache has no entries.	Cmn
`inline operator Unit`	`plusAssign(from: Map<K, V>)` Puts all the key/value mappings in the `from` map into this map.	Cmn
`inline operator Unit`	`plusAssign(from: ScatterMap<K, V>)` Puts all the key/value mappings in the `from` map into this map.	Cmn
`inline operator Unit`	`plusAssign(from: SieveCache<K, V>)` Puts all the key/value mappings in the `from` map into this map.	Cmn
`inline operator Unit`	`plusAssign(pair: Pair<K, V>)` Puts the key/value mapping from the `pair` in this cache, using the first element as the key, and the second element as the value.	Cmn
`inline operator Unit`	`plusAssign(pairs: Array<Pair<K, V>>)` Puts all the `pairs` into this map, using the first component of the pair as the key, and the second component as the value.	Cmn
`inline operator Unit`	`plusAssign(pairs: Iterable<Pair<K, V>>)` Puts all the `pairs` into this map, using the first component of the pair as the key, and the second component as the value.	Cmn
`inline operator Unit`	`plusAssign(pairs: Sequence<Pair<K, V>>)` Puts all the `pairs` into this map, using the first component of the pair as the key, and the second component as the value.	Cmn
`V?`	`put(key: K, value: V)` Adds `value` to the cache using the specific `key`.	Cmn
`Unit`	`putAll(from: Map<K, V>)` Puts all the key/value mappings in the `from` map into this cache.	Cmn
`Unit`	`putAll(from: ScatterMap<K, V>)` Puts all the key/value mappings in the `from` map into this cache.	Cmn
`Unit`	`putAll(from: SieveCache<K, V>)` Puts all the key/value mappings in the `from` cache into this cache.	Cmn
`Unit`	`putAll(pairs: Array<Pair<K, V>>)` Puts all the `pairs` into this cache, using the first component of the pair as the key, and the second component as the value.	Cmn
`Unit`	`putAll(pairs: Iterable<Pair<K, V>>)` Puts all the `pairs` into this cache, using the first component of the pair as the key, and the second component as the value.	Cmn
`Unit`	`putAll(pairs: Sequence<Pair<K, V>>)` Puts all the `pairs` into this cache, using the first component of the pair as the key, and the second component as the value.	Cmn
`V?`	`remove(key: K)` Removes the specified `key` and its associated value from the cache.	Cmn
`Boolean`	`remove(key: K, value: V)` Removes the specified `key` and its associated value from the cache if the associated value equals `value`.	Cmn
`Unit`	`removeIf(predicate: (K, V) -> Boolean)` Removes any mapping for which the specified `predicate` returns true.	Cmn
`Unit`	`resize(maxSize: @IntRange(from = 1, to = 2147483646) Int)` Sets the maximum size of the cache to `maxSize`, in the unit defined by the implementation of `sizeOf`.	Cmn
`inline operator Unit`	`set(key: K, value: V)` Adds `value` to the cache using the specific `key`.	Cmn
`open String`	`toString()`	Cmn
`Unit`	`trimToSize(maxSize: Int)` Remove entries until the total size of the remaining entries is less than or equal to `maxSize`.	Cmn

Public properties
`Int`	`capacity` Returns the number of entries that can be stored in this cache without requiring internal storage reallocation.	Cmn
`Int`	`count` Returns the number of elements held in the cache.	Cmn
`Int`	`maxSize` Return the maximum size of the cache before adding new elements causes existing elements to be evicted.	Cmn
`Int`	`size` Size of the cache in the unit defined by the implementation of `sizeOf` (by default, the number of elements).	Cmn

Public constructors

SieveCache

Cmn

<K : Any, V : Any> SieveCache(
    maxSize: @IntRange(from = 1, to = 2147483646) Int,
    initialCapacity: @IntRange(from = 0, to = 2147483646) Int = DefaultScatterCapacity,
    sizeOf: (key, value) -> Int = { _, _ -> 1 },
    createValueFromKey: (key) -> V? = { null },
    onEntryRemoved: (key, oldValue, newValue?, evicted: Boolean) -> Unit = { _, _, _, _ ->
        }
)

Creates a new SieveCache.

Parameters
`maxSize: @IntRange(from = 1, to = 2147483646) Int`	For caches that do not override `sizeOf`, this is the maximum number of entries in the cache. For all other caches, this is the maximum sum of the sizes of the entries in this cache. The maximum size must be strictly greater than 0 and must be less than or equal to `Int.MAX_VALUE - 1`.
`initialCapacity: @IntRange(from = 0, to = 2147483646) Int = DefaultScatterCapacity`	The initial desired capacity for this cache. The cache will honor this value by guaranteeing its internal structures can hold that many entries without requiring any allocations. The initial capacity can be set to 0.
`sizeOf: (key, value) -> Int = { _, _ -> 1 }`	Returns the size of the entry for the specified key and value. The size of an entry cannot change after it was added to the cache, and must be >= 0.
`createValueFromKey: (key) -> V? = { null }`	Called after a cache miss to compute a value for the specified key. Returning null from this lambda indicates that no value can be computed.
`onEntryRemoved: (key, oldValue, newValue?, evicted: Boolean) -> Unit = { _, _, _, _ -> }`	Called for entries that have been removed by the user of the cache, or automatically evicted. The lambda is supplied with multiple parameters. The `key` of the entry being removed or evicted. The original value (`oldValue`) of the entry if the entry is being evicted or replaced. The new value (`newValue`) for the key, if it exists. If non-null, the removal was caused by a `put()` or a `set()`, otherwise it was caused by an eviction or a removal. A boolean (`evicted`) set to `true` if the entry was evicted to make space in the cache, or set to `false` if the removal happened on demand or while replacing an existing value with `put`.

Public functions

all

Cmn

SieveCache

Summary

Public constructors

Public functions

Public properties

Public constructors

SieveCache

Public functions

all

any

any

contains

containsKey

containsValue

count

count

equals

evictAll

forEach

forEachKey

forEachValue

get

hashCode

isEmpty

isNotEmpty

minusAssign

minusAssign

minusAssign

minusAssign

minusAssign

minusAssign

none

plusAssign

plusAssign

plusAssign

plusAssign

plusAssign

plusAssign

plusAssign

put

putAll

putAll

putAll

putAll

putAll

putAll

remove

remove

removeIf

resize

set

toString

trimToSize

Public properties

capacity

count

maxSize

size