Library
Module
Module type
Parameter
Class
Class type
Ringo is a library for caches.
module type UNBOXED_COLLECTION = sig ... end
A mutable structure that holds at most a fixed number of values of a same type. Values are not removed by hand, instead, once the limit is reached, adding a value replaces the oldest one in the buffer.
module Ring : UNBOXED_COLLECTION
Ring
is a potentially useful module that is used internally to manage bounded, FIFO collections of items. The documentation is available in UNBOXED_COLLECTION
.
module Dll : UNBOXED_COLLECTION
Dll
is a potentially useful module that is used internally to manage bounded, LRU collections of items. The documentation is available in UNBOXED_COLLECTION
.
module type CACHE_MAP = sig ... end
A Mutable structure akin to a hash-table, but with a size bound. Note that, different caches have different policies towards the size bounds: some uphold the bound strictly, some treat the bound as a suggestion. In addition, some caches count their elements somewhat sloppily.
module type CACHE_SET = sig ... end
A Mutable structure akin to a set, but with a size bound. Note that, different caches have different policies towards the size bounds: some uphold the bound strictly, some treat the bound as a suggestion. In addition, some caches count their elements somewhat sloppily.
All caches of Ringo have either the CACHE_MAP
interface (for key-value stores) or the CACHE_SET
interface (for value stores). Their behavior can be tweaked by the parameters below.
replacement
is for defining the replacement policy of a cache. LRU
is for "Least Recently Used", meaning that when a supernumerary item is inserted in the cache, the least recently used item is removed to make room. FIFO
is for "First-In, First-Out" meaning that when a supernumerary item is inserted in the cache, the oldest inserted element is removed to make room.
overflow
is for defining the overflow policy of a cache. Strong
means that the cache never holds more element than is specified when calling create
(see MAP_MAKER
and SET_MAKER
below and CACHE_MAP
and CACHE_SET
). Weak
means that the cache may hold more elements than specified when calling create
but that supernumerary elements may be collected by the Garbage Collector.
accounting
is for defining the accounting policy of a cache.
Precise
means that the cache counts its number of elements precisely: when an element is added, the count increases, when an element is removed, the count decreases, when an already present element is re-inserted the count is unchanged.
Sloppy
means that the cache may count some elements that are not in the cache as still being held by the cache. As a result, adding a new element into the cache may lead to another element being removed even though the size limit was not actually reached.
The element-count of a Sloppy
cache may become offset by one when an element is remove
d or when an element that is already present in the cache is re-add
ed. This effect is cumulative and the element count can be off by more than one if multiple, say, removals happen.
The element-count eventually restores itself if enough new elements are add
ed.
Additional details of the accounting in Sloppy
caches are implementation dependent. Use Precise
only if you use remove
a lot, if you might insert the same key multiple times often, or if you need strong guarantees on the number of elements.
Note that when requesting a Sloppy
cache, the library might give you a Precise
cache if there is no additional runtime cost. In general, Sloppy
caches are more efficient, but depending on the other parameters they might be only as-efficient-as (not strictly more efficient than) Precise
caches.
A MAP_MAKER
is a functor that instantiates CACHE_MAP
s based on a given type and its associated hash function.
type map_maker = (module MAP_MAKER)
val map_maker :
replacement:replacement ->
overflow:overflow ->
accounting:accounting ->
map_maker
map_maker ~replacement ~overflow ~accounting
is a first-class MAP_MAKER
that instantiates caches with the policies specified by replacement
, overflow
, and accounting
.
module EmptyMap (H : Hashtbl.HashedType) : sig ... end
EmptyMap(H)
is a map module but it only supports the empty map: a map with zero elements.
module SingletonMap (H : Hashtbl.HashedType) : sig ... end
SingletonMap(H)
is a map module but it only supports singleton maps: maps with at most one element.
A SET_MAKER
is a functor that instantiates CACHE_SET
s based on a given type and its associated hash function.
type set_maker = (module SET_MAKER)
val set_maker :
replacement:replacement ->
overflow:overflow ->
accounting:accounting ->
set_maker
set_maker ~replacement ~overflow ~accounting
is a first-class SET_MAKER
that instantiates caches with the policies specified by replacement
, overflow
, and accounting
.
module EmptySet (H : Hashtbl.HashedType) : sig ... end
EmptySet(H)
is a set module but it only supports the empty set: a set with zero elements.
module SingletonSet (H : Hashtbl.HashedType) : sig ... end
SingletonSey(H)
is a set module but it only supports singleton sets: sets with at most one element.