#include
#include

int num_of_threads = 1;
LARGE_INTEGER start, end, freq;

class NODE {
public:
int key;
NODE *next;

NODE() { next = NULL;}

NODE(int key_value) {
next = NULL;
key = key_value;
}

~NODE() {}
};

class QUEUE {
NODE *head, *tail;
CRITICAL_SECTION enq_lock, deq_lock;
public:
QUEUE()
{
head = tail = new NODE(0);
InitializeCriticalSection(&enq_lock);
InitializeCriticalSection(&deq_lock);
}
~QUEUE() {}

void Init()
{
}
void Enq(int key)
{
EnterCriticalSection(&enq_lock);
NODE *e = new NODE(key);
tail->next = e;
tail = e;
LeaveCriticalSection(&enq_lock);
}

int Deq()
{
EnterCriticalSection(&deq_lock);
if (head->next == NULL) {LeaveCriticalSection(&deq_lock); return -999; }
int result = head->next->key;
NODE *temp = head;
head = head->next;
delete temp;
LeaveCriticalSection(&deq_lock);
return result;
}

};

bool CAS (NODE * volatile *Addr, NODE *Old, NODE *New)
{
LONG temp = InterlockedCompareExchange(
reinterpret_cast(Addr),
reinterpret_cast(New),
reinterpret_cast(Old));
return temp == reinterpret_cast(Old);
}

class LFQUEUE {
NODE * volatile head;
NODE * volatile tail;
public:
LFQUEUE()
{
head = tail = new NODE(0);
}
~LFQUEUE() {}

void Init()
{
NODE *ptr;
while(head->next != NULL) {
ptr = head;
head = head->next;
delete ptr;
}
tail = head;
}

void Enq(int x) {
NODE *e = new NODE(x);
while (true) {
NODE *last = tail;
NODE *next = last->next;
if (last != tail) continue;
if (NULL == next) {
if (CAS(&(last->next), NULL, e)) {
CAS(&tail, last, e);
return;
}
} else CAS(&tail, last, next);
} }


int Deq() {
while (true) {
NODE *first = head;
NODE *last = tail;
NODE *next = first->next;
if (first != head) continue;
if (first == last) {
if (next == NULL) {return -999;};
CAS(&tail, last, next);
continue;
}
int value = next->key;
if (false == CAS(&head, first, next)) continue;
delete first;
return value;
}
}
};



LFQUEUE lfqueue;
QUEUE queue;

DWORD WINAPI ThreadFunc(LPVOID lpVoid)
{
for (int i=0;i < 10000000 / num_of_threads;i++) {
if ((rand() % 2) || (i < 1000 / num_of_threads)) {
//queue.Enq(i);
lfqueue.Enq(i);
} else {
//queue.Deq();
lfqueue.Deq();
}
}
return 0;
}


int main()
{
HANDLE threads[64];

QueryPerformanceFrequency(&freq);
for (num_of_threads = 1; num_of_threads <=64 ; num_of_threads *= 2) {
lfqueue.Init();
QueryPerformanceCounter(&start);
for(int i=0;i threads[i] = CreateThread(NULL, 0, ThreadFunc, NULL, 0, NULL);
for(int i=0;i WaitForSingleObject(threads[i], INFINITE);
QueryPerformanceCounter(&end);
for(int i=0;i CloseHandle(threads[i]);
int dur = (int)((end.QuadPart - start.QuadPart) / (freq.QuadPart / 1000));
printf("%d threads, %dms\n", num_of_threads, dur);
}
return 0;
}