Queue.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "Templates/UnrealTemplate.h"
#include "HAL/PlatformAtomics.h"
#include "HAL/PlatformMisc.h"
#include <type_traits>
 
// WARNING: This queue is planned for deprecation in favor of TSpscQueue or TMpscQueue
 
enum class EQueueMode
{
    Mpsc,
 
    Spsc,
 
    SingleThreaded,
};
 
 
template<typename T, EQueueMode Mode = EQueueMode::Spsc>
class TQueue
{
public:
    using FElementType = T;
 
    [[nodiscard]] TQueue()
    {
        Head = Tail = new TNode();
    }
 
    ~TQueue()
    {
        while (Tail != nullptr)
        {
            TNode* Node = Tail;
            Tail = Tail->NextNode;
 
            delete Node;
        }
    }
 
    UE_NONCOPYABLE(TQueue);
 
    bool Dequeue(FElementType& OutItem)
    {
        TNode* Popped = Tail->NextNode;
 
        if (Popped == nullptr)
        {
            return false;
        }
 
        if constexpr (Mode != EQueueMode::SingleThreaded)
        {
            TSAN_AFTER(&Tail->NextNode);
        }
 
        OutItem = MoveTemp(Popped->Item);
 
        TNode* OldTail = Tail;
        Tail = Popped;
        Tail->Item = FElementType();
        delete OldTail;
 
        return true;
    }
 
    void Empty()
    {
        while (Pop());
    }
 
    bool Enqueue(const FElementType& Item)
    {
        TNode* NewNode = new TNode(Item);
 
        if (NewNode == nullptr)
        {
            return false;
        }
 
        TNode* OldHead;
 
        if constexpr (Mode == EQueueMode::Mpsc)
        {
            OldHead = (TNode*)FPlatformAtomics::InterlockedExchangePtr((void**)&Head, NewNode);
            TSAN_BEFORE(&OldHead->NextNode);
            FPlatformAtomics::InterlockedExchangePtr((void**)&OldHead->NextNode, NewNode);
        }
        else
        {
            OldHead = Head;
            Head = NewNode;
 
            if constexpr (Mode == EQueueMode::Spsc)
            {
                TSAN_BEFORE(&OldHead->NextNode);
                FPlatformMisc::MemoryBarrier();
            }
 
            OldHead->NextNode = NewNode;
        }
 
        return true;
    }
 
    bool Enqueue(FElementType&& Item)
    {
        TNode* NewNode = new TNode(MoveTemp(Item));
 
        if (NewNode == nullptr)
        {
            return false;
        }
 
        TNode* OldHead;
 
        if constexpr (Mode == EQueueMode::Mpsc)
        {
            OldHead = (TNode*)FPlatformAtomics::InterlockedExchangePtr((void**)&Head, NewNode);
            TSAN_BEFORE(&OldHead->NextNode);
            FPlatformAtomics::InterlockedExchangePtr((void**)&OldHead->NextNode, NewNode);
        }
        else
        {
            OldHead = Head;
            Head = NewNode;
 
            if constexpr (Mode == EQueueMode::Spsc)
            {
                TSAN_BEFORE(&OldHead->NextNode);
                FPlatformMisc::MemoryBarrier();
            }
 
            OldHead->NextNode = NewNode;
        }
 
        return true;
    }
 
    [[nodiscard]] bool IsEmpty() const
    {
        return (Tail->NextNode == nullptr);
    }
 
    bool Peek(FElementType& OutItem) const
    {
        if (Tail->NextNode == nullptr)
        {
            return false;
        }
 
        OutItem = Tail->NextNode->Item;
 
        return true;
    }
 
    [[nodiscard]] FElementType* Peek()
    {
        if (Tail->NextNode == nullptr)
        {
            return nullptr;
        }
 
        return &Tail->NextNode->Item;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT const FElementType* Peek() const
    {
        return const_cast<TQueue*>(this)->Peek();
    }
 
    bool Pop()
    {
        TNode* Popped = Tail->NextNode;
 
        if (Popped == nullptr)
        {
            return false;
        }
 
        if constexpr (Mode != EQueueMode::SingleThreaded)
        {
            TSAN_AFTER(&Tail->NextNode);
        }
 
        TNode* OldTail = Tail;
        Tail = Popped;
        Tail->Item = FElementType();
        delete OldTail;
 
        return true;
    }
 
private:
 
    struct TNode;
    using TNodeVolatilePtr = std::conditional_t<Mode == EQueueMode::SingleThreaded, TNode*, TNode* volatile>;
 
    struct TNode
    {
        TNodeVolatilePtr NextNode = nullptr;
 
        FElementType Item;
 
        [[nodiscard]] TNode() = default;
 
        [[nodiscard]] explicit TNode(const FElementType& InItem)
            : Item(InItem)
        {
        }
 
        [[nodiscard]] explicit TNode(FElementType&& InItem)
            : Item(MoveTemp(InItem))
        {
        }
    };
 
    MS_ALIGN(16) TNodeVolatilePtr Head GCC_ALIGN(16);
 
    TNode* Tail;
};