#ifndef THREADSAFELIST_H
#define THREADSAFELIST_H

#include <iostream>
#include <stdexcept>
#include <vector>
#include <iterator>

#include "Atomic.h"

using namespace std;

/***
 *
 * This file provides a template for a list that can be safely iterated
 *  in one thread while it is modified from another. The iterable list
 *  performs no allocations or frees so it is safe to call from a restricted
 *  environment such as a real-time thread. Typical usage will
 *  be like this, where T is some pointer type:
 *
 *  realtime thread:
 *
 *  iterator<T> it = tsl.begin()
 *  while( it != tsl.end() ) {
 *    ..do stuff with it..
 *    ++it;
 *  }
 *  tsl.markAsCleanable();
 *
 *
 * while the other thread (the control thread) might look like this:
 *
 * ThreadSafeList<T> tsl();
 * ..start/stop realtime thread as needed while using insert() and erase()..
 * (you can call tsl.clean() from time to time in the control thread if you like)
 *
 * Of course, ThreadSafeList is abstract, so you'll need something like this:
 * class MyList : public ThreadSafeList< void * >
 * {
 *    virtual void cleanSingle( void * d ) {
 *       //something to do when done with d, like delete it
 *    }
 * } ;
 *
 * On destruction, ThreadSafeList will attempt to erase all elements in the list,
 * so it's a good idea to over-write the destructor, otherwise the cleanSingle()
 * function on the super-class will be called, leading to a pure-virtual function call
 * which will crash the app. The simplest solution is to write a destructor as follows:
   ~MyThreadSafeList()
   {
      eraseAll();
      markAsCleanable();
      clean();
   }
 *
 ***/

/*****
 * Node class used only here.
 * It should be static.
 *****/
template< class T > class Node {
 public:
   const T elt;
   Node * next;
   Node * prev;
   Node() : elt(NULL), next(NULL), prev(NULL) {}
   Node(const T& elt, Node * prev, Node * next)
          : elt(elt), next(next), prev(prev) {}
};

template< class T > class LockFreeStack {
 private:
    Node<T>* head;
 public:
    LockFreeStack() {
       head = new Node<T>( NULL, NULL, NULL );
    }
    ~LockFreeStack() {
       if( head->next || head->prev || head->elt )
          throw runtime_error( "memory leak in ThreadSafeList (Lock Free Stack)" );
       delete head;
    }
    void push( Node<T>* node) {
       node->prev = NULL;
       do {
          node->next = head;
          writeMemoryBarrier();
       } while (!CASPointer(node->next,node,&head));
    }
    Node<T>* pop() {
       Node<T>* ret;
       Node<T>* node;
       do {
          ret = head;
          node = ret;
          if( node->elt == NULL || node->next == NULL )
             return NULL;
          node = node->next;
          writeMemoryBarrier();
       } while( !CASPointer(ret,node,&head) );
       return ret;
    }
};

// this class produces an interater that is always read-safe.
// that is, you can always move along it
// even as another thread is inserting or removing elements.
// the thread reading elements is treated as realtime and no
// allocations will happen on that thread.
// It does not mimic nearly all the functionality of the stl list.
// T needs to be a pointer type and NULL values are not allowed.

