#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <assert.h>

/* global variable for compare and exchange */
pthread_mutex_t CE_MUTEX;		// compare and exchange

/*
This c code is porting from C# version

The Empty Exception class:
1   class EmptyException : Exception {}

The Node Class:
1   public class Node<T> where T : class {
2     public T val;
3     public Node<T> next;
4     public Node (T val) {
5       this.val = val;
6       this.next = null;
7     }
8   }
*/

/* Node and Queue structure */
typedef struct NODE {
	void *val;
	struct NODE *next;
} Node;

typedef struct LOCKFREEQUEUE {
	Node *head, *tail;
} LockFreeQueue;

/*
1   [TestClass]
2   public class QueueTest {
3     public Struct EnqContainer {
4       String first;
5       String second;
6       LockFreeQueue q;
7     }
*/
typedef struct ENQCONTAINER {
	char *first;
	char *second;
	LockFreeQueue *queue;
} EnqContainer;


/* function prototype */
Node *NewNode(void *init_val);
LockFreeQueue *NewLockFreeQueue();

void InitCE (pthread_mutex_t *ce_lock);
void DestroyCE (pthread_mutex_t *ce_lock);
int CompareAndExchange (void **destination, void *value, void *comparand);

void LockFreeQueue_enq(LockFreeQueue *this_queue, void *x);
void *LockFreeQueue_deq(LockFreeQueue *this_queue);

void LockFreeQueue_enq_WithError1 (LockFreeQueue *this_queue, void *x);
void LockFreeQueue_enq_WithError2 (LockFreeQueue *this_queue, void *x);

void *EnqTwoStrings (void *contain);
void *EnqTwoStrings_WithError1 (void *contain);
void *EnqTwoStrings_WithError2 (void *contain);

void *DeqThreeStrings (void *lfq);


Node *NewNode(void *init_val) {
	Node *new_node = (Node*) malloc(sizeof(Node));

	new_node->val = init_val;
	new_node->next = NULL;
	
	return new_node;
}

/*
The LockFreeQueue Class:
1   public class LockFreeQueue<T> where T : class {
2     public Node<T> head, tail;
3     public LockFreeQueue () {
4       Node<T> node = new Node<T>();
5       head = tail = node;
6     }
7     
*/
LockFreeQueue *NewLockFreeQueue() {
	Node *init_head_tail = NewNode(NULL);
	LockFreeQueue *new_queue = (LockFreeQueue*) malloc(sizeof(LockFreeQueue));

	new_queue->head = new_queue->tail = init_head_tail;

	return new_queue;
}

/*
Interlocked.CompareExchange(
17                       ref last.next,node,next)) {
18              Interlocked.CompareExchange(
19                     ref tail, node, last);
*/

/* compare and exchange functions */
void InitCE (pthread_mutex_t *ce_lock) {
	pthread_mutex_init(ce_lock, NULL);
}

void DestroyCE (pthread_mutex_t *ce_lock) {
	pthread_mutex_destroy(ce_lock);
}

// return 1 for true and 0 for fasle
int CompareAndExchange (void **destination, void *value, void *comparand) {
	int success = 0;

	pthread_mutex_lock(&CE_MUTEX);
	if ((*destination) == comparand) {
		(*destination) = value;
		success = 1;
	}
	pthread_mutex_unlock(&CE_MUTEX);
	
	return success;
}

/*
8     public void enq(T x) {
9       Node<T> node = new Node<T>(x);
10      while (true) {
11        Node<T> last = tail;
12        Node<T> next = last.next;
13        if (last == tail) {
14          if (next == null) {
15            if (next == 
16                   Interlocked.CompareExchange(
17                       ref last.next,node,next)) {
18              Interlocked.CompareExchange(
19                     ref tail, node, last);
20              return;
21            }
22          } else {
23            Interlocked.CompareExchange(
24                   ref tail, next, last);
25          }
26        }
================================================ original java code
15        if (last == tail.get()) {
16          if (next == null) {
17            if (last.next.compareAndSet(
18                             next, node)) {
19              tail.compareAndSet(last, node);
20              return;
21            }
22          } else {
23            tail.compareAndSet(last, next);
24          }
25        }
================================================
27      }
28    }
*/

/* lock free queue enqueue */
void LockFreeQueue_enq(LockFreeQueue *this_queue, void *x) {
	Node *last = NULL;
	Node *next = NULL;
	Node *node = NewNode(x);

	while (1) {
		last = this_queue->tail;
		next = last->next;

		if (last == this_queue->tail) {
			if (next == NULL) {
				if ( CompareAndExchange(&(this_queue->tail->next), node, next) ) {
					CompareAndExchange(&(this_queue->tail), node, last);
					return;
				} 
			} else {
				CompareAndExchange(&(this_queue->tail), next, last);
			}
		}
	}
}

/*
8     
9     public void EnqTwoStrings (Object o) {
10      EnqContainer e = (EnqContainer)o;
11      e.q.enq(e.first);
12      e.q.enq(e.second);
13    }
*/
void *EnqTwoStrings (void *contain) {
	LockFreeQueue_enq(((EnqContainer*)contain)->queue, ((EnqContainer*)contain)->first);
	LockFreeQueue_enq(((EnqContainer*)contain)->queue, ((EnqContainer*)contain)->second);
	return NULL;
}

/*
14    
15    [TestMethod]
16    [HostType("Chess")]
17    [TestProperty("ChessMonitorVolatiles","True")]
18    public void TestLockFreeQueueWithError1(){
19      QueueTest qt = new QueueTest();
20      LockFreeQueue lfq = 
21          new LockFreeQueueWithError1();
22      EnqContainer firstParams, secondParams;
23      firstParams.q = secondParams.q = lfq;
24      firstParams.first = "a";
25      firstParams.second = "b";
26      secondParams.first = "c";
27      secondParams.second = "d";
28      Thread t2 = new Thread(
29                    new ParameterizedThreadStart(
30                                qt.EnqTwoStrings));
31      t2.start(secondParams);
32      QueueTwoItems(firstParams);
33      t2.join();
34      
35        // Test - Verify that the head is 
36        //   connected to the tail and that
37        //   the tail is exactly 4 nodes 
38        //   away from the head.
39      Node current = lfq.head;
40      for (int i = 0; i < 4; i++)
41        current = current.next;
42      Assert.IsTrue (current == lfq.tail);
43    }
44  }
*/
void TestLockFreeQueue () {
	int i;
	pthread_t t1;
	pthread_t t2;
	LockFreeQueue *lfq = NewLockFreeQueue();
	EnqContainer firstParams, secondParams;	
	
	firstParams.queue = secondParams.queue = lfq;
	firstParams.first = "a";
	firstParams.second = "b";
	secondParams.first = "c";
	secondParams.second = "d";

	pthread_create(&t1, NULL, EnqTwoStrings, &firstParams);
	pthread_create(&t2, NULL, EnqTwoStrings, &secondParams);
	pthread_join(t1, NULL);
	pthread_join(t2, NULL);	

	Node *current = lfq->head;
	for (i = 0 ; i < 4 ; i++) {
		current = current->next;
		assert(current != NULL);
		printf("%d: %s\n", i, (char*)current->val);
	}
}	

int main (void) {
	InitCE(&CE_MUTEX);
	TestLockFreeQueue ();
	DestroyCE(&CE_MUTEX);
	return 0;
}