treiber-stack/stack_wildcard.h

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