williams-queue/williams-queue.h

   1 /*
   2  * Lock-free queue code from
   3  * "C++ Concurrency in Action: Practical Multithreading", by Anthony Williams
   4  *
   5  * Code taken from:
   6  *  http://www.manning.com/williams/CCiA_SourceCode.zip
   7  *  http://www.manning.com/williams/
   8  */
   9
  10 // ./listing_7.13.cpp
  11
  12 #include <memory>
  13 #include <atomic>
  14
  15 template<typename T>
  16 class lock_free_queue
  17 {
  18 private:
  19     struct node
  20     {
  21         std::shared_ptr<T> data;
  22         node* next;
  23         node():
  24             next(nullptr)
  25         {}
  26     };
  27     std::atomic<node*> head;
  28     std::atomic<node*> tail;
  29     node* pop_head()
  30     {
  31         node* const old_head=head.load();
  32         if(old_head==tail.load())
  33         {
  34             return nullptr;
  35         }
  36         head.store(old_head->next);
  37         return old_head;
  38     }
  39 public:
  40     lock_free_queue():
  41         head(new node),tail(head.load())
  42     {}
  43     lock_free_queue(const lock_free_queue& other)=delete;
  44     lock_free_queue& operator=(const lock_free_queue& other)=delete;
  45     ~lock_free_queue()
  46     {
  47         while(node* const old_head=head.load())
  48         {
  49             head.store(old_head->next);
  50             delete old_head;
  51         }
  52     }
  53     std::shared_ptr<T> pop()
  54     {
  55         node* old_head=pop_head();
  56         if(!old_head)
  57         {
  58             return std::shared_ptr<T>();
  59         }
  60         std::shared_ptr<T> const res(old_head->data);
  61         delete old_head;
  62         return res;
  63     }
  64     void push(T new_value)
  65     {
  66         std::shared_ptr<T> new_data(std::make_shared<T>(new_value));
  67         node* p=new node;
  68         node* const old_tail=tail.load();
  69         old_tail->data.swap(new_data);
  70         old_tail->next=p;
  71         tail.store(p);
  72     }
  73 };
  74
  75
  76 // ./listing_7.15.cpp
  77
  78 #include <atomic>
  79
  80 template<typename T>
  81 class lock_free_queue
  82 {
  83 private:
  84     struct node;
  85     struct counted_node_ptr
  86     {
  87         int external_count;
  88         node* ptr;
  89     };
  90     std::atomic<counted_node_ptr> head;
  91     std::atomic<counted_node_ptr> tail;
  92     struct node_counter
  93     {
  94         unsigned internal_count:30;
  95         unsigned external_counters:2;
  96     };
  97     struct node
  98     {
  99         std::atomic<T*> data;
 100         std::atomic<node_counter> count;
 101         counted_node_ptr next;
 102         node()
 103         {
 104             node_counter new_count;
 105             new_count.internal_count=0;
 106             new_count.external_counters=2;
 107             count.store(new_count);
 108             next.ptr=nullptr;
 109             next.external_count=0;
 110         }
 111     };
 112 public:
 113     void push(T new_value)
 114     {
 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();
 120         for(;;)
 121         {
 122             increase_external_count(tail,old_tail);
 123             T* old_data=nullptr;
 124             if(old_tail.ptr->data.compare_exchange_strong(
 125                    old_data,new_data.get()))
 126             {
 127                 old_tail.ptr->next=new_next;
 128                 old_tail=tail.exchange(new_next);
 129                 free_external_counter(old_tail);
 130                 new_data.release();
 131                 break;
 132             }
 133             old_tail.ptr->release_ref();
 134         }
 135     }
 136 };
 137
 138
 139 // ./listing_7.16.cpp
 140
 141 template<typename T>
 142 class lock_free_queue
 143 {
 144 private:
 145     struct node
 146     {
 147         void release_ref();
 148     };
 149 public:
 150     std::unique_ptr<T> pop()
 151     {
 152         counted_node_ptr old_head=head.load(std::memory_order_relaxed);
 153         for(;;)
 154         {
 155             increase_external_count(head,old_head);
 156             node* const ptr=old_head.ptr;
 157             if(ptr==tail.load().ptr)
 158             {
 159                 ptr->release_ref();
 160                 return std::unique_ptr<T>();
 161             }
 162             if(head.compare_exchange_strong(old_head,ptr->next))
 163             {
 164                 T* const res=ptr->data.exchange(nullptr);
 165                 free_external_counter(old_head);
 166                 return std::unique_ptr<T>(res);
 167             }
 168             ptr->release_ref();
 169         }
 170     }
 171 };
 172
 173
 174 // ./listing_7.17.cpp
 175
 176 template<typename T>
 177 class lock_free_queue
 178 {
 179 private:
 180     struct node
 181     {
 182         void release_ref()
 183         {
 184             node_counter old_counter=
 185                 count.load(std::memory_order_relaxed);
 186             node_counter new_counter;
 187             do
 188             {
 189                 new_counter=old_counter;
 190                 --new_counter.internal_count;
 191             }
 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)
 197             {
 198                 delete this;
 199             }
 200         }
 201     };
 202 };
 203
 204
 205 // ./listing_7.18.cpp
 206
 207 template<typename T>
 208 class lock_free_queue
 209 {
 210 private:
 211     static void increase_external_count(
 212         std::atomic<counted_node_ptr>& counter,
 213         counted_node_ptr& old_counter)
 214     {
 215         counted_node_ptr new_counter;
 216         do
 217         {
 218             new_counter=old_counter;
 219             ++new_counter.external_count;
 220         }
 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;
 225     }
 226 };
 227
 228
 229 // ./listing_7.19.cpp
 230
 231 template<typename T>
 232 class lock_free_queue
 233 {
 234 private:
 235     static void free_external_counter(counted_node_ptr &old_node_ptr)
 236     {
 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;
 242         do
 243         {
 244             new_counter=old_counter;
 245             --new_counter.external_counters;
 246             new_counter.internal_count+=count_increase;
 247         }
 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)
 253         {
 254             delete ptr;
 255         }
 256     }
 257 };
 258
 259
 260 // ./listing_7.20.cpp
 261
 262 template<typename T>
 263 class lock_free_queue
 264 {
 265 private:
 266     struct node
 267     {
 268         std::atomic<T*> data;
 269         std::atomic<node_counter> count;
 270         std::atomic<counted_node_ptr> next;
 271     };
 272 public:
 273     std::unique_ptr<T> pop()
 274     {
 275         counted_node_ptr old_head=head.load(std::memory_order_relaxed);
 276         for(;;)
 277         {
 278             increase_external_count(head,old_head);
 279             node* const ptr=old_head.ptr;
 280             if(ptr==tail.load().ptr)
 281             {
 282                 return std::unique_ptr<T>();
 283             }
 284             counted_node_ptr next=ptr->next.load();
 285             if(head.compare_exchange_strong(old_head,next))
 286             {
 287                 T* const res=ptr->data.exchange(nullptr);
 288                 free_external_counter(old_head);
 289                 return std::unique_ptr<T>(res);
 290             }
 291             ptr->release_ref();
 292         }
 293     }
 294 };
 295
 296
 297 // ./listing_7.21.cpp
 298
 299 template<typename T>
 300 class lock_free_queue
 301 {
 302 private:
 303     void set_new_tail(counted_node_ptr &old_tail,
 304                       counted_node_ptr const &new_tail)
 305     {
 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);
 311         else
 312             current_tail_ptr->release_ref();
 313     }
 314 public:
 315     void push(T new_value)
 316     {
 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();
 322         for(;;)
 323         {
 324             increase_external_count(tail,old_tail);
 325             T* old_data=nullptr;
 326             if(old_tail.ptr->data.compare_exchange_strong(
 327                    old_data,new_data.get()))
 328             {
 329                 counted_node_ptr old_next={0};
 330                 if(!old_tail.ptr->next.compare_exchange_strong(
 331                        old_next,new_next))
 332                 {
 333                     delete new_next.ptr;
 334                     new_next=old_next;
 335                 }
 336                 set_new_tail(old_tail, new_next);
 337                 new_data.release();
 338                 break;
 339             }
 340             else
 341             {
 342                 counted_node_ptr old_next={0};
 343                 if(old_tail.ptr->next.compare_exchange_strong(
 344                        old_next,new_next))
 345                 {
 346                     old_next=new_next;
 347                     new_next.ptr=new node;
 348                 }
 349                 set_new_tail(old_tail, old_next);
 350             }
 351         }
 352     }
 353 };