template< class T > class ThreadSafeList
{
 public:
   class iterator {
      friend class ThreadSafeList;
    private:
      Node<T> * node;
      iterator();
      iterator( Node<T> * node ) : node( node ) {}
      Node<T> * getNode() { return node; }
    public:
      iterator( const iterator& it ) : node( it.node ) {}
      bool operator==(const iterator &it)
      { return node == it.node; }
      bool operator!=(const iterator &it)
      { return ! (*this == it ); }
      iterator& operator++() // prefix ++
      {
         if( node == NULL )
            throw out_of_range( "ThreadSafeList iterator out of range" );
         node = node->next;
         readMemoryBarrier();
         return *this;
      }
      iterator operator++(int) // postfix ++
      {
         if( node == NULL )
            throw out_of_range( "ThreadSafeList iterator out of range" );
         iterator tmp( *this );
         readMemoryBarrier();
         ++*this;
         return tmp;
      }
      const T* operator->()
      {
         if( node == NULL )
            throw out_of_range( "ThreadSafeList iterator out of range" );
         return &(node->elt);
      }
      const T& operator*()
      {
         if( node == NULL )
            throw out_of_range( "ThreadSafeList iterator out of range" );
         return (node->elt);
      }
   };
 private:
   Node<T> * first;
   Node<T> * last;
   LockFreeStack<T> deletable;
   LockFreeStack<T> cleanable;
   size_t malloccount;
   size_t eltcount;
 public:
   ThreadSafeList() : deletable(), malloccount( 0 ), eltcount( 0 )
   {
      first = last = new Node<T>( NULL, NULL, NULL );
      ++malloccount;
   }
   void push_back( const T& val )
   {
      if( first == last ) { // the list is empty
         first = new Node<T>( val, NULL, last ); //iterator( &val, NULL, last );
         ++malloccount;
         last->prev = first;
      } else {
         Node<T> * newNode  = new Node<T>( val, last->prev, last );
         ++malloccount;
         last->prev = newNode;
         writeMemoryBarrier();
         if( newNode->prev )
            newNode->prev->next = newNode;
      }
      ++eltcount;
   }
   // insert before
   iterator insert( iterator i, const T & val )
   {
      clean();
      if( i.getNode() == last ) {
         push_back( val );
         return iterator( last->prev );
      } else {
         Node<T> * newNode = new Node<T>( val, i.getNode()->prev, i.getNode() );
         ++malloccount;
         Node<T> * tmp = i.getNode()->prev;
         writeMemoryBarrier();
         i.getNode()->prev = newNode;
         writeMemoryBarrier();
         if( tmp ) // if there was an element before this, we set it's "next"
            tmp->next = newNode;
         else // otherwise, we are inserting to the beginning of the list
            first = newNode;
         ++eltcount;
         return iterator( newNode );
      }
   }
   iterator begin() { return iterator( first ); }
   iterator end()   { return iterator( last ); }
   // not safe to be called from real-time thread
   iterator nberase( iterator i )
   { 
      if( i.getNode() == last )
         throw out_of_range( "ThreadSafeList iterator out of range" );
      if( i.getNode() == first ) {
         Node<T> * node = first;
         if( node->next )
            node->next->prev = NULL;
         writeMemoryBarrier();
         first = node->next;
         deletable.push( node );
         --eltcount;
         return iterator( first );
      } else {
         Node<T> * node = i.getNode();
         node->next->prev = node->prev;
         writeMemoryBarrier();
         node->prev->next = node->next;
         deletable.push( node );
         --eltcount;
         return iterator( node->next );
      }
   }
   // removes the element pointed to by i. note that i remains a valid
   // (though unreachable) iterator until clean is called.
   iterator erase( iterator i )
   { 
      clean();
      return nberase( i );
   }
   void eraseAll() {
      while( begin() != end() )
         erase( begin() );
   }
   size_t size() { return eltcount; }
   // called from realtime thead (or after joining) to indicate that
   // the iterator is not being used so some housekeeping can be done
   // to make the items in the list cleanable.
   void markAsCleanable() {
      Node<T> *tmp;
      while( ( tmp = cleanable.pop() ) ) {
         deletable.push( tmp );
      }
   }
   virtual void cleanSingle( T t ) = 0;
   // frees memory allocated by previous calls to erase.
   // must be called in the control thread. It is not strictly necessary
   // to call this function because it is called automatically when calling
   // erase ot insert, so it is unlikely that more than one or two items will
   // ever need to be cleaned.
   void clean()
   {
      Node<T> *tmp;
      while( ( tmp = deletable.pop() ) ) {
         fullMemoryBarrier();
         cleanSingle( tmp->elt );
         delete tmp;
         --malloccount;
      }
      if( malloccount != eltcount+1 ) {
         cout << "memory leak in ThreadSafeList (a)" << endl;
         throw runtime_error( "memory leak in ThreadSafeList" );
      }
   }
   virtual ~ThreadSafeList()
    {
      iterator tmp = begin();

      while( tmp != end() ) {
         tmp = erase( tmp );
      }
      markAsCleanable();
      clean();
      delete( last );
      --malloccount;
      if( malloccount != 0 ) {
         cout << "memory leak in ThreadSafeList (b)" << endl;
         throw runtime_error( "memory leak in ThreadSafeList" );
      }
   }
};
#endif /* THREADSAFELIST_H */