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);
31 head(new node),tail(head.load())
33 // lock_free_queue(const lock_free_queue& other)=delete;
34 // lock_free_queue& operator=(const lock_free_queue& other)=delete;
37 while(node* const old_head=head.load())
39 head.store(old_head->next);
45 struct counted_node_ptr
50 std::atomic<counted_node_ptr> head;
51 std::atomic<counted_node_ptr> tail;
54 unsigned internal_count:30;
55 unsigned external_counters:2;
61 std::atomic<node_counter> count;
62 std::atomic<counted_node_ptr> next;
65 node_counter new_count;
66 new_count.internal_count=0;
67 new_count.external_counters=2;
68 count.store(new_count);
70 next.external_count=0;
74 node_counter old_counter=
75 count.load(std::memory_order_relaxed);
76 node_counter new_counter;
79 new_counter=old_counter;
80 --new_counter.internal_count;
82 while(!count.compare_exchange_strong(
83 old_counter,new_counter,
84 std::memory_order_acquire,std::memory_order_relaxed));
85 if(!new_counter.internal_count &&
86 !new_counter.external_counters)
93 static void increase_external_count(
94 std::atomic<counted_node_ptr>& counter,
95 counted_node_ptr& old_counter)
97 counted_node_ptr new_counter;
100 new_counter=old_counter;
101 ++new_counter.external_count;
103 while(!counter.compare_exchange_strong(
104 old_counter,new_counter,
105 std::memory_order_acquire,std::memory_order_relaxed));
106 old_counter.external_count=new_counter.external_count;
109 static void free_external_counter(counted_node_ptr &old_node_ptr)
111 node* const ptr=old_node_ptr.ptr;
112 int const count_increase=old_node_ptr.external_count-2;
113 node_counter old_counter=
114 ptr->count.load(std::memory_order_relaxed);
115 node_counter new_counter;
118 new_counter=old_counter;
119 --new_counter.external_counters;
120 new_counter.internal_count+=count_increase;
122 while(!ptr->count.compare_exchange_strong(
123 old_counter,new_counter,
124 std::memory_order_acquire,std::memory_order_relaxed));
125 if(!new_counter.internal_count &&
126 !new_counter.external_counters)
132 std::unique_ptr<T> pop()
134 counted_node_ptr old_head=head.load(std::memory_order_relaxed);
137 increase_external_count(head,old_head);
138 node* const ptr=old_head.ptr;
139 if(ptr==tail.load().ptr)
141 return std::unique_ptr<T>();
143 counted_node_ptr next=ptr->next.load();
144 if(head.compare_exchange_strong(old_head,next))
146 T* const res=ptr->data.exchange(nullptr);
147 free_external_counter(old_head);
148 return std::unique_ptr<T>(res);
155 void set_new_tail(counted_node_ptr &old_tail,
156 counted_node_ptr const &new_tail)
158 node* const current_tail_ptr=old_tail.ptr;
159 while(!tail.compare_exchange_weak(old_tail,new_tail) &&
160 old_tail.ptr==current_tail_ptr);
161 if(old_tail.ptr==current_tail_ptr)
162 free_external_counter(old_tail);
164 current_tail_ptr->release_ref();
167 void push(T new_value)
169 std::unique_ptr<T> new_data(new T(new_value));
170 counted_node_ptr new_next;
171 new_next.ptr=new node;
172 new_next.external_count=1;
173 counted_node_ptr old_tail=tail.load();
176 increase_external_count(tail,old_tail);
178 if(old_tail.ptr->data.compare_exchange_strong(
179 old_data,new_data.get()))
181 counted_node_ptr old_next={0};
182 if(!old_tail.ptr->next.compare_exchange_strong(
188 set_new_tail(old_tail, new_next);
194 counted_node_ptr old_next={0};
195 if(old_tail.ptr->next.compare_exchange_strong(
199 new_next.ptr=new node;
201 set_new_tail(old_tail, old_next);