ResizableCircularQueue.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "Misc/AssertionMacros.h"
#include "Containers/Array.h"
#include "Templates/IsPODType.h"
#include "Templates/MemoryOps.h"
#include <type_traits>
 
template<typename T, typename AllocatorT = FDefaultAllocator>
class TResizableCircularQueue
{
public:
    typedef T ElementT;
 
    explicit TResizableCircularQueue(SIZE_T InitialCapacity);
    inline TResizableCircularQueue() : TResizableCircularQueue(0U) {}
    ~TResizableCircularQueue();
 
    bool IsEmpty() const { return Head == Tail; }
 
    SIZE_T Count() const { return Head - Tail; }
 
    SIZE_T AllocatedCapacity() const { return Storage.Num(); }
 
    void Enqueue(const ElementT& SrcData);
 
    ElementT& EnqueueDefaulted_GetRef();
 
    ElementT& Enqueue_GetRef();
 
    ElementT& Enqueue();
 
    void Pop();
 
    void Pop(SIZE_T Count);
 
    void PopNoCheck();
 
    void PopNoCheck(SIZE_T Count);
 
    const ElementT& PeekAtOffset(SIZE_T Offset = 0) const { check(Offset < Count()); return PeekAtOffsetNoCheck(Offset); }
 
    ElementT& PokeAtOffset(SIZE_T Offset = 0) { check(Offset < Count()); return PokeAtOffsetNoCheck(Offset); }
 
    const ElementT& Peek() const { return PeekAtOffset(0); }
 
    ElementT& Poke() { return PokeAtOffset(0); }
 
    const ElementT& PeekAtOffsetNoCheck(SIZE_T Offset = 0) const { return Storage.GetData()[(Tail + Offset) & IndexMask]; }
 
    ElementT& PokeAtOffsetNoCheck(SIZE_T Offset = 0) { return Storage.GetData()[(Tail + Offset) & IndexMask]; }
 
    const ElementT& PeekNoCheck() const { return PeekAtOffsetNoCheck(0); }
 
    void Trim();
 
    void Reset();
 
    void Empty();
    
private:
    enum : uint32
    {
        bConstructElements = (TIsPODType<T>::Value ? 0U : 1U),
        bDestructElements = (std::is_trivially_destructible_v<T> ? 0U : 1U),
    };
 
#if WITH_DEV_AUTOMATION_TESTS
    friend struct FResizableCircularQueueTestUtil;
#endif
 
    // Resize buffer maintaining validity of stored data.
    void SetCapacity(SIZE_T NewCapacity);
 
    typedef uint32 IndexT;
    typedef TArray<ElementT, AllocatorT> StorageT;
 
    IndexT Head;
    IndexT Tail;
 
    IndexT IndexMask;
    StorageT Storage;
};
 
 
template<typename T, typename AllocatorT>
TResizableCircularQueue<T, AllocatorT>::TResizableCircularQueue(SIZE_T InitialCapacity)
: Head(0u)
, Tail(0u)
, IndexMask(0u)
{
    // Capacity should be power of two, it will be rounded up but lets warn the user anyway in debug builds.
    checkSlow((InitialCapacity & (InitialCapacity - 1)) == 0);
    if (InitialCapacity > 0)
    {
        SetCapacity(InitialCapacity);
    }
}
 
template<typename T, typename AllocatorT>
TResizableCircularQueue<T, AllocatorT>::~TResizableCircularQueue()
{
    PopNoCheck(Count());
    Storage.SetNumUnsafeInternal(0);
}
 
template<typename T, typename AllocatorT>
void TResizableCircularQueue<T, AllocatorT>::Enqueue(const ElementT& SrcData)
{ 
    const SIZE_T RequiredCapacity = Count() + 1;
    if (RequiredCapacity > AllocatedCapacity())
    {
        // Capacity must be power of two
        SetCapacity(RequiredCapacity);
    }
 
    const IndexT MaskedIndex = Head++ & IndexMask;
    T* DstData = Storage.GetData() + MaskedIndex;
    new (DstData) T(SrcData);
}
 
template<typename T, typename AllocatorT>
typename TResizableCircularQueue<T, AllocatorT>::ElementT& TResizableCircularQueue<T, AllocatorT>::EnqueueDefaulted_GetRef()
{
    const SIZE_T RequiredCapacity = Count() + 1;
    if (RequiredCapacity > AllocatedCapacity())
    {
        // Capacity must be power of two
        SetCapacity(RequiredCapacity);
    }
 
    const IndexT MaskedIndex = Head++ & IndexMask;
    T* DstData = Storage.GetData() + MaskedIndex;
    new (DstData) T();
 
    return *DstData;
}
 
template<typename T, typename AllocatorT>
typename TResizableCircularQueue<T, AllocatorT>::ElementT& TResizableCircularQueue<T, AllocatorT>::Enqueue_GetRef()
{
    const SIZE_T RequiredCapacity = Count() + 1;
    if (RequiredCapacity > AllocatedCapacity())
    {
        // Capacity must be power of two
        SetCapacity(RequiredCapacity);
    }
 
    const IndexT MaskedIndex = Head++ & IndexMask;
    T* DstData = Storage.GetData() + MaskedIndex;
    if (bConstructElements)
    {
        new (DstData) T();
    }
 
    return *DstData;
}
 
