#ifndef __ATOMIC_H__
#define __ATOMIC_H__

#include <deque>
#include <Exceptions.h>

namespace Atomic {

#if (__GNUC__ >= 5) || ((__GNUC__ == 4) && ((__GNUC_MINOR__ >= 1)))
// gcc version of the atomic operations
template <class T> T Or(volatile T * ptr, T mask) { __sync_or_and_fetch(ptr, mask); }
template <class T> T And(volatile T * ptr, T mask) { __sync_and_and_fetch(ptr, mask); }
template <class T> T Xor(volatile T * ptr, T mask) { __sync_xor_and_fetch(ptr, mask); }
template <class T> T Nand(volatile T * ptr, T mask) { __sync_nand_and_fetch(ptr, mask); }
template <class T> T Increment(volatile T * ptr, T delta = 1) { __sync_add_and_fetch(ptr, delta); }
template <class T> T Decrement(volatile T * ptr, T delta = 1) { __sync_sub_and_fetch(ptr, delta); }

namespace Prefetch {
template <class T> T Or(volatile T * ptr, T mask) { __sync_fetch_and_or(ptr, mask); }
template <class T> T And(volatile T * ptr, T mask) { __sync_fetch_and_and(ptr, mask); }
template <class T> T Xor(volatile T * ptr, T mask) { __sync_fetch_and_xor(ptr, mask); }
template <class T> T Nand(volatile T * ptr, T mask) { __sync_fetch_and_nand(ptr, mask); }
template <class T> T Increment(volatile T * ptr, T delta = 1) { __sync_fetch_and_add(ptr, delta); }
template <class T> T Decrement(volatile T * ptr, T delta = 1) { __sync_fetch_and_sub(ptr, delta); }
};

template <class T> T CmpXChgVal(volatile T * ptr, const T xch, const T cmp) { return __sync_val_compare_and_swap(ptr, cmp, xch); }
template <class T> bool CmpXChgBool(volatile T * ptr, const T xch, const T cmp) { return __sync_bool_compare_and_swap(ptr, cmp, xch); }

template <class T> T Exchange32(volatile T * ptr, const T exchange) {
#if defined(i386) || defined (__x86_64)
    __asm__ __volatile__("lock xchgl %0, (%1)" : "+r"(exchange) : "r"(ptr));
    return exchange;
#else
    T p;
    do { p = *ptr; } while (!__sync_bool_compare_and_swap(ptr, p, exchange));
    return p;
#endif
}

template <class T> T Exchange64(volatile T * ptr, const T exchange) {
#if defined(i386) || defined (__x86_64)
    __asm__ __volatile__("lock xchgq %0, (%1)" : "+r"(exchange) : "r"(ptr));
    return exchange;
#else
    T p;
    do { p = *ptr; } while (!__sync_bool_compare_and_swap(ptr, p, exchange));
    return p;
#endif
}

#else
#ifdef _MSVC
// Visual Studio version of the atomic operations

#error MSVC not yet implemented... and probably never will -.-

#else
#error No known platform for atomic operations.
#endif
#endif

template <class T> T * ExchangePtr(T * volatile * ptr, const T * exchange) {
#if defined (__x86_64)
    return Exchange64(ptr, exchange);
#else
    return Exchange32(ptr, exchange);
#endif
}

// This is a multiple producers / single consumer queue system. Stolen from the Fugue VM.

template<class T>
class Queue {
  private:
    struct ptr_t;
    struct node_t {
          node_t() : next(0), val(0) { }
          explicit node_t(T * val) : next(0), val(val) { }
        node_t * next;
        T * val;
        ptr_t * ptr;
    };
    
    struct ptr_t {
          ptr_t() : next(0), node(0) { }
          explicit ptr_t(node_t * node) : next(0), node(node) { }
          ptr_t(ptr_t * next, node_t * node) : next(next), node(node) { }
        ptr_t * next;
        node_t * node;
    };
    
  public:
    static const int NUMSLOTS = 16384;
      Queue() {
          unsigned int i;
          
          WHead = OWHead = new node_t;
          RHead = ORHead = new node_t;
          
          NodeFreeList = NULL;
          
          for(i = 0; i < NUMSLOTS; i++) {
              ptr_t * ptr = new ptr_t(NodeFreeList, &NodeBuffer[i]);
              FreeListHead = NodeFreeList = ptr;
              NodeBuffer[i].ptr = ptr;
          }
      }
      ~Queue() {
          unsigned int i;
          typename std::deque<node_t *>::iterator itr;
      
          for (itr = PendingReads.begin(); itr != PendingReads.end(); itr++)
              delete (*itr)->val;
          
          node_t * n;
          
          n = WHead;
          while (n) {
              delete n->val;
              n = n->next;
          }
          
          n = RHead;
          while (n) {
              delete n->val;
              n = n->next;
          }
          
          for (i = 0; i < NUMSLOTS; i++)
              delete NodeBuffer[i].ptr;
          
          delete ORHead;
          delete OWHead;
      }

    void enqueue(T * val) {
        node_t * node = AllocateNode(val);
        
        while (true) {
            node->next = WHead;
            if (CmpXChgBool(&WHead, node, node->next))
                return;
        }
    }

  public:
    T * unqueue(T ** pval = 0) {
        T * r;
        if (!PendingReads.empty()) {
            r = PopPendingRead();
            if (pval)
                *pval = r;
            return r;
        }
        
        if (!RHead->next)
            SwapReadAndWrite();
        
        node_t * n;

        n = RHead;
        while (RHead->next) {
            PendingReads.push_back(n);
            n = n->next;
            RHead = n;
        }
        
        if (PendingReads.empty()) {
            if (pval)
                *pval = 0;
            return 0;
        }
        
        r = this->PopPendingRead();
        if (pval)
            *pval = r;
        return r;
    }

  private:
    T * PopPendingRead() {
        node_t * node = PendingReads.back();
        T * val = node->val;
        FreeNode(node);
        PendingReads.pop_back();
        return val;
    }
    
    void SwapReadAndWrite() {
        while (true) {
            node_t * rh = RHead, * ow = WHead;
            if (CmpXChgBool(&WHead, rh, ow)) {
                RHead = ow;
                return;
            }
        }
    }
    
    node_t * AllocateNode(T * val) throw (GeneralException) {
        ptr_t * ptr;
        
        if (!FreeListHead->next)
            throw GeneralException("No more free slots in the queue.");
        
        ptr_t * newhead;
        
        do {
            ptr = FreeListHead;
            newhead = ptr->next;
        } while (!CmpXChgBool(&FreeListHead, newhead, ptr));
        
        ptr->node->val = val;
        return ptr->node;
    }
    
    void FreeNode(node_t * node) {
        node->val = 0;
        
        while (true) {
            node->ptr->next = FreeListHead;
            if (CmpXChgBool(&FreeListHead, node->ptr, node->ptr->next))
                break;
        }
    }
    
    node_t * WHead, * OWHead, * RHead, * ORHead, NodeBuffer[NUMSLOTS];
    ptr_t * NodeFreeList, * FreeListHead;
    // this should be stored in TLS...
    typename std::deque<node_t *> PendingReads;
};

}; // namespace Atomic

#endif