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