forked from taskflow/taskflow
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathclasstf_1_1UnboundedTaskQueue.html
More file actions
259 lines (259 loc) · 15.1 KB
/
Copy pathclasstf_1_1UnboundedTaskQueue.html
File metadata and controls
259 lines (259 loc) · 15.1 KB
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<title>tf::UnboundedTaskQueue class | Taskflow QuickStart</title>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Source+Sans+Pro:400,400i,600,600i%7CSource+Code+Pro:400,400i,600" />
<link rel="stylesheet" href="m-dark+documentation.compiled.css" />
<link rel="icon" href="favicon.ico" type="image/x-icon" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="theme-color" content="#22272e" />
</head>
<body>
<header><nav id="navigation">
<div class="m-container">
<div class="m-row">
<span id="m-navbar-brand" class="m-col-t-8 m-col-m-none m-left-m">
<a href="https://taskflow.github.io"><img src="taskflow_logo.png" alt="" />Taskflow</a> <span class="m-breadcrumb">|</span> <a href="index.html" class="m-thin">QuickStart</a>
</span>
<div class="m-col-t-4 m-hide-m m-text-right m-nopadr">
<a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
<path id="m-doc-search-icon-path" d="m6 0c-3.31 0-6 2.69-6 6 0 3.31 2.69 6 6 6 1.49 0 2.85-0.541 3.89-1.44-0.0164 0.338 0.147 0.759 0.5 1.15l3.22 3.79c0.552 0.614 1.45 0.665 2 0.115 0.55-0.55 0.499-1.45-0.115-2l-3.79-3.22c-0.392-0.353-0.812-0.515-1.15-0.5 0.895-1.05 1.44-2.41 1.44-3.89 0-3.31-2.69-6-6-6zm0 1.56a4.44 4.44 0 0 1 4.44 4.44 4.44 4.44 0 0 1-4.44 4.44 4.44 4.44 0 0 1-4.44-4.44 4.44 4.44 0 0 1 4.44-4.44z"/>
</svg></a>
<a id="m-navbar-show" href="#navigation" title="Show navigation"></a>
<a id="m-navbar-hide" href="#" title="Hide navigation"></a>
</div>
<div id="m-navbar-collapse" class="m-col-t-12 m-show-m m-col-m-none m-right-m">
<div class="m-row">
<ol class="m-col-t-6 m-col-m-none">
<li><a href="pages.html">Handbook</a></li>
<li><a href="namespaces.html">Namespaces</a></li>
</ol>
<ol class="m-col-t-6 m-col-m-none" start="3">
<li><a href="annotated.html">Classes</a></li>
<li><a href="files.html">Files</a></li>
<li class="m-show-m"><a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
<use href="#m-doc-search-icon-path" />
</svg></a></li>
</ol>
</div>
</div>
</div>
</div>
</nav></header>
<main><article>
<div class="m-container m-container-inflatable">
<div class="m-row">
<div class="m-col-l-10 m-push-l-1">
<h1>
<div class="m-doc-include m-code m-inverted m-right-m m-text-right"><span class="cp">#include</span> <a class="cpf" href="tsq_8hpp.html"><taskflow/core/tsq.hpp></a></div>
<div class="m-doc-template">template<typename T></div>
<span class="m-breadcrumb"><a href="namespacetf.html">tf</a>::<wbr/></span>UnboundedTaskQueue <span class="m-thin">class</span>
</h1>
<p>class to create a lock-free unbounded work-stealing queue</p>
<table class="m-table m-fullwidth m-flat">
<thead>
<tr><th colspan="2">Template parameters</th></tr>
</thead>
<tbody>
<tr>
<td style="width: 1%">T</td>
<td>data type (must be a pointer type)</td>
</tr>
</tbody>
</table>
<nav class="m-block m-default">
<h3>Contents</h3>
<ul>
<li>
Reference
<ul>
<li><a href="#typeless-methods">Constructors, destructors, conversion operators</a></li>
<li><a href="#pub-methods">Public functions</a></li>
</ul>
</li>
</ul>
</nav>
<p>This class implements the work-stealing queue described in the paper, <a href="https://www.di.ens.fr/~zappa/readings/ppopp13.pdf">Correct and Efficient Work-Stealing for Weak Memory Models</a>.</p><p>Only the queue owner can perform pop and push operations, while others can steal data from the queue simultaneously.</p>
<section id="typeless-methods">
<h2><a href="#typeless-methods">Constructors, destructors, conversion operators</a></h2>
<dl class="m-doc">
<dt>
<span class="m-doc-wrap-bumper"><a href="#accc811a0a5d692a3cda366378367d7b6" class="m-doc">UnboundedTaskQueue</a>(</span><span class="m-doc-wrap">int64_t LogSize = <a href="tsq_8hpp.html#a45e25b85f72dd5c43f2c9010205c3e37" class="m-doc">TF_<wbr />DEFAULT_<wbr />UNBOUNDED_<wbr />TASK_<wbr />QUEUE_<wbr />LOG_<wbr />SIZE</a>) <span class="m-label m-flat m-info">explicit</span> </span>
</dt>
<dd>constructs the queue with the given size in the base-2 logarithm</dd>
<dt id="a72babe096da4ffc72a68b9ff76134e95">
<span class="m-doc-wrap-bumper"><a href="#a72babe096da4ffc72a68b9ff76134e95" class="m-doc-self">~UnboundedTaskQueue</a>(</span><span class="m-doc-wrap">)</span>
</dt>
<dd>destructs the queue</dd>
</dl>
</section>
<section id="pub-methods">
<h2><a href="#pub-methods">Public functions</a></h2>
<dl class="m-doc">
<dt id="a625c75d38982b8eb5d6e6d6f2aa49dec">
<span class="m-doc-wrap-bumper">auto <a href="#a625c75d38982b8eb5d6e6d6f2aa49dec" class="m-doc-self">empty</a>(</span><span class="m-doc-wrap">) const -> bool <span class="m-label m-flat m-success">noexcept</span></span>
</dt>
<dd>queries if the queue is empty at the time of this call</dd>
<dt id="aa701e0781b063a889ee77f71d3b68d3d">
<span class="m-doc-wrap-bumper">auto <a href="#aa701e0781b063a889ee77f71d3b68d3d" class="m-doc-self">size</a>(</span><span class="m-doc-wrap">) const -> size_t <span class="m-label m-flat m-success">noexcept</span></span>
</dt>
<dd>queries the number of items at the time of this call</dd>
<dt id="a54eb8fe122dd783c486c683e7c50c5e5">
<span class="m-doc-wrap-bumper">auto <a href="#a54eb8fe122dd783c486c683e7c50c5e5" class="m-doc-self">capacity</a>(</span><span class="m-doc-wrap">) const -> int64_t <span class="m-label m-flat m-success">noexcept</span></span>
</dt>
<dd>queries the capacity of the queue</dd>
<dt>
<span class="m-doc-wrap-bumper">void <a href="#a3d077fbe105a2712c1b22696edfbf061" class="m-doc">push</a>(</span><span class="m-doc-wrap">T item)</span>
</dt>
<dd>inserts an item to the queue</dd>
<dt>
<span class="m-doc-wrap-bumper">auto <a href="#a169eee6096445fe32ae0e34cae629c38" class="m-doc">pop</a>(</span><span class="m-doc-wrap">) -> T</span>
</dt>
<dd>pops out an item from the queue</dd>
<dt>
<span class="m-doc-wrap-bumper">auto <a href="#a038400d9c48a421d3e27379cf319e2ff" class="m-doc">steal</a>(</span><span class="m-doc-wrap">) -> T</span>
</dt>
<dd>steals an item from the queue</dd>
<dt>
<span class="m-doc-wrap-bumper">auto <a href="#a1e73bc73447fa1d60b0957348c987d38" class="m-doc">steal_with_hint</a>(</span><span class="m-doc-wrap">size_t& num_empty_steals) -> T</span>
</dt>
<dd>attempts to steal a task with a hint mechanism</dd>
</dl>
</section>
<section>
<h2>Function documentation</h2>
<section class="m-doc-details" id="accc811a0a5d692a3cda366378367d7b6"><div>
<h3>
<div class="m-doc-template">
template<typename T>
</div>
<span class="m-doc-wrap-bumper"> tf::<wbr />UnboundedTaskQueue<T>::<wbr /></span><span class="m-doc-wrap"><span class="m-doc-wrap-bumper"><a href="#accc811a0a5d692a3cda366378367d7b6" class="m-doc-self">UnboundedTaskQueue</a>(</span><span class="m-doc-wrap">int64_t LogSize = <a href="tsq_8hpp.html#a45e25b85f72dd5c43f2c9010205c3e37" class="m-doc">TF_<wbr />DEFAULT_<wbr />UNBOUNDED_<wbr />TASK_<wbr />QUEUE_<wbr />LOG_<wbr />SIZE</a>) <span class="m-label m-info">explicit</span> </span></span>
</h3>
<p>constructs the queue with the given size in the base-2 logarithm</p>
<table class="m-table m-fullwidth m-flat">
<thead>
<tr><th colspan="2">Parameters</th></tr>
</thead>
<tbody>
<tr>
<td style="width: 1%">LogSize</td>
<td>the base-2 logarithm of the queue size</td>
</tr>
</tbody>
</table>
</div></section>
<section class="m-doc-details" id="a3d077fbe105a2712c1b22696edfbf061"><div>
<h3>
<div class="m-doc-template">
template<typename T>
</div>
<span class="m-doc-wrap-bumper">void tf::<wbr />UnboundedTaskQueue<T>::<wbr /></span><span class="m-doc-wrap"><span class="m-doc-wrap-bumper"><a href="#a3d077fbe105a2712c1b22696edfbf061" class="m-doc-self">push</a>(</span><span class="m-doc-wrap">T item)</span></span>
</h3>
<p>inserts an item to the queue</p>
<table class="m-table m-fullwidth m-flat">
<thead>
<tr><th colspan="2">Parameters</th></tr>
</thead>
<tbody>
<tr>
<td style="width: 1%">item</td>
<td>the item to push to the queue</td>
</tr>
</tbody>
</table>
<p>Only the owner thread can insert an item to the queue. The operation can trigger the queue to resize its capacity if more space is required.</p>
</div></section>
<section class="m-doc-details" id="a169eee6096445fe32ae0e34cae629c38"><div>
<h3>
<div class="m-doc-template">
template<typename T>
</div>
<span class="m-doc-wrap-bumper">T tf::<wbr />UnboundedTaskQueue<T>::<wbr /></span><span class="m-doc-wrap"><span class="m-doc-wrap-bumper"><a href="#a169eee6096445fe32ae0e34cae629c38" class="m-doc-self">pop</a>(</span><span class="m-doc-wrap">)</span></span>
</h3>
<p>pops out an item from the queue</p>
<p>Only the owner thread can pop out an item from the queue. The return can be a <code>nullptr</code> if this operation failed (empty queue).</p>
</div></section>
<section class="m-doc-details" id="a038400d9c48a421d3e27379cf319e2ff"><div>
<h3>
<div class="m-doc-template">
template<typename T>
</div>
<span class="m-doc-wrap-bumper">T tf::<wbr />UnboundedTaskQueue<T>::<wbr /></span><span class="m-doc-wrap"><span class="m-doc-wrap-bumper"><a href="#a038400d9c48a421d3e27379cf319e2ff" class="m-doc-self">steal</a>(</span><span class="m-doc-wrap">)</span></span>
</h3>
<p>steals an item from the queue</p>
<p>Any threads can try to steal an item from the queue. The return can be a <code>nullptr</code> if this operation failed (not necessary empty).</p>
</div></section>
<section class="m-doc-details" id="a1e73bc73447fa1d60b0957348c987d38"><div>
<h3>
<div class="m-doc-template">
template<typename T>
</div>
<span class="m-doc-wrap-bumper">T tf::<wbr />UnboundedTaskQueue<T>::<wbr /></span><span class="m-doc-wrap"><span class="m-doc-wrap-bumper"><a href="#a1e73bc73447fa1d60b0957348c987d38" class="m-doc-self">steal_with_hint</a>(</span><span class="m-doc-wrap">size_t& num_empty_steals)</span></span>
</h3>
<p>attempts to steal a task with a hint mechanism</p>
<table class="m-table m-fullwidth m-flat">
<thead>
<tr><th colspan="2">Parameters</th></tr>
</thead>
<tbody>
<tr>
<td style="width: 1%">num_empty_steals</td>
<td>a reference to a counter tracking consecutive empty steal attempts</td>
</tr>
</tbody>
</table>
<p>This function tries to steal a task from the queue. If the steal attempt is successful, the stolen task is returned. Additionally, if the queue is empty, the provided counter <code>num_empty_steals</code> is incremented; otherwise, <code>num_empty_steals</code> is reset to zero.</p>
</div></section>
</section>
</div>
</div>
</div>
</article></main>
<div class="m-doc-search" id="search">
<a href="#!" onclick="return hideSearch()"></a>
<div class="m-container">
<div class="m-row">
<div class="m-col-m-8 m-push-m-2">
<div class="m-doc-search-header m-text m-small">
<div><span class="m-label m-default">Tab</span> / <span class="m-label m-default">T</span> to search, <span class="m-label m-default">Esc</span> to close</div>
<div id="search-symbolcount">…</div>
</div>
<div class="m-doc-search-content">
<form>
<input type="search" name="q" id="search-input" placeholder="Loading …" disabled="disabled" autofocus="autofocus" autocomplete="off" spellcheck="false" />
</form>
<noscript class="m-text m-danger m-text-center">Unlike everything else in the docs, the search functionality <em>requires</em> JavaScript.</noscript>
<div id="search-help" class="m-text m-dim m-text-center">
<p class="m-noindent">Search for symbols, directories, files, pages or
modules. You can omit any prefix from the symbol or file path; adding a
<code>:</code> or <code>/</code> suffix lists all members of given symbol or
directory.</p>
<p class="m-noindent">Use <span class="m-label m-dim">↓</span>
/ <span class="m-label m-dim">↑</span> to navigate through the list,
<span class="m-label m-dim">Enter</span> to go.
<span class="m-label m-dim">Tab</span> autocompletes common prefix, you can
copy a link to the result using <span class="m-label m-dim">⌘</span>
<span class="m-label m-dim">L</span> while <span class="m-label m-dim">⌘</span>
<span class="m-label m-dim">M</span> produces a Markdown link.</p>
</div>
<div id="search-notfound" class="m-text m-warning m-text-center">Sorry, nothing was found.</div>
<ul id="search-results"></ul>
</div>
</div>
</div>
</div>
</div>
<script src="search-v2.js"></script>
<script src="searchdata-v2.js" async="async"></script>
<footer><nav>
<div class="m-container">
<div class="m-row">
<div class="m-col-l-10 m-push-l-1">
<p>Taskflow handbook is part of the <a href="https://taskflow.github.io">Taskflow project</a>, copyright © <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>, 2018–2025.<br />Generated by <a href="https://doxygen.org/">Doxygen</a> 1.12.0 and <a href="https://mcss.mosra.cz/">m.css</a>.</p>
</div>
</div>
</div>
</nav></footer>
</body>
</html>