lrucache-0.2.0.1: a simple, pure LRU cache

Data.Cache.LRU.Internal

Description

This module provides access to all the internals use by the LRU type. This can be used to create data structures that violate the invariants the public interface maintains. Be careful when using this module. The valid function can be used to check if an LRU structure satisfies the invariants the public interface maintains.

If this degree of control isn't needed, consider using Data.Cache.LRU instead.

Synopsis

Documentation

data LRU key val Source

Stores the information that makes up an LRU cache

Constructors

LRU 

Fields

first :: !(Maybe key)

the key of the most recently accessed entry

last :: !(Maybe key)

the key of the least recently accessed entry

maxSize :: !Int

the maximum size of the LRU cache

content :: !(Map key (LinkedVal key val))

the backing Map

Instances

(Eq key, Eq val) => Eq (LRU key val) 

data LinkedVal key val Source

The values stored in the Map of the LRU cache. They embed a doubly-linked list through the values of the Map.

Constructors

Link 

Fields

value :: val

The actual value

prev :: !(Maybe key)

the key of the value before this one

next :: !(Maybe key)

the key of the value after this one

Instances

(Eq key, Eq val) => Eq (LinkedVal key val) 

newLRUSource

Arguments

:: Ord key 
=> Int

the maximum size of the LRU

-> LRU key val 

Make an LRU. The LRU is guaranteed to not grow above the specified number of entries.

fromListSource

Arguments

:: Ord key 
=> Int

the maximum size of the LRU

-> [(key, val)] 
-> LRU key val 

Build a new LRU from the given maximum size and list of contents, in order from most recently accessed to least recently accessed.

toList :: Ord key => LRU key val -> [(key, val)]Source

Retrieve a list view of an LRU. The items are returned in order from most recently accessed to least recently accessed.

insert :: Ord key => key -> val -> LRU key val -> LRU key valSource

Add an item to an LRU. If the key was already present in the LRU, the value is changed to the new value passed in. The item added is marked as the most recently accessed item in the LRU returned.

If this would cause the LRU to exceed its maximum size, the least recently used item is dropped from the cache.

lookup :: Ord key => key -> LRU key val -> (LRU key val, Maybe val)Source

Look up an item in an LRU. If it was present, it is marked as the most recently accesed in the returned LRU.

delete :: Ord key => key -> LRU key val -> (LRU key val, Bool)Source

Remove an item from an LRU. Returns the new LRU, and if the item was present to be removed.

size :: LRU key val -> IntSource

Returns the number of elements the LRU currently contains.

hit' :: Ord key => key -> LRU key val -> LRU key valSource

Internal function. The key passed in must be present in the LRU. Moves the item associated with that key to the most recently accessed position.

delete'Source

Arguments

:: Ord key 
=> key

The key must be present in the provided LRU

-> LRU key val

This is the LRU to modify

-> Map key (LinkedVal key val)

this is the Map from the previous argument, but with the key already removed from it. This isn't consistent yet, as it still might contain LinkedVals with pointers to the removed key.

-> LinkedVal key val

This is the LinkedVal that corresponds to the key in the passed in LRU. It is absent from the passed in map.

-> LRU key val 

An internal function used by insert (when the cache is full) and delete. This function has strict requirements on its arguments in order to work properly.

As this is intended to be an internal function, the arguments were chosen to avoid repeated computation, rather than for simplicity of calling this function.

adjust' :: Ord k => (a -> a) -> k -> Map k a -> Map k aSource

Internal function. This is very similar to adjust, with two major differences. First, it's strict in the application of the function, which is a huge win when working with this structure.

Second, it requires that the key be present in order to work. If the key isn't present, undefined will be inserted into the Map, which will cause problems later.

valid :: Ord key => LRU key val -> BoolSource

Internal function. This checks the three structural invariants of the LRU cache structure:

  1. The cache's size does not exceed the specified max size.
  2. The linked list through the nodes is consistent in both directions.
  3. The linked list contains the same number of nodes as the cache.