abstract-deque (empty) → 0.1.1
raw patch · 6 files changed
+386/−0 lines, 6 filesdep +basedep +containerssetup-changed
Dependencies added: base, containers
Files
- Data/Concurrent/Deque/Class.hs +174/−0
- Data/Concurrent/Deque/Reference.hs +109/−0
- Data/Concurrent/Deque/Reference/DequeInstance.hs +23/−0
- LICENSE +34/−0
- Setup.hs +2/−0
- abstract-deque.cabal +44/−0
+ Data/Concurrent/Deque/Class.hs view
@@ -0,0 +1,174 @@+{-# LANGUAGE TypeFamilies, CPP, TypeSynonymInstances, MultiParamTypeClasses,+ FlexibleInstances, EmptyDataDecls, DefaultSignatures #-}++{- |+ An abstract, parameterizable interface for queues. ++ This interface includes a non-associated type family for Deques+ plus separate type classes encapusulating the Deque operations.+ This design strives to hide the extra phantom-type parameters from+ the Class constraints and therefore from the type signatures of+ client code.++-} +module Data.Concurrent.Deque.Class+ (+ -- * Highly parameterized Deque type(s)+ Deque+ -- ** The choices that select a queue-variant.+ -- *** Choice #1 -- thread saftety.+ , Threadsafe, Nonthreadsafe+ -- *** Choice #2 -- double or or single functionality on an end.+ , SingleEnd, DoubleEnd+ -- *** Choice #3 -- bounded or growing queues:+ , Bound, Grow+ -- *** Choice #4 -- duplication of elements.+ , Safe, Dup+ -- ** Aliases enabling more concise Deque types:+ , S, D, NT, T++ -- ** Aliases for commonly used Deque configurations:+ , Queue, ConcQueue, ConcDeque, WSDeque++ -- * Classes containing Deque operations+ , DequeClass(..)++ -- * Auxilary type classes. ++ -- | In spite of hiding the extra phantom type+ -- parameters in the DequeClass, we wish to retain the ability for+ -- clients to constrain the set of implementations they work with+ -- **statically**.++ -- ** The \"unnatural\" double ended cases: pop left, push right.+ , PopL(..), PushR(..)+ -- ** Operations that only make sense for bounded queues.+ , BoundedL(..), BoundedR(..)+)+++ where++import Prelude hiding (Bounded)++{- | ++ A family of Deques implementations. A concrete Deque implementation+ is selected based on the (phantom) type parameters, which encode+ several choices.++ For example, a work stealing deque is threadsafe only on one end and+ supports push/pop on one end (and popo-only) on the other:++ >> (Deque NT T D S Grow elt)++ Note, however, that the above example is overconstraining in many+ situations. It demands an implementation which is NOT threadsafe on+ one end and does NOT support push on one end, whereas both these+ features would not hurt, if present.++ Thus when accepting a queue as input to a function you probably never+ want to overconstrain by demanding a less-featureful option.++ For example, rather than @(Deque NT D T S Grow elt)@+ You would probably want: @(Deque nt D T s Grow elt)@++ -}+-- data family Deque lThreaded rThreaded lDbl rDbl bnd safe elt +type family Deque lThreaded rThreaded lDbl rDbl bnd safe elt ++-- | Haskell IO threads ("Control.Concurrent") may concurrently access+-- this end of the queue. Note that this attribute is set+-- separately for the left and right ends.+data Threadsafe+-- | Only one thread at a time may access this end of the queue.+data Nonthreadsafe++-- | This end of the queue provides push-only (left) or pop-only+-- (right) functionality. Thus a 'SingleEnd' / 'SingleEnd' combination+-- is what is commonly referred to as a /single ended queue/, whereas+-- 'DoubleEnd' / 'DoubleEnd' is +-- a /double ended queue/. Heterogenous combinations are sometimes+-- colloquially referred to as \"1.5 ended queues\".+data SingleEnd+-- | This end of the queue supports both push and pop.+data DoubleEnd++-- | The queue has bounded capacity.+data Bound+-- | The queue can grow as elements are added.+data Grow++-- | The queue will not duplicate elements.+data Safe +-- | Pop operations may possibly duplicate elements. Hopefully with low probability!+data Dup ++-- Possible #5:+-- data Lossy -- I know of no algorithm which would motivate having a Lossy mode.++----------------------------------------++type T = Threadsafe+type NT = Nonthreadsafe+type S = SingleEnd+type D = DoubleEnd++-- | A traditional single-threaded, single-ended queue.+type Queue a = Deque Nonthreadsafe Nonthreadsafe SingleEnd SingleEnd Grow Safe a+-- | A concurrent queue.+type ConcQueue a = Deque Threadsafe Threadsafe SingleEnd SingleEnd Grow Safe a+-- | A concurrent deque.+type ConcDeque a = Deque Threadsafe Threadsafe DoubleEnd DoubleEnd Grow Safe a+-- | Work-stealing deques (1.5 ended). Typically the worker pushes+-- and pops its own queue (left) whereas thieves only pop (right).+type WSDeque a = Deque Nonthreadsafe Threadsafe DoubleEnd SingleEnd Grow Safe a++--------------------------------------------------------------------------------++-- | Class encompassing the basic queue operations that hold for all+-- single, 1.5, and double ended modes. We arbitrarily call the+-- ends \"left\" and \"right\" and choose the natural operations to be+-- pushing on the left and popping on the right.+class DequeClass d where+ -- | Create a new deque. Most appropriate for unbounded deques.+ -- If bounded, the size is unspecified.+ newQ :: IO (d elt)++ default newQ :: BoundedL d => IO (d elt)+ newQ = newBoundedQ 256++ nullQ :: d elt -> IO Bool++ -- | Natural push: push onto the left end of the deque.+ pushL :: d elt -> elt -> IO ()+ -- | Natural pop: pop from the right end of the deque.+ tryPopR :: d elt -> IO (Maybe elt)++ -- TODO: Consider adding a peek operation?++ -- TODO: It would also be possible to include blocking/spinning pops.+ -- But maybe those should go in separate type classes...++class DequeClass d => PopL d where + -- | PopL is not the native operation for the left end, so it requires+ -- that the left end be a 'DoubleEnd', but places no other requirements+ -- on the input queue.+ -- + tryPopL :: d elt -> IO (Maybe elt)++class DequeClass d => PushR d where + -- | Pushing is not the native operation for the right end, so it requires+ -- that end be a 'DoubleEnd'.+ pushR :: d elt -> elt -> IO ()++class DequeClass d => BoundedL d where + -- | Create a new, bounded deque with a specified capacity.+ newBoundedQ :: Int -> IO (d elt)+ -- | For a bounded deque, pushing may fail if the deque is full.+ tryPushL :: d elt -> elt -> IO Bool++class PushR d => BoundedR d where + -- | For a bounded deque, pushing may fail if the deque is full.+ tryPushR :: d elt -> elt -> IO Bool+
+ Data/Concurrent/Deque/Reference.hs view
@@ -0,0 +1,109 @@+{-# LANGUAGE TypeFamilies #-}++{-| + A strawman implementation of concurrent Dequeus. This+ implementation is so simple that it also makes a good reference+ implementation for debugging.++ The queue representation is simply an IORef containing a Data.Sequence.++ Note, alse see "Data.Concurrent.Deque.Reference.DequeInstance". + By convention a module of this name is also provided.++-}++module Data.Concurrent.Deque.Reference + (SimpleDeque(..),+ newQ, newBoundedQ, pushL, pushR, tryPopR, tryPopL, tryPushL, tryPushR+ )+ where++import Prelude hiding (length)+import qualified Data.Concurrent.Deque.Class as C+import Data.Sequence+import Data.IORef++-- | Stores a size bound (if any) as well as a mutable Seq.+data SimpleDeque elt = DQ {-# UNPACK #-} !Int !(IORef (Seq elt))++{-# INLINE modify #-}+-- Toggle these and compare performance:+modify = atomicModifyIORef+-- modify = atomicModifyIORefCAS++newQ = do r <- newIORef empty+ return (DQ 0 r)++newBoundedQ lim = + do r <- newIORef empty+ return (DQ lim r)++pushL (DQ 0 qr) x = modify qr (\s -> (x <| s, ()))+pushL (DQ n _) _ = error$ "should not call pushL on Deque with size bound "++ show n++tryPopR (DQ _ qr) = modify qr $ \s -> + case viewr s of+ EmptyR -> (empty, Nothing)+ s' :> x -> (s', Just x)++nullQ :: SimpleDeque elt -> IO Bool+nullQ (DQ _ qr) = + do s <- readIORef qr+ case viewr s of + EmptyR -> return True+ _ :> _ -> return False++-- -- This simplistic version simply spins:+-- popR q = do x <- tryPopR q +-- case x of +-- Nothing -> popR q+-- Just x -> return x++-- popL q = do x <- tryPopL q +-- case x of +-- Nothing -> popL q+-- Just x -> return x++tryPopL (DQ _ qr) = modify qr $ \s -> + case viewl s of+ EmptyL -> (empty, Nothing)+ x :< s' -> (s', Just x)++pushR (DQ 0 qr) x = modify qr (\s -> (s |> x, ()))+pushR (DQ n _) _ = error$ "should not call pushR on Deque with size bound "++ show n++tryPushL q@(DQ 0 _) v = pushL q v >> return True+tryPushL (DQ lim qr) v = + modify qr $ \s -> + if length s == lim+ then (s, False)+ else (v <| s, True)++tryPushR q@(DQ 0 _) v = pushR q v >> return True+tryPushR (DQ lim qr) v = + modify qr $ \s -> + if length s == lim+ then (s, False)+ else (s |> v, True)++--------------------------------------------------------------------------------+-- Instances+--------------------------------------------------------------------------------++instance C.DequeClass SimpleDeque where + newQ = newQ+ nullQ = nullQ+ pushL = pushL+ tryPopR = tryPopR+instance C.PopL SimpleDeque where + tryPopL = tryPopL+instance C.PushR SimpleDeque where + pushR = pushR++instance C.BoundedL SimpleDeque where + tryPushL = tryPushL+ newBoundedQ = newBoundedQ++instance C.BoundedR SimpleDeque where + tryPushR = tryPushR+
+ Data/Concurrent/Deque/Reference/DequeInstance.hs view
@@ -0,0 +1,23 @@+{-# LANGUAGE TypeFamilies, TypeSynonymInstances #-}++{- | + By convention, every provider of the "Data.Concurrent.Deque.Class"+ interface optionally provides a module that provides the relevant+ instances of the 'Deque' type class, covering the portion of the+ configuration space that the implementation is able to handle.++ This is kept in a separate package because importing instances is+ unconditional and the user may well want to assemble their own+ combination of 'Deque' instances to cover the configuration+ space.+ -}++module Data.Concurrent.Deque.Reference.DequeInstance () where++import Data.Concurrent.Deque.Class+import qualified Data.Concurrent.Deque.Reference as R++-- | The reference implementation is a fully general Deque. It can+-- thus cover the full configuration space.+type instance Deque lt rt l r bnd safe elt = R.SimpleDeque elt+
+ LICENSE view
@@ -0,0 +1,34 @@+Unless otherwise noted in individual files, the below+copyright/LICENSE applies to the source files in this repository.+--------------------------------------------------------------------------------++Copyright (c)2011, Ryan R. Newton++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Ryan R. Newton nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ abstract-deque.cabal view
@@ -0,0 +1,44 @@+Name: abstract-deque+Version: 0.1.1+License: BSD3+License-file: LICENSE+Author: Ryan R. Newton+Maintainer: rrnewton@gmail.com+Category: Data+Build-type: Simple+Cabal-version: >=1.2++-- Version History:+-- 0.1: +-- 0.1.1: Added nullQ to interface.++Synopsis: Abstract, parameterized interface to mutable Deques.++Description:++ An abstract interface to highly-parameterizable queues/deques.+ . + Background: There exists a feature space for queues that extends between:+ .+ * simple, single-ended, non-concurrent, bounded queues + .+ * double-ended, threadsafe, growable queues+ .+ ... with important points inbetween (such as+ the queues used for work-stealing).+ .+ This package includes an interface for Deques that allows the+ programmer to use a single API for all of the above, while using the+ type-system to select an efficient implementation given the+ requirements (using type families).+ .+ This package also includes a simple reference implementation based+ on 'IORef' and 'Data.Sequence'.++Library+ exposed-modules: Data.Concurrent.Deque.Class,+ Data.Concurrent.Deque.Reference,+ Data.Concurrent.Deque.Reference.DequeInstance+ build-depends: base >= 4.4.0.0 && < 5, + containers+ ghc-options: -O2