RingBuffer.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/ArrayView.h"
#include "Templates/IsPODType.h"
#include "Templates/MemoryOps.h"
#include "Templates/UnrealTemplate.h"
 
#include <type_traits>
 
template< typename ContainerType, typename ElementType, typename SizeType>
class TRingBufferIterator
{
public:
    [[nodiscard]] TRingBufferIterator(ContainerType& InContainer, SizeType StartIndex = 0)
        : Container(InContainer)
        , Index(StartIndex)
    {
    }
 
    TRingBufferIterator& operator++()
    {
        ++Index;
        return *this;
    }
    TRingBufferIterator operator++(int)
    {
        TRingBufferIterator Tmp(*this);
        ++Index;
        return Tmp;
    }
 
    TRingBufferIterator& operator--()
    {
        --Index;
        return *this;
    }
    TRingBufferIterator operator--(int)
    {
        TRingBufferIterator Tmp(*this);
        --Index;
        return Tmp;
    }
 
    TRingBufferIterator& operator+=(SizeType Offset)
    {
        Index += Offset;
        return *this;
    }
 
    TRingBufferIterator operator+(SizeType Offset) const
    {
        TRingBufferIterator Tmp(*this);
        return Tmp += Offset;
    }
 
    TRingBufferIterator& operator-=(SizeType Offset)
    {
        return *this += -Offset;
    }
 
