package lru

  1. Overview
  2. Docs

Module M.MakeSource

Make(K)(V) is the LRU map with bindings K.t -> V.t. The weight of an individual binding is the Weighted.weight of V.t.

Parameters

module V : Weighted

Signature

Mutable LRU map

Sourcetype t

A map.

Sourcetype k = K.t

Keys in t.

Sourcetype v = V.t

Values in t.

Sourceval create : ?random:bool -> int -> t

create ?random cap is a new map with capacity cap.

~random randomizes the underlying hash table. It defaults to false. See Hashtbl.create.

Note. The internal hash table is created with size cap.

Sourceval is_empty : t -> bool

is_empty t is true iff there are no bindings in t.

Sourceval size : t -> int

size t is the number of bindings in t.

Limiting the weight of bindings

Sourceval weight : t -> int

weight t is the combined weight of bindings in t.

Sourceval capacity : t -> int

capacity t is the maximum combined weight of bindings that trim will retain.

Sourceval resize : int -> t -> unit

resize cap t sets t's capacity to cap, while leaving the bindings unchanged.

Sourceval trim : t -> unit

trim t ensures that weight t <= capacity t by dropping bindings in LRU-to-MRU order.

Access by k

Sourceval mem : k -> t -> bool

mem k t is true iff k is bound in t.

Sourceval find : k -> t -> v option

find k t is Some v when k -> v is bound in t, or None otherwise.

Note This operation does not change the recently-used order.

Sourceval promote : k -> t -> unit

promote k t promotes the binding for k, if it exists, to most-recently-used.

Sourceval add : k -> v -> t -> unit

add k v t adds the binding k -> v to t as the most-recently-used binding.

Note add does not remove bindings. To ensure that the resulting map is not over capacity, combine with trim.

Sourceval remove : k -> t -> unit

remove k t is t without a binding for k.

Access to least-recently-used bindings

Sourceval lru : t -> (k * v) option

lru t is the least-recently-used binding in t, or None, when t is empty.

Sourceval drop_lru : t -> unit

drop_lru t removes the binding lru t.

Aggregate access

Sourceval fold : (k -> v -> 'a -> 'a) -> 'a -> t -> 'a

fold f z t is f k0 v0 (... (f kn vn z)), where k0 -> v0 is LRU and kn -> vn is MRU.

Sourceval iter : (k -> v -> unit) -> t -> unit

iter f t applies f to all the bindings in t in in LRU-to-MRU order.

Conversions

Sourceval of_list : (k * v) list -> t

of_list kvs is a map with bindings kvs, where the order of the list becomes LRU-to-MRU ordering, and its capacity is set to its weight.

The resulting t has the same shape as if the bindings were sequentially added in list order, except for capacity.

Sourceval to_list : t -> (k * v) list

to_list t are the bindings in t in LRU-to-MRU order.

Pretty-printing

Sourceval pp : ?pp_size:(Format.formatter -> (int * int) -> unit) -> ?sep:(Format.formatter -> unit -> unit) -> (Format.formatter -> (k * v) -> unit) -> Format.formatter -> t -> unit

pp ~pp_size ~sep pp_kv ppf t pretty-prints t to ppf, using pp_kv to print the bindings, ~sep to separate them, and ~pp_size to print the weight and capacity. ~sep and ~pp_size default to unspecified printers.