testsuite: attempt fixing fallout from 089b72f52
[ghc.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 EXTERN_INLINE 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 EXTERN_INLINE rtsBool looksEmptyWSDeque (WSDeque* q);
97
98 EXTERN_INLINE long dequeElements (WSDeque *q);
99
100 /* -----------------------------------------------------------------------------
101 * PRIVATE below here
102 * -------------------------------------------------------------------------- */
103
104 EXTERN_INLINE 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 EXTERN_INLINE rtsBool
114 looksEmptyWSDeque (WSDeque *q)
115 {
116 return (dequeElements(q) <= 0);
117 }
118
119 EXTERN_INLINE void
120 discardElements (WSDeque *q)
121 {
122 q->top = q->bottom;
123 // pool->topBound = pool->top;
124 }
125
126 #endif // WSDEQUE_H