Module Ringo

Ringo

Preamble

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.

Caches

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 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.

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 is removed or when an element that is already present in the cache is re-added. 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 added.

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.

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 instantiates CACHE_MAPs 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 : 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 instantiates CACHE_SETs 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 : 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.