template<typename T, typename AllocatorT>
typename TResizableCircularQueue<T, AllocatorT>::ElementT& TResizableCircularQueue<T, AllocatorT>::Enqueue()
{
    return Enqueue_GetRef();
}
 
template<typename T, typename AllocatorT>
void
TResizableCircularQueue<T, AllocatorT>::Pop(SIZE_T PopCount)
{
    if (ensure(Count() >= PopCount))
    {
        PopNoCheck(PopCount);
    }
}
 
template<typename T, typename AllocatorT>
void TResizableCircularQueue<T, AllocatorT>::Pop()
{
    if (ensure(Count() > 0))
    {
        PopNoCheck();
    }
}
 
template<typename T, typename AllocatorT>
void TResizableCircularQueue<T, AllocatorT>::PopNoCheck()
{ 
    if (bDestructElements)
    {
        const IndexT MaskedIndex = Tail & IndexMask;
        T* Data = Storage.GetData() + MaskedIndex;
        DestructItem(Data);
    }
 
    ++Tail;
}
 
template<typename T, typename AllocatorT>
void TResizableCircularQueue<T, AllocatorT>::PopNoCheck(SIZE_T Count)
{
    if (bDestructElements)
    {
        const IndexT MaskedTailStart = Tail & IndexMask;
        const IndexT MaskedTailEnd = (Tail + Count) & IndexMask;
 
        if ((Count > 0) & (MaskedTailStart >= MaskedTailEnd))
        {
            T* Data = Storage.GetData();
            const SIZE_T FirstDestructCount = (Storage.Num() - MaskedTailStart);
            DestructItems(Data + MaskedTailStart, FirstDestructCount);
            DestructItems(Data, MaskedTailEnd);
        }
        else
        {
            T* Data = Storage.GetData() + MaskedTailStart;
            DestructItems(Data, Count);
        }
    }
 
    check(SIZE_T(Tail) + Count <= TNumericLimits<IndexT>::Max());
    Tail += (IndexT)Count;
}
 
template<typename T, typename AllocatorT>
void TResizableCircularQueue<T, AllocatorT>::SetCapacity(SIZE_T RequiredCapacity)
{
    using SizeType = typename StorageT::SizeType; 
 
    SIZE_T NewCapacity = FMath::RoundUpToPowerOfTwo64(RequiredCapacity);
 
    if ((NewCapacity == Storage.Num()) || (NewCapacity < Count()))
    {
        return;
    }
 
    if (Storage.Num() > 0)
    {
        StorageT NewStorage;
        NewStorage.Empty(static_cast<SizeType>(NewCapacity));
        
        // copy data to new storage
        const IndexT MaskedTail = Tail & IndexMask;
        const IndexT MaskedHead = Head & IndexMask;
 
        const ElementT* SrcData = Storage.GetData();
        const SIZE_T SrcCapacity = Storage.Num();
        const SIZE_T SrcSize = Count();
        ElementT* DstData = NewStorage.GetData();
 
        // MaskedTail will be equal to MaskedHead both when the queue is full and when it is empty.
        if ((SrcSize > 0) & (MaskedTail >= MaskedHead))
        {
            const SIZE_T CopyCount = (SrcCapacity - MaskedTail);
            NewStorage.Append(SrcData + MaskedTail, static_cast<SizeType>(CopyCount));
            NewStorage.Append(SrcData, MaskedHead);
        }
        else
        {
            NewStorage.Append(SrcData + MaskedTail, static_cast<SizeType>(SrcSize));
        }
 
        NewStorage.AddUninitialized(static_cast<SizeType>(NewCapacity - SrcSize));
 
        this->Storage = MoveTemp(NewStorage);
        IndexMask = static_cast<IndexT>(NewCapacity - 1);
        Tail = 0u;
        Head = static_cast<IndexT>(SrcSize);
    }
    else
    {
        IndexMask = static_cast<IndexT>(NewCapacity - 1);
        Storage.AddUninitialized(static_cast<SizeType>(NewCapacity));
    }
}
 
template<typename T, typename AllocatorT>
void TResizableCircularQueue<T, AllocatorT>::Trim()
{
    if (IsEmpty())
    {
        Empty();
    }
    else
    {
        SetCapacity(Count());
    }
}
 
template<typename T, typename AllocatorT>
void TResizableCircularQueue<T, AllocatorT>::Reset()
{
    PopNoCheck(Count());
    Head = 0;
    Tail = 0;
}
 
template<typename T, typename AllocatorT>
void TResizableCircularQueue<T, AllocatorT>::Empty()
{
    PopNoCheck(Count());
    Head = 0;
    Tail = 0;
    IndexMask = IndexT(-1);
 
    // We've already destructed items. We just want to free the memory.
    Storage.SetNumUnsafeInternal(0);
    Storage.Empty();
}
 
#if UE_ENABLE_INCLUDE_ORDER_DEPRECATED_IN_5_5
#include "Templates/IsTriviallyDestructible.h"
#endif