#ifndef stack_h
#define stack_h 1

#include <atomic>
#include <chrono>
#include <exception>
#include <thread>

using namespace std::chrono_literals;

class spinlock
{
public:
	void lock()
	{
		auto sleep = 16us;
		while (flag.test_and_set())
			std::this_thread::sleep_for(sleep *= 2);
	}

	void unlock()
	{
		flag.clear();
	}

private:
	std::atomic_flag flag;
};

template<class lock> class lock_guard
{
public:
	 lock_guard(lock& l): l(l) { l.lock(); }
	 lock_guard(const lock_guard&) = delete;
	 lock_guard& operator=(const lock_guard&) = delete;
	~lock_guard() { l.unlock(); }
private:
	lock& l;
};

template<class T> class stack
{
public:
	stack(): head(nullptr) {}

	struct empty: std::exception {};

	void push(const T& t)
	{
		lock_guard<spinlock> l(s);
		head = new node{head, t};
	}

	T pop()
	{
		lock_guard<spinlock> l(s);
		if (head)
		{
			node* n = head;
			head = head->next;
			T t = n->data;
			delete n;
			return t;
		}
		throw empty();
	}

private:
	struct node
	{
		node* next;
		T     data;
	};

	spinlock s;
	node* head;
};

#endif // stack_h