// a nonatomic stack implementation

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


// **************************************************************
// Interface

// a stack is represented as a `top' pointer to a linked list of nodes, 
// each with a data value (an int distinct from EMPTY) and a 
// pointer to the next node.
// For an empty stack, the `top' pointer is NULL.

#define EMPTY -1    // NB hacky coding for emptiness signalling

typedef struct Node {
  int data;
  struct Node *next;
} Node;

typedef struct stack { 
  Node *top; 
} stack; 

stack *init_stack(void); 
// init_stack mallocs a fresh stack structure and initialises it to 
// represent an empty stack

void push(stack *st, Node *n); 
// push should be called with a fresh node containing the value to be pushed
// (and an arbitrary next pointer); the value must not be equal to EMPTY

Node* pop(stack *st); 
// pop returns the popped node, or NULL if the stack was empty

// **************************************************************
// Implementation

stack *init_stack(void) { 
  stack *st = malloc(sizeof(stack)); // NB error handling omitted
  st->top = NULL;
  return st;
}
 
void push(stack *st, Node* n) {
  Node *t;
  t = st->top;        // R top = t
  n->next = t;        // W n->next = t
  st->top = n;        // W st->top = n
}

Node* pop(stack *st) {
  Node *t, *n;
  t = st->top;        // R st->top = t
  if (t != NULL) {
    n = t->next;      // R t->next = n
    st->top = n;      // W st->top = n
  }
  return t; 
}
//

// *************************************************************
// wrappers with allocation and leaking

void push_and_malloc(stack *st, int v); 
// push_and_malloc is a wrapper around push() that mallocs a fresh node;
// the value must not be equal to EMPTY

int pop_and_leak(stack* st);
// pop_and_leak is a wrapper around pop() that returns the value of the 
// popped node, leaking the node itself, or EMPTY if the stack is empty

void push_and_malloc(stack *st, int v) {
  Node *n;
  n = (Node *) malloc(sizeof (struct Node));  // NB error handling omitted
  n->data = v;
  push(st,n);
}

int pop_and_leak(stack *st) {
  Node *t;
  t = pop(st);
  if (t == NULL) 
    return EMPTY;
  else 
    return t->data;
}

// **************************************************************
// Clients

// ******* sequential

void sequential_client() {
  stack * st;
  int x1,x2,x3,x4;
  st = init_stack();
  push_and_malloc(st,3);
  push_and_malloc(st,5);
  push_and_malloc(st,7);
  x1 = pop_and_leak(st);
  x2 = pop_and_leak(st);
  x3 = pop_and_leak(st);
  x4 = pop_and_leak(st);
  printf("Sequential read client:  x1=%d  x2=%d  x3=%d  x4=%d\n",x1,x2,x3,x4);
}

// ******* concurrent readers

typedef struct Thread_arguments {
  stack *st;
  int *result;
} Thread_arguments;

void *read_client_thread(void *arg) {
  int x;
  Thread_arguments *targ;
  targ = (Thread_arguments *) arg;
  x = pop_and_leak(targ->st);
  *(targ->result) = x;
  return NULL;
}

void concurrent_read_client() {
  stack * st;
  int x1,x2,x3,x4;
  st = init_stack();
  struct Thread_arguments arg1 = {.st = st, .result = &x1};
  struct Thread_arguments arg2 = {.st = st, .result = &x2};

  push_and_malloc(st,3);
  push_and_malloc(st,5);
  push_and_malloc(st,7);

  pthread_t t1,t2;
  x1 = pthread_create(&t1,NULL,read_client_thread,(void *) &arg1);
  x2 = pthread_create(&t2,NULL,read_client_thread,(void *) &arg2);
  pthread_join(t1,NULL); // NB omitted error handling
  pthread_join(t2,NULL); // NB omitted error handling
  x3 = pop_and_leak(st);
  x4 = pop_and_leak(st);
  printf("Concurrent read client:  x1=%d  x2=%d  x3=%d  x4=%d\n",x1,x2,x3,x4);
}

// ******* concurrent readers, with mutex lock and unlocks 
// wrapped around the concurrent calls to pop_and_leak

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;

void *locked_read_client_thread(void *arg) {
  int x;
  Thread_arguments *targ;
  targ = (Thread_arguments *) arg;
  pthread_mutex_lock( &mutex1 );
  x = pop_and_leak(targ->st);
  pthread_mutex_unlock( &mutex1 );
  *(targ->result) = x;
  return NULL;
}

void concurrent_locked_read_client() {
  stack * st;
  int x1,x2,x3,x4;
  st = init_stack();
  struct Thread_arguments arg1 = {.st = st, .result = &x1};
  struct Thread_arguments arg2 = {.st = st, .result = &x2};

  push_and_malloc(st,3);
  push_and_malloc(st,5);
  push_and_malloc(st,7);

  pthread_t t1,t2;
  pthread_create(&t1,NULL,locked_read_client_thread,(void *) &arg1);
  pthread_create(&t2,NULL,locked_read_client_thread,(void *) &arg2);
  pthread_join(t1,NULL); // NB omitted error handling
  pthread_join(t2,NULL); // NB omitted error handling
  x3 = pop_and_leak(st);
  x4 = pop_and_leak(st);
  printf("Concurrent locked read client:  x1=%d  x2=%d  x3=%d  x4=%d\n",x1,x2,x3,x4);
}

// **************************************************************

int main() {
  sequential_client();
  concurrent_read_client();
  concurrent_locked_read_client();
}