package lru

  1. Overview
  2. Docs
On This Page
  1. Lru

Module Lru

Scalable LRU caches

Lru provides size-bounded finite maps that remove the least-recently-used (LRU) bindings in order to maintain the size constraint. Two implementations are provided: one is functional, the other imperative.

The functional map is backed by a priority search queue. Operations on individual elements are O(log n).

The mutable map is backed by the standard Hashtbl paired with a doubly-linked list. Operations on individual elements incur an O(1) overhead on top of hash table access.

Both versions support differentially weighted bindings, and have a capacity parameter that limits the combined weight of the bindings. To limit the maps by the number of bindings, use let weight _ = 1.

v0.1.1 — homepage

Lru

module type Ordered = sig ... end

Signature of ordered types.

module type Weighted = sig ... end

Signature of types with measurable weight.

module F : sig ... end

Functional LRU map.

module M : sig ... end

Mutable LRU map.