-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | a simple, pure LRU cache -- -- This package contains a simple, pure LRU cache, implemented in terms -- of Data.Map. -- -- It also contains a mutable IO wrapper providing atomic updates to an -- LRU cache. -- -- Version History: -- --
    --
  1. 0 - Breaking API changes: 1) The newLRU smart constructor now -- makes the maximum size optional. 2) The delete function now returns -- the value removed, if one was. Additionally, a function was added to -- remove the least-recently used element in the LRU.
    2. --
  2. 3 - Added a Show instance for LRU. (Requested by Ben Lee)
    3. --
  3. 2.0.1 - Increase strictness slightly. Remove cabal target for test -- executable. (Just include test sources instead.)
    4. --
  4. 2 - Added an Eq instance for LRU. Added strictness to eliminate -- space leaks in common use patterns.
    5. --
  5. 1.1 - Add the Data.Cache.LRU.IO.Internal module. Clean up build -- warnings on GHC 6.12.1.
    6. --
  6. 1.0.1 - Minor refactoring
    7. --
  7. 1 - First release
    8. --
@package lrucache @version 1.0 -- | 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. module Data.Cache.LRU.Internal -- | Stores the information that makes up an LRU cache data LRU key val LRU :: !Maybe key -> !Maybe key -> !Maybe Int -> !Map key (LinkedVal key val) -> LRU key val -- | the key of the most recently accessed entry first :: LRU key val -> !Maybe key -- | the key of the least recently accessed entry last :: LRU key val -> !Maybe key -- | the maximum size of the LRU cache maxSize :: LRU key val -> !Maybe Int -- | the backing Map content :: LRU key val -> !Map key (LinkedVal key val) -- | The values stored in the Map of the LRU cache. They embed a -- doubly-linked list through the values of the Map. data LinkedVal key val Link :: val -> !Maybe key -> !Maybe key -> LinkedVal key val -- | The actual value value :: LinkedVal key val -> val -- | the key of the value before this one prev :: LinkedVal key val -> !Maybe key -- | the key of the value after this one next :: LinkedVal key val -> !Maybe key -- | Make an LRU. If a size limit is specified, the LRU is guaranteed to -- not grow above the specified number of entries. newLRU :: (Ord key) => Maybe Int -> 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. fromList :: (Ord key) => Maybe Int -> [(key, val)] -> LRU key val -- | Retrieve a list view of an LRU. The items are returned in order from -- most recently accessed to least recently accessed. toList :: (Ord key) => LRU key val -> [(key, val)] -- | 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. insert :: (Ord key) => key -> val -> LRU key val -> LRU key val -- | Look up an item in an LRU. If it was present, it is marked as the most -- recently accesed in the returned LRU. lookup :: (Ord key) => key -> LRU key val -> (LRU key val, Maybe val) -- | Remove an item from an LRU. Returns the new LRU, and if the item was -- present to be removed. delete :: (Ord key) => key -> LRU key val -> (LRU key val, Maybe val) -- | 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. pop :: (Ord key) => LRU key val -> (LRU key val, Maybe (key, val)) -- | Returns the number of elements the LRU currently contains. size :: LRU key val -> Int -- | 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. hit' :: (Ord key) => key -> LRU key val -> 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. delete' :: (Ord key) => key -> LRU key val -> Map key (LinkedVal key val) -> LinkedVal key val -> LRU key val -- | 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. adjust' :: (Ord k) => (a -> a) -> k -> Map k a -> Map k a -- | 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. --
  2. The linked list through the nodes is consistent in both -- directions.
    3. --
  3. The linked list contains the same number of nodes as the -- cache.
    4. --
  4. Every key in the linked list is in the Map.
    5. --
