Module Ringo
Ringo
Preamble
module type UNBOXED_COLLECTION = Ringo__.Sigs.UNBOXED_COLLECTION
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 inUNBOXED_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 inUNBOXED_COLLECTION
.
Caches
module type CACHE_MAP = Ringo__.Sigs.CACHE_MAP
module type CACHE_SET = Ringo__.Sigs.CACHE_SET
Cache policies
type replacement
=
|
LRU
|
FIFO
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.
type overflow
=
|
Strong
|
Weak
overflow
is for defining the overflow policy of a cache.Strong
means that the cache never holds more element than is specified when callingcreate
(seeMAP_MAKER
andSET_MAKER
below andCACHE_MAP
andCACHE_SET
).Weak
means that the cache may hold more elements than specified when callingcreate
but that supernumerary elements may be collected by the Garbage Collector.
type accounting
=
|
Precise
|
Sloppy
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 isremove
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. UsePrecise
only if you useremove
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 aPrecise
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.
Cache instantiating
module type MAP_MAKER = functor (H : Stdlib.Hashtbl.HashedType) -> CACHE_MAP with type key = H.t
A
MAP_MAKER
is a functor that instantiatesCACHE_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-classMAP_MAKER
that instantiates caches with the policies specified byreplacement
,overflow
, andaccounting
.
module EmptyMap : functor (H : Stdlib.Hashtbl.HashedType) -> sig ... end
EmptyMap(H)
is a map module but it only supports the empty map: a map with zero elements.
module SingletonMap : functor (H : Stdlib.Hashtbl.HashedType) -> sig ... end
SingletonMap(H)
is a map module but it only supports singleton maps: maps with at most one element.
module type SET_MAKER = functor (H : Stdlib.Hashtbl.HashedType) -> CACHE_SET with type elt = H.t
A
SET_MAKER
is a functor that instantiatesCACHE_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-classSET_MAKER
that instantiates caches with the policies specified byreplacement
,overflow
, andaccounting
.
module EmptySet : functor (H : Stdlib.Hashtbl.HashedType) -> sig ... end
EmptySet(H)
is a set module but it only supports the empty set: a set with zero elements.
module SingletonSet : functor (H : Stdlib.Hashtbl.HashedType) -> sig ... end
SingletonSey(H)
is a set module but it only supports singleton sets: sets with at most one element.