本文简述了一种 环形缓冲区(ring buffer) 的实现方法
环形缓冲区(ring buffer)在一些情况下非常有用, UE4 中提供了一个默认的实现 TCircularBuffer(代码较短,下面直接贴出完整源码):
代码语言：javascript复制// Copyright Epic Games, Inc. All Rights Reserved.
#pragma once
#include "CoreTypes.h"
#include "Misc/AssertionMacros.h"
#include "Containers/Array.h"
#include "Math/UnrealMathUtility.h"
/**
* Template for circular buffers.
*
* The size of the buffer is rounded up to the next power of two in order speed up indexing
* operations using a simple bit mask instead of the commonly used modulus operator that may
* be slow on some platforms.
*/
template<typename ElementType> class TCircularBuffer
{
public:
/**
* Creates and initializes a new instance of the TCircularBuffer class.
*
* @param Capacity The number of elements that the buffer can store (will be rounded up to the next power of 2).
*/
explicit TCircularBuffer(uint32 Capacity)
{
checkSlow(Capacity > 0);
checkSlow(Capacity <= 0xffffffffU);
Elements.AddZeroed(FMath::RoundUpToPowerOfTwo(Capacity));
IndexMask = Elements.Num() - 1;
}
/**
* Creates and initializes a new instance of the TCircularBuffer class.
*
* @param Capacity The number of elements that the buffer can store (will be rounded up to the next power of 2).
* @param InitialValue The initial value for the buffer's elements.
*/
TCircularBuffer(uint32 Capacity, const ElementType& InitialValue)
{
checkSlow(Capacity <= 0xffffffffU);
Elements.Init(InitialValue, FMath::RoundUpToPowerOfTwo(Capacity));
IndexMask = Elements.Num() - 1;
}
public:
/**
* Returns the mutable element at the specified index.
*
* @param Index The index of the element to return.
*/
FORCEINLINE ElementType& operator[](uint32 Index)
{
return Elements[Index & IndexMask];
}
/**
* Returns the immutable element at the specified index.
*
* @param Index The index of the element to return.
*/
FORCEINLINE const ElementType& operator[](uint32 Index) const
{
return Elements[Index & IndexMask];
}
public:
/**
* Returns the number of elements that the buffer can hold.
*
* @return Buffer capacity.
*/
FORCEINLINE uint32 Capacity() const
{
return Elements.Num();
}
/**
* Calculates the index that follows the given index.
*
* @param CurrentIndex The current index.
* @return The next index.
*/
FORCEINLINE uint32 GetNextIndex(uint32 CurrentIndex) const
{
return ((CurrentIndex 1) & IndexMask);
}
/**
* Calculates the index previous to the given index.
*
* @param CurrentIndex The current index.
* @return The previous index.
*/
FORCEINLINE uint32 GetPreviousIndex(uint32 CurrentIndex) const
{
return ((CurrentIndex - 1) & IndexMask);
}
private:
/** Holds the mask for indexing the buffer's elements. */
uint32 IndexMask;
/** Holds the buffer's elements. */
TArray<ElementType> Elements;
};实现上比较简单易懂,但同时在使用上也有不少局限,下面给出一个提供了更多功能的环形缓冲区实现(TRingBuffer),有兴趣的朋友可以看看:
代码语言：javascript复制// desc template ring buffer
// maintainer hugoyu
#pragma once
#include "CoreTypes.h"
#include "Misc/AssertionMacros.h"
#include "Containers/Array.h"
#include "Math/UnrealMathUtility.h"
enum class EKGRingBufferOverflowBehavior
{
// the size of the ring buffer will double and elements will be copied over to the new buffer
AutomaticExpansion,
// log error
LogError,
// the new element is ignored
DropElement,
// overrides the element considered Head, but does not advance further. Additional overflows will override the same element, as long as it's not removed with UseHead()
OverrideHead,
// overrides the head and advances (the element that was 2nd now becomes the Head). Further overflows will keep overriding the element considered the current head
OverrideHeadAndContinue,
};
template<typename ElementType>
class TKGRingBuffer
{
public:
TKGRingBuffer(int initialSize = 32, EKGRingBufferOverflowBehavior overflowBehavior = EKGRingBufferOverflowBehavior::OverrideHeadAndContinue)
{
if (initialSize <= 0)
{
initialSize = 32;
}
m_overflowBehavior = overflowBehavior;
m_elements.Reserve(initialSize);
for (int i = 0; i < initialSize; i)
{
m_elements.Add(ElementType());
}
m_headIndex = 0;
m_tailIndex = 0;
m_usedElements = 0;
}
// adds the specified element as the Tail
void Add(ElementType element)
{
if (m_usedElements == m_elements.Num())
{
// list is full
switch (m_overflowBehavior)
{
case EKGRingBufferOverflowBehavior::AutomaticExpansion:
Expand();
return;
case EKGRingBufferOverflowBehavior::LogError:
UE_LOG(LogTemp, Error, TEXT("[RingBuffer]Ring buffer is full and expansion is not allowed"));
return;
case EKGRingBufferOverflowBehavior::DropElement:
return;
case EKGRingBufferOverflowBehavior::OverrideHead:
m_elements[m_headIndex] = element;
return;
case EKGRingBufferOverflowBehavior::OverrideHeadAndContinue:
m_headIndex = (m_headIndex 1) % m_usedElements;
m_elements[m_tailIndex] = element;
m_tailIndex = (m_tailIndex 1) % m_usedElements;
return;
}
}
else
{
// list is not full
m_elements[m_tailIndex] = element;
m_tailIndex = (m_tailIndex 1) % m_elements.Num();
m_usedElements;
}
}
// expands the backing store to allow more elements. Involves a Copy operation of previous elements
void Expand()
{
int oldCount = m_elements.Num();
int newCount = oldCount * 2;
TArray<ElementType> newElemenets;
newElemenets.Reserve(newCount);
for (int i = 0; i < newCount; i)
{
newElemenets.Add(ElementType());
}
for (int i = 0; i < oldCount; i)
{
newElemenets[i] = GetValue(i);
}
m_headIndex = 0;
m_tailIndex = oldCount;
m_usedElements = oldCount;
m_elements = newElemenets;
}
// gets the head element without removing it
const ElementType& PeekHead() const
{
check(m_usedElements > 0);
return m_elements[m_headIndex];
}
// returns the head and removes it, thus advancing the buffer
ElementType PopHead()
{
check(m_usedElements > 0);
ElementType head = m_elements[m_headIndex];
if (m_headIndex == m_elements.Num() - 1)
{
m_headIndex = 0;
}
else
{
m_headIndex;
}
--m_usedElements;
return head;
}
// gets the number of currently used elements
int Count() const
{
return m_usedElements;
}
// gets the capacity of the ring buffer
int Capacity() const
{
return m_elements.Num();
}
// get value by logic index
ElementType& GetValue(int logicIndex)
{
check(logicIndex >= 0 && logicIndex < m_usedElements);
int realIndex = (m_headIndex logicIndex) % m_elements.Num();
return m_elements[realIndex];
}
// get value by logic index const
const ElementType& GetValue(int logicIndex) const
{
check(logicIndex >= 0 && logicIndex < m_usedElements);
int realIndex = (m_headIndex logicIndex) % m_elements.Num();
return m_elements[realIndex];
}
// get value be logic index
ElementType& operator[](int logicIndex)
{
return GetValue(logicIndex);
}
// get value be logic index const
const ElementType& operator[](int logicIndex) const
{
return GetValue(logicIndex);
}
// convert to TArray
TArray<ElementType> ToArray() const
{
TArray<ElementType> arrayBuffer;
for (int i = m_headIndex, j = 0; j < m_usedElements; i = (i 1) % m_elements.Num(), j)
{
arrayBuffer.Add(m_elements[i]);
}
return arrayBuffer;
}
protected:
int m_headIndex{ 0 };
int m_tailIndex{ 0 };
int m_usedElements{ 0 };
EKGRingBufferOverflowBehavior m_overflowBehavior{ EKGRingBufferOverflowBehavior::OverrideHeadAndContinue };
TArray<ElementType> m_elements;
};
