lrucache-1.2.0.1: a simple, pure LRU cache

Safe Haskell | Safe-Inferred
Language | Haskell98

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

- data LRU key val = LRU {
  - first :: !(Maybe key)
  - last :: !(Maybe key)
  - maxSize :: !(Maybe Integer)
  - content :: !(Map key (LinkedVal key val))
  }
- data LinkedVal key val = Link {
  - value :: val
  - prev :: !(Maybe key)
  - next :: !(Maybe key)
  }
- newLRU :: Ord key => Maybe Integer -> LRU key val
- fromList :: Ord key => Maybe Integer -> [(key, val)] -> LRU key val
- toList :: Ord key => LRU key val -> [(key, val)]
- pairs :: (Ord key, Applicative f, Contravariant f) => ((key, val) -> f (key, val)) -> LRU key val -> f (LRU key val)
- keys :: (Ord key, Applicative f, Contravariant f) => (key -> f key) -> LRU key val -> f (LRU key val)
- insert :: Ord key => key -> val -> LRU key val -> LRU key val
- insertInforming :: Ord key => key -> val -> LRU key val -> (LRU key val, Maybe (key, val))
- lookup :: Ord key => key -> LRU key val -> (LRU key val, Maybe val)
- delete :: Ord key => key -> LRU key val -> (LRU key val, Maybe val)
- pop :: Ord key => LRU key val -> (LRU key val, Maybe (key, val))
- size :: LRU key val -> Int
- hit' :: Ord key => key -> LRU key val -> LRU key val
- delete' :: Ord key => key -> LRU key val -> Map key (LinkedVal key val) -> LinkedVal key val -> LRU key val
- adjust' :: Ord k => (a -> a) -> k -> Map k a -> Map k a
- valid :: Ord key => LRU key val -> Bool

# 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 :: !(Maybe Integer)

  the maximum size of the LRU cache

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

  the backing `Map`

#### Instances

Instances details

Functor (LRU key) Source # |
Instance details Defined in Data.Cache.LRU.Internal Methods fmap :: (a -> b) -> LRU key a -> LRU key b Source # (<$) :: a -> LRU key b -> LRU key a Source #
Ord key => Foldable (LRU key) Source # |

Instance details

Defined in Data.Cache.LRU.Internal

Methods

fold :: Monoid m => LRU key m -> m Source #

foldMap :: Monoid m => (a -> m) -> LRU key a -> m Source #

foldMap' :: Monoid m => (a -> m) -> LRU key a -> m Source #

foldr :: (a -> b -> b) -> b -> LRU key a -> b Source #

foldr' :: (a -> b -> b) -> b -> LRU key a -> b Source #

foldl :: (b -> a -> b) -> b -> LRU key a -> b Source #

foldl' :: (b -> a -> b) -> b -> LRU key a -> b Source #

foldr1 :: (a -> a -> a) -> LRU key a -> a Source #

foldl1 :: (a -> a -> a) -> LRU key a -> a Source #

toList :: LRU key a -> [a] Source #

null :: LRU key a -> Bool Source #

length :: LRU key a -> Int Source #

elem :: Eq a => a -> LRU key a -> Bool Source #

maximum :: Ord a => LRU key a -> a Source #

minimum :: Ord a => LRU key a -> a Source #

sum :: Num a => LRU key a -> a Source #

product :: Num a => LRU key a -> a Source #

Ord key => Traversable (LRU key) Source # |
Instance details Defined in Data.Cache.LRU.Internal Methods traverse :: Applicative f => (a -> f b) -> LRU key a -> f (LRU key b) Source # sequenceA :: Applicative f => LRU key (f a) -> f (LRU key a) Source # mapM :: Monad m => (a -> m b) -> LRU key a -> m (LRU key b) Source # sequence :: Monad m => LRU key (m a) -> m (LRU key a) Source #
(Data key, Data val, Ord key) => Data (LRU key val) Source # |

Instance details

Defined in Data.Cache.LRU.Internal

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> LRU key val -> c (LRU key val) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (LRU key val) Source #

toConstr :: LRU key val -> Constr Source #

dataTypeOf :: LRU key val -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (LRU key val)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (LRU key val)) Source #

gmapT :: (forall b. Data b => b -> b) -> LRU key val -> LRU key val Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> LRU key val -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> LRU key val -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> LRU key val -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> LRU key val -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> LRU key val -> m (LRU key val) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> LRU key val -> m (LRU key val) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> LRU key val -> m (LRU key val) Source #

(Ord key, Show key, Show val) => Show (LRU key val) Source # |
Instance details Defined in Data.Cache.LRU.Internal Methods showsPrec :: Int -> LRU key val -> ShowS Source # show :: LRU key val -> String Source # showList :: [LRU key val] -> ShowS Source #
(Eq key, Eq val) => Eq (LRU key val) Source # |
Instance details Defined in Data.Cache.LRU.Internal Methods (==) :: LRU key val -> LRU key val -> Bool Source # (/=) :: LRU key val -> LRU key val -> Bool Source #

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

