mutable-containers 0.2.1.2 → 0.3.0

raw patch · 6 files changed

+111/−107 lines, 6 files

Files

ChangeLog.md +4/−0
Data/Mutable.hs +3/−3
Data/Mutable/DLList.hs +101/−0
Data/Mutable/DList.hs +0/−101
mutable-containers.cabal +2/−2
test/Spec.hs +1/−1

ChangeLog.md view

@@ -1,3 +1,7 @@+## 0.3.0++* Rename `DList` to `DLList` to avoid conflict with difference lists+ ## 0.2.1.2  * `Deque` optimizations by avoiding modulus operations completely.

Data/Mutable.hs view

@@ -28,8 +28,8 @@     , asSDeque     , BDeque     , asBDeque-    , DList-    , asDList+    , DLList+    , asDLList       -- * Type classes     , MutableContainer (..)     , MutableRef (..)@@ -58,7 +58,7 @@ import Data.Mutable.PRef import Data.Mutable.BRef import Data.Mutable.Deque-import Data.Mutable.DList+import Data.Mutable.DLList import Data.Vector.Unboxed (Unbox) import Data.Primitive (Prim) import Data.Vector.Storable (Storable)

+ Data/Mutable/DLList.hs view

@@ -0,0 +1,101 @@+{-# LANGUAGE TypeFamilies #-}+-- | Doubly-linked list+module Data.Mutable.DLList+    ( DLList+    , asDLList+    , module Data.Mutable.Class+    ) where++import Data.Mutable.Class++data Node s a = Node+    a+    (MutVar s (Maybe (Node s a))) -- previous+    (MutVar s (Maybe (Node s a))) -- next++-- | A doubly-linked list.+--+-- Since 0.3.0+data DLList s a = DLList (MutVar s (Maybe (Node s a))) (MutVar s (Maybe (Node s a)))++-- |+-- Since 0.2.0+asDLList :: DLList s a -> DLList s a+asDLList = id+{-# INLINE asDLList #-}++instance MutableContainer (DLList s a) where+    type MCState (DLList s a) = s+instance MutableCollection (DLList s a) where+    type CollElement (DLList s a) = a+    newColl = do+        x <- newRef $! Nothing+        y <- newRef $! Nothing+        return $! DLList x y+    {-# INLINE newColl #-}+instance MutablePopFront (DLList s a) where+    popFront (DLList frontRef backRef) = do+        mfront <- readRef frontRef+        case mfront of+            Nothing -> return Nothing+            Just (Node val _ nextRef) -> do+                mnext <- readRef nextRef+                case mnext of+                    Nothing -> do+                        writeRef frontRef $! Nothing+                        writeRef backRef $! Nothing+                    Just next@(Node _ prevRef _) -> do+                        writeRef prevRef $! Nothing+                        writeRef frontRef $! Just next+                return $ Just val+    {-# INLINE popFront #-}+instance MutablePopBack (DLList s a) where+    popBack (DLList frontRef backRef) = do+        mback <- readRef backRef+        case mback of+            Nothing -> return Nothing+            Just (Node val prevRef _) -> do+                mprev <- readRef prevRef+                case mprev of+                    Nothing -> do+                        writeRef frontRef $! Nothing+                        writeRef backRef $! Nothing+                    Just prev@(Node _ _ nextRef) -> do+                        writeRef nextRef $! Nothing+                        writeRef backRef (Just prev)+                return $ Just val+    {-# INLINE popBack #-}+instance MutablePushFront (DLList s a) where+    pushFront (DLList frontRef backRef) val = do+        mfront <- readRef frontRef+        case mfront of+            Nothing -> do+                prevRef <- newRef $! Nothing+                nextRef <- newRef $! Nothing+                let node = Just $ Node val prevRef nextRef+                writeRef frontRef node+                writeRef backRef node+            Just front@(Node _ prevRef _) -> do+                prevRefNew <- newRef $! Nothing+                nextRef <- newRef $ Just front+                let node = Just $ Node val prevRefNew nextRef+                writeRef prevRef node+                writeRef frontRef node+    {-# INLINE pushFront #-}+instance MutablePushBack (DLList s a) where+    pushBack (DLList frontRef backRef) val = do+        mback <- readRef backRef+        case mback of+            Nothing -> do+                prevRef <- newRef $! Nothing+                nextRef <- newRef $! Nothing+                let node = Just $! Node val prevRef nextRef+                writeRef frontRef $! node+                writeRef backRef $! node+            Just back@(Node _ _ nextRef) -> do+                nextRefNew <- newRef $! Nothing+                prevRef <- newRef $! Just back+                let node = Just $! Node val prevRef nextRefNew+                writeRef nextRef $! node+                writeRef backRef $! node+    {-# INLINE pushBack #-}

− Data/Mutable/DList.hs

@@ -1,101 +0,0 @@-{-# LANGUAGE TypeFamilies #-}--- | Doubly-linked list-module Data.Mutable.DList-    ( DList-    , asDList-    , module Data.Mutable.Class-    ) where--import Data.Mutable.Class--data Node s a = Node-    a-    (MutVar s (Maybe (Node s a))) -- previous-    (MutVar s (Maybe (Node s a))) -- next---- | A doubly-linked list.------ Since 0.2.0-data DList s a = DList (MutVar s (Maybe (Node s a))) (MutVar s (Maybe (Node s a)))---- |--- Since 0.2.0-asDList :: DList s a -> DList s a-asDList = id-{-# INLINE asDList #-}--instance MutableContainer (DList s a) where-    type MCState (DList s a) = s-instance MutableCollection (DList s a) where-    type CollElement (DList s a) = a-    newColl = do-        x <- newRef $! Nothing-        y <- newRef $! Nothing-        return $! DList x y-    {-# INLINE newColl #-}-instance MutablePopFront (DList s a) where-    popFront (DList frontRef backRef) = do-        mfront <- readRef frontRef-        case mfront of-            Nothing -> return Nothing-            Just (Node val _ nextRef) -> do-                mnext <- readRef nextRef-                case mnext of-                    Nothing -> do-                        writeRef frontRef $! Nothing-                        writeRef backRef $! Nothing-                    Just next@(Node _ prevRef _) -> do-                        writeRef prevRef $! Nothing-                        writeRef frontRef $! Just next-                return $ Just val-    {-# INLINE popFront #-}-instance MutablePopBack (DList s a) where-    popBack (DList frontRef backRef) = do-        mback <- readRef backRef-        case mback of-            Nothing -> return Nothing-            Just (Node val prevRef _) -> do-                mprev <- readRef prevRef-                case mprev of-                    Nothing -> do-                        writeRef frontRef $! Nothing-                        writeRef backRef $! Nothing-                    Just prev@(Node _ _ nextRef) -> do-                        writeRef nextRef $! Nothing-                        writeRef backRef (Just prev)-                return $ Just val-    {-# INLINE popBack #-}-instance MutablePushFront (DList s a) where-    pushFront (DList frontRef backRef) val = do-        mfront <- readRef frontRef-        case mfront of-            Nothing -> do-                prevRef <- newRef $! Nothing-                nextRef <- newRef $! Nothing-                let node = Just $ Node val prevRef nextRef-                writeRef frontRef node-                writeRef backRef node-            Just front@(Node _ prevRef _) -> do-                prevRefNew <- newRef $! Nothing-                nextRef <- newRef $ Just front-                let node = Just $ Node val prevRefNew nextRef-                writeRef prevRef node-                writeRef frontRef node-    {-# INLINE pushFront #-}-instance MutablePushBack (DList s a) where-    pushBack (DList frontRef backRef) val = do-        mback <- readRef backRef-        case mback of-            Nothing -> do-                prevRef <- newRef $! Nothing-                nextRef <- newRef $! Nothing-                let node = Just $! Node val prevRef nextRef-                writeRef frontRef $! node-                writeRef backRef $! node-            Just back@(Node _ _ nextRef) -> do-                nextRefNew <- newRef $! Nothing-                prevRef <- newRef $! Just back-                let node = Just $! Node val prevRef nextRefNew-                writeRef nextRef $! node-                writeRef backRef $! node-    {-# INLINE pushBack #-}

mutable-containers.cabal view

@@ -1,5 +1,5 @@ name:                mutable-containers-version:             0.2.1.2+version:             0.3.0 synopsis:            Abstactions and concrete implementations of mutable containers description:         See docs and README at <http://www.stackage.org/package/mutable-containers> homepage:            https://github.com/fpco/mutable-containers@@ -19,7 +19,7 @@                        Data.Mutable.URef                        Data.Mutable.PRef                        Data.Mutable.BRef-                       Data.Mutable.DList+                       Data.Mutable.DLList                        Data.Mutable.Deque   build-depends:       base >= 4.7 && < 5                      , primitive

test/Spec.hs view

@@ -90,7 +90,7 @@         test "UDeque" asUDeque         test "SDeque" asSDeque         test "BDeque" asBDeque-        test "DList" asDList+        test "DLList" asDLList         test "MutVar Seq" (id :: MutVar (PrimState IO) (Seq Int) -> MutVar (PrimState IO) (Seq Int))         test "STRef Vector" (id :: STRef (PrimState IO) (Vector Int) -> STRef (PrimState IO) (Vector Int))         test "BRef Vector" (id :: BRef (PrimState IO) (Vector Int) -> BRef (PrimState IO) (Vector Int))