úÎj eU;      !"#$%&'()*+,-./0123456789: Safe-Inferred<For a bounded deque, pushing may fail if the deque is full. 7Create a new, bounded deque with a specified capacity. <For a bounded deque, pushing may fail if the deque is full. FPushing is not the native operation for the right end, so it requires  that end be a . BPopL is not the native operation for the left end, so it requires  that the left end be a #, but places no other requirements  on the input queue. @Class encompassing the basic queue operations that hold for all A single, 1.5, and double ended modes. We arbitrarily call the  ends "left" and "right") and choose the natural operations to be 1 pushing on the left and popping on the right. <Create a new deque. Most appropriate for unbounded deques. ( If bounded, the size is unspecified. QIs the queue currently empty? Beware that this can be a highly transient state. 3Natural push: push onto the left end of the deque. 2Natural pop: pop from the right end of the deque. (Runtime indication of thread saftey for   (and popL).  (Argument unused.) (Runtime indication of thread saftey for   (and ).  (Argument unused.) ?Work-stealing deques (1.5 ended). Typically the worker pushes C and pops its own queue (left) whereas thieves only pop (right). A concurrent deque. A concurrent queue. 3A traditional single-threaded, single-ended queue. QPop operations may possibly duplicate elements. Hopefully with low probability! 'The queue will not duplicate elements. *The queue can grow as elements are added.  The queue has bounded capacity. 2This end of the queue supports both push and pop. <This end of the queue provides push-only (left) or pop-only ! (right) functionality. Thus a  /  combination ( is what is commonly referred to as a single ended queue , whereas   /  is  a double ended queue,. Heterogeneous combinations are sometimes  colloquially referred to as "1.5 ended queues". <Only one thread at a time may access this end of the queue. 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. EA family of Deques implementations. A concrete Deque implementation B is selected based on the (phantom) type parameters, which encode  several choices. EFor example, a work stealing deque is threadsafe only on one end and  supports push/,pop on one end (and pop-only) on the other:  > (Deque NT T D S Grow elt) BNote, however, that the above example is overconstraining in many F situations. It demands an implementation which is NOT threadsafe on B one end and does NOT support push on one end, whereas both these & features would not hurt, if present. FThus 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) !  !  !      Safe-Inferred!7Stores a size bound (if any) as well as a mutable Seq. !";#$%&'()*+,<=>?@ !"#$%&'()*+, !"$(%&*')+,#!";#$%&'()*+,<=>?@None.=How many communicating agents are there? By default one per  thread used by the RTS. /BIt is possible to have imbalanced concurrency where there is more E contention on the producing or consuming side (which corresponds to : settings of this parameter less than or greater than 1). 0ODig through the test constructors to find the leaf IO actions and bracket them ! with a thread-setting action. 28This test serially fills up a queue and then drains it. 3This test splits the  numAgents threads into producers and ? consumers which all communicate through a SINGLE queue. Each D thread performs its designated operation as fast as possible. The  A argument total+ designates how many total items should be  communicated (irrespective of  numAgents). B,This test uses a separate queue per producer/consumer pair. The queues , are used in a single-writer single-reader. CLThis test uses a number of producer and consumer threads which push and pop 6 elements from random positions in an array of FIFOs. 4IThis creates an HUnit test list to perform all the tests that apply to a B single-ended (threadsafe) queue. It requires thread safety at both ends. D5Tests exclusive to single-ended (threadsafe) queues: ETests that don''t require thread safety at either end. 5Trivial test: push then pop. 6-Trivial test: push left, pop left and right. FQThis test uses a number of worker threads which randomly either push or pop work N to their local work stealing deque. Also, there are consumer (always thief) / threads which never produce and only consume. 7OAggregate tests for work stealing queues. None of these require thread-safety > on the left end. There is some duplication with tests_fifo. 8DThis requires double ended queues that are threadsafe on BOTH ends. G$Pop from the right end more gently. HOThis is always a crazy and dangerous thing to do -- GHC cannot deschedule this Q spinning thread because it does not allocate. Thus one can run into a deadlock N situation where the consumer holds the capabilitity hostage, not letting the * producer run (and therefore unblock it). I*Debugging flag shared by several modules. D This is activated by setting the environment variable DEBUG=1..5 J5Print if the debug level is at or above a threshold. #KL-M./N0123BCO4DE56F7P8QRSGHTUVIWJX -./012345678 2345678-./01#KL-M./N0123BCO4DE56F7P8QRSGHTUVIWJX Safe-Inferred Safe-Inferred9OWarning, this enforces the excessively STRONG invariant that if any end of the S deque is non-threadsafe then it may ever only be touched by one thread during its  entire lifetime. AThis extreme form of monagamy is easier to verify, because we don't have enough P information to know if two operations on different threads are racing with one ' another or are properly synchronized. PThe wrapper data structure has two IORefs to track the last thread that touched 4 the left and right end of the deque, respectively. Y+Mark the last thread to use this endpoint. 9:YZ[9:9:9:YZ[\      !"#$%&'()   *+,-./01234566789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZabstract-deque-0.2.2Data.Concurrent.Deque.ClassData.Concurrent.Deque.ReferenceData.Concurrent.Deque.TestsData.Concurrent.Deque.Debugger-Data.Concurrent.Deque.Reference.DequeInstanceBoundedRtryPushRBoundedL newBoundedQtryPushLPushRpushRPopLtryPopL DequeClassnewQnullQpushLtryPopRleftThreadSaferightThreadSafeWSDeque ConcDeque ConcQueueQueueDSNTTDupSafeGrowBound DoubleEnd SingleEnd Nonthreadsafe ThreadsafeDeque SimpleDequeDQ _is_using_CASnumElems getNumAgents producerRatiosetTestThreadsstdTestHarnesstest_fifo_filldraintest_fifo_OneBottleneck tests_fifo test_ws_triv1 test_ws_triv2 tests_wsqueue tests_all DebugDequemodify$fBoundedRSimpleDeque$fBoundedLSimpleDeque$fPushRSimpleDeque$fPopLSimpleDeque$fDequeClassSimpleDequeghc-prim GHC.TypesInttest_contention_free_paralleltest_random_array_commtests_fifo_exclusive tests_basictest_random_work_stealing spinPopBkoff spinPopHarddbgdbgPrintElttheEnv forkThread warnUsing expectedSumtests_wsqueue_exclusivemyforkforkWithExceptionsforkJoinspinPopNfor_forI_ defaultDbg dbgPrintLn markThread$fPopLDebugDeque$fDequeClassDebugDeque