ringo 1.0.0 · OCaml Package

LRU_Collection is a COLLECTION meant to be used as a building block in a cache: specifically a cache with a Least-Recently Used replacement policy.

Attempting to insert a supernumerary element causes the least-recently promoted element to be removed. Thus, the cache implementation simply needs to use promote_read and promote_write according to cache accesses to obtain an LRU replacement policy.

In addition, accounting in LRU_Collection is precise: removed elements never count towards the length-limit.

type 'a t

The type of bounded-size buffers.

type 'a node

nodes are boxes that contain data. Boxes are never meant to be returned to the end user (they can be unsafe), they are meant to build some abstraction on top of the buffer.

In order to make the module safe and remove all notion of box, use the functor Misc.Unbox.

val data : 'a node -> 'a

data n is the value contained in the node n.

val create : int -> 'a t

create n allocates a buffer that can hold up to n elements.

raises [Invalid_argument]
if n is 0 or less.

val capacity : 'a t -> int

capacity b is the number of elements that b can hold.

val length : 'a t -> int

length b is the number of elements that are currently in b.

val add : 'a t -> 'a -> 'a node

add b v adds the value v to the buffer b. If the buffer b already has capacity b values, then a value is dropped.

adds b v returns the node containing the value v. This node can be used to promote or remove the value v from the buffer b.

val add_and_return_erased : 'a t -> 'a -> 'a node * 'a option

add_and_return_erased b v has the same effect as add b v but it returns the dropped value when applicable (and None otherwise).

val add_list : 'a t -> 'a list -> 'a node list

add_list b vs adds each element of the list vs in the order they appear in the list. It returns a list of nodes, for each of the inserted elements.

If length vs > capacity b, then each value from vs is added, but the ones at the front of the list are popped. In this case, add_list b vs returns a list of capacity b nodes only.

val clear : 'a t -> unit

clear b removes all values from the buffer b.

val fold : 'a t -> init:'b -> f:('b -> 'a node -> 'b) -> 'b

fold b ~init ~f folds over the value of the buffer b, newest to oldest.

val fold_oldest_first : 'a t -> init:'b -> f:('b -> 'a node -> 'b) -> 'b

fold_oldest_first b ~init ~f folds over the value of the buffer b, oldest to newest.

val elements : 'a t -> 'a node list

elements b is a list of nodes from b. They appear oldest first, newest last.

val elements_data : 'a t -> 'a list

val remove : 'a t -> 'a node -> unit

remove b n removes the node n from the buffer b.

The behavior of this function is undefined if n is not part of b, i.e., if List.exists ((==) n) (elements b) is false.

It is the responsibility of the user of this library (presumably, another library wrapping the primitives of this one) to ensure this is never the case.

val promote : 'a t -> 'a node -> unit

promote b n places the node n to the front of the buffer b, making the node n the newest of the nodes of the buffer b.

promote b n is similar to remove b n; ignore (add b @@ data n) except that: it is more efficient, and it keeps the value data n in the same node it was originally inserted in.

The behavior of this function is undefined if n is not part of b, i.e., if List.exists ((==) n) (elements b) is false.

val promote_read : 'a t -> 'a node -> unit

val promote_write : 'a t -> 'a node -> unit

package ringo