#ifndef CONCQUEUE_INCLUDED
#define CONCQUEUE_INCLUDED

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct {

    volatile int lock_value;

} lock_queue;

template<class data_val_type> class QueueElement
{
	data_val_type data_value;
	QueueElement *next;
public:
	QueueElement(data_val_type a):data_value(a),next(NULL)
	{
	}

	data_val_type GetData() const
	{
		return data_value;
	}

	void SetData(data_val_type val)
	{
		data_value = val;
	}

	void SetPointer(QueueElement *a)
	{
		next = a;
	}

	QueueElement* GetPointer()
	{
		return next;
	}

	const data_val_type* GetPointerToData()
	{
		return (&data_value);
	}
};

template<class data_val_type> class ConcQueue
{
	QueueElement<data_val_type> *head;
	QueueElement<data_val_type> *tail;
	lock_queue insertion_lock;
	lock_queue deletion_lock;
public:
	ConcQueue():head(NULL),tail(NULL)
	{
		insertion_lock.lock_value = 0;
		deletion_lock.lock_value = 0;
	}
	
	int CAS(volatile int *val, int compare_value, int swap_value)
	{

		return __sync_bool_compare_and_swap(val, compare_value, swap_value);
	}

	void PrintQueue()
	{
		QueueElement<data_val_type> *traverse = NULL;

		traverse = head;

		while(traverse != NULL)
		{
			cout<<traverse->GetData()<<endl;
			traverse = traverse->GetPointer();
		}
	}
	
	const QueueElement<data_val_type>* AddElement(data_val_type val)
	{
		QueueElement<data_val_type> *temp = NULL;
		lock_queue current_lock;
		timespec time1, time2;

		temp = new QueueElement<data_val_type>(val);
		temp->SetPointer(NULL);

		/* Synchronization by locking with compare and swap.The current value of 
                 * lock is compared with the expected value(locked,unlocked) and  
                 * swapped accordingly.Threads spin until they acquire the lock.
                 */
		 while(!(CAS(&(insertion_lock.lock_value), 0, 1)))
		 {
			// Spinning waiting for lock.
		 }

		 if(head == NULL && tail == NULL)
		 {
		 	head = new QueueElement<data_val_type>(val);
		 	tail = head;
			CAS(&(insertion_lock.lock_value), 1 ,0);

			return (head);
		 }
		 else
		 {
		 	tail->SetPointer(temp);
		 	tail = temp;
			CAS(&(insertion_lock.lock_value), 1, 0);

			return (temp);
		 }
	}

	QueueElement<data_val_type>* GetElement()
	{
		QueueElement<data_val_type>* current_element = NULL;
		
		current_element = head;
		while(!(CAS(&(deletion_lock.lock_value), 0, 1)))
		{
			//Spin waiting for the lock
		}

		if(head != NULL)
		{
			head = head->GetPointer();
		}

		CAS(&(deletion_lock.lock_value) ,1, 0);

		return (current_element);
	}

	~ConcQueue()
	{
		QueueElement<data_val_type> *temp = NULL;

		temp = head;

		while(head != NULL)
		{
			temp = head->GetPointer();
			delete head;
			head = temp;
		}

	}
};
		 
#endif