#include <vector>
#include <chrono>
#include <atomic>
#include <thread>
#include <cassert>
#include <iostream>

struct list {
  struct node {
    std::atomic<node*> next;

    void start_operation() {
      static std::atomic_int i;
      ++i;
      int j = i;
      using namespace std::literals;
      std::this_thread::sleep_for((rand()%100/100.)*.01s);
      std::cerr <<"doing it! i="<<j<<"\n";
      assert(i == 1);
      --i;
    }
  };

  std::atomic<node*> tail{ nullptr };

  void push(node* new_node) {
    using namespace std::literals;

    std::this_thread::sleep_for((rand()%100/100.)*.2s);

    node* old_tail = tail.exchange(new_node);

    std::this_thread::sleep_for((rand()%100/100.)*.2s);

    if(old_tail == nullptr || old_tail->next.exchange(new_node) == old_tail) {
      node* current = new_node;
      while(true) {
        current->start_operation();
        std::this_thread::sleep_for((rand()%100/100.)*0.01s);
        node* expected = nullptr;
        if(current->next.compare_exchange_strong(expected, new_node)) return;
        else current = expected;
      }
    }
  }
};

int main() {
  srand(1);
  list l;
  std::vector<std::thread> ts;
  for (int i=0; i<10; ++i) {
    ts.emplace_back([&l,i]() {
        list::node n;
        std::string s="push "+std::to_string(i)+"\n";
        std::cerr << s;
        l.push(&n);
        s="finished "+std::to_string(i)+"\n";
        std::cerr << s;
        using namespace std::literals;
        std::this_thread::sleep_for(1s);
      });
  }
  for (auto& t : ts)
    t.join();
  std::cerr << "done\n";
}