From db665945760baeb8f0d50f663db8caeede59697c Mon Sep 17 00:00:00 2001
From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Mon, 23 May 2011 14:49:11 +0200
Subject: [PATCH] Add a lock-free synchronized queue.

---
 README       |  2 ++
 sync_queue.h | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 84 insertions(+)
 create mode 100644 sync_queue.h

diff --git a/README b/README
index d92ee39..8fcbc7c 100644
--- a/README
+++ b/README
@@ -226,6 +226,8 @@ Liste de fichiers
 
     synchro.h                   mutex, condition, etc.
 
+    sync_queue.h                lock-free synchronized queue
+
     timer.h                     gestion de timer
 
     tracing.h                   définitions liées au traçage
diff --git a/sync_queue.h b/sync_queue.h
new file mode 100644
index 0000000..8888548
--- /dev/null
+++ b/sync_queue.h
@@ -0,0 +1,82 @@
+#ifndef SYNC_QUEUE_H
+#define SYNC_QUEUE_H
+
+#if __GNUC__ == 4 && __GNUC_MINOR__ == 4
+#  include <cstdatomic>         // <atomic> is named <cstdatomic> in gcc 4.4
+#else
+#  include <atomic>
+#endif
+
+template <typename T>
+class sync_queue {
+public:
+    sync_queue()
+    {
+        node* n = new node(NULL, NULL);
+        std::atomic_store(&head, n); // head.store(n);
+        std::atomic_store(&tail, n); // tail.store(n);
+    }
+
+    ~sync_queue()
+    {
+        node* n = head.load();
+        while (n != NULL) {
+            node* prev = n;
+            n = n->next;
+            delete prev;
+        }
+    }
+
+    bool empty() const
+    {
+        return head.load() == tail.load();
+    }
+
+    // size() is not not thread-safe
+    size_t size() const
+    {
+        size_t count = 0;
+        for (node* n = head.load()->next; n != NULL; n = n->next)
+            ++count;
+        return count;
+    }
+
+    bool push(const T& val)
+    {
+        node* old_tail = tail.load();
+        node* n = new node(val, NULL);
+        old_tail->next = n;
+        std::atomic_store(&tail, n); // tail.store(n);
+        return (old_tail == head.load());
+    }
+
+    bool try_pop(T& res)
+    {
+        node* old_head = head.load();
+        if (old_head == tail.load()) { // empty?
+            return false;
+        } else {
+            node* new_head = old_head->next;
+            std::atomic_store(&head, new_head); // head.store(new_head);
+            delete old_head;
+            res = new_head->value;
+            return true;
+        }
+    }
+
+private:
+    struct node {
+        node(const T& v, node* n): value(v), next(n) { }
+        T value;
+        node* next;
+    };
+
+    std::atomic<node*> head;
+    std::atomic<node*> tail;
+};
+
+#endif // !SYNC_QUEUE_H
+
+// Local variables:
+// mode: c++
+// End:
-- 
2.39.5