Bob's Ringbuffer.c

#include "CoreTypes.h"
#include "Misc/AssertionMacros.h"
#include "Containers/Array.h"
#include "Math/UnrealMathUtility.h"

/**
 * Template class TRingBuffer
 * 
 * An expanding ring buffer with client specifiable maximum capacity.
 *
 * Coding style and local vernaculars from Epic's own Containers/TCircularBuffer (Copyright Epic Games,
 * Inc. All Rights Reserved.). Extended substantially to provide what could be described as a
 * "concertina-style" ring buffer.
 * 
 * In this implementation, the buffer starts with a size of 0 making the presence of an instance 
 * in memory essentially "free to pay" i.e. taking no memory at the moment of insantiation or until
 * actually in use.
 * 
 * Allocations begin when data is actually pushed, the buffer grows per demand in powers of two to
 * accommodate upto a specified maximum number of elements and when the maximum capacity is reached,
 * the buffer becomes a ring in that each push (new entry) is then accompanied by a corresponding pop.
 * For this reason pushes can continue indefinitely while the memory footprint remains constant.
 *
 * The power of two condition on the size of the buffer is to allow index wrapping by a simple bit mask
 * instead of modulo division. 
 * This fact also allows indexes Begin and End to be incremented only during normal operation
 * (without being wrapped back into the index space). They are only masked/wrapped when used as an index.
 * For this trick to work we require also (from the operating environment) that an unsigned integer
 * overflow wrap to zero i.e. that 0xffffffffu + 1 == 0. This is mostly the case and easily verfied.
 * A small price, 1 bit of indexable space, is also paid to allow begin == end to signal "ring empty"
 * as distinct from "buffer full".
 * 
 */
template<typename ElementType> class TRingBuffer
{
public:

	/**
	 * Instantiates a TRingBuffer with given maximum capacity.
	 *
	 * @param Capacity The number of elements that the buffer can expand to (will be rounded up to the next power of 2). 
	 */
	explicit TRingBuffer(uint32 Capacity)
	{
		Reset(Capacity);
	}

	/**
	 * Default ctor for TRingBuffer
	 *
	 * Remaining setup of internals is triggered via a call to Reset()
	 */
	FORCEINLINE TRingBuffer() : MaxCapacity(0) {}

public:

	/**
	* Reset does a hard reset of the instance with full tear-down.
	* 
	* Performs a full deallocation
	* Sets the given Capacity for a new ring buffer
	* Zeroes the ring markers - i.e. restarts the ring.
	*
	   @param Capacity The number of elements that the buffer can expand to (will be rounded up to the next power of 2). 
	*/
	FORCEINLINE void Reset(uint32 Capacity)
	{
		// dealloc
		Elements.Empty();

		// check that Capacity is within indexible space to allow for largest possible index mask of 2^31 - 1
		checkSlow(0 < Capacity && Capacity <= (1U << 31));
		// power of two large enough to meet specified value
		MaxCapacity = FMath::RoundUpToPowerOfTwo(Capacity);

		// restart ring markers from 0
		Begin = End = 0;
	}

	/**
	* Restart provides a very fast "soft reset" through which the ring can be collapsed
	* to zero length.
	*
	* This is achieved by moving Begin to End. A new ring is restarted where the last one
	* ended, effectively all existing ring elements are "popped" in one shot.
	*/
	FORCEINLINE void Restart()
	{
		Begin = End;
	}

	/**
	 * Returns a reference to the ring buffer element at the specified index.
	 *
	 * @param i The index of the element to return.
	 */
	FORCEINLINE ElementType& operator[](uint32 i)
	{
		return Elements[(Begin + i) & IndexMask];
	}

	/**
	 * Returns a const reference to the ring buffer element at the specified index.
	 *
	 * @param i The index of the element to return.
	 */
	FORCEINLINE const ElementType& operator[](uint32 i) const
	{
		return Elements[(Begin + i ) & IndexMask];
	}

	/**
	 * Calculates the index that follows the given index.
	 *
	 * @param i the index.
	 * @return The next index.
	 */
	FORCEINLINE uint32 IndexAfter(uint32 i) const
	{
		return ((i + 1) & IndexMask);
	}

	/**
	 * Calculates the index previous to the given index.
	 *
	 * @param i The current index.
	 * @return The previous index.
	 */
	FORCEINLINE uint32 IndexBefore(uint32 i) const
	{
		return ((i - 1) & IndexMask);
	}
	
public:

	/**
	 * Returns the number of elements that the buffer can currently hold.
	 *
	 * @return Buffer capacity.
	 */
	FORCEINLINE uint32 Capacity() const
	{
		return Elements.Num();
	}

	/**
	 * Returns the number of elements that the buffer can be expanded to hold.
	 *
	 * @return Buffer capacity.
	 */
	FORCEINLINE uint32 GetMaxCapacity() const
	{
		return MaxCapacity;
	}

	/**
	 * Returns the number of elements in the ring
	 *
	 * @return Difference of Begin and End indexes.
	 */
	FORCEINLINE uint32 Size() const
	{
		return End - Begin;
	}

	/**
	 * Returns true if the ring is empty, false otherwise.
	 *
	 * @return true if number of elements in the ring is zero
	 */
	FORCEINLINE bool IsEmpty() const
	{
		return Size() == 0;
	}

	/**
	 * Returns true if the ring is populated to capacity.
	 *
	 * @return true if the ring is the same size as its containing buffer
	 */
	FORCEINLINE bool IsFull() const
	{
		return Size() == Capacity();
	}

	/**
	 * Returns true if MaximumCapacity of the buffer has not yet been requested
	 *
	 * @return true if MaximumCapacity is gerater than current.
	 */
	FORCEINLINE bool Expandable() const
	{
		return MaxCapacity > Capacity();
	}

	/**
	* Expands buffer capacity to the next power of two beyond it's current size and
	* updates the IndexMask member.
	*/
	FORCEINLINE void Expand()
	{
		typedef TArray<ElementType>::SizeType SizeType;

		const SizeType OldNum = Elements.Num();
		const SizeType NewNum = FMath::RoundUpToPowerOfTwo(Capacity() + 1);
		verifySlow(Elements.AddZeroed(NewNum - OldNum) == OldNum); // failed allocation
		IndexMask = Elements.Num() - 1;
	}

	/**
	* Shifts the start of the ring by one, effectively discarding the first elemnent.
	* A reference to the elemeent is also returned.
	*/
	FORCEINLINE ElementType& Pop()
	{
		checkfSlow(!IsEmpty(), TEXT("Access violation attempt to read and shift the start of an empty ring."));
		return Elements[IndexMask & Begin++];
	}

	/**
	 * Pushes a new value onto the end of the ring.
	 *
	 * To make space, the ring expands with each push to capacity or "rotates" indefinitely.
	 *
	 */
	FORCEINLINE void Push(const ElementType& val)
	{
		if (IsFull())
		{
			if (Expandable())
			{
				Expand();
			}
			else
			{
				Pop();
			}
		}
		Elements[IndexMask & End++] = val;
	}

private:

	/** User specified maximum capacity of the ring buffer.*/
	uint32 MaxCapacity;

	/** Buffer index to the first element of the ring.*/
	uint32 Begin;

	/** Buffer index to one past the last element of the ring.*/
	uint32 End;

	/* Holds the mask for indexing buffer elements. /
	uint32 IndexMask;

	/* Holds the buffer's elements. /
	TArray<ElementType> Elements;
};