mesos-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From git-site-r...@apache.org
Subject mesos-site git commit: Updated the website built from mesos SHA: 800f669.
Date Wed, 25 Jul 2018 23:02:53 GMT
Repository: mesos-site
Updated Branches:
  refs/heads/asf-site 18a865743 -> 103bbf360


Updated the website built from mesos SHA: 800f669.


Project: http://git-wip-us.apache.org/repos/asf/mesos-site/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos-site/commit/103bbf36
Tree: http://git-wip-us.apache.org/repos/asf/mesos-site/tree/103bbf36
Diff: http://git-wip-us.apache.org/repos/asf/mesos-site/diff/103bbf36

Branch: refs/heads/asf-site
Commit: 103bbf3609a8f9b110b89866562ea646b2a72c11
Parents: 18a8657
Author: jenkins <builds@apache.org>
Authored: Wed Jul 25 23:02:49 2018 +0000
Committer: jenkins <builds@apache.org>
Committed: Wed Jul 25 23:02:49 2018 +0000

----------------------------------------------------------------------
 content/api/latest/c++/mpsc__linked__queue_8hpp_source.html | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/mesos-site/blob/103bbf36/content/api/latest/c++/mpsc__linked__queue_8hpp_source.html
----------------------------------------------------------------------
diff --git a/content/api/latest/c++/mpsc__linked__queue_8hpp_source.html b/content/api/latest/c++/mpsc__linked__queue_8hpp_source.html
index d76d340..9606ac0 100644
--- a/content/api/latest/c++/mpsc__linked__queue_8hpp_source.html
+++ b/content/api/latest/c++/mpsc__linked__queue_8hpp_source.html
@@ -52,7 +52,7 @@
 <div class="title">mpsc_linked_queue.hpp</div>  </div>
 </div><!--header-->
 <div class="contents">
