-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Abstract, parameterized interface to mutable Deques.
--   
--   An abstract interface to highly-parameterizable queues/deques.
--   
--   Background: There exists a feature space for queues that extends
--   between:
--   
--   <ul>
--   <li>simple, single-ended, non-concurrent, bounded queues</li>
--   <li>double-ended, threadsafe, growable queues</li>
--   </ul>
--   
--   ... 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
--   <a>IORef</a> and <a>Data.Sequence</a>.
@package abstract-deque
@version 0.2


-- | An abstract, parameterizable interface for queues.
--   
--   This interface includes a non-associated type family for Deques plus
--   separate type classes encapsulating the Deque operations. That is, we
--   separate type selection (type family) from function overloading
--   (vanilla type classes).
--   
--   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

-- | 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 pop-only) on the other:
--   
--   <pre>
--   &gt; (Deque NT T  D S Grow elt)
--   </pre>
--   
--   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 <tt>(Deque NT D T S Grow elt)</tt> You would
--   probably want: <tt>(Deque nt D T s Grow elt)</tt>

-- | Haskell IO threads (<a>Control.Concurrent</a>) 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 <a>SingleEnd</a> / <a>SingleEnd</a> combination
--   is what is commonly referred to as a <i>single ended queue</i>,
--   whereas <a>DoubleEnd</a> / <a>DoubleEnd</a> is a <i>double ended
--   queue</i>. Heterogeneous 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
type S = SingleEnd
type D = DoubleEnd
type NT = Nonthreadsafe
type T = Threadsafe

-- | 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
newQ :: DequeClass d => IO (d elt)
nullQ :: DequeClass d => d elt -> IO Bool
pushL :: DequeClass d => d elt -> elt -> IO ()
tryPopR :: DequeClass d => d elt -> IO (Maybe elt)
leftThreadSafe :: DequeClass d => d elt -> Bool
rightThreadSafe :: DequeClass d => d elt -> Bool
class DequeClass d => PopL d
tryPopL :: PopL d => d elt -> IO (Maybe elt)
class DequeClass d => PushR d
pushR :: PushR d => d elt -> elt -> IO ()
class DequeClass d => BoundedL d
newBoundedQ :: BoundedL d => Int -> IO (d elt)
tryPushL :: BoundedL d => d elt -> elt -> IO Bool
class PushR d => BoundedR d
tryPushR :: BoundedR d => d elt -> elt -> IO Bool


-- | A strawman implementation of concurrent Dequeues. 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.
--   
--   Also see <a>Data.Concurrent.Deque.Reference.DequeInstance</a>. By
--   convention a module of this name is also provided.
module Data.Concurrent.Deque.Reference

-- | Stores a size bound (if any) as well as a mutable Seq.
data SimpleDeque elt
DQ :: {-# UNPACK #-} !Int -> !(IORef (Seq elt)) -> SimpleDeque elt
newQ :: IO (SimpleDeque elt)
nullQ :: SimpleDeque elt -> IO Bool
newBoundedQ :: Int -> IO (SimpleDeque elt)
pushL :: SimpleDeque t -> t -> IO ()
pushR :: SimpleDeque t -> t -> IO ()
tryPopR :: SimpleDeque a -> IO (Maybe a)
tryPopL :: SimpleDeque a -> IO (Maybe a)
tryPushL :: SimpleDeque a -> a -> IO Bool
tryPushR :: SimpleDeque a -> a -> IO Bool
_is_using_CAS :: Bool
instance BoundedR SimpleDeque
instance BoundedL SimpleDeque
instance PushR SimpleDeque
instance PopL SimpleDeque
instance DequeClass SimpleDeque


-- | This module contains a battery of simple tests for queues implementing
--   the interface defined in ` Data.Concurrent.Deque.Class`.
module Data.Concurrent.Deque.Tests

-- | This test serially fills up a queue and then drains it.
test_fifo_filldrain :: DequeClass d => d Int -> IO ()

-- | This test splits the <a>numAgents</a> threads into producers and
--   consumers which all communicate through a SINGLE queue. Each thread
--   performs its designated operation as fast as possible. The <a>Int</a>
--   argument <tt>total</tt> designates how many total items should be
--   communicated (irrespective of <a>numAgents</a>).
test_fifo_OneBottleneck :: DequeClass d => Bool -> Int -> d Int -> IO ()

-- | This creates an HUnit test list to perform all the tests that apply to
--   a single-ended (threadsafe) queue. It requires thread safety at
--   <i>both</i> ends.
tests_fifo :: DequeClass d => (forall elt. IO (d elt)) -> Test

-- | Trivial test: push then pop.
test_ws_triv1 :: PopL d => d [Char] -> IO ()

-- | Trivial test: push left, pop left and right.
test_ws_triv2 :: PopL d => d [Char] -> IO ()

-- | Aggregate tests for work stealing queues. None of these require
--   thread-safety on the left end. There is some duplication with
--   tests_fifo.
tests_wsqueue :: PopL d => (forall elt. IO (d elt)) -> Test

-- | This requires double ended queues that are threadsafe on BOTH ends.
tests_all :: PopL d => (forall elt. IO (d elt)) -> Test
numElems :: Int

-- | How many communicating agents are there? By default one per thread
--   used by the RTS.
numAgents :: Int

-- | It is possible to have imbalanced concurrency where there is more
--   contention on the producing or consuming side (which corresponds to
--   settings of this parameter less than or greater than 1).
producerRatio :: Double


-- | By convention, every provider of the
--   <a>Data.Concurrent.Deque.Class</a> interface optionally provides a
--   module that provides the relevant instances of the <a>Deque</a> type
--   class, covering the [maximum] 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 <a>Deque</a> instances to cover the configuration
--   space.
module Data.Concurrent.Deque.Reference.DequeInstance