lfstl/treiber_stack.cpp at main · avii778/lfstl · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <atomic>
#include <optional>

template <typename T> class TreiberStack {

  private:
    class Node {

      public:
        T item;
        std::atomic<Node*> next;

        Node(T i) : item(i), next(nullptr) {}
        Node() : item{} {};
    };

  public:
    Node* fh;

    TreiberStack() : fh{new Node()} {}

    void push(T item) {

        Node* nn = new Node(item);

        while (1) {

            nn->next.store(fh->next, std::memory_order_acq_rel);

            if (fh->next.compare_exchange_weak(nn->next, nn)) {
                return;
            }
        }
    }

    T pop() {

        while (1) {

            Node* tr;

            if (!tr) {
                return std::nullopt;
            }

            tr = fh->next.load(std::memory_order_acquire);

            if (fh->next.compare_exchange_weak(tr, tr->next)) {
                return tr->item;
            }
        }
    }
};