X-Git-Url: http://demsky.eecs.uci.edu/git/?p=model-checker-benchmarks.git;a=blobdiff_plain;f=williams-queue%2Fwilliams-queue.h;fp=williams-queue%2Fwilliams-queue.h;h=0000000000000000000000000000000000000000;hp=36633db2b4a5d157c2a62284215a1c1a9a274d0a;hb=819715e1278ec7efecc81cf1d62c298eb396c730;hpb=69d1985b2a13f7f53fd717c094641a795b9c0410

diff --git a/williams-queue/williams-queue.h b/williams-queue/williams-queue.h
deleted file mode 100644
index 36633db..0000000
--- a/williams-queue/williams-queue.h
+++ /dev/null
@@ -1,208 +0,0 @@
-/*
- * Lock-free queue code from
- * "C++ Concurrency in Action: Practical Multithreading", by Anthony Williams
- *
- * Code taken from:
- *  http://www.manning.com/williams/CCiA_SourceCode.zip
- *  http://www.manning.com/williams/
- */
-
-#include <memory>
-#include <atomic>
-
-template<typename T>
-class lock_free_queue
-{
-private:
-    struct node;
-    struct node_counter;
-    node* pop_head()
-    {
-        node* const old_head=head.load();
-        if(old_head==tail.load())
-        {
-            return nullptr;
-        }
-        head.store(old_head->next);
-        return old_head;
-    }
-
-    struct counted_node_ptr
-    {
-        int external_count;
-        node* ptr;
-    };
-    std::atomic<counted_node_ptr> head;
-    std::atomic<counted_node_ptr> tail;
-    struct node_counter
-    {
-        unsigned internal_count:30;
-        unsigned external_counters:2;
-    };
-
-    struct node
-    {
-        std::atomic<T*> data;
-        std::atomic<node_counter> count;
-        std::atomic<counted_node_ptr> next;
-        node()
-        {
-            node_counter new_count;
-            new_count.internal_count=0;
-            new_count.external_counters=2;
-            count.store(new_count);
-
-	    counted_node_ptr emptynode = {0, nullptr};
-	    next = emptynode;
-        }
-        void release_ref()
-        {
-            node_counter old_counter=
-                count.load(std::memory_order_relaxed);
-            node_counter new_counter;
-            do
-            {
-                new_counter=old_counter;
-                --new_counter.internal_count;
-            }
-            while(!count.compare_exchange_strong(
-                      old_counter,new_counter,
-                      std::memory_order_acquire,std::memory_order_relaxed));
-            if(!new_counter.internal_count &&
-               !new_counter.external_counters)
-            {
-                delete this;
-            }
-        }
-    };
-
-    static void increase_external_count(
-        std::atomic<counted_node_ptr>& counter,
-        counted_node_ptr& old_counter)
-    {
-        counted_node_ptr new_counter;
-        do
-        {
-            new_counter=old_counter;
-            ++new_counter.external_count;
-        }
-        while(!counter.compare_exchange_strong(
-                  old_counter,new_counter,
-                  std::memory_order_acquire,std::memory_order_relaxed));
-        old_counter.external_count=new_counter.external_count;
-    }
-
-    static void free_external_counter(counted_node_ptr &old_node_ptr)
-    {
-        node* const ptr=old_node_ptr.ptr;
-        int const count_increase=old_node_ptr.external_count-2;
-        node_counter old_counter=
-            ptr->count.load(std::memory_order_relaxed);
-        node_counter new_counter;
-        do
-        {
-            new_counter=old_counter;
-            --new_counter.external_counters;
-            new_counter.internal_count+=count_increase;
-        }
-        while(!ptr->count.compare_exchange_strong(
-                  old_counter,new_counter,
-                  std::memory_order_acquire,std::memory_order_relaxed));
-        if(!new_counter.internal_count &&
-           !new_counter.external_counters)
-        {
-            delete ptr;
-        }
-    }
-public:
-    std::unique_ptr<T> pop()
-    {
-        counted_node_ptr old_head=head.load(std::memory_order_relaxed);
-        for(;;)
-        {
-            increase_external_count(head,old_head);
-            node* const ptr=old_head.ptr;
-            if(ptr==tail.load().ptr)
-            {
-                return std::unique_ptr<T>();
-            }
-            counted_node_ptr next=ptr->next.load();
-            if(head.compare_exchange_strong(old_head,next))
-            {
-                T* const res=ptr->data.exchange(nullptr);
-                free_external_counter(old_head);
-                return std::unique_ptr<T>(res);
-            }
-            ptr->release_ref();
-        }
-    }
-
-private:
-    void set_new_tail(counted_node_ptr &old_tail,
-                      counted_node_ptr const &new_tail)
-    {
-        node* const current_tail_ptr=old_tail.ptr;
-        while(!tail.compare_exchange_weak(old_tail,new_tail) &&
-              old_tail.ptr==current_tail_ptr);
-        if(old_tail.ptr==current_tail_ptr)
-            free_external_counter(old_tail);
-        else
-            current_tail_ptr->release_ref();
-    }
-public:
-    lock_free_queue()
-    {
-        counted_node_ptr newnode = {0, new node};
-        head = newnode;
-	tail = head.load();
-    }
-    // lock_free_queue(const lock_free_queue& other)=delete;
-    // lock_free_queue& operator=(const lock_free_queue& other)=delete;
-    ~lock_free_queue()
-    {
-        while(node* const old_head=head.load())
-        {
-            head.store(old_head->next);
-            delete old_head;
-        }
-    }
-
-    void push(T new_value)
-    {
-        std::unique_ptr<T> new_data(new T(new_value));
-        counted_node_ptr new_next;
-        new_next.ptr=new node;
-        new_next.external_count=1;
-        counted_node_ptr old_tail=tail.load();
-        for(;;)
-        {
-            increase_external_count(tail,old_tail);
-            T* old_data=nullptr;
-            if(old_tail.ptr->data.compare_exchange_strong(
-                   old_data,new_data.get()))
-            {
-                counted_node_ptr old_next={0};
-                if(!old_tail.ptr->next.compare_exchange_strong(
-                       old_next,new_next))
-                {
-                    delete new_next.ptr;
-                    new_next=old_next;
-                }
-                set_new_tail(old_tail, new_next);
-                new_data.release();
-                break;
-            }
-            else
-            {
-                counted_node_ptr old_next={0};
-                if(old_tail.ptr->next.compare_exchange_strong(
-                       old_next,new_next))
-                {
-                    old_next=new_next;
-                    new_next.ptr=new node;
-                }
-                set_new_tail(old_tail, old_next);
-            }
-        }
-    }
-};