Queue.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
#pragma once
 
#include "uLang/Common/Common.h"
 
#include <atomic>
#include <utility>
 
namespace uLang
{
 
enum class EQueueMode : int8_t
{
    MultipleProducersSingleConsumer,
    SingleProducerSingleConsumer,
};
 
// TODO: (yiliang.siew) Allow for custom allocators as the rest of `uLang` does.
// TODO: (yiliang.siew) See if some of the memory ordering requirements can be relaxed. For now
// since it guarantees an `MFENCE` instruction on x86-64 arch. Unreal issues a `_mm_sfence` intrinsic,
// which I'm not sure if I can guarantee via `std::atomic`.
template <typename InElementType, EQueueMode Mode = EQueueMode::SingleProducerSingleConsumer>
class TQueueG
{
public:
    TQueueG()
    {
        Head = Tail = new TNode();
    }
 
    ~TQueueG()
    {
        while (Tail != nullptr)
        {
            TNode* Node = Tail;
            Tail = Tail->Next;
            delete Node;
        }
    }
 
    bool Enqueue(const InElementType& InElement)
    {
        TNode* NewNode = new TNode(InElement);
        if (NewNode == nullptr)
        {
            return false;
        }
        TNode* OldHead;
        if (Mode == EQueueMode::MultipleProducersSingleConsumer)
        {
            OldHead = std::atomic_exchange_explicit(&Head, NewNode, std::memory_order_seq_cst);
            std::atomic_exchange_explicit(&OldHead->Next, NewNode, std::memory_order_seq_cst);
        }
        else
        {
            OldHead = Head;
            Head = NewNode;
            std::atomic_thread_fence(std::memory_order_seq_cst);
            OldHead->Next = NewNode;
        }
 
        return true;
    }
 
    bool Enqueue(const InElementType&& InElement)
    {
        TNode* NewNode = new TNode(InElement);
        if (NewNode == nullptr)
        {
            return false;
        }
        TNode* OldHead;
        if (Mode == EQueueMode::MultipleProducersSingleConsumer)
        {
            OldHead = std::atomic_exchange_explicit(&Head, NewNode, std::memory_order_seq_cst);
            std::atomic_exchange_explicit(&OldHead->Next, NewNode, std::memory_order_seq_cst);
        }
        else
        {
            OldHead = Head;
            Head = NewNode;
            std::atomic_thread_fence(std::memory_order_seq_cst);
            OldHead->Next = NewNode;
        }
 
        return true;
    }
 
    bool Dequeue(InElementType& OutElement)
    {
        TNode* Popped = Tail->Next;
        if (Popped == nullptr)
        {
            return false;
        }
        OutElement = std::move(Popped->Element);
        TNode* OldTail = Tail;
        Tail = Popped;
        Tail->Element = InElementType();
        delete OldTail;
 
        return true;
    }
    bool Pop()
    {
        TNode* Popped = Tail->Next;
        if (Popped == nullptr)
        {
            return false;
        }
        TNode* OldTail = Tail;
        Tail = Popped;
        Tail->Element = InElementType();
        delete OldTail;
 
        return true;
    }
 
    void Empty()
    {
        while (Pop())
        {
            ;
        }
    }
 
    bool IsEmpty()
    {
        return (Tail->Next.load() == nullptr);
    }
 
private:
    struct TNode
    {
        TNode() : Next(nullptr)
        {}
 
        explicit TNode(const InElementType& InElement) : Next(nullptr), Element(InElement)
        {}
 
        explicit TNode(const InElementType&& InElement) : Next(nullptr), Element(std::move(InElement))
        {}
 
        std::atomic<TNode*> Next;
        InElementType Element;
    };
 
    std::atomic<TNode*> Head;
 
    TNode* Tail;
 
protected:
    TQueueG(const TQueueG&) = delete;
 
    TQueueG& operator=(const TQueueG&) = delete;
};
 
template <typename InElementType>
using TQueue = TQueueG<InElementType>;
 
template <typename InElementType>
using TMQueue = TQueueG<InElementType, EQueueMode::MultipleProducersSingleConsumer>;
 
}    // namespace uLang