Instances details

Functor (LinkedVal key) Source # |
Instance details Defined in Data.Cache.LRU.Internal Methods fmap :: (a -> b) -> LinkedVal key a -> LinkedVal key b Source # (<$) :: a -> LinkedVal key b -> LinkedVal key a Source #
Foldable (LinkedVal key) Source # |

Instance details

Defined in Data.Cache.LRU.Internal

Methods

fold :: Monoid m => LinkedVal key m -> m Source #

foldMap :: Monoid m => (a -> m) -> LinkedVal key a -> m Source #

foldMap' :: Monoid m => (a -> m) -> LinkedVal key a -> m Source #

foldr :: (a -> b -> b) -> b -> LinkedVal key a -> b Source #

foldr' :: (a -> b -> b) -> b -> LinkedVal key a -> b Source #

foldl :: (b -> a -> b) -> b -> LinkedVal key a -> b Source #

foldl' :: (b -> a -> b) -> b -> LinkedVal key a -> b Source #

foldr1 :: (a -> a -> a) -> LinkedVal key a -> a Source #

foldl1 :: (a -> a -> a) -> LinkedVal key a -> a Source #

toList :: LinkedVal key a -> [a] Source #

null :: LinkedVal key a -> Bool Source #

length :: LinkedVal key a -> Int Source #

elem :: Eq a => a -> LinkedVal key a -> Bool Source #

maximum :: Ord a => LinkedVal key a -> a Source #

minimum :: Ord a => LinkedVal key a -> a Source #

sum :: Num a => LinkedVal key a -> a Source #

product :: Num a => LinkedVal key a -> a Source #

Traversable (LinkedVal key) Source # |
Instance details Defined in Data.Cache.LRU.Internal Methods traverse :: Applicative f => (a -> f b) -> LinkedVal key a -> f (LinkedVal key b) Source # sequenceA :: Applicative f => LinkedVal key (f a) -> f (LinkedVal key a) Source # mapM :: Monad m => (a -> m b) -> LinkedVal key a -> m (LinkedVal key b) Source # sequence :: Monad m => LinkedVal key (m a) -> m (LinkedVal key a) Source #
(Data key, Data val) => Data (LinkedVal key val) Source # |

Instance details

Defined in Data.Cache.LRU.Internal

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> LinkedVal key val -> c (LinkedVal key val) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (LinkedVal key val) Source #

toConstr :: LinkedVal key val -> Constr Source #

dataTypeOf :: LinkedVal key val -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (LinkedVal key val)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (LinkedVal key val)) Source #

gmapT :: (forall b. Data b => b -> b) -> LinkedVal key val -> LinkedVal key val Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> LinkedVal key val -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> LinkedVal key val -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> LinkedVal key val -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> LinkedVal key val -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> LinkedVal key val -> m (LinkedVal key val) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> LinkedVal key val -> m (LinkedVal key val) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> LinkedVal key val -> m (LinkedVal key val) Source #

(Eq val, Eq key) => Eq (LinkedVal key val) Source # |
Instance details Defined in Data.Cache.LRU.Internal Methods (==) :: LinkedVal key val -> LinkedVal key val -> Bool Source # (/=) :: LinkedVal key val -> LinkedVal key val -> Bool Source #

newLRU Source #

Arguments

:: Ord key |
=> Maybe Integer | the optional maximum size of the LRU
-> LRU key val |

Make an LRU. If a size limit is specified, the LRU is guaranteed to not grow above the specified number of entries.

fromList Source #

Arguments

:: Ord key |
=> Maybe Integer | the optional 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.

pairs :: (Ord key, Applicative f, Contravariant f) => ((key, val) -> f (key, val)) -> LRU key val -> f (LRU key val) Source #

Traverse the (key, value) pairs of the LRU, in a read-only way. This is a `Fold` in the sense used by the lens package. It must be read-only because alterations could break the underlying `Map` structure.

keys :: (Ord key, Applicative f, Contravariant f) => (key -> f key) -> LRU key val -> f (LRU key val) Source #

Traverse the keys of the LRU, in a read-only way. This is a `Fold` in the sense used by the lens package. It must be read-only because alterations could break the underlying `Map` structure.

insert :: Ord key => key -> val -> LRU key val -> LRU key val Source #

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.

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

Same as `insert`, but also returns element which was dropped from cache, if any.

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, Maybe val) Source #

Remove an item from an LRU. Returns the new LRU, and the value removed if the key was present.

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

Removes the least-recently accessed element from the LRU. Returns the new LRU, and the key and value from the least-recently used element, if there was one.

size :: LRU key val -> Int Source #

Returns the number of elements the LRU currently contains.

hit' :: Ord key => key -> LRU key val -> LRU key val Source #

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 a Source #

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 -> Bool Source #

Internal function. This checks the four 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.
4. Every key in the linked list is in the `Map`.