Don't generate Haskell dependencies if we don't have any Haskell sources
[ghc-hetmet.git] / rts / WSDeque.h
1 /* -----------------------------------------------------------------------------
2  *
3  * (c) The GHC Team, 2009
4  *
5  * Work-stealing Deque data structure
6  * 
7  * ---------------------------------------------------------------------------*/
8
9 #ifndef WSDEQUE_H
10 #define WSDEQUE_H
11
12 typedef struct WSDeque_ {
13     // Size of elements array. Used for modulo calculation: we round up
14     // to powers of 2 and use the dyadic log (modulo == bitwise &) 
15     StgWord size; 
16     StgWord moduloSize; /* bitmask for modulo */
17
18     // top, index where multiple readers steal() (protected by a cas)
19     volatile StgWord top;
20
21     // bottom, index of next free place where one writer can push
22     // elements. This happens unsynchronised.
23     volatile StgWord bottom;
24
25     // both top and bottom are continuously incremented, and used as
26     // an index modulo the current array size.
27   
28     // lower bound on the current top value. This is an internal
29     // optimisation to avoid unnecessarily accessing the top field
30     // inside pushBottom
31     volatile StgWord topBound;
32
33     // The elements array
34     void ** elements;
35
36     //  Please note: the dataspace cannot follow the admin fields
37     //  immediately, as it should be possible to enlarge it without
38     //  disposing the old one automatically (as realloc would)!
39
40 } WSDeque;
41
42 /* INVARIANTS, in this order: reasonable size,
43    topBound consistent, space pointer, space accessible to us.
44    
45    NB. This is safe to use only (a) on a spark pool owned by the
46    current thread, or (b) when there's only one thread running, or no
47    stealing going on (e.g. during GC).
48 */
49 #define ASSERT_WSDEQUE_INVARIANTS(p)         \
50   ASSERT((p)->size > 0);                        \
51   ASSERT((p)->topBound <= (p)->top);            \
52   ASSERT((p)->elements != NULL);                \
53   ASSERT(*((p)->elements) || 1);                \
54   ASSERT(*((p)->elements - 1  + ((p)->size)) || 1);
55
56 // No: it is possible that top > bottom when using pop()
57 //  ASSERT((p)->bottom >= (p)->top);           
58 //  ASSERT((p)->size > (p)->bottom - (p)->top);
59
60 /* -----------------------------------------------------------------------------
61  * Operations
62  *
63  * A WSDeque has an *owner* thread.  The owner can perform any operation;
64  * other threads are only allowed to call stealWSDeque_(),
65  * stealWSDeque(), looksEmptyWSDeque(), and dequeElements().
66  *
67  * -------------------------------------------------------------------------- */
68
69 // Allocation, deallocation
70 WSDeque * newWSDeque  (nat size);
71 void      freeWSDeque (WSDeque *q);
72
73 // Take an element from the "write" end of the pool.  Can be called
74 // by the pool owner only.
75 void* popWSDeque (WSDeque *q);
76
77 // Push onto the "write" end of the pool.  Return true if the push
78 // succeeded, or false if the deque is full.
79 rtsBool pushWSDeque (WSDeque *q, void *elem);
80
81 // Removes all elements from the deque
82 INLINE_HEADER void discardElements (WSDeque *q);
83
84 // Removes an element of the deque from the "read" end, or returns
85 // NULL if the pool is empty, or if there was a collision with another
86 // thief.
87 void * stealWSDeque_ (WSDeque *q);
88
89 // Removes an element of the deque from the "read" end, or returns
90 // NULL if the pool is empty.
91 void * stealWSDeque (WSDeque *q);
92
93 // "guesses" whether a deque is empty. Can return false negatives in
94 //  presence of concurrent steal() calls, and false positives in
95 //  presence of a concurrent pushBottom().
96 INLINE_HEADER rtsBool looksEmptyWSDeque (WSDeque* q);
97
98 INLINE_HEADER long dequeElements   (WSDeque *q);
99
100 /* -----------------------------------------------------------------------------
101  * PRIVATE below here
102  * -------------------------------------------------------------------------- */
103
104 INLINE_HEADER long
105 dequeElements (WSDeque *q)
106 {
107     StgWord t = q->top;
108     StgWord b = q->bottom;
109     // try to prefer false negatives by reading top first
110     return ((long)b - (long)t);
111 }
112
113 INLINE_HEADER rtsBool
114 looksEmptyWSDeque (WSDeque *q)
115 {
116     return (dequeElements(q) <= 0);
117 }
118
119 INLINE_HEADER void
120 discardElements (WSDeque *q)
121 {
122     q->top = q->bottom;
123 //    pool->topBound = pool->top;
124 }
125
126 #endif // WSDEQUE_H