/*---------------------------------------------------------------------------*
  Project:  Horizon
  File:     util_LockFreeQueueImpl.h

  Copyright (C)2009 Nintendo Co., Ltd.  All rights reserved.

  These coded instructions, statements, and computer programs contain
  proprietary information of Nintendo of America Inc. and/or Nintendo
  Company Ltd., and are protected by Federal copyright law.  They may
  not be disclosed to third parties or copied or duplicated in any form,
  in whole or in part, without the prior written consent of Nintendo.

  $Rev: 12449 $
 *---------------------------------------------------------------------------*/

#ifndef NN_UTIL_ARMV6_UTIL_LOCKFREEQUEUEIMPL_H_
#define NN_UTIL_ARMV6_UTIL_LOCKFREEQUEUEIMPL_H_

#include <nn/types.h>
#include <nn/assert.h>
#include <nn/util/util_Noncopyable.h>
#include <nn/util/util_StaticAssert.h>

namespace nn { namespace util { namespace ARMv6 {

namespace detail {
    
    class LockFreeQueueNodeBase;
    
    struct LockFreeQueuePointerData
    {
        LockFreeQueueNodeBase* pointer;
        u32 tag;
    };
    struct LockFreeQueuePointer
    {
        union
        {
            bit64 buf;
            LockFreeQueuePointerData data;
        };
        LockFreeQueuePointer() {}
        LockFreeQueuePointer(const LockFreeQueuePointer& other) : buf(other.buf) {}
        bool operator==(const LockFreeQueuePointer& other) { return buf == other.buf; }
    };
    
    class LockFreeQueueNodeBase : private NonCopyable<LockFreeQueueNodeBase>
    {
        friend class LockFreeQueueImplBase;
        template <typename> friend class LockFreeQueueImpl;
    private:
        typedef LockFreeQueuePointer Pointer;
        
        Pointer m_next;
        
        void MarkAsNotInserted()
        {
#ifdef NN_BUILD_NOOPT
            m_next.buf = 0xffffffffffffffffULL;
#endif
        }
        
        void AssertNotInserted() const
        {
#ifdef NN_BUILD_NOOPT
            NN_TASSERT_(m_next.buf == 0xffffffffffffffffULL);
#endif
        }
        
    protected:
        void Initialize()
        {
            MarkAsNotInserted();
        }
    };

    template <typename T>
    class LockFreeQueueNode : private nn::util::NonCopyable<LockFreeQueueNode<T> >, private LockFreeQueueNodeBase
    {
        friend class LockFreeQueueImplBase;
        template <typename> friend class LockFreeQueueImpl;
    private:
        typedef LockFreeQueueNodeBase Base;
        
        T m_x;
        void Initialize() { Base::Initialize(); }
        
    public:
        LockFreeQueueNode() { Initialize(); }
        explicit LockFreeQueueNode(const T& x) : m_x(x) { Initialize(); }
        
        T& Value() { return m_x; }
        const T& Value() const { return m_x; }
    };
    
    class LockFreeQueueImplBase : private NonCopyable<LockFreeQueueImplBase>
    {
    protected:
        typedef LockFreeQueuePointer Pointer;
        typedef LockFreeQueueNodeBase NodeType;
        
        Pointer m_head, m_tail;
    
        LockFreeQueueImplBase(NodeType* emptyNode)
        {
            emptyNode->m_next.data.pointer = 0;
            m_head.data.pointer = m_tail.data.pointer = emptyNode;
        }
        
        bool IsEmpty() const
        {
            return m_head.data.pointer == m_tail.data.pointer;
        }
        
        void EnqueueImpl(NodeType* pNode);
    };

    template <typename T>
    class LockFreeQueueImpl : private NonCopyable<LockFreeQueueImpl<T> >, private LockFreeQueueImplBase
    {
    public:
        typedef T ValueType;
        typedef LockFreeQueueNode<T> NodeType;
        
        LockFreeQueueImpl(NodeType* nullNode) : LockFreeQueueImplBase(nullNode) {}
        void EnqueueImpl(NodeType* pNode) { return LockFreeQueueImplBase::EnqueueImpl(pNode); }
        NodeType* DequeueImpl(T* pDequeuedObject); // 返されたノードは、ユーザ側が適切に破棄などをする必要がある。このノードはpDequeuedObjectとは無関係
        using LockFreeQueueImplBase::IsEmpty;
    };
    
    bool CompareAndSwapQueuePointer(LockFreeQueuePointer* pTarget, const LockFreeQueuePointer& comp, LockFreeQueueNodeBase* swapNode, u32 swapTag);
    
    template <typename T>
    LockFreeQueueImpl<T>::NodeType* LockFreeQueueImpl<T>::DequeueImpl(T* pDequeuedObject)
    {
        while (true)
        {
            LockFreeQueuePointer head = this->m_head;
            LockFreeQueuePointer tail = this->m_tail;
            LockFreeQueuePointer next = head.data.pointer->m_next;
            if (head == this->m_head)
            {
                if (head.data.pointer == tail.data.pointer)
                {
                    if (!next.data.pointer)
                    {
                        return 0;
                    }
                    else
                    {
                        CompareAndSwapQueuePointer(&(this->m_tail), tail, next.data.pointer, tail.data.tag + 1);
                    }
                }
                else
                {
                    T DequeuedObject = static_cast<LockFreeQueueNode<T>*>(next.data.pointer)->Value();
                    if (CompareAndSwapQueuePointer(&(this->m_head), head, next.data.pointer, head.data.tag + 1))
                    {
                        *pDequeuedObject = DequeuedObject;
                        LockFreeQueueNode<T>* ret = static_cast<LockFreeQueueNode<T>*>(head.data.pointer);
                        ret->MarkAsNotInserted();
                        return ret;
                    }
                }
            }
        }
    }
    
}

}}}

#endif