GxLockFreeQueue.h

Go to the documentation of this file.

//===========================================================================
//===========================================================================
#pragma once
 
GX_CORE_NAMESPACE_BEGIN()
 
//===========================================================================
//===========================================================================
template <class T, GxAllocatorList::ALLOCATOR_TYPE ALLOCATOR>
class GxLockFreeQueue
{
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    // new, delete定義
    GX_OPERATOR_NEW_DELETE(ALLOCATOR)
 
    
    struct Node
    {
        struct Node*        _pNext;     
        T                   _item;      
    };
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GxLockFreeQueue(void)
        : _pAllocatorList(nullptr)
        , _pBuffer(nullptr)
        , _pFree(nullptr)
        , _pHead(nullptr)
        , _pTail(nullptr)
        , _queueMax(0)
    {}
 
    ~GxLockFreeQueue(void){ terminate(); }
 
private:
    // コピーコンストラクタ (コピー禁止)
    GxLockFreeQueue(const GxLockFreeQueue&) = delete;
    // 代入演算子 (コピー禁止)
    GX_FORCE_INLINE const GxLockFreeQueue& operator=(const GxLockFreeQueue&) = delete;
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    b32 initialize(u32 queueMax);
    void terminate(void);
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    b32 enqueue(const T& src);
    b32 dequeue(T& dst);
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    b32 isEmpty(void) const;
    u32 getCount(void) const;
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
private:
    GxAllocatorList*            _pAllocatorList;            
    Node*                       _pBuffer;                   
    volatile Node*              _pFree;                     
    volatile Node*              _pHead;                     
    volatile Node*              _pTail;                     
    u32                         _queueMax;                  
 
};
 
//-----------------------------------------------------------
//  初期化
//-----------------------------------------------------------
template<class T, GxAllocatorList::ALLOCATOR_TYPE ALLOCATOR>
b32 GxLockFreeQueue<T, ALLOCATOR>::initialize(u32 queueMax)
{
    b32 ret = true;
 
    // アロケータ設定
    _pAllocatorList = GxAllocatorList::getAllocatorList(ALLOCATOR);
    GX_ASSERT(_pAllocatorList != nullptr, "getAllocatorList(%d) failed!!", ALLOCATOR);
 
    // キューバッファ個数設定 (終端判定分+1しておく)
    _queueMax = queueMax + 1;
 
    // キューバッファ確保
    u32 size = sizeof(Node) * _queueMax;
    _pBuffer = reinterpret_cast<Node*>( GX_ALLOCATE_MEMORY(_pAllocatorList, size) );
    if( !_pBuffer )
    {
        GX_ERROR(false, "allocateMemory<number:%d, size:%d> failed!!", ALLOCATOR, size);
        ret = false;    
    }
    else
    {
        // 初期化 (リストの連結)
        GX_MEMSET(_pBuffer, 0, size);
        for (u32 i = 0; i < _queueMax - 1; ++i)
        {
            _pBuffer[i]._pNext = &_pBuffer[i + 1];
        }
        _pFree = _pBuffer;
        _pHead = _pTail = &_pBuffer[_queueMax - 1];
    }
 
    return ret;
}
 
//-----------------------------------------------------------
// 終了
//-----------------------------------------------------------
template<class T, GxAllocatorList::ALLOCATOR_TYPE ALLOCATOR>
void GxLockFreeQueue<T, ALLOCATOR>::terminate(void)
{
    _pFree = _pHead = _pTail = nullptr;
    GX_SAFE_FREE_MEMORY(_pBuffer);
}
 
