Ring Buffer Data Structure + Source Code
RingBuffer is one of those simple, useful data structures that you don't get in the .NET Framework (or not quite the way we want it) and can be useful in certain situations within game development when we want to pack the data tightly.
Let's say we want to implement a simple message queue of FIFO type. Messages get registered with message processor and they get handled in their own turn. You could write a List<Message>, but that would be inefficient. If we add Message-s at the end of a list and consume them at the front, the whole queue would have to be shifted element by element as the front is consumed, and that's slow.
A little less naive implementation would be to use LinkedList<Message> and consume the top while adding the new ones to the bottom. This would cause the elements to "slide towards the right" in memory.
You want the data structure called RingBuffer, an array of continual elements in memory that has a Head and a Tail. New elements are added to the Tail position, so it fills from tail to the right and empties from head to the right. Once the tail reaches the end, it starts from the first element. If it "catches up" with head it is considered an overflow condition, most commonly handled by doubling its size. The list is pre-allocated and elements are initialized to default(T). Used elements are not de-allocated but stay in the list and are overwritten when tail has caught up to them.
You can read more details here.
You could also use a Queue<Message> and I certainly have, but then you don't get the access to the implementation so you are missing some options: Once the queue runs out of elements, should it expand, drop an element, throw an exception or override the front element? With .NET implementation you get the expansion as mandatory.
Lastly, you can use my implementation posted here:
This is a very simple implementation of a
RingBuffer<T>, without any excessive API and without thread safety. It presumes usage of value-type elements.
Add(T element) - Adds the specified element as the Tail.
DoubleTheSize() - Doubles the size of allowed elements in memory. Involves a Copy operation of previous elements.
PeekHead - Gets the head element without removing it.
UseHead() - Returns the head and removes it, thus advancing the buffer.
Count - Gets the number of currently used elements.
Capacity - Gets the capacity of the ring buffer.
ToString() - Returns a simple string representation of the Ring, elements separated by commas. Values returned represent values in memory, including the layout, unused and previous elements. Useful for debugging.
Print(string prefix = "", string postfix = ",") - Returns the string representation of values in the ring, elements in order (from head to tail), separated by commas. When appending the string representation, elements are added between a prefix and a postfix string. Last postfix string is removed at the end.
GetElementAtReverseIndex(int index) - Returns the value of an element at specified index, counted in the reverse order (from tail to head), starting at 0.
It allows the selection of following behaviours when the ring is full:
- AutomaticExpansion: The size of the Ring buffer will double and elements will be copied over to the new buffer.
- ThrowException: Throws OverflowException.
- DropElement: The new element is ignored.
- OverrideHead: 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().
- OverrideHeadAndContinue: Overrides the head and advances (the element that was 2nd now becomes the Head). Further additions will keep overriding the element considered the current head.
I have presumed the value data type because the benefits of 'data packing' are the biggest when using those, so make your 'Message' a struct.
If you're finding this article helpful, consider our asset Dialogical on the Unity Asset store for your game dialogues.