Created
June 22, 2022 19:54
-
-
Save amb26/04ce49264da1c961f21444091885a6a0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment