#define GROW_BY_SIZE 16

template<class T>
class LockFreeMemCache
{
public:
    LockFreeMemCache()
    {
        Head=NULL;
        FreeStack=NULL;
        AddSomeCache();
    }
    ~LockFreeMemCache()
    {

    }
    T *Malloc()
    {
        T *returnValue = NULL;
        returnValue=Pop();
        while(returnValue==NULL)
        {
            AddSomeCache();
            returnValue=Pop();
        }
        return returnValue;
    }
    void Free(T *ptr)
    {
        Push(ptr);
    }

private:
    void AddSomeCache()
    {
        for(int i=0; i < GROW_BY_SIZE; i++)
        {
            T *tmp = new T();
            Push(tmp);
        }
    }

private:
    void Push(T *item)
    {
        Node<T> * new_node = PopNode();
        new_node->Data=item;

        bool done = false;
        while(!done)
        {
            Node<T>* head = Head;
            new_node->Next = head;
            if(__sync_bool_compare_and_swap(&Head,head,new_node))
            {
                done = true;
            }
        }

    }
    T *Pop()
    {
        T *returnValue = NULL;
        bool done = false;
        while(!done)
        {
            Node<T> * head= Head;
            if(Head == NULL)
            {
                done=true;
            }
            else
            {
                Node<T> *curr = head;
                if(__sync_bool_compare_and_swap(&Head,head,curr->Next))
                {
                    done = true;
                    returnValue = curr->Data;
                    PushNode(curr);
                }

            }
        }
        return returnValue;
    }
    void PushNode(Node<T> *item)
    {
        item->Next = NULL;
        item->Data = NULL;
        bool done = false;
        while(!done)
        {
            Node<T>* fs = FreeStack;
            item->Next = fs;
            if(__sync_bool_compare_and_swap(&FreeStack,fs,item))
            {
                done = true;
            }
        }
    }
    Node<T> *PopNode()
    {
        Node<T> *returnValue = NULL;
        bool done = false;
        while(!done)
        {
            Node<T> *fs = FreeStack;
            if(fs == NULL)
            {
                done=true;
            }
            else
            {
                Node<T> *curr = fs;
                if(__sync_bool_compare_and_swap(&FreeStack,fs,curr->Next))
                {
                    done = true;
                    returnValue = curr;
                }

            }
        }
        if (returnValue == NULL)
        {
            returnValue = new Node<T>();
            returnValue->Data = NULL;
            returnValue->Next = NULL;
        }
        return returnValue;
    }
    Node<T> *Head;
    Node<T> *FreeStack;
};

template<class T>
class LockFreeStack
{
public:
    LockFreeStack()
    {
        Head = NULL;
    }
    ~LockFreeStack(){
    }
    void Push(T *item)
    {
        Node<T> * new_node = Cache.Malloc();
        new_node->Data=item;

        bool done = false;
        while(!done)
        {
            Node<T>* head = Head;
            new_node->Next = head;
            if(__sync_bool_compare_and_swap(&Head,head,new_node))
            {
                done = true;
            }
        }
    }

    T *Pop()
    {
        T *returnValue = NULL;
        bool done = false;
        while(!done)
        {
            Node<T> *head = Head;
            if(head == NULL)
            {
                done=true;
            }
            else
            {
                Node<T> *curr = head;
                if(__sync_bool_compare_and_swap(&Head,head,curr->Next))
                {
                    done = true;
                    returnValue = curr->Data;
                    curr->Next =NULL;
                    Cache.Free(curr);
                }

            }
        }
        return returnValue;
    }
public:

    Node<T> *Head;

private:
    LockFreeMemCache<Node<T> > Cache;
};

template<class T>
class LockFreeQueue
{
public:
    LockFreeQueue()
    {
        Head=NULL;
    }
    ~LockFreeQueue(){
    }
    void Enqueue(T *item)
    {
        Node<T> * new_node = Cache.Malloc();
        new_node->Data=item;

        bool done = false;
        while(!done)
        {
            Node<T>* head = Head;
            new_node->Next = head;
            if(__sync_bool_compare_and_swap(&Head,head,new_node))
            {
                done = true;
            }
        }
    }
    T *Dequeue()
    {
        T *returnValue=NULL;
        bool done = false;
        while(!done)
        {
            if(Head == NULL)
            {
                done = true;
            }
            else
            {
                volatile Node<T> *prev = NULL, *curr = Head, *head = Head;
                bool found = false;
                while(!found)
                {
                    if(curr->Next == NULL)
                    {
                        found=true;
                        break;
                    }
                    prev = curr;
                    curr = curr->Next;
                }
                if(prev == NULL)
                {
                    if(__sync_bool_compare_and_swap(&Head,head,NULL))
                    {
                        done = true;
                    }
                }
                else
                {
                    if(__sync_bool_compare_and_swap(&prev->Next,prev->Next,NULL))
                    {
                        done = true;
                    }
                }
                if(done)
                {
                    returnValue = curr->Data;
                    curr->Data = NULL;
                    curr->Next= NULL;
                    Cache.Free(curr);
                }

            }
        }

        return returnValue;
    }
public:


private:
    Node<T> *Head;
    LockFreeMemCache<Node<T> > Cache;
};