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.
- data LRU key val = LRU {}
- data LinkedVal key val = Link {}
- newLRU :: Ord key => Int -> LRU key val
- fromList :: Ord key => Int -> [(key, val)] -> LRU key val
- toList :: Ord key => LRU key val -> [(key, val)]
- insert :: Ord key => key -> val -> LRU key val -> LRU key val
- lookup :: Ord key => key -> LRU key val -> (LRU key val, Maybe val)
- delete :: Ord key => key -> LRU key val -> (LRU key val, Bool)
- size :: LRU key val -> Int
- hit' :: Ord key => key -> LRU key val -> LRU key val
- valid :: Ord key => LRU key val -> Bool
Documentation
Stores the information that makes up an LRU cache
The values stored in the Map of the LRU cache. They embed a
doubly-linked list through the values of the Map
.
Make an LRU. The LRU is guaranteed to not grow above the specified number of entries.
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.
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.
valid :: Ord key => LRU key val -> BoolSource
Internal function. This checks the three structural invariants of the LRU cache structure:
- The cache's size does not exceed the specified max size.
- The linked list through the nodes is consistent in both directions.
- The linked list contains the same number of nodes as the cache.