ms-queue: finally, the correct (?) memory orderings
[model-checker-benchmarks.git] / spsc-queue / queue.h
1 #include <unrelacy.h>
2 #include <atomic>
3
4 #include "eventcount.h"
5
6 template<typename T>
7 class spsc_queue
8 {
9 public:
10         spsc_queue()
11         {
12                 node* n = new node ();
13                 head = n;
14                 tail = n;
15         }
16
17         ~spsc_queue()
18         {
19                 RL_ASSERT(head == tail);
20                 delete ((node*)head($));
21         }
22
23         void enqueue(T data)
24         {
25                 node* n = new node (data);
26                 head($)->next.store(n, std::memory_order_release);
27                 head = n;
28                 ec.signal_relaxed();
29         }
30
31         T dequeue()
32         {
33                 T data = try_dequeue();
34                 while (0 == data)
35                 {
36                         int cmp = ec.get();
37                         data = try_dequeue();
38                         if (data)
39                                 break;
40                         ec.wait(cmp);
41                         data = try_dequeue();
42                         if (data)
43                                 break;
44                 }
45                 return data;
46         }
47
48 private:
49         struct node
50         {
51                 std::atomic<node*> next;
52                 rl::var<T> data;
53
54                 node(T data = T())
55                         : data(data)
56                 {
57                         next = 0;
58                 }
59         };
60
61         rl::var<node*> head;
62         rl::var<node*> tail;
63
64         eventcount ec;
65
66         T try_dequeue()
67         {
68                 node* t = tail($);
69                 node* n = t->next.load(std::memory_order_acquire);
70                 if (0 == n)
71                         return 0;
72                 T data = n->data($);
73                 delete (t);
74                 tail = n;
75                 return data;
76         }
77 };