2 * Lock-free queue code from
3 * "C++ Concurrency in Action: Practical Multithreading", by Anthony Williams
6 * http://www.manning.com/williams/CCiA_SourceCode.zip
7 * http://www.manning.com/williams/
21 std::shared_ptr<T> data;
27 std::atomic<node*> head;
28 std::atomic<node*> tail;
31 node* const old_head=head.load();
32 if(old_head==tail.load())
36 head.store(old_head->next);
41 head(new node),tail(head.load())
43 lock_free_queue(const lock_free_queue& other)=delete;
44 lock_free_queue& operator=(const lock_free_queue& other)=delete;
47 while(node* const old_head=head.load())
49 head.store(old_head->next);
53 std::shared_ptr<T> pop()
55 node* old_head=pop_head();
58 return std::shared_ptr<T>();
60 std::shared_ptr<T> const res(old_head->data);
64 void push(T new_value)
66 std::shared_ptr<T> new_data(std::make_shared<T>(new_value));
68 node* const old_tail=tail.load();
69 old_tail->data.swap(new_data);
85 struct counted_node_ptr
90 std::atomic<counted_node_ptr> head;
91 std::atomic<counted_node_ptr> tail;
94 unsigned internal_count:30;
95 unsigned external_counters:2;
100 std::atomic<node_counter> count;
101 counted_node_ptr next;
104 node_counter new_count;
105 new_count.internal_count=0;
106 new_count.external_counters=2;
107 count.store(new_count);
109 next.external_count=0;
113 void push(T new_value)
115 std::unique_ptr<T> new_data(new T(new_value));
116 counted_node_ptr new_next;
117 new_next.ptr=new node;
118 new_next.external_count=1;
119 counted_node_ptr old_tail=tail.load();
122 increase_external_count(tail,old_tail);
124 if(old_tail.ptr->data.compare_exchange_strong(
125 old_data,new_data.get()))
127 old_tail.ptr->next=new_next;
128 old_tail=tail.exchange(new_next);
129 free_external_counter(old_tail);
133 old_tail.ptr->release_ref();
139 // ./listing_7.16.cpp
142 class lock_free_queue
150 std::unique_ptr<T> pop()
152 counted_node_ptr old_head=head.load(std::memory_order_relaxed);
155 increase_external_count(head,old_head);
156 node* const ptr=old_head.ptr;
157 if(ptr==tail.load().ptr)
160 return std::unique_ptr<T>();
162 if(head.compare_exchange_strong(old_head,ptr->next))
164 T* const res=ptr->data.exchange(nullptr);
165 free_external_counter(old_head);
166 return std::unique_ptr<T>(res);
174 // ./listing_7.17.cpp
177 class lock_free_queue
184 node_counter old_counter=
185 count.load(std::memory_order_relaxed);
186 node_counter new_counter;
189 new_counter=old_counter;
190 --new_counter.internal_count;
192 while(!count.compare_exchange_strong(
193 old_counter,new_counter,
194 std::memory_order_acquire,std::memory_order_relaxed));
195 if(!new_counter.internal_count &&
196 !new_counter.external_counters)
205 // ./listing_7.18.cpp
208 class lock_free_queue
211 static void increase_external_count(
212 std::atomic<counted_node_ptr>& counter,
213 counted_node_ptr& old_counter)
215 counted_node_ptr new_counter;
218 new_counter=old_counter;
219 ++new_counter.external_count;
221 while(!counter.compare_exchange_strong(
222 old_counter,new_counter,
223 std::memory_order_acquire,std::memory_order_relaxed));
224 old_counter.external_count=new_counter.external_count;
229 // ./listing_7.19.cpp
232 class lock_free_queue
235 static void free_external_counter(counted_node_ptr &old_node_ptr)
237 node* const ptr=old_node_ptr.ptr;
238 int const count_increase=old_node_ptr.external_count-2;
239 node_counter old_counter=
240 ptr->count.load(std::memory_order_relaxed);
241 node_counter new_counter;
244 new_counter=old_counter;
245 --new_counter.external_counters;
246 new_counter.internal_count+=count_increase;
248 while(!ptr->count.compare_exchange_strong(
249 old_counter,new_counter,
250 std::memory_order_acquire,std::memory_order_relaxed));
251 if(!new_counter.internal_count &&
252 !new_counter.external_counters)
260 // ./listing_7.20.cpp
263 class lock_free_queue
268 std::atomic<T*> data;
269 std::atomic<node_counter> count;
270 std::atomic<counted_node_ptr> next;
273 std::unique_ptr<T> pop()
275 counted_node_ptr old_head=head.load(std::memory_order_relaxed);
278 increase_external_count(head,old_head);
279 node* const ptr=old_head.ptr;
280 if(ptr==tail.load().ptr)
282 return std::unique_ptr<T>();
284 counted_node_ptr next=ptr->next.load();
285 if(head.compare_exchange_strong(old_head,next))
287 T* const res=ptr->data.exchange(nullptr);
288 free_external_counter(old_head);
289 return std::unique_ptr<T>(res);
297 // ./listing_7.21.cpp
300 class lock_free_queue
303 void set_new_tail(counted_node_ptr &old_tail,
304 counted_node_ptr const &new_tail)
306 node* const current_tail_ptr=old_tail.ptr;
307 while(!tail.compare_exchange_weak(old_tail,new_tail) &&
308 old_tail.ptr==current_tail_ptr);
309 if(old_tail.ptr==current_tail_ptr)
310 free_external_counter(old_tail);
312 current_tail_ptr->release_ref();
315 void push(T new_value)
317 std::unique_ptr<T> new_data(new T(new_value));
318 counted_node_ptr new_next;
319 new_next.ptr=new node;
320 new_next.external_count=1;
321 counted_node_ptr old_tail=tail.load();
324 increase_external_count(tail,old_tail);
326 if(old_tail.ptr->data.compare_exchange_strong(
327 old_data,new_data.get()))
329 counted_node_ptr old_next={0};
330 if(!old_tail.ptr->next.compare_exchange_strong(
336 set_new_tail(old_tail, new_next);
342 counted_node_ptr old_next={0};
343 if(old_tail.ptr->next.compare_exchange_strong(
347 new_next.ptr=new node;
349 set_new_tail(old_tail, old_next);