ringo 1.1.0 · OCaml Package

Weighted_LRU_Collection is similar to LRU_Collection but comes with a notion of data weight as capacity instead of being based on the number of elements.

This differentiation allows building memory-bounded cache using a Least-Recently Used replacement policy.

Attempting to insert an element causes the least-recently promoted elements to be removed. The cache will remove as many elements as required so that the new element fits.

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 length : 'a t -> int

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

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

elements_data b is a list of the data content of the nodes of b. It is equivalent to List.map data (elements b) but with better performance.

val oldest_element : 'a t -> 'a node option

oldest_element b returns the oldest inserted element from the buffer b if any.

val newest_element : 'a t -> 'a node option

newest_element b returns the oldest inserted element from the buffer b if any.

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 remove_oldest : 'a t -> 'a node option

remove_oldest b removes and returns the oldest inserted element from the buffer b or None if the buffer is empty.

val remove_newest : 'a t -> 'a node option

remove_newest b removes and returns the most recently inserted element from the buffer b or None if the buffer is empty.

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 capacity : 'a t -> int

capacity b is the maximum weight that b can hold.

val weight : 'a node -> int

weight e returns the weight of the element e.

val total_weight : 'a t -> int

total_weight b is the summed weight of all elements that are currently in b.

val add : 'a t -> ('a * int) -> 'a node option

add b (v, w) adds the value v of weight w to the buffer b. If the buffer b cannot hold this value, i.e., w > capacity b then this value is not added. And, if by adding this value, the buffer would get too full, older values will be dropped until the v fits.

adds b (v, w) 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 * int) -> 'a node option * 'a list

add_and_return_erased b (v, w) has the same effect as add b (v,w) but it also returns the dropped values when applicable (and None otherwise). Dropped values are ordered from the oldest to the most recently inserted.

val add_list : 'a t -> ('a * int) list -> 'a node list

add_list b vs adds each element (with their weight) of the list vs in the order they appear in the list. It returns a list of nodes, for each of the inserted elements. Elements that are too large in vs w.r.t to capacity b are filtered out.

If the total weight of vs is larger than capacity b then a first-fit strategy is used and the last elements in vs are prioritized.

For instance: add_list (create 5) [(x, 1); (y, 3); (z, 4)] will successfully return [x ; z] which are added in the buffer.

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

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

package ringo