//-----------------------------------------------------------
// エンキュー
//-----------------------------------------------------------
template<class T, GxAllocatorList::ALLOCATOR_TYPE ALLOCATOR>
b32 GxLockFreeQueue<T, ALLOCATOR>::enqueue(const T& src)
{
    // 初期化済みチェック
    if( !_pHead )
    {
        return false;
    }
 
    //---- 空きノード取得
    Node* pNode = nullptr;
    for(;;)
    {
        // Double-Checked Lock パターン
        auto* pOldFree     = (Node*)_pFree;
        auto* pOldHead     = (Node*)_pHead;
        Node* pOldFreeNext = _pFree->_pNext;
 
        // 変更チェック → 変更されていたらもう一度取得
        if( pOldFree != _pFree )
        {
            continue;
        }
 
        // 満杯チェック
        if( pOldFree == pOldHead )
        {
            GX_TRACE(GX_TRACE_CATEGORY_CORE, "queue is Full!!");
            return false;
        }
 
        // 空き領域取得
        pNode = pOldFree;
 
        // キュー先頭を進める
        if(GxThread::casPointer((volatile void**)(&_pFree), pOldFree, pOldFreeNext))
        {
            break;
        }
    }
    
    //---- データ格納
    pNode->_item  = src;
    pNode->_pNext = nullptr;
 
    //---- 終端に追加
    Node* pOldTail     = nullptr;
    Node* pOldTailNext = nullptr;
    for(;;)
    {
        // Double-Checked Lock パターン
        pOldTail     = (Node*)_pTail;
        pOldTailNext = pOldTail->_pNext;
 
        // 変更チェック → 変更されていたらもう一度取得
        if( _pTail != pOldTail )
        {
            continue;
        }
 
        // 次リストチェック
        if( !pOldTailNext )
        {
            // 末尾のNextポインタ更新
            if(GxThread::casPointer((volatile void**)(&_pTail->_pNext), nullptr, pNode))
            {
                break;
            }
        }
        else
        {
            // 他スレッドで更新された → 終端ポインタを更新
            GxThread::casPointer((volatile void**)(&_pTail), pOldTail, pOldTailNext);
        }
    }
 
    // 終端ポインタを更新 ※次のエンキューで再設定される為、失敗は無視
    GxThread::casPointer((volatile void**)(&_pTail), pOldTail, pNode);
 
    return true;
}
 
//-----------------------------------------------------------
// デキュー
//-----------------------------------------------------------
template<class T, GxAllocatorList::ALLOCATOR_TYPE ALLOCATOR>
b32 GxLockFreeQueue<T, ALLOCATOR>::dequeue(T& dst)
{
    // 初期化済みチェック
    if( !_pHead )
    {
        return false;
    }
 
    //---- 終端要素取得
    T temporary;
    for(;;)
    {
        // Double-Checked Lock パターン
        Node* pOldHead     = (Node*)_pHead;
        Node* pOldTail     = (Node*)_pTail;
        Node* pOldHeadNext = pOldHead->_pNext;
 
        // 変更チェック → 変更されていたらもう一度取得
        if( _pHead != pOldHead )
        {
            continue;
        }
 
        // リスト要素存在チェック
        if( pOldHead == pOldTail )
        {
            // Nextが無ければデータなし
            if( pOldHeadNext == nullptr )
            {
                return false;
            }
            // Nextがあれば他スレッドで更新された → 終端ポインタ更新
            GxThread::casPointer((volatile void**)(&_pTail), pOldTail, pOldHeadNext);
        }
        else
        {
            // 情報取得
            temporary = pOldHeadNext->_item;
 
            // キュー先頭を進める
            if(GxThread::casPointer((volatile void**)(&_pHead), pOldHead, pOldHeadNext))
            {
                break;
            }
        }
    }
 
    // データ格納
    dst = temporary;
 
    return true;
}
 
//-----------------------------------------------------------
// キュー空判定
//-----------------------------------------------------------
template<class T, GxAllocatorList::ALLOCATOR_TYPE ALLOCATOR>
b32 GxLockFreeQueue<T, ALLOCATOR>::isEmpty(void) const
{
    GxThread::barrierMemory();
    return (_pHead == _pTail);
}
 
//-----------------------------------------------------------
// データ数を取得
//-----------------------------------------------------------
template<class T, GxAllocatorList::ALLOCATOR_TYPE ALLOCATOR>
u32 GxLockFreeQueue<T, ALLOCATOR>::getCount(void) const
{
    return static_cast<u32>(_pTail - _pHead);
}
 
GX_CORE_NAMESPACE_END()