-<a href="mpsc__linked__queue_8hpp.html">Go to the documentation of this file.</a><div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno">    1</span>&#160;<span class="comment">// Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);</span></div><div class="line"><a name="l00002"></a><span class="lineno">    2</span>&#160;<span class="comment">// you may not use this file except in compliance with the License.</span></div><div class="line"><a name="l00003"></a><span class="lineno">    3</span>&#160;<span class="comment">// You may obtain a copy of the License at</span></div><div class="line"><a name="l00004"></a><span class="lineno">    4</span>&#160;<span class="comment">//</span></div><div class="line"><a name="l00005"></a><span class="lineno">    5</span>&#160;<span class="comment">//     http://www.apache.org/licenses/LICENSE-2.0</span></div><div class="line"><a name="l00006"></a><span class="lineno">    6</span>&#160;<span class="co
 mment">//</span></div><div class="line"><a name="l00007"></a><span class="lineno">    7</span>&#160;<span class="comment">// Unless required by applicable law or agreed to in writing, software</span></div><div class="line"><a name="l00008"></a><span class="lineno">    8</span>&#160;<span class="comment">// distributed under the License is distributed on an &quot;AS IS&quot; BASIS,</span></div><div class="line"><a name="l00009"></a><span class="lineno">    9</span>&#160;<span class="comment">// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.</span></div><div class="line"><a name="l00010"></a><span class="lineno">   10</span>&#160;<span class="comment">// See the License for the specific language governing permissions and</span></div><div class="line"><a name="l00011"></a><span class="lineno">   11</span>&#160;<span class="comment">// limitations under the License</span></div><div class="line"><a name="l00012"></a><span class="lineno">   12</span>&#160;</div><
 div class="line"><a name="l00013"></a><span class="lineno">   13</span>&#160;<span class="preprocessor">#ifndef __MPSC_LINKED_QUEUE_HPP__</span></div><div class="line"><a name="l00014"></a><span class="lineno">   14</span>&#160;<span class="preprocessor">#define __MPSC_LINKED_QUEUE_HPP__</span></div><div class="line"><a name="l00015"></a><span class="lineno">   15</span>&#160;</div><div class="line"><a name="l00016"></a><span class="lineno">   16</span>&#160;<span class="preprocessor">#include &lt;atomic&gt;</span></div><div class="line"><a name="l00017"></a><span class="lineno">   17</span>&#160;<span class="preprocessor">#include &lt;functional&gt;</span></div><div class="line"><a name="l00018"></a><span class="lineno">   18</span>&#160;</div><div class="line"><a name="l00019"></a><span class="lineno">   19</span>&#160;<span class="preprocessor">#include &lt;glog/logging.h&gt;</span></div><div class="line"><a name="l00020"></a><span class="lineno">   20</span>&#160;</div><div clas
 s="line"><a name="l00021"></a><span class="lineno">   21</span>&#160;<span class="keyword">namespace </span><a class="code" href="namespaceprocess.html">process</a> {</div><div class="line"><a name="l00022"></a><span class="lineno">   22</span>&#160;</div><div class="line"><a name="l00023"></a><span class="lineno">   23</span>&#160;<span class="comment">// This queue is a C++ port of the MpscLinkedQueue of JCTools, but limited to</span></div><div class="line"><a name="l00024"></a><span class="lineno">   24</span>&#160;<span class="comment">// the core methods:</span></div><div class="line"><a name="l00025"></a><span class="lineno">   25</span>&#160;<span class="comment">// https://github.com/JCTools/JCTools/blob/master/jctools-core/src/main/java/org/jctools/queues/MpscLinkedQueue.java</span></div><div class="line"><a name="l00026"></a><span class="lineno">   26</span>&#160;<span class="comment">//</span></div><div class="line"><a name="l00027"></a><span class="lineno">   27</span>&#
 160;<span class="comment">// which is a Java port of the MPSC algorithm as presented in following article:</span></div><div class="line"><a name="l00028"></a><span class="lineno">   28</span>&#160;<span class="comment">// http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue</span></div><div class="line"><a name="l00029"></a><span class="lineno">   29</span>&#160;<span class="comment">//</span></div><div class="line"><a name="l00030"></a><span class="lineno">   30</span>&#160;<span class="comment">// The queue has following properties:</span></div><div class="line"><a name="l00031"></a><span class="lineno">   31</span>&#160;<span class="comment">//   Producers are wait-free (one atomic exchange per enqueue)</span></div><div class="line"><a name="l00032"></a><span class="lineno">   32</span>&#160;<span class="comment">//   Consumer is</span></div><div class="line"><a name="l00033"></a><span class="lineno">   33</span>&#160;<span class="comment"
 >//     - lock-free</span></div><div class="line"><a name="l00034"></a><span class="lineno">   34</span>&#160;<span class="comment">//     - mostly wait-free, except when consumer reaches the end of the queue</span></div><div class="line"><a name="l00035"></a><span class="lineno">   35</span>&#160;<span class="comment">//       and producer enqueued a new node, but did not update the next pointer</span></div><div class="line"><a name="l00036"></a><span class="lineno">   36</span>&#160;<span class="comment">//       on the old node, yet</span></div><div class="line"><a name="l00037"></a><span class="lineno">   37</span>&#160;<span class="keyword">template</span> &lt;<span class="keyword">typename</span> T&gt;</div><div class="line"><a name="l00038"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html">   38</a></span>&#160;<span class="keyword">class </span><a class="code" href="classprocess_1_1MpscLinkedQueue.html">MpscLinkedQueue</a></div><div class="
 line"><a name="l00039"></a><span class="lineno">   39</span>&#160;{</div><div class="line"><a name="l00040"></a><span class="lineno">   40</span>&#160;<span class="keyword">private</span>:</div><div class="line"><a name="l00041"></a><span class="lineno">   41</span>&#160;  <span class="keyword">template</span> &lt;<span class="keyword">typename</span> E&gt;</div><div class="line"><a name="l00042"></a><span class="lineno">   42</span>&#160;  <span class="keyword">struct </span>Node</div><div class="line"><a name="l00043"></a><span class="lineno">   43</span>&#160;  {</div><div class="line"><a name="l00044"></a><span class="lineno">   44</span>&#160;  <span class="keyword">public</span>:</div><div class="line"><a name="l00045"></a><span class="lineno">   45</span>&#160;    <span class="keyword">explicit</span> Node(E* element = <span class="keyword">nullptr</span>) : element(element) {}</div><div class="line"><a name="l00046"></a><span class="lineno">   46</span>&#160;</div><div class
 ="line"><a name="l00047"></a><span class="lineno">   47</span>&#160;    E* element;</div><div class="line"><a name="l00048"></a><span class="lineno">   48</span>&#160;    std::atomic&lt;Node&lt;E&gt;*&gt; next = ATOMIC_VAR_INIT(<span class="keyword">nullptr</span>);</div><div class="line"><a name="l00049"></a><span class="lineno">   49</span>&#160;  };</div><div class="line"><a name="l00050"></a><span class="lineno">   50</span>&#160;</div><div class="line"><a name="l00051"></a><span class="lineno">   51</span>&#160;<span class="keyword">public</span>:</div><div class="line"><a name="l00052"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#a4955e95e3146ffd4865f47636f934a6f">   52</a></span>&#160;  <a class="code" href="classprocess_1_1MpscLinkedQueue.html#a4955e95e3146ffd4865f47636f934a6f">MpscLinkedQueue</a>()</div><div class="line"><a name="l00053"></a><span class="lineno">   53</span>&#160;  {</div><div class="line"><a name="l00054"></a><span cl
 ass="lineno">   54</span>&#160;    tail = <span class="keyword">new</span> Node&lt;T&gt;();</div><div class="line"><a name="l00055"></a><span class="lineno">   55</span>&#160;    head.store(tail);</div><div class="line"><a name="l00056"></a><span class="lineno">   56</span>&#160;  }</div><div class="line"><a name="l00057"></a><span class="lineno">   57</span>&#160;</div><div class="line"><a name="l00058"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#ac6ff02deeadfed9066166093769b3b9a">   58</a></span>&#160;  <a class="code" href="classprocess_1_1MpscLinkedQueue.html#ac6ff02deeadfed9066166093769b3b9a">~MpscLinkedQueue</a>()</div><div class="line"><a name="l00059"></a><span class="lineno">   59</span>&#160;  {</div><div class="line"><a name="l00060"></a><span class="lineno">   60</span>&#160;    <span class="keywordflow">while</span> (<span class="keyword">auto</span> element = <a class="code" href="classprocess_1_1MpscLinkedQueue.html#af9711afa3db
 6d73c2c31bab3f30e5f61">dequeue</a>()) {</div><div class="line"><a name="l00061"></a><span class="lineno">   61</span>&#160;      <span class="keyword">delete</span> element;</div><div class="line"><a name="l00062"></a><span class="lineno">   62</span>&#160;    }</div><div class="line"><a name="l00063"></a><span class="lineno">   63</span>&#160;</div><div class="line"><a name="l00064"></a><span class="lineno">   64</span>&#160;    <span class="keyword">delete</span> tail;</div><div class="line"><a name="l00065"></a><span class="lineno">   65</span>&#160;  }</div><div class="line"><a name="l00066"></a><span class="lineno">   66</span>&#160;</div><div class="line"><a name="l00067"></a><span class="lineno">   67</span>&#160;  <span class="comment">// Multi producer safe.</span></div><div class="line"><a name="l00068"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#a15b0656de08bb0b8810a4d1bec88ab45">   68</a></span>&#160;  <span class="keywordtype">voi
 d</span> <a class="code" href="classprocess_1_1MpscLinkedQueue.html#a15b0656de08bb0b8810a4d1bec88ab45">enqueue</a>(T* element)</div><div class="line"><a name="l00069"></a><span class="lineno">   69</span>&#160;  {</div><div class="line"><a name="l00070"></a><span class="lineno">   70</span>&#160;    <span class="comment">// A `nullptr` is used to denote an empty queue when doing a</span></div><div class="line"><a name="l00071"></a><span class="lineno">   71</span>&#160;    <span class="comment">// `dequeue()` so producers can&#39;t use it as an element.</span></div><div class="line"><a name="l00072"></a><span class="lineno">   72</span>&#160;    CHECK_NOTNULL(element);</div><div class="line"><a name="l00073"></a><span class="lineno">   73</span>&#160;</div><div class="line"><a name="l00074"></a><span class="lineno">   74</span>&#160;    <span class="keyword">auto</span> newNode = <span class="keyword">new</span> Node&lt;T&gt;(element);</div><div class="line"><a name="l00075"></a><sp
 an class="lineno">   75</span>&#160;</div><div class="line"><a name="l00076"></a><span class="lineno">   76</span>&#160;    <span class="comment">// Exchange is guaranteed to only give the old value to one</span></div><div class="line"><a name="l00077"></a><span class="lineno">   77</span>&#160;    <span class="comment">// producer, so this is safe and wait-free.</span></div><div class="line"><a name="l00078"></a><span class="lineno">   78</span>&#160;    <span class="keyword">auto</span> oldhead = head.exchange(newNode, std::memory_order_release);</div><div class="line"><a name="l00079"></a><span class="lineno">   79</span>&#160;</div><div class="line"><a name="l00080"></a><span class="lineno">   80</span>&#160;    <span class="comment">// At this point if this thread context switches out we may block</span></div><div class="line"><a name="l00081"></a><span class="lineno">   81</span>&#160;    <span class="comment">// the consumer from doing a dequeue (see below). Eventually we&#39
 ;ll</span></div><div class="line"><a name="l00082"></a><span class="lineno">   82</span>&#160;    <span class="comment">// unblock the consumer once we run again and execute the next</span></div><div class="line"><a name="l00083"></a><span class="lineno">   83</span>&#160;    <span class="comment">// line of code.</span></div><div class="line"><a name="l00084"></a><span class="lineno">   84</span>&#160;    oldhead-&gt;next.store(newNode, std::memory_order_release);</div><div class="line"><a name="l00085"></a><span class="lineno">   85</span>&#160;  }</div><div class="line"><a name="l00086"></a><span class="lineno">   86</span>&#160;</div><div class="line"><a name="l00087"></a><span class="lineno">   87</span>&#160;  <span class="comment">// Single consumer only.</span></div><div class="line"><a name="l00088"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#af9711afa3db6d73c2c31bab3f30e5f61">   88</a></span>&#160;  T* <a class="code" href="classproc
 ess_1_1MpscLinkedQueue.html#af9711afa3db6d73c2c31bab3f30e5f61">dequeue</a>()</div><div class="line"><a name="l00089"></a><span class="lineno">   89</span>&#160;  {</div><div class="line"><a name="l00090"></a><span class="lineno">   90</span>&#160;    <span class="keyword">auto</span> currentTail = tail;</div><div class="line"><a name="l00091"></a><span class="lineno">   91</span>&#160;</div><div class="line"><a name="l00092"></a><span class="lineno">   92</span>&#160;    <span class="comment">// Check and see if there is an actual element linked from `tail`</span></div><div class="line"><a name="l00093"></a><span class="lineno">   93</span>&#160;    <span class="comment">// since we use `tail` as a &quot;stub&quot; rather than the actual element.</span></div><div class="line"><a name="l00094"></a><span class="lineno">   94</span>&#160;    <span class="keyword">auto</span> nextTail = currentTail-&gt;next.exchange(</div><div class="line"><a name="l00095"></a><span class="lineno">   95
 </span>&#160;        <span class="keyword">nullptr</span>,</div><div class="line"><a name="l00096"></a><span class="lineno">   96</span>&#160;        std::memory_order_relaxed);</div><div class="line"><a name="l00097"></a><span class="lineno">   97</span>&#160;</div><div class="line"><a name="l00098"></a><span class="lineno">   98</span>&#160;    <span class="comment">// There are three possible cases here:</span></div><div class="line"><a name="l00099"></a><span class="lineno">   99</span>&#160;    <span class="comment">//</span></div><div class="line"><a name="l00100"></a><span class="lineno">  100</span>&#160;    <span class="comment">// (1) The queue is empty.</span></div><div class="line"><a name="l00101"></a><span class="lineno">  101</span>&#160;    <span class="comment">// (2) The queue appears empty but a producer is still enqueuing</span></div><div class="line"><a name="l00102"></a><span class="lineno">  102</span>&#160;    <span class="comment">//     so let&#39;s wait fo
 r it and then dequeue.</span></div><div class="line"><a name="l00103"></a><span class="lineno">  103</span>&#160;    <span class="comment">// (3) We have something to dequeue.</span></div><div class="line"><a name="l00104"></a><span class="lineno">  104</span>&#160;    <span class="comment">//</span></div><div class="line"><a name="l00105"></a><span class="lineno">  105</span>&#160;    <span class="comment">// Start by checking if the queue is or appears empty.</span></div><div class="line"><a name="l00106"></a><span class="lineno">  106</span>&#160;    <span class="keywordflow">if</span> (nextTail == <span class="keyword">nullptr</span>) {</div><div class="line"><a name="l00107"></a><span class="lineno">  107</span>&#160;      <span class="comment">// Now check if the queue is actually empty or just appears</span></div><div class="line"><a name="l00108"></a><span class="lineno">  108</span>&#160;      <span class="comment">// empty. If it&#39;s actually empty then return `nullptr` 
 to denote</span></div><div class="line"><a name="l00109"></a><span class="lineno">  109</span>&#160;      <span class="comment">// emptiness.</span></div><div class="line"><a name="l00110"></a><span class="lineno">  110</span>&#160;      <span class="keywordflow">if</span> (head.load(std::memory_order_relaxed) == tail) {</div><div class="line"><a name="l00111"></a><span class="lineno">  111</span>&#160;        <span class="keywordflow">return</span> <span class="keyword">nullptr</span>;</div><div class="line"><a name="l00112"></a><span class="lineno">  112</span>&#160;      }</div><div class="line"><a name="l00113"></a><span class="lineno">  113</span>&#160;</div><div class="line"><a name="l00114"></a><span class="lineno">  114</span>&#160;      <span class="comment">// Another thread already inserted a new node, but did not</span></div><div class="line"><a name="l00115"></a><span class="lineno">  115</span>&#160;      <span class="comment">// connect it to the tail, yet, so we spin
 -wait. At this point</span></div><div class="line"><a name="l00116"></a><span class="lineno">  116</span>&#160;      <span class="comment">// we are not wait-free anymore.</span></div><div class="line"><a name="l00117"></a><span class="lineno">  117</span>&#160;      <span class="keywordflow">do</span> {</div><div class="line"><a name="l00118"></a><span class="lineno">  118</span>&#160;        nextTail = currentTail-&gt;next.exchange(</div><div class="line"><a name="l00119"></a><span class="lineno">  119</span>&#160;            <span class="keyword">nullptr</span>,</div><div class="line"><a name="l00120"></a><span class="lineno">  120</span>&#160;            std::memory_order_relaxed);</div><div class="line"><a name="l00121"></a><span class="lineno">  121</span>&#160;      } <span class="keywordflow">while</span> (nextTail == <span class="keyword">nullptr</span>);</div><div class="line"><a name="l00122"></a><span class="lineno">  122</span>&#160;    }</div><div class="line"><a name=
 "l00123"></a><span class="lineno">  123</span>&#160;</div><div class="line"><a name="l00124"></a><span class="lineno">  124</span>&#160;    CHECK_NOTNULL(nextTail);</div><div class="line"><a name="l00125"></a><span class="lineno">  125</span>&#160;</div><div class="line"><a name="l00126"></a><span class="lineno">  126</span>&#160;    <span class="keyword">auto</span> element = nextTail-&gt;element;</div><div class="line"><a name="l00127"></a><span class="lineno">  127</span>&#160;    nextTail-&gt;element = <span class="keyword">nullptr</span>;</div><div class="line"><a name="l00128"></a><span class="lineno">  128</span>&#160;</div><div class="line"><a name="l00129"></a><span class="lineno">  129</span>&#160;    tail = nextTail;</div><div class="line"><a name="l00130"></a><span class="lineno">  130</span>&#160;    <span class="keyword">delete</span> currentTail;</div><div class="line"><a name="l00131"></a><span class="lineno">  131</span>&#160;</div><div class="line"><a name="l00132"
 ></a><span class="lineno">  132</span>&#160;    <span class="keywordflow">return</span> element;</div><div class="line"><a name="l00133"></a><span class="lineno">  133</span>&#160;  }</div><div class="line"><a name="l00134"></a><span class="lineno">  134</span>&#160;</div><div class="line"><a name="l00135"></a><span class="lineno">  135</span>&#160;  <span class="comment">// Single consumer only.</span></div><div class="line"><a name="l00136"></a><span class="lineno">  136</span>&#160;  <span class="comment">//</span></div><div class="line"><a name="l00137"></a><span class="lineno">  137</span>&#160;  <span class="comment">// TODO(drexin): Provide C++ style iteration so someone can just use</span></div><div class="line"><a name="l00138"></a><span class="lineno">  138</span>&#160;  <span class="comment">// the `std::for_each()`.</span></div><div class="line"><a name="l00139"></a><span class="lineno">  139</span>&#160;  <span class="keyword">template</span> &lt;<span class="keyword">t
 ypename</span> F&gt;</div><div class="line"><a name="l00140"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#a361ad3f84e782291c0ec6d714c7e140d">  140</a></span>&#160;  <span class="keywordtype">void</span> <a class="code" href="classprocess_1_1MpscLinkedQueue.html#a361ad3f84e782291c0ec6d714c7e140d">for_each</a>(F&amp;&amp; <a class="code" href="namespaceprocess.html#a62d5333e8ec1817c249cf83e15d568b4">f</a>)</div><div class="line"><a name="l00141"></a><span class="lineno">  141</span>&#160;  {</div><div class="line"><a name="l00142"></a><span class="lineno">  142</span>&#160;    <span class="keyword">auto</span> end = head.load();</div><div class="line"><a name="l00143"></a><span class="lineno">  143</span>&#160;    <span class="keyword">auto</span> node = tail;</div><div class="line"><a name="l00144"></a><span class="lineno">  144</span>&#160;</div><div class="line"><a name="l00145"></a><span class="lineno">  145</span>&#160;    <span class="keywo
 rdflow">for</span> (;;) {</div><div class="line"><a name="l00146"></a><span class="lineno">  146</span>&#160;      node = node-&gt;next.load();</div><div class="line"><a name="l00147"></a><span class="lineno">  147</span>&#160;</div><div class="line"><a name="l00148"></a><span class="lineno">  148</span>&#160;      <span class="comment">// We are following the linked structure until we reach the end</span></div><div class="line"><a name="l00149"></a><span class="lineno">  149</span>&#160;      <span class="comment">// node. There is a race with new nodes being added, so we limit</span></div><div class="line"><a name="l00150"></a><span class="lineno">  150</span>&#160;      <span class="comment">// the traversal to the last node at the time we started.</span></div><div class="line"><a name="l00151"></a><span class="lineno">  151</span>&#160;      <span class="keywordflow">if</span> (node == <span class="keyword">nullptr</span>) {</div><div class="line"><a name="l00152"></a><span clas
 s="lineno">  152</span>&#160;        <span class="keywordflow">return</span>;</div><div class="line"><a name="l00153"></a><span class="lineno">  153</span>&#160;      }</div><div class="line"><a name="l00154"></a><span class="lineno">  154</span>&#160;</div><div class="line"><a name="l00155"></a><span class="lineno">  155</span>&#160;      <a class="code" href="namespaceprocess.html#a62d5333e8ec1817c249cf83e15d568b4">f</a>(node-&gt;element);</div><div class="line"><a name="l00156"></a><span class="lineno">  156</span>&#160;</div><div class="line"><a name="l00157"></a><span class="lineno">  157</span>&#160;      <span class="keywordflow">if</span> (node == end) {</div><div class="line"><a name="l00158"></a><span class="lineno">  158</span>&#160;        <span class="keywordflow">return</span>;</div><div class="line"><a name="l00159"></a><span class="lineno">  159</span>&#160;      }</div><div class="line"><a name="l00160"></a><span class="lineno">  160</span>&#160;    }</div><div clas
 s="line"><a name="l00161"></a><span class="lineno">  161</span>&#160;  }</div><div class="line"><a name="l00162"></a><span class="lineno">  162</span>&#160;</div><div class="line"><a name="l00163"></a><span class="lineno">  163</span>&#160;  <span class="comment">// Single consumer only.</span></div><div class="line"><a name="l00164"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#a995ca5eb7bf5842b0796458f08549ee3">  164</a></span>&#160;  <span class="keywordtype">bool</span> <a class="code" href="classprocess_1_1MpscLinkedQueue.html#a995ca5eb7bf5842b0796458f08549ee3">empty</a>()</div><div class="line"><a name="l00165"></a><span class="lineno">  165</span>&#160;  {</div><div class="line"><a name="l00166"></a><span class="lineno">  166</span>&#160;    <span class="keywordflow">return</span> tail-&gt;next.load(std::memory_order_relaxed) == <span class="keyword">nullptr</span> &amp;&amp;</div><div class="line"><a name="l00167"></a><span class="lineno
 ">  167</span>&#160;      head.load(std::memory_order_relaxed) == tail;</div><div class="line"><a name="l00168"></a><span class="lineno">  168</span>&#160;  }</div><div class="line"><a name="l00169"></a><span class="lineno">  169</span>&#160;</div><div class="line"><a name="l00170"></a><span class="lineno">  170</span>&#160;<span class="keyword">private</span>:</div><div class="line"><a name="l00171"></a><span class="lineno">  171</span>&#160;  <span class="comment">// TODO(drexin): Programatically get the cache line size.</span></div><div class="line"><a name="l00172"></a><span class="lineno">  172</span>&#160;  <span class="comment">//</span></div><div class="line"><a name="l00173"></a><span class="lineno">  173</span>&#160;  <span class="comment">// We align head to 64 bytes (x86 cache line size) to guarantee</span></div><div class="line"><a name="l00174"></a><span class="lineno">  174</span>&#160;  <span class="comment">// it to be put on a new cache line. This is to prevent fal
 se</span></div><div class="line"><a name="l00175"></a><span class="lineno">  175</span>&#160;  <span class="comment">// sharing with other objects that could otherwise end up on</span></div><div class="line"><a name="l00176"></a><span class="lineno">  176</span>&#160;  <span class="comment">// the same cache line as this queue. We also align tail to</span></div><div class="line"><a name="l00177"></a><span class="lineno">  177</span>&#160;  <span class="comment">// avoid false sharing with head and add padding after tail</span></div><div class="line"><a name="l00178"></a><span class="lineno">  178</span>&#160;  <span class="comment">// to avoid false sharing with other objects.</span></div><div class="line"><a name="l00179"></a><span class="lineno">  179</span>&#160;  <span class="keyword">alignas</span>(64) std::atomic&lt;Node&lt;T&gt;*&gt; head;</div><div class="line"><a name="l00180"></a><span class="lineno">  180</span>&#160;  <span class="keyword">alignas</span>(64) Node&lt;T&gt
 ;* tail;</div><div class="line"><a name="l00181"></a><span class="lineno">  181</span>&#160;  <span class="keywordtype">char</span> pad[64 - <span class="keyword">sizeof</span>(tail)];</div><div class="line"><a name="l00182"></a><span class="lineno">  182</span>&#160;};</div><div class="line"><a name="l00183"></a><span class="lineno">  183</span>&#160;</div><div class="line"><a name="l00184"></a><span class="lineno">  184</span>&#160;} <span class="comment">// namespace process {</span></div><div class="line"><a name="l00185"></a><span class="lineno">  185</span>&#160;</div><div class="line"><a name="l00186"></a><span class="lineno">  186</span>&#160;<span class="preprocessor">#endif // __MPSC_LINKED_QUEUE_HPP__</span></div><div class="ttc" id="classprocess_1_1MpscLinkedQueue_html"><div class="ttname"><a href="classprocess_1_1MpscLinkedQueue.html">process::MpscLinkedQueue</a></div><div class="ttdef"><b>Definition:</b> mpsc_linked_queue.hpp:38</div></div>
