Add data structure benchmarks

[c11concurrency-benchmarks.git] / cdschecker_modified_benchmarks / spsc-queue / queue-relacy.h

diff --git a/cdschecker_modified_benchmarks/spsc-queue/queue-relacy.h b/cdschecker_modified_benchmarks/spsc-queue/queue-relacy.h
new file mode 100644 (file)
index 0000000..71aac2a
--- /dev/null
+++ b/cdschecker_modified_benchmarks/spsc-queue/queue-relacy.h
@@ -0,0 +1,74 @@
+#include "eventcount-relacy.h"
+
+template<typename T>
+class spsc_queue
+{
+public:
+       spsc_queue()
+       {
+               node* n = new node ();
+               head($) = n;
+               tail($) = n;
+       }
+
+       ~spsc_queue()
+       {
+               RL_ASSERT(head($) == tail($));
+               delete ((node*)head($));
+       }
+
+       void enqueue(T data)
+       {
+               node* n = new node (data);
+               head($)->next.store(n, std::memory_order_release);
+               head($) = n;
+               ec.signal_relaxed();
+       }
+
+       T dequeue()
+       {
+               T data = try_dequeue();
+               while (0 == data)
+               {
+                       int cmp = ec.get();
+                       data = try_dequeue();
+                       if (data)
+                               break;
+                       ec.wait(cmp);
+                       data = try_dequeue();
+                       if (data)
+                               break;
+               }
+               return data;
+       }
+
+private:
+       struct node
+       {
+               std::atomic<node*> next;
+               rl::var<T> data;
+
+               node(T data = T())
+                       : data(data)
+               {
+                       next($) = 0;
+               }
+       };
+
+       rl::var<node*> head;
+       rl::var<node*> tail;
+
+       eventcount ec;
+
+       T try_dequeue()
+       {
+               node* t = tail($);
+               node* n = t->next.load(std::memory_order_acquire);
+               if (0 == n)
+                       return 0;
+               T data = n->data($);
+               delete (t);
+               tail($) = n;
+               return data;
+       }
+};