本文简述了一种 环形缓冲区(ring buffer) 的实现方法

环形缓冲区(ring buffer)在一些情况下非常有用, UE4 中提供了一个默认的实现 TCircularBuffer(代码较短,下面直接贴出完整源码):

// 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),有兴趣的朋友可以看看:

// 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 ERingBufferOverflowBehavior
{
	// the size of the ring buffer will double and elements will be copied over to the new buffer
	AutomaticExpansion,
	// throws std::overflow_error
	ThrowException,
	// 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 TRingBuffer
{
public:
	TRingBuffer(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())
		{
			// buffer is full
			switch (m_overflowBehavior)
			{
			case EKGRingBufferOverflowBehavior::AutomaticExpansion:
				Expand();
				break;
			case EKGRingBufferOverflowBehavior::ThrowException:
				throw std::overflow_error("[RingBuffer]Ring buffer is full and expansion is not allowed");
			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
		{
			// buffer 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
	{
		return m_elements[m_headIndex];
	}

	// returns the head and removes it, thus advancing the buffer
	ElementType PopHead()
	{
		if (m_usedElements == 0)
		{
			throw std::runtime_error("[TRingBuffer]No elements but trying to get one");
		}

		T 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)
	{
		if (logicIndex >= 0 && logicIndex < m_usedElements)
		{
			int realIndex = (m_headIndex + logicIndex) % m_elements.Num();
			return m_elements[realIndex];
		}

		throw std::out_of_range("[TRingBuffer]GetValue out of index");
	}

	// get value by logic index const
	const ElementType& GetValue(int logicIndex) const
	{
		if (logicIndex >= 0 && logicIndex < m_usedElements)
		{
			int realIndex = (m_headIndex + logicIndex) % m_elements.Num();
			return m_elements[realIndex];
		}

		throw std::out_of_range("[TRingBuffer]GetValue out of index");
	}

	// 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 < Count; 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;
};