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

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

Sourceval is_empty : t -> bool

is_empty t is true iff t is empty.

Sourceval items : t -> int

items t is the number of bindings in t.

Sourceval size : t -> int

size t is the combined size of bindings in t.

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

Sourceval 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

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

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

Sourceval remove : k -> t -> unit

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

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

cache t f caches the results of f in t.

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.

Traversal direction

Sourcetype 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

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

Sourceval 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

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

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

Sourceval 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

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