blob: 5404ee547de6f9d399b727cc48d43f83cc1554cd [file] [log] [blame]
#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