+<a href="mpsc__linked__queue_8hpp.html">Go to the documentation of this file.</a><div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno">    1</span>&#160;<span class="comment">// Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);</span></div><div class="line"><a name="l00002"></a><span class="lineno">    2</span>&#160;<span class="comment">// you may not use this file except in compliance with the License.</span></div><div class="line"><a name="l00003"></a><span class="lineno">    3</span>&#160;<span class="comment">// You may obtain a copy of the License at</span></div><div class="line"><a name="l00004"></a><span class="lineno">    4</span>&#160;<span class="comment">//</span></div><div class="line"><a name="l00005"></a><span class="lineno">    5</span>&#160;<span class="comment">//     http://www.apache.org/licenses/LICENSE-2.0</span></div><div class="line"><a name="l00006"></a><span class="lineno">    6</span>&#160;<span class="co
 mment">//</span></div><div class="line"><a name="l00007"></a><span class="lineno">    7</span>&#160;<span class="comment">// Unless required by applicable law or agreed to in writing, software</span></div><div class="line"><a name="l00008"></a><span class="lineno">    8</span>&#160;<span class="comment">// distributed under the License is distributed on an &quot;AS IS&quot; BASIS,</span></div><div class="line"><a name="l00009"></a><span class="lineno">    9</span>&#160;<span class="comment">// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.</span></div><div class="line"><a name="l00010"></a><span class="lineno">   10</span>&#160;<span class="comment">// See the License for the specific language governing permissions and</span></div><div class="line"><a name="l00011"></a><span class="lineno">   11</span>&#160;<span class="comment">// limitations under the License</span></div><div class="line"><a name="l00012"></a><span class="lineno">   12</span>&#160;</div><
 div class="line"><a name="l00013"></a><span class="lineno">   13</span>&#160;<span class="preprocessor">#ifndef __MPSC_LINKED_QUEUE_HPP__</span></div><div class="line"><a name="l00014"></a><span class="lineno">   14</span>&#160;<span class="preprocessor">#define __MPSC_LINKED_QUEUE_HPP__</span></div><div class="line"><a name="l00015"></a><span class="lineno">   15</span>&#160;</div><div class="line"><a name="l00016"></a><span class="lineno">   16</span>&#160;<span class="preprocessor">#include &lt;atomic&gt;</span></div><div class="line"><a name="l00017"></a><span class="lineno">   17</span>&#160;<span class="preprocessor">#include &lt;functional&gt;</span></div><div class="line"><a name="l00018"></a><span class="lineno">   18</span>&#160;</div><div class="line"><a name="l00019"></a><span class="lineno">   19</span>&#160;<span class="preprocessor">#include &lt;glog/logging.h&gt;</span></div><div class="line"><a name="l00020"></a><span class="lineno">   20</span>&#160;</div><div clas
 s="line"><a name="l00021"></a><span class="lineno">   21</span>&#160;<span class="keyword">namespace </span><a class="code" href="namespaceprocess.html">process</a> {</div><div class="line"><a name="l00022"></a><span class="lineno">   22</span>&#160;</div><div class="line"><a name="l00023"></a><span class="lineno">   23</span>&#160;<span class="comment">// This queue is a C++ port of the MpscLinkedQueue of JCTools, but limited to</span></div><div class="line"><a name="l00024"></a><span class="lineno">   24</span>&#160;<span class="comment">// the core methods:</span></div><div class="line"><a name="l00025"></a><span class="lineno">   25</span>&#160;<span class="comment">// https://github.com/JCTools/JCTools/blob/master/jctools-core/src/main/java/org/jctools/queues/MpscLinkedQueue.java</span></div><div class="line"><a name="l00026"></a><span class="lineno">   26</span>&#160;<span class="comment">//</span></div><div class="line"><a name="l00027"></a><span class="lineno">   27</span>&#
 160;<span class="comment">// which is a Java port of the MPSC algorithm as presented in following article:</span></div><div class="line"><a name="l00028"></a><span class="lineno">   28</span>&#160;<span class="comment">// http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue</span></div><div class="line"><a name="l00029"></a><span class="lineno">   29</span>&#160;<span class="comment">//</span></div><div class="line"><a name="l00030"></a><span class="lineno">   30</span>&#160;<span class="comment">// The queue has following properties:</span></div><div class="line"><a name="l00031"></a><span class="lineno">   31</span>&#160;<span class="comment">//   Producers are wait-free (one atomic exchange per enqueue)</span></div><div class="line"><a name="l00032"></a><span class="lineno">   32</span>&#160;<span class="comment">//   Consumer is</span></div><div class="line"><a name="l00033"></a><span class="lineno">   33</span>&#160;<span class="comment"
 >//     - lock-free</span></div><div class="line"><a name="l00034"></a><span class="lineno">   34</span>&#160;<span class="comment">//     - mostly wait-free, except when consumer reaches the end of the queue</span></div><div class="line"><a name="l00035"></a><span class="lineno">   35</span>&#160;<span class="comment">//       and producer enqueued a new node, but did not update the next pointer</span></div><div class="line"><a name="l00036"></a><span class="lineno">   36</span>&#160;<span class="comment">//       on the old node, yet</span></div><div class="line"><a name="l00037"></a><span class="lineno">   37</span>&#160;<span class="keyword">template</span> &lt;<span class="keyword">typename</span> T&gt;</div><div class="line"><a name="l00038"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html">   38</a></span>&#160;<span class="keyword">class </span><a class="code" href="classprocess_1_1MpscLinkedQueue.html">MpscLinkedQueue</a></div><div class="
 line"><a name="l00039"></a><span class="lineno">   39</span>&#160;{</div><div class="line"><a name="l00040"></a><span class="lineno">   40</span>&#160;<span class="keyword">private</span>:</div><div class="line"><a name="l00041"></a><span class="lineno">   41</span>&#160;  <span class="keyword">template</span> &lt;<span class="keyword">typename</span> E&gt;</div><div class="line"><a name="l00042"></a><span class="lineno">   42</span>&#160;  <span class="keyword">struct </span>Node</div><div class="line"><a name="l00043"></a><span class="lineno">   43</span>&#160;  {</div><div class="line"><a name="l00044"></a><span class="lineno">   44</span>&#160;  <span class="keyword">public</span>:</div><div class="line"><a name="l00045"></a><span class="lineno">   45</span>&#160;    <span class="keyword">explicit</span> Node(E* element = <span class="keyword">nullptr</span>) : element(element) {}</div><div class="line"><a name="l00046"></a><span class="lineno">   46</span>&#160;</div><div class
 ="line"><a name="l00047"></a><span class="lineno">   47</span>&#160;    E* element;</div><div class="line"><a name="l00048"></a><span class="lineno">   48</span>&#160;    std::atomic&lt;Node&lt;E&gt;*&gt; next = ATOMIC_VAR_INIT(<span class="keyword">nullptr</span>);</div><div class="line"><a name="l00049"></a><span class="lineno">   49</span>&#160;  };</div><div class="line"><a name="l00050"></a><span class="lineno">   50</span>&#160;</div><div class="line"><a name="l00051"></a><span class="lineno">   51</span>&#160;<span class="keyword">public</span>:</div><div class="line"><a name="l00052"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#a4955e95e3146ffd4865f47636f934a6f">   52</a></span>&#160;  <a class="code" href="classprocess_1_1MpscLinkedQueue.html#a4955e95e3146ffd4865f47636f934a6f">MpscLinkedQueue</a>()</div><div class="line"><a name="l00053"></a><span class="lineno">   53</span>&#160;  {</div><div class="line"><a name="l00054"></a><span cl
 ass="lineno">   54</span>&#160;    tail = <span class="keyword">new</span> Node&lt;T&gt;();</div><div class="line"><a name="l00055"></a><span class="lineno">   55</span>&#160;    head.store(tail);</div><div class="line"><a name="l00056"></a><span class="lineno">   56</span>&#160;  }</div><div class="line"><a name="l00057"></a><span class="lineno">   57</span>&#160;</div><div class="line"><a name="l00058"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#ac6ff02deeadfed9066166093769b3b9a">   58</a></span>&#160;  <a class="code" href="classprocess_1_1MpscLinkedQueue.html#ac6ff02deeadfed9066166093769b3b9a">~MpscLinkedQueue</a>()</div><div class="line"><a name="l00059"></a><span class="lineno">   59</span>&#160;  {</div><div class="line"><a name="l00060"></a><span class="lineno">   60</span>&#160;    <span class="keywordflow">while</span> (<span class="keyword">auto</span> element = <a class="code" href="classprocess_1_1MpscLinkedQueue.html#af9711afa3db
 6d73c2c31bab3f30e5f61">dequeue</a>()) {</div><div class="line"><a name="l00061"></a><span class="lineno">   61</span>&#160;      <span class="keyword">delete</span> element;</div><div class="line"><a name="l00062"></a><span class="lineno">   62</span>&#160;    }</div><div class="line"><a name="l00063"></a><span class="lineno">   63</span>&#160;</div><div class="line"><a name="l00064"></a><span class="lineno">   64</span>&#160;    <span class="keyword">delete</span> tail;</div><div class="line"><a name="l00065"></a><span class="lineno">   65</span>&#160;  }</div><div class="line"><a name="l00066"></a><span class="lineno">   66</span>&#160;</div><div class="line"><a name="l00067"></a><span class="lineno">   67</span>&#160;  <span class="comment">// Multi producer safe.</span></div><div class="line"><a name="l00068"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#a15b0656de08bb0b8810a4d1bec88ab45">   68</a></span>&#160;  <span class="keywordtype">voi
 d</span> <a class="code" href="classprocess_1_1MpscLinkedQueue.html#a15b0656de08bb0b8810a4d1bec88ab45">enqueue</a>(T* element)</div><div class="line"><a name="l00069"></a><span class="lineno">   69</span>&#160;  {</div><div class="line"><a name="l00070"></a><span class="lineno">   70</span>&#160;    <span class="comment">// A `nullptr` is used to denote an empty queue when doing a</span></div><div class="line"><a name="l00071"></a><span class="lineno">   71</span>&#160;    <span class="comment">// `dequeue()` so producers can&#39;t use it as an element.</span></div><div class="line"><a name="l00072"></a><span class="lineno">   72</span>&#160;    CHECK_NOTNULL(element);</div><div class="line"><a name="l00073"></a><span class="lineno">   73</span>&#160;</div><div class="line"><a name="l00074"></a><span class="lineno">   74</span>&#160;    <span class="keyword">auto</span> newNode = <span class="keyword">new</span> Node&lt;T&gt;(element);</div><div class="line"><a name="l00075"></a><sp
 an class="lineno">   75</span>&#160;</div><div class="line"><a name="l00076"></a><span class="lineno">   76</span>&#160;    <span class="comment">// Exchange is guaranteed to only give the old value to one</span></div><div class="line"><a name="l00077"></a><span class="lineno">   77</span>&#160;    <span class="comment">// producer, so this is safe and wait-free.</span></div><div class="line"><a name="l00078"></a><span class="lineno">   78</span>&#160;    <span class="keyword">auto</span> oldhead = head.exchange(newNode, std::memory_order_release);</div><div class="line"><a name="l00079"></a><span class="lineno">   79</span>&#160;</div><div class="line"><a name="l00080"></a><span class="lineno">   80</span>&#160;    <span class="comment">// At this point if this thread context switches out we may block</span></div><div class="line"><a name="l00081"></a><span class="lineno">   81</span>&#160;    <span class="comment">// the consumer from doing a dequeue (see below). Eventually we&#39
 ;ll</span></div><div class="line"><a name="l00082"></a><span class="lineno">   82</span>&#160;    <span class="comment">// unblock the consumer once we run again and execute the next</span></div><div class="line"><a name="l00083"></a><span class="lineno">   83</span>&#160;    <span class="comment">// line of code.</span></div><div class="line"><a name="l00084"></a><span class="lineno">   84</span>&#160;    oldhead-&gt;next.store(newNode, std::memory_order_release);</div><div class="line"><a name="l00085"></a><span class="lineno">   85</span>&#160;  }</div><div class="line"><a name="l00086"></a><span class="lineno">   86</span>&#160;</div><div class="line"><a name="l00087"></a><span class="lineno">   87</span>&#160;  <span class="comment">// Single consumer only.</span></div><div class="line"><a name="l00088"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#af9711afa3db6d73c2c31bab3f30e5f61">   88</a></span>&#160;  T* <a class="code" href="classproc
 ess_1_1MpscLinkedQueue.html#af9711afa3db6d73c2c31bab3f30e5f61">dequeue</a>()</div><div class="line"><a name="l00089"></a><span class="lineno">   89</span>&#160;  {</div><div class="line"><a name="l00090"></a><span class="lineno">   90</span>&#160;    <span class="keyword">auto</span> currentTail = tail;</div><div class="line"><a name="l00091"></a><span class="lineno">   91</span>&#160;</div><div class="line"><a name="l00092"></a><span class="lineno">   92</span>&#160;    <span class="comment">// Check and see if there is an actual element linked from `tail`</span></div><div class="line"><a name="l00093"></a><span class="lineno">   93</span>&#160;    <span class="comment">// since we use `tail` as a &quot;stub&quot; rather than the actual element.</span></div><div class="line"><a name="l00094"></a><span class="lineno">   94</span>&#160;    <span class="keyword">auto</span> nextTail = currentTail-&gt;next.exchange(</div><div class="line"><a name="l00095"></a><span class="lineno">   95
 </span>&#160;        <span class="keyword">nullptr</span>,</div><div class="line"><a name="l00096"></a><span class="lineno">   96</span>&#160;        std::memory_order_relaxed);</div><div class="line"><a name="l00097"></a><span class="lineno">   97</span>&#160;</div><div class="line"><a name="l00098"></a><span class="lineno">   98</span>&#160;    <span class="comment">// There are three possible cases here:</span></div><div class="line"><a name="l00099"></a><span class="lineno">   99</span>&#160;    <span class="comment">//</span></div><div class="line"><a name="l00100"></a><span class="lineno">  100</span>&#160;    <span class="comment">// (1) The queue is empty.</span></div><div class="line"><a name="l00101"></a><span class="lineno">  101</span>&#160;    <span class="comment">// (2) The queue appears empty but a producer is still enqueuing</span></div><div class="line"><a name="l00102"></a><span class="lineno">  102</span>&#160;    <span class="comment">//     so let&#39;s wait fo
 r it and then dequeue.</span></div><div class="line"><a name="l00103"></a><span class="lineno">  103</span>&#160;    <span class="comment">// (3) We have something to dequeue.</span></div><div class="line"><a name="l00104"></a><span class="lineno">  104</span>&#160;    <span class="comment">//</span></div><div class="line"><a name="l00105"></a><span class="lineno">  105</span>&#160;    <span class="comment">// Start by checking if the queue is or appears empty.</span></div><div class="line"><a name="l00106"></a><span class="lineno">  106</span>&#160;    <span class="keywordflow">if</span> (nextTail == <span class="keyword">nullptr</span>) {</div><div class="line"><a name="l00107"></a><span class="lineno">  107</span>&#160;      <span class="comment">// Now check if the queue is actually empty or just appears</span></div><div class="line"><a name="l00108"></a><span class="lineno">  108</span>&#160;      <span class="comment">// empty. If it&#39;s actually empty then return `nullptr` 
 to denote</span></div><div class="line"><a name="l00109"></a><span class="lineno">  109</span>&#160;      <span class="comment">// emptiness.</span></div><div class="line"><a name="l00110"></a><span class="lineno">  110</span>&#160;      <span class="keywordflow">if</span> (head.load(std::memory_order_relaxed) == tail) {</div><div class="line"><a name="l00111"></a><span class="lineno">  111</span>&#160;        <span class="keywordflow">return</span> <span class="keyword">nullptr</span>;</div><div class="line"><a name="l00112"></a><span class="lineno">  112</span>&#160;      }</div><div class="line"><a name="l00113"></a><span class="lineno">  113</span>&#160;</div><div class="line"><a name="l00114"></a><span class="lineno">  114</span>&#160;      <span class="comment">// Another thread already inserted a new node, but did not</span></div><div class="line"><a name="l00115"></a><span class="lineno">  115</span>&#160;      <span class="comment">// connect it to the tail, yet, so we spin
 -wait. At this point</span></div><div class="line"><a name="l00116"></a><span class="lineno">  116</span>&#160;      <span class="comment">// we are not wait-free anymore.</span></div><div class="line"><a name="l00117"></a><span class="lineno">  117</span>&#160;      <span class="keywordflow">do</span> {</div><div class="line"><a name="l00118"></a><span class="lineno">  118</span>&#160;        nextTail = currentTail-&gt;next.exchange(</div><div class="line"><a name="l00119"></a><span class="lineno">  119</span>&#160;            <span class="keyword">nullptr</span>,</div><div class="line"><a name="l00120"></a><span class="lineno">  120</span>&#160;            std::memory_order_relaxed);</div><div class="line"><a name="l00121"></a><span class="lineno">  121</span>&#160;      } <span class="keywordflow">while</span> (nextTail == <span class="keyword">nullptr</span>);</div><div class="line"><a name="l00122"></a><span class="lineno">  122</span>&#160;    }</div><div class="line"><a name=
 "l00123"></a><span class="lineno">  123</span>&#160;</div><div class="line"><a name="l00124"></a><span class="lineno">  124</span>&#160;    CHECK_NOTNULL(nextTail);</div><div class="line"><a name="l00125"></a><span class="lineno">  125</span>&#160;</div><div class="line"><a name="l00126"></a><span class="lineno">  126</span>&#160;    <span class="keyword">auto</span> element = nextTail-&gt;element;</div><div class="line"><a name="l00127"></a><span class="lineno">  127</span>&#160;    nextTail-&gt;element = <span class="keyword">nullptr</span>;</div><div class="line"><a name="l00128"></a><span class="lineno">  128</span>&#160;</div><div class="line"><a name="l00129"></a><span class="lineno">  129</span>&#160;    tail = nextTail;</div><div class="line"><a name="l00130"></a><span class="lineno">  130</span>&#160;    <span class="keyword">delete</span> currentTail;</div><div class="line"><a name="l00131"></a><span class="lineno">  131</span>&#160;</div><div class="line"><a name="l00132"
 ></a><span class="lineno">  132</span>&#160;    <span class="keywordflow">return</span> element;</div><div class="line"><a name="l00133"></a><span class="lineno">  133</span>&#160;  }</div><div class="line"><a name="l00134"></a><span class="lineno">  134</span>&#160;</div><div class="line"><a name="l00135"></a><span class="lineno">  135</span>&#160;  <span class="comment">// Single consumer only.</span></div><div class="line"><a name="l00136"></a><span class="lineno">  136</span>&#160;  <span class="comment">//</span></div><div class="line"><a name="l00137"></a><span class="lineno">  137</span>&#160;  <span class="comment">// TODO(drexin): Provide C++ style iteration so someone can just use</span></div><div class="line"><a name="l00138"></a><span class="lineno">  138</span>&#160;  <span class="comment">// the `std::for_each()`.</span></div><div class="line"><a name="l00139"></a><span class="lineno">  139</span>&#160;  <span class="keyword">template</span> &lt;<span class="keyword">t
 ypename</span> F&gt;</div><div class="line"><a name="l00140"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#a361ad3f84e782291c0ec6d714c7e140d">  140</a></span>&#160;  <span class="keywordtype">void</span> <a class="code" href="classprocess_1_1MpscLinkedQueue.html#a361ad3f84e782291c0ec6d714c7e140d">for_each</a>(F&amp;&amp; <a class="code" href="namespaceprocess.html#a62d5333e8ec1817c249cf83e15d568b4">f</a>)</div><div class="line"><a name="l00141"></a><span class="lineno">  141</span>&#160;  {</div><div class="line"><a name="l00142"></a><span class="lineno">  142</span>&#160;    <span class="keyword">auto</span> end = head.load();</div><div class="line"><a name="l00143"></a><span class="lineno">  143</span>&#160;    <span class="keyword">auto</span> node = tail;</div><div class="line"><a name="l00144"></a><span class="lineno">  144</span>&#160;</div><div class="line"><a name="l00145"></a><span class="lineno">  145</span>&#160;    <span class="keywo
 rdflow">for</span> (;;) {</div><div class="line"><a name="l00146"></a><span class="lineno">  146</span>&#160;      node = node-&gt;next.load();</div><div class="line"><a name="l00147"></a><span class="lineno">  147</span>&#160;</div><div class="line"><a name="l00148"></a><span class="lineno">  148</span>&#160;      <span class="comment">// We are following the linked structure until we reach the end</span></div><div class="line"><a name="l00149"></a><span class="lineno">  149</span>&#160;      <span class="comment">// node. There is a race with new nodes being added, so we limit</span></div><div class="line"><a name="l00150"></a><span class="lineno">  150</span>&#160;      <span class="comment">// the traversal to the last node at the time we started.</span></div><div class="line"><a name="l00151"></a><span class="lineno">  151</span>&#160;      <span class="keywordflow">if</span> (node == <span class="keyword">nullptr</span>) {</div><div class="line"><a name="l00152"></a><span clas
 s="lineno">  152</span>&#160;        <span class="keywordflow">return</span>;</div><div class="line"><a name="l00153"></a><span class="lineno">  153</span>&#160;      }</div><div class="line"><a name="l00154"></a><span class="lineno">  154</span>&#160;</div><div class="line"><a name="l00155"></a><span class="lineno">  155</span>&#160;      <a class="code" href="namespaceprocess.html#a62d5333e8ec1817c249cf83e15d568b4">f</a>(node-&gt;element);</div><div class="line"><a name="l00156"></a><span class="lineno">  156</span>&#160;</div><div class="line"><a name="l00157"></a><span class="lineno">  157</span>&#160;      <span class="keywordflow">if</span> (node == end) {</div><div class="line"><a name="l00158"></a><span class="lineno">  158</span>&#160;        <span class="keywordflow">return</span>;</div><div class="line"><a name="l00159"></a><span class="lineno">  159</span>&#160;      }</div><div class="line"><a name="l00160"></a><span class="lineno">  160</span>&#160;    }</div><div clas
 s="line"><a name="l00161"></a><span class="lineno">  161</span>&#160;  }</div><div class="line"><a name="l00162"></a><span class="lineno">  162</span>&#160;</div><div class="line"><a name="l00163"></a><span class="lineno">  163</span>&#160;  <span class="comment">// Single consumer only.</span></div><div class="line"><a name="l00164"></a><span class="lineno"><a class="line" href="classprocess_1_1MpscLinkedQueue.html#a995ca5eb7bf5842b0796458f08549ee3">  164</a></span>&#160;  <span class="keywordtype">bool</span> <a class="code" href="classprocess_1_1MpscLinkedQueue.html#a995ca5eb7bf5842b0796458f08549ee3">empty</a>()</div><div class="line"><a name="l00165"></a><span class="lineno">  165</span>&#160;  {</div><div class="line"><a name="l00166"></a><span class="lineno">  166</span>&#160;    <span class="keywordflow">return</span> tail-&gt;next.load(std::memory_order_relaxed) == <span class="keyword">nullptr</span> &amp;&amp;</div><div class="line"><a name="l00167"></a><span class="lineno
 ">  167</span>&#160;      head.load(std::memory_order_relaxed) == tail;</div><div class="line"><a name="l00168"></a><span class="lineno">  168</span>&#160;  }</div><div class="line"><a name="l00169"></a><span class="lineno">  169</span>&#160;</div><div class="line"><a name="l00170"></a><span class="lineno">  170</span>&#160;<span class="keyword">private</span>:</div><div class="line"><a name="l00171"></a><span class="lineno">  171</span>&#160;  <span class="comment">// TODO(drexin): Programatically get the cache line size.</span></div><div class="line"><a name="l00172"></a><span class="lineno">  172</span>&#160;  <span class="comment">//</span></div><div class="line"><a name="l00173"></a><span class="lineno">  173</span>&#160;  <span class="comment">// We align head to 64 bytes (x86 cache line size) to guarantee</span></div><div class="line"><a name="l00174"></a><span class="lineno">  174</span>&#160;  <span class="comment">// it to be put on a new cache line. This is to prevent fal
 se</span></div><div class="line"><a name="l00175"></a><span class="lineno">  175</span>&#160;  <span class="comment">// sharing with other objects that could otherwise end up on</span></div><div class="line"><a name="l00176"></a><span class="lineno">  176</span>&#160;  <span class="comment">// the same cache line as this queue. We also align tail to</span></div><div class="line"><a name="l00177"></a><span class="lineno">  177</span>&#160;  <span class="comment">// avoid false sharing with head and add padding after tail</span></div><div class="line"><a name="l00178"></a><span class="lineno">  178</span>&#160;  <span class="comment">// to avoid false sharing with other objects.</span></div><div class="line"><a name="l00179"></a><span class="lineno">  179</span>&#160;  <span class="keyword">alignas</span>(64) std::atomic&lt;Node&lt;T&gt;*&gt; head;</div><div class="line"><a name="l00180"></a><span class="lineno">  180</span>&#160;  <span class="keyword">alignas</span>(64) Node&lt;T&gt
 ;* tail;</div><div class="line"><a name="l00181"></a><span class="lineno">  181</span>&#160;  <span class="keywordtype">char</span> pad[64 - <span class="keyword">sizeof</span>(Node&lt;T&gt;*)];</div><div class="line"><a name="l00182"></a><span class="lineno">  182</span>&#160;};</div><div class="line"><a name="l00183"></a><span class="lineno">  183</span>&#160;</div><div class="line"><a name="l00184"></a><span class="lineno">  184</span>&#160;} <span class="comment">// namespace process {</span></div><div class="line"><a name="l00185"></a><span class="lineno">  185</span>&#160;</div><div class="line"><a name="l00186"></a><span class="lineno">  186</span>&#160;<span class="preprocessor">#endif // __MPSC_LINKED_QUEUE_HPP__</span></div><div class="ttc" id="classprocess_1_1MpscLinkedQueue_html"><div class="ttname"><a href="classprocess_1_1MpscLinkedQueue.html">process::MpscLinkedQueue</a></div><div class="ttdef"><b>Definition:</b> mpsc_linked_queue.hpp:38</div></div>
 <div class="ttc" id="classprocess_1_1MpscLinkedQueue_html_a361ad3f84e782291c0ec6d714c7e140d"><div class="ttname"><a href="classprocess_1_1MpscLinkedQueue.html#a361ad3f84e782291c0ec6d714c7e140d">process::MpscLinkedQueue::for_each</a></div><div class="ttdeci">void for_each(F &amp;&amp;f)</div><div class="ttdef"><b>Definition:</b> mpsc_linked_queue.hpp:140</div></div>
 <div class="ttc" id="namespaceprocess_html_a62d5333e8ec1817c249cf83e15d568b4"><div class="ttname"><a href="namespaceprocess.html#a62d5333e8ec1817c249cf83e15d568b4">process::f</a></div><div class="ttdeci">F &amp;&amp; f</div><div class="ttdef"><b>Definition:</b> defer.hpp:270</div></div>
 <div class="ttc" id="classprocess_1_1MpscLinkedQueue_html_af9711afa3db6d73c2c31bab3f30e5f61"><div class="ttname"><a href="classprocess_1_1MpscLinkedQueue.html#af9711afa3db6d73c2c31bab3f30e5f61">process::MpscLinkedQueue::dequeue</a></div><div class="ttdeci">T * dequeue()</div><div class="ttdef"><b>Definition:</b> mpsc_linked_queue.hpp:88</div></div>


Mime
View raw message