package lru

  1. Overview
  2. Docs

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

type t

A map.

type k = K.t

Keys in t.

type v = V.t

Values in t.

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

  • raises Invalid_argument

    when cap < 0.

val is_empty : t -> bool

is_empty t is true iff t is empty.

val items : t -> int

items t is the number of bindings in t.

val size : t -> int

size t is the combined weight of bindings in t.

val capacity : t -> int

capacity t is the maximum combined weight of bindings this map will hold before they start being discarded in least-recently-used order.

val trim : t -> unit

trim t discards bindings from t, if needed, until size t <= capacity t. The bindings are discarded in least-recently-used order.

val resize : int -> t -> unit

resize cap t changes the capacity of t to cap, while leavind the bindings unchanged.

  • raises Invalid_argument

    when cap < 0.

Access by k

val mem : k -> t -> bool

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

val find : ?promote:bool -> k -> t -> v option

find k t is the v bound to k. When k is not bound in t, the result is None.

If promote is true, the binding k -> v is promoted to most-recently-used. It defaults to true.

val add : ?trim:bool -> k -> v -> t -> unit

add k v t adds the binding k -> v to t. If k is alread bound, the old binding is replaced. The binding k -> v becomes most-recently-used.

If trim is true, add trims the resulting map, ensuring it is not over capacity. It defaults to true.

val remove : k -> t -> unit

remove k m removes the binding for k, if one exists.

Access to least-recently-used bindings

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

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

val drop_lru : t -> unit

drop_lru t removes the binding lru t.

Traversal direction

type dir = [
  1. | `Up
  2. | `Down
]

Traversal direction for operations that visit all bindings.

  • `Up means least-to-most recently used, or increasing relevance.
  • `Down means most-to-least recently used, or decreasing relevance.

Aggregate access

val fold : ?dir:dir -> (k -> v -> 'a -> 'a) -> 'a -> t -> 'a

fold f z t is f k0 v0 (... (f kn vn z)).

~dir controls the order of folding. Defaults to `Up.

val iter : ?dir:dir -> (k -> v -> unit) -> t -> unit

iter f t applies f to all the bindings in t.

~dir controls the order of application. Defaults to `Up.

Conversions

val to_list : ?dir:dir -> t -> (k * v) list

to_list t are the bindings in t. ~dir controls the order, defaults to `Up.

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

of_list kvs is a map with the bindings from kvs. Its size and capacity are the total weight of its bindings.

With respect to duplicates and the recently-used order, it behaves as if the bindings were added sequentially in the list order.

Pretty-printing

val 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 size and capacity. ~sep and ~pp_size default to unspecified printers.