1 /* -----------------------------------------------------------------------------
3 * (c) The GHC Team, 2009
5 * Work-stealing Deque data structure
7 * ---------------------------------------------------------------------------*/
12 #if defined(THREADED_RTS)
14 typedef struct WSDeque_ {
15 // Size of elements array. Used for modulo calculation: we round up
16 // to powers of 2 and use the dyadic log (modulo == bitwise &)
18 StgWord moduloSize; /* bitmask for modulo */
20 // top, index where multiple readers steal() (protected by a cas)
23 // bottom, index of next free place where one writer can push
24 // elements. This happens unsynchronised.
25 volatile StgWord bottom;
27 // both top and bottom are continuously incremented, and used as
28 // an index modulo the current array size.
30 // lower bound on the current top value. This is an internal
31 // optimisation to avoid unnecessarily accessing the top field
33 volatile StgWord topBound;
38 // Please note: the dataspace cannot follow the admin fields
39 // immediately, as it should be possible to enlarge it without
40 // disposing the old one automatically (as realloc would)!
44 /* INVARIANTS, in this order: reasonable size,
45 topBound consistent, space pointer, space accessible to us.
47 NB. This is safe to use only (a) on a spark pool owned by the
48 current thread, or (b) when there's only one thread running, or no
49 stealing going on (e.g. during GC).
51 #define ASSERT_WSDEQUE_INVARIANTS(p) \
52 ASSERT((p)->size > 0); \
53 ASSERT((p)->topBound <= (p)->top); \
54 ASSERT((p)->elements != NULL); \
55 ASSERT(*((p)->elements) || 1); \
56 ASSERT(*((p)->elements - 1 + ((p)->size)) || 1);
58 // No: it is possible that top > bottom when using pop()
59 // ASSERT((p)->bottom >= (p)->top);
60 // ASSERT((p)->size > (p)->bottom - (p)->top);
62 /* -----------------------------------------------------------------------------
65 * A WSDeque has an *owner* thread. The owner can perform any operation;
66 * other threads are only allowed to call stealWSDeque_(),
67 * stealWSDeque(), looksEmptyWSDeque(), and dequeElements().
69 * -------------------------------------------------------------------------- */
71 // Allocation, deallocation
72 WSDeque * newWSDeque (nat size);
73 void freeWSDeque (WSDeque *q);
75 // Take an element from the "write" end of the pool. Can be called
76 // by the pool owner only.
77 void* popWSDeque (WSDeque *q);
79 // Push onto the "write" end of the pool. Return true if the push
80 // succeeded, or false if the deque is full.
81 rtsBool pushWSDeque (WSDeque *q, void *elem);
83 // Removes all elements from the deque
84 INLINE_HEADER void discardElements (WSDeque *q);
86 // Removes an element of the deque from the "read" end, or returns
87 // NULL if the pool is empty, or if there was a collision with another
89 void * stealWSDeque_ (WSDeque *q);
91 // Removes an element of the deque from the "read" end, or returns
92 // NULL if the pool is empty.
93 void * stealWSDeque (WSDeque *q);
95 // "guesses" whether a deque is empty. Can return false negatives in
96 // presence of concurrent steal() calls, and false positives in
97 // presence of a concurrent pushBottom().
98 INLINE_HEADER rtsBool looksEmptyWSDeque (WSDeque* q);
100 INLINE_HEADER long dequeElements (WSDeque *q);
102 /* -----------------------------------------------------------------------------
104 * -------------------------------------------------------------------------- */
107 dequeElements (WSDeque *q)
110 StgWord b = q->bottom;
111 // try to prefer false negatives by reading top first
112 return ((long)b - (long)t);
115 INLINE_HEADER rtsBool
116 looksEmptyWSDeque (WSDeque *q)
118 return (dequeElements(q) <= 0);
122 discardElements (WSDeque *q)
125 // pool->topBound = pool->top;
128 #endif // THREADED_RTS