treiber-stack/stack.h

   1 #include <stdatomic.h>
   2 #include <atomic>
   3
   4 #define release memory_order_release
   5 #define acquire memory_order_acquire
   6 #define acq_rel memory_order_acq_rel
   7 #define relaxed memory_order_relaxed
   8
   9 struct node {
  10         unsigned int value;
  11         // This field does not have to be atomic, but in the inference analysis, we
  12         // might have a data race for this field without the proper synchronization.
  13         //node *next;
  14         atomic<node*> next;
  15
  16         node(unsigned int v) {
  17                 value = v;
  18                 next = NULL;
  19         }
  20 };
  21
  22 struct stack {
  23         atomic<node*> top;
  24
  25         stack() {
  26                 atomic_init(&top, NULL);
  27         }
  28
  29         void push(unsigned int val) {
  30                 node *n = new node(val);
  31                 node *old = top.load(relaxed);
  32                 do {
  33                         // n->next = old;
  34                         n->next.store(old, relaxed);
  35                 } while (!top.compare_exchange_strong(old, n, release, relaxed));
  36         }
  37
  38         unsigned int pop() {
  39                 node *old = top.load(acquire);
  40                 node *n;
  41                 do {
  42                         if (!old)
  43                                 return 0;
  44                         //n = old->next;
  45                         n = old->next.load(relaxed);
  46                 } while (!top.compare_exchange_strong(old, n, relaxed, relaxed));
  47                 return old->value;
  48         }
  49 };
  50