<title>Taskflow: A General-purpose Task-parallel Programming System: tf::BoundedPriorityWSQ< Q, MaxPriority, PriorityFn > Class Template Reference</title>
<trclass="memdesc:ae95c19e8ea0b60f2842129ae244f66a1"><tdclass="mdescLeft"> </td><tdclass="mdescRight">the return type of pop and steal operations <br/></td></tr>
<trclass="memdesc:a4cf8e79b9fd8f76e256d73701f1a6ce7"><tdclass="mdescLeft"> </td><tdclass="mdescRight">constructs the queue with an optional priority function <br/></td></tr>
<trclass="memitem:a83a9e8b439ac53dc7c1c7d5ab6dc5484"><tdclass="memTemplItemLeft" align="right" valign="top">bool </td><tdclass="memTemplItemRight" valign="bottom"><aclass="el" href="#a83a9e8b439ac53dc7c1c7d5ab6dc5484">try_push</a> (O &&item)</td></tr>
<trclass="memdesc:a83a9e8b439ac53dc7c1c7d5ab6dc5484"><tdclass="mdescLeft"> </td><tdclass="mdescRight">tries to insert an item into the sub-queue determined by its priority <br/></td></tr>
<trclass="memitem:ae2faaf78030cd3eb7c23663f075697c9"><tdclass="memTemplItemLeft" align="right" valign="top">size_t </td><tdclass="memTemplItemRight" valign="bottom"><aclass="el" href="#ae2faaf78030cd3eb7c23663f075697c9">try_bulk_push</a> (I &first, size_t N)</td></tr>
<trclass="memdesc:ae2faaf78030cd3eb7c23663f075697c9"><tdclass="mdescLeft"> </td><tdclass="mdescRight">tries to insert a batch of items, routing contiguous same-priority runs to the corresponding sub-queue via bulk push <br/></td></tr>
<trclass="memdesc:a8e3650caab2c86a4acb76c41ba9ff282"><tdclass="mdescLeft"> </td><tdclass="mdescRight">pops an item from the highest-priority non-empty sub-queue <br/></td></tr>
<trclass="memdesc:a7c4ff903f70f22f74081b819970ab9bf"><tdclass="mdescLeft"> </td><tdclass="mdescRight">steals an item from the highest-priority non-empty sub-queue <br/></td></tr>
<trclass="memdesc:a4e407ebd21c81a9ade75668b3cede048"><tdclass="mdescLeft"> </td><tdclass="mdescRight">queries whether all sub-queues are empty at the time of this call <br/></td></tr>
<trclass="memdesc:a3cef7861456688c399107408a87725dc"><tdclass="mdescLeft"> </td><tdclass="mdescRight">queries the total number of items across all sub-queues at the time of this call <br/></td></tr>
<trclass="memdesc:acd7416b56e971ce6b600ec25cb64159b"><tdclass="mdescLeft"> </td><tdclass="mdescRight">queries the total capacity across all sub-queues <br/></td></tr>
<trclass="memdesc:a3f4fb190d4cf05441775a017102915c5"><tdclass="mdescLeft"> </td><tdclass="mdescRight">returns a reference to the sub-queue at the given priority level <br/></td></tr>
<trclass="memdesc:a3f701dd3996ac03aa405ad8d6ad10aa0"><tdclass="mdescLeft"> </td><tdclass="mdescRight">returns a const reference to the sub-queue at the given priority level <br/></td></tr>
<divclass="textblock"><divclass="compoundTemplParams">template<BoundedWSQLike Q, size_t MaxPriority, typename PriorityFn = DefaultPriorityFn><br/>
class tf::BoundedPriorityWSQ< Q, MaxPriority, PriorityFn ></div><p>class to create a lock-free bounded work-stealing queue with priority support </p>
<tr><tdclass="paramname">Q</td><td>underlying bounded work-stealing queue type; must satisfy <code><aclass="el" href="concepttf_1_1BoundedWSQLike.html" title="concept to check if a type supports bounded work-stealing queue operations">BoundedWSQLike</a></code></td></tr>
<tr><tdclass="paramname">MaxPriority</td><td>number of priority levels (sub-queues); must be at least 1 </td></tr>
<tr><tdclass="paramname">PriorityFn</td><td>callable <code></code>(const element&) -> size_t that maps an item to its priority index; the returned value must be in <code></code>[0, MaxPriority). Defaults to <code>DefaultPriorityFn</code>.</td></tr>
</table>
</dd>
</dl>
<p><code><aclass="el" href="classtf_1_1BoundedPriorityWSQ.html" title="class to create a lock-free bounded work-stealing queue with priority support">BoundedPriorityWSQ</a></code> wraps an array of <codeclass="param">MaxPriority</code> sub-queues of type <codeclass="param">Q</code> and routes each item to the sub-queue that corresponds to its priority. Priority levels are numbered from <code>0</code> to <code>MaxPriority-1</code> in decreasing order of urgency: priority <code>0</code> is the highest and priority <code>MaxPriority-1</code> is the lowest. Pop and steal operations always service sub-queues in ascending index order, so higher-priority items are consumed before lower-priority ones.</p>
<divclass="fragment"><divclass="line"><spanclass="comment">// 3-level priority queue with a custom priority function</span></div>
<divclass="ttc" id="aclasstf_1_1BoundedPriorityWSQ_html"><divclass="ttname"><ahref="classtf_1_1BoundedPriorityWSQ.html">tf::BoundedPriorityWSQ</a></div><divclass="ttdoc">class to create a lock-free bounded work-stealing queue with priority support</div><divclass="ttdef"><b>Definition</b> wsq.hpp:983</div></div>
</div><!-- fragment --></div><h2class="groupheader">Member Typedef Documentation</h2>
template<BoundedWSQLike Q, size_t MaxPriority, typename PriorityFn = DefaultPriorityFn> </div>
<tableclass="memname">
<tr>
<tdclass="memname">using <aclass="el" href="classtf_1_1BoundedPriorityWSQ.html">tf::BoundedPriorityWSQ</a>< Q, MaxPriority, PriorityFn >::value_type = typename Q::value_type</td>
</tr>
</table>
</div><divclass="memdoc">
<p>the return type of pop and steal operations </p>
<p>Inherits the <code><aclass="el" href="#ae95c19e8ea0b60f2842129ae244f66a1" title="the return type of pop and steal operations">value_type</a></code> of the underlying queue <codeclass="param">Q</code>. For pointer element types, it is the pointer type itself (using <code>nullptr</code> as the empty sentinel); for non-pointer types it is <code>std::optional<T></code>. </p>
</div>
</div>
<h2class="groupheader">Constructor & Destructor Documentation</h2>
<divclass="ttc" id="aclasstf_1_1BoundedPriorityWSQ_html_acd7416b56e971ce6b600ec25cb64159b"><divclass="ttname"><ahref="#acd7416b56e971ce6b600ec25cb64159b">tf::BoundedPriorityWSQ::capacity</a></div><divclass="ttdeci">constexpr size_t capacity() const</div><divclass="ttdoc">queries the total capacity across all sub-queues</div><divclass="ttdef"><b>Definition</b> wsq.hpp:1186</div></div>
<divclass="ttc" id="aclasstf_1_1BoundedPriorityWSQ_html_a4e407ebd21c81a9ade75668b3cede048"><divclass="ttname"><ahref="#a4e407ebd21c81a9ade75668b3cede048">tf::BoundedPriorityWSQ::empty</a></div><divclass="ttdeci">bool empty() const noexcept</div><divclass="ttdoc">queries whether all sub-queues are empty at the time of this call</div><divclass="ttdef"><b>Definition</b> wsq.hpp:1148</div></div>
<divclass="ttc" id="aclasstf_1_1BoundedPriorityWSQ_html_a83a9e8b439ac53dc7c1c7d5ab6dc5484"><divclass="ttname"><ahref="#a83a9e8b439ac53dc7c1c7d5ab6dc5484">tf::BoundedPriorityWSQ::try_push</a></div><divclass="ttdeci">bool try_push(O &&item)</div><divclass="ttdoc">tries to insert an item into the sub-queue determined by its priority</div><divclass="ttdef"><b>Definition</b> wsq.hpp:1023</div></div>
template<BoundedWSQLike Q, size_t MaxPriority, typename PriorityFn = DefaultPriorityFn> </div>
<tableclass="mlabels">
<tr>
<tdclass="mlabels-left">
<tableclass="memname">
<tr>
<tdclass="memname">Q & <aclass="el" href="classtf_1_1BoundedPriorityWSQ.html">tf::BoundedPriorityWSQ</a>< Q, MaxPriority, PriorityFn >::operator[] </td>
<divclass="ttc" id="aclasstf_1_1BoundedPriorityWSQ_html_a3cef7861456688c399107408a87725dc"><divclass="ttname"><ahref="#a3cef7861456688c399107408a87725dc">tf::BoundedPriorityWSQ::size</a></div><divclass="ttdeci">size_t size() const noexcept</div><divclass="ttdoc">queries the total number of items across all sub-queues at the time of this call</div><divclass="ttdef"><b>Definition</b> wsq.hpp:1167</div></div>
<divclass="ttc" id="aclasstf_1_1BoundedPriorityWSQ_html_a8e3650caab2c86a4acb76c41ba9ff282"><divclass="ttname"><ahref="#a8e3650caab2c86a4acb76c41ba9ff282">tf::BoundedPriorityWSQ::pop</a></div><divclass="ttdeci">value_type pop()</div><divclass="ttdoc">pops an item from the highest-priority non-empty sub-queue</div><divclass="ttdef"><b>Definition</b> wsq.hpp:1103</div></div>
template<BoundedWSQLike Q, size_t MaxPriority, typename PriorityFn = DefaultPriorityFn> </div>
<tableclass="mlabels">
<tr>
<tdclass="mlabels-left">
<tableclass="memname">
<tr>
<tdclass="memname">const Q & <aclass="el" href="classtf_1_1BoundedPriorityWSQ.html">tf::BoundedPriorityWSQ</a>< Q, MaxPriority, PriorityFn >::operator[] </td>
<p>pops an item from the highest-priority non-empty sub-queue </p>
<dlclass="section return"><dt>Returns</dt><dd>the popped item, or <code>empty_value()</code> if all sub-queues are empty</dd></dl>
<p>Sub-queues are checked in ascending index order (index 0 is highest priority). The element is removed from the owner (back) end of the selected sub-queue, following last-in-first-out (LIFO) order within each priority level.</p>
<divclass="line"><spanclass="comment">// process item</span></div>
<divclass="line">}</div>
<divclass="ttc" id="aclasstf_1_1BoundedWSQ_html_a97bbadef093d7518b88c62bc3de85b47"><divclass="ttname"><ahref="classtf_1_1BoundedWSQ.html#a97bbadef093d7518b88c62bc3de85b47">tf::BoundedWSQ::empty_value</a></div><divclass="ttdeci">static constexpr auto empty_value()</div><divclass="ttdoc">returns the empty sentinel value for the queue element type</div><divclass="ttdef"><b>Definition</b> wsq.hpp:751</div></div>
</div><!-- fragment --><p>Only the owner thread may call this method. </p>
<p>steals an item from the highest-priority non-empty sub-queue </p>
<dlclass="section return"><dt>Returns</dt><dd>the stolen item, or <code>empty_value()</code> if all sub-queues are empty</dd></dl>
<p>Sub-queues are checked in ascending index order (index 0 is highest priority). The element is removed from the thief (front) end of the selected sub-queue, following first-in-first-out (FIFO) order within each priority level.</p>
<divclass="line"><spanclass="comment">// process item</span></div>
<divclass="line">}</div>
<divclass="ttc" id="aclasstf_1_1BoundedPriorityWSQ_html_a7c4ff903f70f22f74081b819970ab9bf"><divclass="ttname"><ahref="#a7c4ff903f70f22f74081b819970ab9bf">tf::BoundedPriorityWSQ::steal</a></div><divclass="ttdeci">value_type steal()</div><divclass="ttdoc">steals an item from the highest-priority non-empty sub-queue</div><divclass="ttdef"><b>Definition</b> wsq.hpp:1129</div></div>
</div><!-- fragment --><p>Any thread may call this method concurrently. </p>
<tr><tdclass="paramname">I</td><td>random-access iterator type </td></tr>
</table>
</dd>
</dl>
<dlclass="params"><dt>Parameters</dt><dd>
<tableclass="params">
<tr><tdclass="paramname">first</td><td>iterator to the first item; advanced in place by the number of items inserted </td></tr>
<tr><tdclass="paramname">N</td><td>number of items to insert starting at <codeclass="param">first</code></td></tr>
</table>
</dd>
</dl>
<dlclass="section return"><dt>Returns</dt><dd>number of items successfully inserted</dd></dl>
<p>Scans <codeclass="param">first</code> for contiguous runs of items that map to the same sub-queue (as determined by <code>_priority_fn</code>) and delegates each run to the underlying queue's <code>try_bulk_push</code> (a single atomic bottom update per run). Stops immediately if a run is only partially inserted (the target sub-queue became full), leaving <codeclass="param">first</code> pointing at the first uninserted item.</p>
<tr><tdclass="paramname">O</td><td>item type (forwarded) </td></tr>
</table>
</dd>
</dl>
<dlclass="params"><dt>Parameters</dt><dd>
<tableclass="params">
<tr><tdclass="paramname">item</td><td>the item to insert; <code>_priority_fn(item)</code> determines the target sub-queue and must return a value in <code></code>[0, MaxPriority) </td></tr>
</table>
</dd>
</dl>
<dlclass="section return"><dt>Returns</dt><dd><code>true</code> if the item was inserted, <code>false</code> if the target sub-queue is full</dd></dl>