lrucaching 0.1.0 → 0.2.0

raw patch · 5 files changed

+23/−8 lines, 5 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• CHANGELOG.md +5/−0
• README.md +1/−0
• lrucaching.cabal +1/−1
• src/Data/LruCache.hs +15/−4
• src/Data/LruCache/Internal.hs +1/−3

@@ -1,3 +1,8 @@+0.2.0+----+* Don’t clear cache on clock overflow. This means that elements are+  never evicted without notifying the user via insertView.+ 0.1.0 ----- Initial release.

@@ -1,6 +1,7 @@ # lrucaching  [![Build Status](https://travis-ci.org/cocreature/lrucaching.svg?branch=master)](https://travis-ci.org/cocreature/lrucaching)+[![Hackage](https://img.shields.io/hackage/v/lrucaching.svg?maxAge=2592000)]()  An implementation of lrucaches based on a [blogpost](https://jaspervdj.be/posts/2015-02-24-lru-cache.html) by

@@ -1,5 +1,5 @@ name:                  lrucaching-version:               0.1.0+version:               0.2.0 synopsis:              LRU cache description:           Please see README.md homepage:              https://github.com/cocreature/lrucaching#readme

@@ -21,6 +21,7 @@  import qualified Data.HashPSQ as HashPSQ import           Data.Hashable (Hashable)+import           Data.List (sortOn) import           Data.Maybe (isNothing) import           Prelude hiding (lookup) @@ -39,12 +40,17 @@         }  -- | Restore 'LruCache' invariants returning the evicted element if any.------ When the logical clock reaches its maximum value and all values are--- evicted 'Nothing' is returned. trim' :: (Hashable k, Ord k) => LruCache k v -> (Maybe (k, v), LruCache k v) trim' c-  | lruTick c == maxBound     = (Nothing, empty (lruCapacity c))+  | lruTick c == maxBound     =+      -- It is not physically possible to have that many elements but+      -- the clock could potentially get here. We then simply decrease+      -- all priorities in O(nlogn) and start over.+      let queue' = HashPSQ.fromList . compress . HashPSQ.toList $ lruQueue c+      in trim' $!+           c { lruTick = fromIntegral (lruSize c)+             , lruQueue = queue'+             }   | lruSize c > lruCapacity c =        let Just (k, _, v) = HashPSQ.findMin (lruQueue c)           c' = c  { lruSize  = lruSize c - 1@@ -52,6 +58,11 @@                   }       in seq c' (Just (k, v), c')   | otherwise                 = (Nothing, c)++compress :: [(k,Priority,v)] -> [(k,Priority,v)]+compress q =+  let sortedQ = sortOn (\(_,p,_) -> p) q+  in zipWith (\(k,_,v) p -> (k,p,v)) sortedQ [1..]  -- TODO benchmark to see if this is actually faster than snd . trim' -- | Restore 'LruCache' invariants. For performance reasons this is

@@ -26,9 +26,7 @@ -- | Logical time at which an element was last accessed. type Priority = Int64 --- | LRU cache based on hashing. The times of access are stored in a--- monotonically increasing 'Int64', when that time is at 'maxbound'--- the cache is emptied.+-- | LRU cache based on hashing. data LruCache k v = LruCache   { lruCapacity :: !Int                         -- ^ The maximum number of elements in the queue   , lruSize :: !Int                             -- ^ The current number of elements in the queue