#include <assert.h>
#include <pthread.h>
#include <stdatomic.h>

#define PTR(V)      (LF_SLIST *)((V) & (~(intptr_t)1))
#define DELETED(V)  ((void*)(((intptr_t)V) & 1L))

/* An element of the list */
typedef struct {
  intptr_t volatile link; /* a pointer to the next element in a list and a flag */
  uint8_t *key;
} LF_SLIST;

// a global LF_SLIST list
LF_SLIST node1, node2, node3;
LF_SLIST* global_node = NULL;

void* t_read(void* param) {
  // CURSOR
  LF_SLIST* prev = NULL;
  LF_SLIST* curr = NULL;
  LF_SLIST* next = NULL;

  // l_find
  intptr_t link = (intptr_t)NULL;
  uint8_t* cur_key = NULL;

  prev = global_node;
  do {
    curr = (LF_SLIST*)prev->link;
  } while (atomic_load_explicit((_Atomic(LF_SLIST*)*)&prev->link, __ATOMIC_SEQ_CST) != curr);

  if(!curr)
    return NULL;

  cur_key = curr->key;

  do {
    link = (intptr_t) curr->link;
    next = PTR(link);
  } while (link != curr->link);

  if(!DELETED(link))
    assert(cur_key != NULL);

  return NULL;
}

void* t_write(void* param) {
  // CURSOR
  LF_SLIST* prev = NULL;
  LF_SLIST* curr = NULL;
  LF_SLIST* next = NULL;

  // set CURSOR as l_find would do
  prev = global_node;
  curr = (LF_SLIST*)prev->link;
  next = (LF_SLIST*)curr->link;

  // l_delete

  // Mark node to be deleted
  if(atomic_compare_exchange_strong_explicit((_Atomic(LF_SLIST*)*)&curr->link, &next, (LF_SLIST*)( ((intptr_t)next) | 1), __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
    // Take node out of list
    if(atomic_compare_exchange_strong_explicit((_Atomic(LF_SLIST*)*)&prev->link, &curr, next, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)){
      // lf_pinbox_free
      // add to purgatory
      curr->key = NULL;
    }
  }

  return NULL;
}

void init() {
  node1.link=(intptr_t)&node2;
  node2.link=(intptr_t)&node3;
  node3.link=(intptr_t)NULL;

  node1.key = (uint8_t*)1;
  node2.key = (uint8_t*)1;
  node3.key = (uint8_t*)1;

  global_node = &node1;
}

int main() {
  pthread_t thread_read, thread_write;

  init();

  pthread_create(&thread_read, NULL, t_read, NULL);
  pthread_create(&thread_write, NULL, t_write, NULL);

  pthread_join(thread_read, NULL);
  pthread_join(thread_write, NULL);
}