packages feed

ctrie 0.1.0.3 → 0.1.1.0

raw patch · 4 files changed

+56/−2 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

- Control.Concurrent.Map: instance (Eq k, Eq v) => Eq (SNode k v)
- Control.Concurrent.Map: instance (Show k, Show v) => Show (SNode k v)
+ Control.Concurrent.Map: insertIfAbsent :: (Eq k, Hashable k) => k -> v -> Map k v -> IO ()
+ Control.Concurrent.Map: instance (GHC.Classes.Eq v, GHC.Classes.Eq k) => GHC.Classes.Eq (Control.Concurrent.Map.SNode k v)
+ Control.Concurrent.Map: instance (GHC.Show.Show v, GHC.Show.Show k) => GHC.Show.Show (Control.Concurrent.Map.SNode k v)

Files

Control/Concurrent/Map.hs view
@@ -26,6 +26,7 @@       -- * Modification     , insert     , delete+    , insertIfAbsent        -- * Query     , lookup@@ -137,6 +138,52 @@                     unlessM (fst <$> casIORef inode ticket col') go0  {-# INLINABLE insert #-}++-- | /O(log n)/. Associate the given value with the given key.+-- If the key is already present in the map, don't change the value.+insertIfAbsent :: (Eq k, Hashable k) => k -> v -> Map k v -> IO ()+insertIfAbsent k v (Map root) = go0+    where+        h = hash k+        go0 = go 0 undefined root+        go lev parent inode = do+            ticket <- readForCAS inode+            case peekTicket ticket of+                CNode bmp arr -> do+                    let m = mask h lev+                        i = sparseIndex bmp m+                        n = popCount bmp+                    if bmp .&. m == 0+                        then do+                            let arr' = A.insert (SNode (S k v)) i n arr+                                cn'  = CNode (bmp .|. m) arr'+                            unlessM (fst <$> casIORef inode ticket cn') go0++                        else case A.index arr i of+                            SNode (S k2 v2)+                                | k == k2 -> return ()++                                | otherwise -> do+                                    let h2 = hash k2+                                    inode2 <- newINode h k v h2 k2 v2 (nextLevel lev)+                                    let arr' = A.update (INode inode2) i n arr+                                        cn'  = CNode bmp arr'+                                    unlessM (fst <$> casIORef inode ticket cn') go0++                            INode inode2 -> go (nextLevel lev) inode inode2++                Tomb _ -> clean parent (prevLevel lev) >> go0++                Collision arr -> +                    if any (\(S k2 _) -> k2 == k) arr+                        then return ()+                        else do+                            let arr' = S k v : filter (\(S k2 _) -> k2 /= k) arr+                                col' = Collision arr'+                            unlessM (fst <$> casIORef inode ticket col') go0++{-# INLINABLE insertIfAbsent #-}+  newINode :: Hash -> k -> v -> Hash -> k -> v -> Int -> IO (INode k v) newINode h1 k1 v1 h2 k2 v2 lev
changelog.md view
@@ -1,3 +1,6 @@+# 0.1.1.0 (April 2016)+	* Add insertIfAbsent (https://github.com/mcschroeder/ctrie/pull/2)+ # 0.1.0.3 (December 2015) 	* Eliminate a redundant import warning on GHC 7.10 	* Loosen dependency bounds
ctrie.cabal view
@@ -1,5 +1,5 @@ name:                ctrie-version:             0.1.0.3+version:             0.1.1.0 synopsis:            Non-blocking concurrent map description:   A non-blocking concurrent map implementation based on@@ -10,7 +10,7 @@ maintainer:          mc.schroeder@gmail.com homepage:            https://github.com/mcschroeder/ctrie bug-reports:         https://github.com/mcschroeder/ctrie/issues-copyright:           (c) 2013-2015 Michael Schröder+copyright:           (c) 2013-2016 Michael Schröder category:            Concurrency, Data Structures build-type:          Simple cabal-version:       >=1.8
tests/MapProperties.hs view
@@ -22,6 +22,7 @@                         [ testProperty "lookup" pLookup                         , testProperty "insert" pInsert                         , testProperty "delete" pDelete+                        , testProperty "insertIfAbsent" pInsertIfAbsent                         ]                      , testGroup "conversions"                         [ testProperty "fromList" pFromList@@ -77,6 +78,9 @@  pDelete :: Key -> [(Key,Int)] -> Property pDelete k = M.delete k `eq_` CM.delete k++pInsertIfAbsent :: Key -> Int -> [(Key,Int)] -> Property+pInsertIfAbsent k v = M.insertWith (\new old -> old) k v `eq_` CM.insertIfAbsent k v  pFromList :: [(Key,Int)] -> Property pFromList = id `eq_` (\_ -> return ())