valid :: (Ord key) => LRU key val -> Bool instance (Eq key, Eq val) => Eq (LinkedVal key val) instance (Eq key, Eq val) => Eq (LRU key val) instance (Ord key, Show key, Show val) => Show (LRU key val) -- | Implements an LRU cache. -- -- This module provides a pure LRU cache based on a doubly-linked list -- through a Data.Map structure. This gives O(log n) operations on -- insert, lookup, delete, and pop, and O(n * -- log n) for toList. -- -- The interface this module provides is opaque. If further control is -- desired, the Data.Cache.LRU.Internal module can be used. module Data.Cache.LRU -- | Stores the information that makes up an LRU cache data 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. newLRU :: (Ord key) => Maybe Int -> 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. fromList :: (Ord key) => Maybe Int -> [(key, val)] -> LRU key val -- | Retrieve a list view of an LRU. The items are returned in order from -- most recently accessed to least recently accessed. toList :: (Ord key) => LRU key val -> [(key, val)] -- | the maximum size of the LRU cache maxSize :: LRU key val -> (Maybe Int) -- | 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. insert :: (Ord key) => key -> val -> LRU key val -> LRU key val -- | Look up an item in an LRU. If it was present, it is marked as the most -- recently accesed in the returned LRU. lookup :: (Ord key) => key -> LRU key val -> (LRU key val, Maybe val) -- | Remove an item from an LRU. Returns the new LRU, and if the item was -- present to be removed. delete :: (Ord key) => key -> LRU key val -> (LRU key val, Maybe val) -- | 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. pop :: (Ord key) => LRU key val -> (LRU key val, Maybe (key, val)) -- | Returns the number of elements the LRU currently contains. size :: LRU key val -> Int -- | This module contains a mutable wrapping of an LRU in the IO monad, -- providing atomic access in a concurrent environment. All calls -- preserve the same semantics as those in Data.Cache.LRU, but -- perform updates in place. -- -- This module contains the internal implementation details. It's -- possible to put an AtomicLRU into a bad state with this module. -- It is highly recommended that the external interface, -- Data.Cache.LRU.IO, be used instead. module Data.Cache.LRU.IO.Internal -- | The opaque wrapper type newtype AtomicLRU key val C :: (MVar (LRU key val)) -> AtomicLRU key val -- | Make a new AtomicLRU that will not grow beyond the optional maximum -- size, if specified. newAtomicLRU :: (Ord key) => Maybe Int -> IO (AtomicLRU key val) -- | Build a new LRU from the optional maximum size and list of contents. -- See fromList for the semantics. fromList :: (Ord key) => Maybe Int -> [(key, val)] -> IO (AtomicLRU key val) -- | Retrieve a list view of an AtomicLRU. See toList for the -- semantics. toList :: (Ord key) => AtomicLRU key val -> IO [(key, val)] maxSize :: AtomicLRU key val -> IO (Maybe Int) -- | Insert a key/value pair into an AtomicLRU. See insert for the -- semantics. insert :: (Ord key) => key -> val -> AtomicLRU key val -> IO () -- | Look up a key in an AtomicLRU. See lookup for the semantics. lookup :: (Ord key) => key -> AtomicLRU key val -> IO (Maybe val) -- | Remove an item from an AtomicLRU. Returns the value for the removed -- key, if it was present delete :: (Ord key) => key -> AtomicLRU key val -> IO (Maybe val) -- | Remove the least-recently accessed item from an AtomicLRU. Returns the -- (key, val) pair removed, if one was present. pop :: (Ord key) => AtomicLRU key val -> IO (Maybe (key, val)) -- | Returns the number of elements the AtomicLRU currently contains. size :: AtomicLRU key val -> IO Int -- | A version of modifyMVar_ that forces the result of the function -- application to WHNF. modifyMVar_' :: MVar a -> (a -> IO a) -> IO () -- | A version of modifyMVar that forces the result of the function -- application to WHNF. modifyMVar' :: MVar a -> (a -> IO (a, b)) -> IO b -- | This module contains a mutable wrapping of an LRU in the IO monad, -- providing atomic access in a concurrent environment. All calls -- preserve the same semantics as those in Data.Cache.LRU, but -- perform updates in place. -- -- The interface this module provides is opaque. If further control is -- desired, the Data.Cache.LRU.IO.Internal module can be used in -- combination with Data.Cache.LRU.Internal. -- -- (This implementation uses an MVar for coarse locking. It's unclear if -- anything else would give better performance, given that many calls -- alter the head of the access list.) module Data.Cache.LRU.IO -- | The opaque wrapper type data AtomicLRU key val -- | Make a new AtomicLRU that will not grow beyond the optional maximum -- size, if specified. newAtomicLRU :: (Ord key) => Maybe Int -> IO (AtomicLRU key val) -- | Build a new LRU from the optional maximum size and list of contents. -- See fromList for the semantics. fromList :: (Ord key) => Maybe Int -> [(key, val)] -> IO (AtomicLRU key val) -- | Retrieve a list view of an AtomicLRU. See toList for the -- semantics. toList :: (Ord key) => AtomicLRU key val -> IO [(key, val)] maxSize :: AtomicLRU key val -> IO (Maybe Int) -- | Insert a key/value pair into an AtomicLRU. See insert for the -- semantics. insert :: (Ord key) => key -> val -> AtomicLRU key val -> IO () -- | Look up a key in an AtomicLRU. See lookup for the semantics. lookup :: (Ord key) => key -> AtomicLRU key val -> IO (Maybe val) -- | Remove an item from an AtomicLRU. Returns the value for the removed -- key, if it was present delete :: (Ord key) => key -> AtomicLRU key val -> IO (Maybe val) -- | Remove the least-recently accessed item from an AtomicLRU. Returns the -- (key, val) pair removed, if one was present. pop :: (Ord key) => AtomicLRU key val -> IO (Maybe (key, val)) -- | Returns the number of elements the AtomicLRU currently contains. size :: AtomicLRU key val -> IO Int