#ifndef LF_LIST_H
#define LF_LIST_H

#include <atomic>
#include <cassert>

/* simple lock-free list */

template <typename T>
class LFList {
   private:
      struct Element;
   public:
      LFList() : head(nullptr) {
      }
      ~LFList() {
	 Element* next;
	 for (Element* p = head.load(); p; p = next) {
	    next = p->next.load();
	    delete p;
	 }
      }
      void push(const T& item) {
	 Element* element = new Element(item);
	 Element* p = head.load();
	 element->next.store(p);
	 while (!head.compare_exchange_weak(p, element)) {
	    element->next.store(p);
	 }
      }
      bool pop(T& item) {
	 Element* p = head.load();
	 while (p && !head.compare_exchange_weak(p, p->next.load()))
	    ;
	 if (p) {
	    item = p->item;
	    return true;
	 } else {
	    return false;
	 }
      }
   private:
      struct Element {
	 Element() : next(nullptr) {
	 }
	 Element(const T& item_) : item(item_), next(nullptr) {
	 }
	 T item;
	 std::atomic<Element*> next;
      };
      std::atomic<Element*> head;
};

#endif