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         node *next;
  12
  13         node(unsigned int v) {
  14                 value = v;
  15                 next = NULL;
  16         }
  17 };
  18
  19 struct stack {
  20         atomic<node*> top;
  21
  22         stack() {
  23                 atomic_init(&top, NULL);
  24         }
  25
  26         void push(unsigned int val) {
  27                 node *n = new node(val);
  28                 node *old = top.load(acquire);
  29                 do {
  30                         n->next = old;
  31                 } while (!top.compare_exchange_strong(old, n, acq_rel, relaxed));
  32         }
  33
  34         unsigned int pop() {
  35                 node *old = top.load(acquire);
  36                 node *n;
  37                 do {
  38                         if (!old)
  39                                 return 0;
  40                         n = old->next;
  41                 } while (!top.compare_exchange_strong(old, n, acq_rel, acquire));
  42                 return old->value;
  43         }
  44 };
  45