// an sc-atomics implementation of a stack
// (using the verbose memory order syntax)
// Note: this stack `deals' with the ABA problem by leaking memory in the pop().

#include <stdio.h>
#include <stdlib.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);                                    // Wna st->top = NULL
  return st;
}
 
void push(stack *st, Node* n) {
  Node *t;
  do {
    t = atomic_load_explicit(&st->top, memory_order_seq_cst);     // Rsc top = t
    n->next = t;                                                  // Wna n->next = t
  } while (! atomic_compare_exchange_weak_explicit(&st->top,&t,n, // CASsc,sc st->top=t,n
                 memory_order_seq_cst, memory_order_seq_cst) ); 
}

Node * pop(stack *st) {
  Node *t, *n;
  do {
    t = atomic_load_explicit(&st->top, memory_order_seq_cst);    // Rsc top=t
    if (t == NULL) return t; 
    n = t->next;                                                 // Rna t->next = n
  } while (!atomic_compare_exchange_weak_explicit(&st->top,&t,n, // CASsc,sc st->top=t,n
                  memory_order_seq_cst, memory_order_seq_cst) ); 
  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;
}



// **************************************************************
// Client

int main() {
  stack * st;
  int x1,x2,x3;
  st = init_stack();
  push_and_malloc(st,3);
  push_and_malloc(st,7);
  x1 = pop_and_leak(st);
  x2 = pop_and_leak(st);
  x3 = pop_and_leak(st);
  printf("x1=%d  x2=%d  x3=%d\n",x1,x2,x3);
  }