package lru

  1. Overview
  2. Docs

Module M.Make

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, and defaults to false. See Hashtbl.create.

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 size 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 resize : int -> t -> unit

resize cap t will change the capacity of t to cap. If the current size is greater than cap, least-recently-used elements are discarded to fit cap.

Access by k

val mem : k -> t -> bool

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

val find : k -> t -> v option

find k t is the v bound to k. The binding k -> v is promoted to most-recently-used. When k is not bound in t, the result is None.

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

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

val remove : k -> t -> unit

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

val cache : t -> (k -> v) -> k -> v

cache t f caches the results of f in t.

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 : ?cap:int -> (k * v) list -> t

of_list kvs is a new map with the bindings from kvs. If there are multiple bindings for k, the right-most is chosen.

~cap is the capacity of the new map. It defaults to the total weight of bindings in kvs. If given, and smaller than total weight of vs, bindings are discarded from the left of the list.

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.