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 node* const old_head=head.load();
22 if(old_head==tail.load())
26 head.store(old_head->next);
30 struct counted_node_ptr
35 std::atomic<counted_node_ptr> head;
36 std::atomic<counted_node_ptr> tail;
39 unsigned internal_count:30;
40 unsigned external_counters:2;
46 std::atomic<node_counter> count;
47 std::atomic<counted_node_ptr> next;
50 node_counter new_count;
51 new_count.internal_count=0;
52 new_count.external_counters=2;
53 count.store(new_count);
55 counted_node_ptr emptynode = {0, nullptr};
60 node_counter old_counter=
61 count.load(std::memory_order_relaxed);
62 node_counter new_counter;
65 new_counter=old_counter;
66 --new_counter.internal_count;
68 while(!count.compare_exchange_strong(
69 old_counter,new_counter,
70 std::memory_order_acquire,std::memory_order_relaxed));
71 if(!new_counter.internal_count &&
72 !new_counter.external_counters)
79 static void increase_external_count(
80 std::atomic<counted_node_ptr>& counter,
81 counted_node_ptr& old_counter)
83 counted_node_ptr new_counter;
86 new_counter=old_counter;
87 ++new_counter.external_count;
89 while(!counter.compare_exchange_strong(
90 old_counter,new_counter,
91 std::memory_order_acquire,std::memory_order_relaxed));
92 old_counter.external_count=new_counter.external_count;
95 static void free_external_counter(counted_node_ptr &old_node_ptr)
97 node* const ptr=old_node_ptr.ptr;
98 int const count_increase=old_node_ptr.external_count-2;
99 node_counter old_counter=
100 ptr->count.load(std::memory_order_relaxed);
101 node_counter new_counter;
104 new_counter=old_counter;
105 --new_counter.external_counters;
106 new_counter.internal_count+=count_increase;
108 while(!ptr->count.compare_exchange_strong(
109 old_counter,new_counter,
110 std::memory_order_acquire,std::memory_order_relaxed));
111 if(!new_counter.internal_count &&
112 !new_counter.external_counters)
118 std::unique_ptr<T> pop()
120 counted_node_ptr old_head=head.load(std::memory_order_relaxed);
123 increase_external_count(head,old_head);
124 node* const ptr=old_head.ptr;
125 if(ptr==tail.load().ptr)
127 return std::unique_ptr<T>();
129 counted_node_ptr next=ptr->next.load();
130 if(head.compare_exchange_strong(old_head,next))
132 T* const res=ptr->data.exchange(nullptr);
133 free_external_counter(old_head);
134 return std::unique_ptr<T>(res);
141 void set_new_tail(counted_node_ptr &old_tail,
142 counted_node_ptr const &new_tail)
144 node* const current_tail_ptr=old_tail.ptr;
145 while(!tail.compare_exchange_weak(old_tail,new_tail) &&
146 old_tail.ptr==current_tail_ptr);
147 if(old_tail.ptr==current_tail_ptr)
148 free_external_counter(old_tail);
150 current_tail_ptr->release_ref();
155 counted_node_ptr newnode = {0, new node};
159 // lock_free_queue(const lock_free_queue& other)=delete;
160 // lock_free_queue& operator=(const lock_free_queue& other)=delete;
163 while(node* const old_head=head.load())
165 head.store(old_head->next);
170 void push(T new_value)
172 std::unique_ptr<T> new_data(new T(new_value));
173 counted_node_ptr new_next;
174 new_next.ptr=new node;
175 new_next.external_count=1;
176 counted_node_ptr old_tail=tail.load();
179 increase_external_count(tail,old_tail);
181 if(old_tail.ptr->data.compare_exchange_strong(
182 old_data,new_data.get()))
184 counted_node_ptr old_next={0};
185 if(!old_tail.ptr->next.compare_exchange_strong(
191 set_new_tail(old_tail, new_next);
197 counted_node_ptr old_next={0};
198 if(old_tail.ptr->next.compare_exchange_strong(
202 new_next.ptr=new node;
204 set_new_tail(old_tail, old_next);