// a weak-atomics implementation of a stack
// Note: this stack `deals' with the ABA problem by leaking memory in the pop().

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

#include <../algorithms/stdatomic.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 { 
  _Atomic(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

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

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

stack *init_stack(void) { 
  stack *st = malloc(sizeof(stack)); // NB error handling omitted
  atomic_init(&st->top, NULL);
  return st;
}
 
void push(stack *st, Node* n) {
  Node *t;
  do {
    t = atomic_load_explicit(&st->top, memory_order_relaxed);     // Rrlx top = t
    n->next = t;                                                  // Wna n->next = t
  } while (! atomic_compare_exchange_weak_explicit(&st->top,&t,n, // CASrlx,rel st->top=t,n (beware mo arg order)
                 memory_order_release, memory_order_relaxed) ); 
}

Node* pop(stack *st) {
  Node *t, *n;
  do {
    t = atomic_load_explicit(&st->top, memory_order_acquire);     // Racq top=t
    if (t == NULL) return t; 
    n = t->next;                                                  // Rna t->next = n
  } while (!atomic_compare_exchange_weak_explicit(&st->top,&t,n,  // CASrlx,rlx st->top=t,n
                  memory_order_relaxed, memory_order_relaxed) ); 
  return t; 
}


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);
}

// ******* MP across the stack


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

void *writer_client_thread(void *arg) {
  Thread_arguments *targ = (Thread_arguments *) arg;
  targ->node->data = 7;            // Wna data = 7
  push(targ->st, targ->node);      // rel-acq synchronise in library
  return NULL;
}

void *reader_client_thread(void *arg) {
  int x;
  Thread_arguments *targ = (Thread_arguments *) arg;
  Node *n;
  do { n = pop(targ->st); } while (n == NULL);   // rel-acq synchronise in library
  x = n->data;                                   // Rna data = 7
  *(targ->result) = x;
  return NULL;
}


void mp_client() {
  stack * st;
  int x_mp,x2,x3;
  Node *n;
  st = init_stack();
  n = (Node *) malloc(sizeof (struct Node));  // NB error handling omitted
  struct Thread_arguments arg1 = {.st = st, .result = &x_mp, .node = n};
  struct Thread_arguments arg2 = {.st = st, .result = &x_mp, .node = n};

  //push_and_malloc(st,3);

  pthread_t t1,t2;
  pthread_create(&t1,NULL,writer_client_thread,(void *) &arg1);
  pthread_create(&t2,NULL,reader_client_thread,(void *) &arg2);
  pthread_join(t1,NULL); 
  pthread_join(t2,NULL); // NB omitted error handling
  x2 = pop_and_leak(st);
  x3 = pop_and_leak(st);
  printf("message-passing read client:  x_mp=%d  x2=%d  x3=%d\n",x_mp,x2,x3);
}

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

int main() {
  sequential_client();
  mp_client();
}