#ifndef stack_h
#define stack_h 1

#include <atomic>
#include <exception>
#include <boost/lockfree/detail/tagged_ptr.hpp>

template<class T> class stack
{
public:
	using empty = std::exception;
	
	~stack() { while (head.load()) pop(); }
	
	void push(const T& t)
	{
		pointer p(new node{pointer(), t});
		do {
			p->next = head;
			p.set_tag(p->next.get_tag());
		} while (!head.compare_exchange_strong(p->next, p));
	}
	
	T pop()
	{
		pointer old;
		do {
			old = head;
			if (!old)
				throw empty();
		} while (!head.compare_exchange_strong(old, pointer(old->next.get_ptr(), old.get_next_tag())));
		T data = old->data;
		delete old.get_ptr();
		return data;
	}
	
private:
	struct node;
	using pointer = typename boost::lockfree::detail::tagged_ptr<node>;
	
	struct node
	{
		pointer next;
		T       data;
	};
	
	std::atomic<pointer> head;
};

#endif // stack_h