-- 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. 3 - Added a Show instance for LRU.
    2. --
  2. 2.0.1 - Increase strictness slightly. Remove cabal target for test -- executable. (Just include test sources instead.)
    3. --
  3. 2 - Added an Eq instance for LRU. Added strictness to eliminate -- space leaks in common use patterns.
    4. --
  4. 1.1 - Add the Data.Cache.LRU.IO.Internal module. Clean up build -- warnings on GHC 6.12.1.
    5. --
  5. 1.0.1 - Minor refactoring
    6. --
  6. 1 - First release
    7. --
@package lrucache @version 0.3 -- | 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 -> !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 -> !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. The LRU is guaranteed to not grow above the specified -- number of entries. newLRU :: (Ord key) => 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) => 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, Bool) -- | 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 three 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. --
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 and lookup, and O(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. The LRU is guaranteed to not grow above the specified -- number of entries. newLRU :: (Ord key) => 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) => 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 -> 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, Bool) -- | 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 with the given maximum size. newAtomicLRU :: (Ord key) => Int -> IO (AtomicLRU key val) -- | Build a new LRU from the given maximum size and list of contents. See -- fromList for the semantics. fromList :: (Ord key) => Int -> [(key, val)] -> IO (AtomicLRU key val) -- | Retreive 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 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 whether the item was present -- to be removed. delete :: (Ord key) => key -> AtomicLRU key val -> IO Bool -- | Returns the number of elements the AtomicLRU currently contains. size :: AtomicLRU key val -> IO Int -- | A version of modifyMVar_ that applies the modification function -- strictly. modifyMVar_' :: MVar a -> (a -> IO a) -> IO () -- | A version of modifyMVar that applies the modification function -- strictly. The returned value is not evaluated strictly. 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 with the given maximum size. newAtomicLRU :: (Ord key) => Int -> IO (AtomicLRU key val) -- | Build a new LRU from the given maximum size and list of contents. See -- fromList for the semantics. fromList :: (Ord key) => Int -> [(key, val)] -> IO (AtomicLRU key val) -- | Retreive 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 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 whether the item was present -- to be removed. delete :: (Ord key) => key -> AtomicLRU key val -> IO Bool -- | Returns the number of elements the AtomicLRU currently contains. size :: AtomicLRU key val -> IO Int