    TRingBufferIterator operator-(SizeType Offset) const
    {
        TRingBufferIterator Tmp(*this);
        return Tmp -= Offset;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ElementType& operator*() const
    {
        return Container[Index];
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ElementType* operator->() const
    {
        return &Container[Index];
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT explicit operator bool() const
    {
        return Container.IsValidIndex(Index);
    }
 
    [[nodiscard]] SizeType GetIndex() const
    {
        return Index;
    }
 
    void Reset()
    {
        Index = 0;
    }
 
    void SetToEnd()
    {
        Index = Container.Num();
    }
 
    void RemoveCurrent()
    {
        Container.RemoveAt(Index);
        --Index;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT bool operator==(const TRingBufferIterator& Rhs) const { return &Container == &Rhs.Container && Index == Rhs.Index; }
    [[nodiscard]] UE_FORCEINLINE_HINT bool operator!=(const TRingBufferIterator& Rhs) const { return &Container != &Rhs.Container || Index != Rhs.Index; }
 
private:
 
    ContainerType& Container;
    SizeType      Index;
};
 
template<typename T, typename AllocatorT = FDefaultAllocator>
class TRingBuffer
{
public:
    typedef T ElementType;
    /* The Allocator type being used */
    typedef AllocatorT Allocator;
    using ElementAllocatorType = std::conditional_t<
        Allocator::NeedsElementType,
        typename Allocator::template ForElementType<ElementType>,
        typename Allocator::ForAnyElementType
    >;
    typedef std::make_signed_t<typename Allocator::SizeType> IndexType;
    typedef std::make_unsigned_t<typename Allocator::SizeType> SizeType;
    typedef TRingBufferIterator<TRingBuffer, ElementType, typename Allocator::SizeType> TIterator;
    typedef TRingBufferIterator<const TRingBuffer, const ElementType, typename Allocator::SizeType> TConstIterator;
private:
    typedef std::make_unsigned_t<typename Allocator::SizeType> StorageModuloType;
public:
 
    [[nodiscard]] TRingBuffer()
        : IndexMask(static_cast<StorageModuloType>(-1))
        , Front(0u)
        , AfterBack(0u)
    {
    }
 
    [[nodiscard]] explicit TRingBuffer(SizeType InitialCapacity)
        : TRingBuffer()
    {
        Reserve(InitialCapacity);
    }
 
    [[nodiscard]] TRingBuffer(std::initializer_list<ElementType> InitList)
        : TRingBuffer(static_cast<SizeType>(InitList.size()))
    {
        for (const ElementType& Element : InitList)
        {
            Add(Element);
        }
    }
 
    [[nodiscard]] TRingBuffer(TRingBuffer&& Other)
        : TRingBuffer()
    {
        *this = MoveTemp(Other);
    }
 
    TRingBuffer& operator=(TRingBuffer&& Other)
    {
        if (this == &Other)
        {
            return *this;
        }
        Empty();
        AllocatorInstance.MoveToEmpty(Other.AllocatorInstance);
        Swap(IndexMask, Other.IndexMask);
        Swap(Front, Other.Front);
        Swap(AfterBack, Other.AfterBack);
        return *this;
    }
 
    [[nodiscard]] TRingBuffer(const TRingBuffer& Other)
        :TRingBuffer()
    {
        *this = Other;
    }
 
    TRingBuffer& operator=(const TRingBuffer& Other)
    {
        Empty(Other.Max());
        for (const ElementType& Element : Other)
        {
            Add(Element);
        }
        return *this;
    }
 
    ~TRingBuffer()
    {
        Empty();
    }
 
    [[nodiscard]] bool IsEmpty() const
    {
        return AfterBack == Front;
    }
 
    [[nodiscard]] IndexType Num() const
    {
        return AfterBack - Front;
    }
 
    [[nodiscard]] IndexType Max() const
    {
        return static_cast<SizeType>(IndexMask + 1);
    }
 
    void Reserve(SizeType RequiredCapacity)
    {
        SizeType NewCapacity = NormalizeCapacity(RequiredCapacity);
        if (NewCapacity <= static_cast<SizeType>(Max()))
        {
            return;
        }
        Reallocate(NewCapacity);
    }
 
    void Trim()
    {
        SizeType NewCapacity = NormalizeCapacity(Num());
        Reallocate(NewCapacity);
    }
 
    void Reset()
    {
        PopFrontNoCheck(Num());
        AfterBack = 0;
        Front = 0;
    }
 
    void Empty(SizeType Capacity = 0)
    {
        Reset();
        SizeType NewCapacity = NormalizeCapacity(Capacity);
        Reallocate(NewCapacity);
    }
 
    IndexType Add(ElementType&& Element)
    {
        IndexType ResultIndex = AddUninitialized();
        ElementType& Result = GetAtIndexNoCheck(ResultIndex);
        ::new ((void*)&Result) ElementType(MoveTempIfPossible(Element));
        return ResultIndex;
    }
 
    [[nodiscard]] ElementType& Add_GetRef(ElementType&& Element)
    {
        ElementType& Result = AddUninitialized_GetRef();
        ::new ((void*)&Result) ElementType(MoveTempIfPossible(Element));
        return Result;
    }
 
    IndexType Add(const ElementType& Element)
    {
        IndexType ResultIndex = AddUninitialized();
        ElementType& Result = GetAtIndexNoCheck(ResultIndex);
        ::new ((void*)&Result) ElementType(Element);
        return ResultIndex;
    }
 
    [[nodiscard]] ElementType& Add_GetRef(const ElementType& Element)
    {
        IndexType ResultIndex = AddUninitialized();
        ElementType& Result = GetAtIndexNoCheck(ResultIndex);
        ::new ((void*)&Result) ElementType(Element);
        return Result;
    }
 
    template <typename... ArgsType>
    IndexType Emplace(ArgsType&&... Args)
    {
        IndexType ResultIndex = AddUninitialized();
        ElementType& Result = GetAtIndexNoCheck(ResultIndex);
        ::new ((void*)&Result) ElementType(Forward<ArgsType>(Args)...);
        return ResultIndex;
    }
 
    template <typename... ArgsType>
    [[nodiscard]] ElementType& Emplace_GetRef(ArgsType&&... Args)
    {
        ElementType& Result = AddUninitialized_GetRef();
        ::new ((void*)&Result) ElementType(Forward<ArgsType>(Args)...);
        return Result;
    }
 
    IndexType AddUninitialized()
    {
        ConditionalIncrementCapacity();
        // Note this increment may overflow and set AfterBack = 0.  This overflow is legal;
        // the constraint ((AfterBack - Front) == Num()) will still be true despite Front and AfterBack being
        // on opposite sides of 0.
        IndexType Result = static_cast<IndexType>(AfterBack++ - Front); 
        SlackTrackerNumChanged();
        return Result;
    }
 
    [[nodiscard]] ElementType& AddUninitialized_GetRef()
    {
        return GetAtIndexNoCheck(AddUninitialized());
    }
 
    void MoveAppendRange(ElementType* OtherData, SizeType OtherNum)
    {
        if (OtherNum == 0)
        {
            return;
        }
        check(OtherData);
        const SizeType OldNum = static_cast<SizeType>(Num());
        const SizeType NewNum = OldNum + OtherNum;
        checkf(NewNum > OldNum, TEXT("Overflow: Num() == %d, OtherNum == %d, NewNum == %d"), OldNum, OtherNum, NewNum);
        Reserve(NewNum);
        const SizeType LocalIndexMask = IndexMask;
 
        const SizeType MoveRangeStart = AfterBack;
        const SizeType MoveRangeEnd = AfterBack + OtherNum;
        const StorageModuloType MaskedMoveRangeStart = MoveRangeStart & LocalIndexMask;
        const StorageModuloType MaskedMoveRangeEnd = MoveRangeEnd & LocalIndexMask;
        ElementType* const Data = GetStorage();
        if (MaskedMoveRangeStart >= MaskedMoveRangeEnd)
        {
            // We should not be reaching capacity and overwriting front
            check(MaskedMoveRangeEnd <= (Front & LocalIndexMask) && (Front & LocalIndexMask) <= MaskedMoveRangeStart);
            const SizeType FirstMoveCount = (LocalIndexMask + 1 - MaskedMoveRangeStart);
            MoveConstructItems(Data + MaskedMoveRangeStart, OtherData, FirstMoveCount);
            MoveConstructItems(Data, OtherData + FirstMoveCount, MaskedMoveRangeEnd);
        }
        else
        {
            // We should not be reaching capacity and overwriting front
            check((Front & LocalIndexMask) <= MaskedMoveRangeStart || MaskedMoveRangeEnd <= (Front & LocalIndexMask));
            MoveConstructItems(Data + MaskedMoveRangeStart, OtherData, OtherNum);
        }
        AfterBack += OtherNum;
        SlackTrackerNumChanged();
    }
 
    IndexType AddFront(ElementType&& Element)
    {
        IndexType ResultIndex = AddFrontUninitialized();
        ElementType& Result = GetAtIndexNoCheck(ResultIndex);
        ::new ((void*)&Result) ElementType(MoveTempIfPossible(Element));
        return ResultIndex;
    }
 
    [[nodiscard]] ElementType& AddFront_GetRef(ElementType&& Element)
    {
        ElementType& Result = AddFrontUninitialized_GetRef();
        ::new ((void*)&Result) ElementType(MoveTempIfPossible(Element));
        return Result;
    }
 
    IndexType AddFront(const ElementType& Element)
    {
        IndexType ResultIndex = AddFrontUninitialized();
        ElementType& Result = GetAtIndexNoCheck(ResultIndex);
        ::new ((void*)&Result) ElementType(Element);
        return ResultIndex;
    }
 
    [[nodiscard]] ElementType& AddFront_GetRef(const ElementType& Element)
    {
        IndexType ResultIndex = AddFrontUninitialized();
        ElementType& Result = GetAtIndexNoCheck(ResultIndex);
        ::new ((void*)&Result) ElementType(Element);
        return Result;
    }
 
    template <typename... ArgsType>
    IndexType EmplaceFront(ArgsType&&... Args)
    {
        IndexType ResultIndex = AddFrontUninitialized();
        ElementType& Result = GetAtIndexNoCheck(ResultIndex);
        ::new ((void*)&Result) ElementType(Forward<ArgsType>(Args)...);
        return ResultIndex;
    }
 
    template <typename... ArgsType>
    [[nodiscard]] ElementType& EmplaceFront_GetRef(ArgsType&&... Args)
    {
        ElementType& Result = AddFrontUninitialized_GetRef();
        ::new ((void*)&Result) ElementType(Forward<ArgsType>(Args)...);
        return Result;
    }
 
    IndexType AddFrontUninitialized()
    {
        ConditionalIncrementCapacity();
        // Note this decrement may underflow and set Front = 0xffffffff.  This underflow is legal;
        // the constraint ((AfterBack - Front) == Num()) will still be true despite Front and AfterBack being on
        // opposite sides of 0.
        --Front;
        SlackTrackerNumChanged();
        return 0;
    }
 
    [[nodiscard]] ElementType& AddFrontUninitialized_GetRef()
    {
        return GetAtIndexNoCheck(AddFrontUninitialized());
    }
 
    [[nodiscard]] ElementType& First()
    {
        return (*this)[0];
    }
 
    [[nodiscard]] const ElementType& First() const
    {
        return (*this)[0];
    }
 
    [[nodiscard]] ElementType& Last()
    {
        return (*this)[Num() - 1];
    }
 
    [[nodiscard]] const ElementType& Last() const
    {
        return (*this)[Num() - 1];
    }
 
    void PopFront(SizeType PopCount=1)
    {
        PopRangeCheck(PopCount);
        PopFrontNoCheck(PopCount);
    }
 
    void PopFrontNoCheck(SizeType PopCount=1)
    {
        DestructRange(Front, Front + PopCount);
        // Note this increment may overflow (wrapping around to 0xffffffff) if AfterBack has already underflowed; this is valid.
        Front += PopCount;
        SlackTrackerNumChanged();
    }
 
    /* Pop one element from the front pointer of the RingBuffer and return the popped value. Invalid to call when the RingBuffer is empty. */
    ElementType PopFrontValue()
    {
        PopRangeCheck(1);
        ElementType Result(MoveTemp(First()));
        PopFrontNoCheck(1);
        return Result;
    }
 
    void Pop(SizeType PopCount=1)
    {
        PopRangeCheck(PopCount);
        PopNoCheck(PopCount);
    }
 
    void PopNoCheck(SizeType PopCount=1)
    {
        DestructRange(AfterBack - PopCount, AfterBack);
        // Note this decrement may underflow (wrapping around to 0xffffffff) if Front has already underflowed; this is valid.
        AfterBack -= PopCount;
        SlackTrackerNumChanged();
    }
 
    /* Pop one element from the back pointer of the RingBuffer and return the popped value. Invalid to call when the RingBuffer is empty. */
    ElementType PopValue()
    {
        PopRangeCheck(1);
        ElementType Result(MoveTemp(Last()));
        PopNoCheck(1);
        return Result;
    }
 
    void ShiftIndexToFront(IndexType Index)
    {
        RangeCheck(Index);
        if (Index == 0)
        {
            return;
        }
 
        ShiftLastToFirst(Front, Front + Index, -1);
    }
 
    void ShiftIndexToBack(IndexType Index)
    {
        IndexType LocalNum = Num();
        RangeCheck(Index);
        if (Index == LocalNum - 1)
        {
            return;
        }
 
        ShiftLastToFirst(AfterBack - 1, Front + Index, 1); // Note 0 <= AfterBack - 1 - (Front + Index) is <= (Num()-1) because AfterBack - Front - 1 == Num()-1 and 0 <= Index <= Num()-1
    }
 
    [[nodiscard]] TIterator begin()
    {
        return TIterator(*this);
    }
 
    [[nodiscard]] TConstIterator begin() const
    {
        return TConstIterator(*this);
    }
 
    [[nodiscard]] TIterator end()
    {
        return TIterator(*this, Num());
    }
 
    [[nodiscard]] TConstIterator end() const
    {
        return TConstIterator(*this, Num());
    }
 
    [[nodiscard]] bool IsValidIndex(IndexType Index) const
    {
        return Index >= 0 && Index < Num();
    }
 
    [[nodiscard]] ElementType& operator[](IndexType Index)
    {
        RangeCheck(Index);
        return GetAtIndexNoCheck(Index);
    }
 
    [[nodiscard]] const ElementType& operator[](IndexType Index) const
    {
        RangeCheck(Index);
        return GetAtIndexNoCheck(Index);
    }
 
    [[nodiscard]] ElementType& GetAtIndexNoCheck(IndexType Index)
    {
        return GetStorage()[(Front + Index) & IndexMask];
    }
 
    [[nodiscard]] const ElementType& GetAtIndexNoCheck(IndexType Index) const
    {
        return GetStorage()[(Front + Index) & IndexMask];
    }
 
    [[nodiscard]] IndexType ConvertPointerToIndex(const ElementType* Ptr) const
    {
        const ElementType* const Data = GetStorage();
        const ElementType* const DataEnd = Data + Max();
        const ElementType* const FrontPtr = Data + (Front & IndexMask);
        IndexType Index;
        if (Ptr >= FrontPtr)
        {
            if (Ptr >= DataEnd)
            {
                return INDEX_NONE;
            }
            Index = static_cast<IndexType>(Ptr - FrontPtr);
        }
        else
        {
            if (Ptr < Data)
            {
                return INDEX_NONE;
            }
            Index = static_cast<IndexType>(Ptr - Data) + static_cast<IndexType>(DataEnd - FrontPtr);
        }
        if (Index >= Num())
        {
            return INDEX_NONE;
        }
        return Index;
    }
 
    void RemoveAt(IndexType Index)
    {
        RangeCheck(Index);
        const IndexType Capacity = Max();
        const StorageModuloType MaskedFront = Front & IndexMask;
        const StorageModuloType MaskedIndex = (Front + Index) & IndexMask;
        const StorageModuloType MaskedAfterBack = AfterBack & IndexMask;
        StorageModuloType OrderedIndex = MaskedIndex >= MaskedFront ? MaskedIndex : MaskedIndex + Capacity;
        StorageModuloType OrderedAfterBack = MaskedAfterBack >= OrderedIndex ? MaskedAfterBack : MaskedAfterBack + Capacity;
        if (OrderedIndex - MaskedFront <= OrderedAfterBack - OrderedIndex)
        {
            ShiftIndexToFront(Index);
            PopFront();
        }
        else
        {
            ShiftIndexToBack(Index);
            Pop();
        }
    }
 
    SizeType Remove(const ElementType& Item)
    {
        return RemoveAll([&Item](const ElementType& ExistingItem) { return ExistingItem == Item; });
    }
 
    template <typename PredicateType>
    SizeType RemoveAll(PredicateType Predicate)
    {
        if (AfterBack == Front)
        {
            return 0;
        }
 
        StorageModuloType FirstRemoval;
        ElementType* Data = GetStorage();
        for (FirstRemoval = Front; FirstRemoval != AfterBack; ++FirstRemoval)
        {
            if (Predicate(Data[FirstRemoval & IndexMask]))
            {
                break;
            }
        }
        if (FirstRemoval == AfterBack)
        {
            return 0;
        }
 
        StorageModuloType WriteIndex = FirstRemoval;
        StorageModuloType ReadIndex = FirstRemoval + 1;
        while (ReadIndex != AfterBack)
        {
            if (!Predicate(Data[ReadIndex & IndexMask]))
            {
                if (NeedsDestructElements())
                {
                    DestructItem(&Data[WriteIndex & IndexMask]);
                }
                ::new ((void*)&Data[WriteIndex & IndexMask]) ElementType(MoveTemp(Data[ReadIndex & IndexMask]));
                ++WriteIndex;
            }
            ++ReadIndex;
        }
        AfterBack = WriteIndex;
 
        SizeType NumDeleted = static_cast<SizeType>(ReadIndex - WriteIndex);
        if (NeedsDestructElements())
        {
            while (WriteIndex != ReadIndex)
            {
                DestructItem(&Data[WriteIndex & IndexMask]);
                ++WriteIndex;
            }
        }
        SlackTrackerNumChanged();
        return NumDeleted;
    }
 
    template <typename OtherAllocator>
    [[nodiscard]] bool operator==(const TRingBuffer<ElementType, OtherAllocator>& Other) const
    {
        const IndexType LocalNum = Num();
        if (Other.Num() != LocalNum)
        {
            return false;
        }
        for (IndexType Index = 0; Index < LocalNum; ++Index)
        {
            if (!(GetAtIndexNoCheck(Index) == Other.GetAtIndexNoCheck(Index)))
            {
                return false;
            }
        }
        return true;
    }
 
    template <typename OtherAllocator>
    [[nodiscard]] bool operator!=(const TRingBuffer<ElementType, OtherAllocator>& Other) const
    {
        return !(*this == Other);
    }
 
    TArrayView<T> Compact()
    {
        StorageModuloType MaskedFront = Front & IndexMask;
        const StorageModuloType MaskedAfterBack = AfterBack & IndexMask;
        if ((MaskedFront > MaskedAfterBack) | // Non-empty, non-full RingBuffer, and back pointer wraps around to be before front
            ((MaskedFront == MaskedAfterBack) & (AfterBack != Front) & (MaskedFront != 0))) // Full, non-empty RingBuffer, and front is not at the beginning of the storage
        {
            Reallocate(Max());
            MaskedFront = Front & IndexMask;
        }
        return TArrayView<T>(GetStorage() + MaskedFront, Num());
    }
 
    [[nodiscard]] SIZE_T GetAllocatedSize(void) const
    {
        return Max() * sizeof(ElementType);
    }
 
private:
    [[nodiscard]] static constexpr bool NeedsDestructElements()
    {
        return !std::is_trivially_destructible_v<T>;
    }
 
    void Reallocate(SizeType NewCapacity)
    {
        ElementType* SrcData = GetStorage();
        const SizeType SrcCapacity = static_cast<SizeType>(Max());
        const SizeType SrcNum = static_cast<SizeType>(Num());
 
        check(NormalizeCapacity(NewCapacity) == NewCapacity);
        check(NewCapacity >= SrcNum);
 
        StorageModuloType NewIndexMask;
        if (NewCapacity > 0 && SrcNum > 0)
        {
            // Allocate SwapStorage
            ElementAllocatorType SwapStorageBuffer;
            AllocatorResizeAllocation(SwapStorageBuffer, 0, NewCapacity);
            ElementType* SwapStorage = (ElementType*)SwapStorageBuffer.GetAllocation();
 
            // Move data to swap storage
            const StorageModuloType MaskedFront = Front & IndexMask;
            const StorageModuloType MaskedAfterBack = AfterBack & IndexMask;
 
            // MaskedFront equal to MaskedAfterBack will occur if the queue's Num equals Capacity or if the Num == 0.  We checked Num == 0 above, so here it means Num == Capacity.
            if (MaskedFront >= MaskedAfterBack)
            {
                StorageModuloType WriteIndex = 0;
                for (StorageModuloType ReadIndex = MaskedFront; ReadIndex < SrcCapacity; ++ReadIndex)
                {
                    ::new ((void*)&SwapStorage[WriteIndex++]) ElementType(MoveTemp(SrcData[ReadIndex]));
                }
                DestructRange(MaskedFront, SrcCapacity);
                for (StorageModuloType ReadIndex = 0; ReadIndex < MaskedAfterBack; ++ReadIndex)
                {
                    ::new ((void*)&SwapStorage[WriteIndex++]) ElementType(MoveTemp(SrcData[ReadIndex]));
                }
                DestructRange(0, MaskedAfterBack);
            }
            else
            {
                StorageModuloType WriteIndex = 0;
                for (StorageModuloType ReadIndex = MaskedFront; ReadIndex < MaskedAfterBack; ++ReadIndex)
                {
                    ::new((void*)&SwapStorage[WriteIndex++]) ElementType(MoveTemp(SrcData[ReadIndex]));
                }
                DestructRange(MaskedFront, MaskedAfterBack);
            }
            // Move the swap storage into this->AllocatorInstance. "Empty" in MoveToEmpty means the elements have been
            // destructed, but the array memory might still be allocated; MoveToEmpty reallocates or frees it.
            AllocatorInstance.MoveToEmpty(SwapStorageBuffer);
            NewIndexMask = NewCapacity - 1;
        }
        else
        {
            AllocatorResizeAllocation(AllocatorInstance, 0, NewCapacity);
            NewIndexMask = static_cast<StorageModuloType>(NewCapacity - 1);
        }
 
        IndexMask = NewIndexMask;
        Front = 0u;
        AfterBack = SrcNum;
    }
 
    void AllocatorResizeAllocation(ElementAllocatorType& InAllocatorInstance, SizeType CurrentNum, SizeType NewArrayMax)
    {
        if constexpr (TAllocatorTraits<Allocator>::SupportsElementAlignment)
        {
            InAllocatorInstance.ResizeAllocation(CurrentNum, NewArrayMax, sizeof(ElementType), alignof(ElementType));
        }
        else
        {
            InAllocatorInstance.ResizeAllocation(CurrentNum, NewArrayMax, sizeof(ElementType));
        }
    }
 
    void SlackTrackerNumChanged()
    {
#if UE_ENABLE_ARRAY_SLACK_TRACKING
        if constexpr (TAllocatorTraits<Allocator>::SupportsSlackTracking)
        {
            AllocatorInstance.SlackTrackerLogNum(Num());
        }
#endif
    }
 
    void DestructRange(StorageModuloType RangeStart, StorageModuloType RangeEnd)
    {
        const IndexType Capacity = Max();
        if (RangeEnd - RangeStart > static_cast<StorageModuloType>(Capacity))
        {
            check(false);
            return;
        }
        const StorageModuloType DestructCount = RangeEnd - RangeStart;
        if (NeedsDestructElements() && DestructCount > 0)
        {
            ElementType* Data = GetStorage();
            const StorageModuloType MaskedRangeStart = RangeStart & IndexMask;
            const StorageModuloType MaskedRangeEnd = RangeEnd & IndexMask;
            if (MaskedRangeStart >= MaskedRangeEnd)
            {
                const SizeType FirstDestructCount = (Capacity - MaskedRangeStart);
                DestructItems(Data + MaskedRangeStart, FirstDestructCount);
                DestructItems(Data, MaskedRangeEnd);
            }
            else
            {
                DestructItems(Data + MaskedRangeStart, DestructCount);
            }
        }
    }
 
    SizeType NormalizeCapacity(SizeType InCapacity)
    {
        // 0 -> 0
        // All other positive integers -> RoundUpPowerOf2
 
        SizeType ResultCapacity = (InCapacity != 0)*FMath::RoundUpToPowerOfTwo(InCapacity);
        // Make sure we won't overflow
        // The largest value computed for a StorageModuloType is Capacity - 1 + Capacity, so we need 2*Capacity - 1 < TNumericLimits::Max, which we simplify to 2*Capacity < TNumericLimits::Max
        // We may also have overflowed InCapacity when we rounded it up, so check that InCapacity is less than ResultCapacity
        checkf(((static_cast<StorageModuloType>(ResultCapacity) <= (TNumericLimits<StorageModuloType>::Max() >> 1)) & (InCapacity <= ResultCapacity)),  TEXT("Integer overflow in TRingBuffer capacity"));
        return ResultCapacity;
    }
 
    void ConditionalIncrementCapacity()
    {
        Reserve(Num() + 1);
    }
 
    void ShiftLastToFirst(StorageModuloType RangeFirst, StorageModuloType RangeLast, int RangeDirection)
    {
        // This check for Range constraint is made complicated by needing to handle overflow; only subtractions of x - y can be verified, we can't use x > y because they might be on opposite sides of unsigned 0.
        // We also want to avoid doing a branch.  TODO: Is there a FMath::Select function that does this branch-less style select?
        check((RangeLast - RangeFirst) * (RangeDirection == 1) + (RangeFirst - RangeLast) * (RangeDirection != -1) <= static_cast<StorageModuloType>(Max()));
 
        ElementType* Data = GetStorage();
        ElementType Copy(MoveTemp(Data[RangeLast & IndexMask]));
        if (NeedsDestructElements())
        {
            for (StorageModuloType Index = RangeLast; Index != RangeFirst; Index += RangeDirection)
            {
                StorageModuloType OldValueIndex = Index & IndexMask;
                StorageModuloType NewValueIndex = (Index + RangeDirection) & IndexMask;
                DestructItems(Data + OldValueIndex, 1);
                ::new ((void*)(Data + OldValueIndex)) ElementType(MoveTemp(Data[NewValueIndex]));
            }
            StorageModuloType OldValueIndex = RangeFirst & IndexMask;
            DestructItems(Data + OldValueIndex, 1);
            ::new ((void*)(Data + OldValueIndex)) ElementType(MoveTemp(Copy));
        }
        else
        {
            for (StorageModuloType Index = RangeLast; Index != RangeFirst; Index += RangeDirection)
            {
                StorageModuloType OldValueIndex = Index & IndexMask;
                StorageModuloType NewValueIndex = (Index + RangeDirection) & IndexMask;
                ::new ((void*)(Data + OldValueIndex)) ElementType(MoveTemp(Data[NewValueIndex]));
            }
            StorageModuloType OldValueIndex = RangeFirst & IndexMask;
            ::new ((void*)(Data + OldValueIndex)) ElementType(MoveTemp(Copy));
        }
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT const ElementType* GetStorage() const
    {
        return const_cast<TRingBuffer*>(this)->GetStorage();
    }
 
    [[nodiscard]] ElementType* GetStorage()
    {
        return (ElementType*)AllocatorInstance.GetAllocation();
    }
 
    /* Check and return whether the given Index is within range. */
    void RangeCheck(IndexType Index) const
    {
        if (Allocator::RequireRangeCheck) // Template property, branch will be optimized out
        {
            checkf((Index >= 0) & (Index < Num()), TEXT("RingBuffer index out of bounds: %i from a RingBuffer of size %i"), Index, Num());
        }
    }
 
    /* Check whether the given PopSize is within range. */
    void PopRangeCheck(SizeType PopCount) const
    {
        if (Allocator::RequireRangeCheck) // Template property, branch will be optimized out
        {
            checkf(PopCount <= static_cast<SizeType>(Num()), TEXT("RingBuffer PopCount out of bounds: %i from a RingBuffer of size %i"), PopCount, Num());
        }
    }
 
    friend class FRingBufferTest;
 
    ElementAllocatorType AllocatorInstance;
    StorageModuloType IndexMask;
    StorageModuloType Front;
    StorageModuloType AfterBack;
};
 
#if UE_ENABLE_INCLUDE_ORDER_DEPRECATED_IN_5_4
#include "Templates/IsTriviallyDestructible.h"
#include "Templates/MakeSigned.h"
#include "Templates/MakeUnsigned.h"
#endif