A RingBuffer (aka. Circular Buffer) is a kind of a collection with a fixed maximal count of items to be stored within. After it reaches its capacity, the next insertion of a new items causes the first item to be overwritten.
These kind of objects is especially useful when working with large amounts of data where it is required to look back at some previous items (e.g. for validation). A RingBuffer provides this functionality by avoiding to hold all the data ever stored within.
This can be imagined like a window when driving by train. We see the next tree and the previous some, but we don't see all the trees since the journey started.
Before I wrote this blog entry, I searched the .NET framework and some common web sources. I have to say, I was wondering that I did not find another (working) .NET implementation of a RingBuffer.
Here is my version of a generic RingBuffer. Source file and unit tests are attached at the bottom of this post.
/* using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; */ /// <summary> /// Represents a fixted length ring buffer to store a specified maximal count of items within. /// </summary> /// <typeparam name="T">The generic type of the items stored within the ring buffer.</typeparam> [DebuggerDisplay("Count = {Count}")] public class RingBuffer<T> : IList<T>, ICollection<T>, IEnumerable<T>, IEnumerable { /// <summary> /// Creates a new instance of a <see cref="RingBuffer<T>"/> with a /// specified cache size. /// </summary> /// <param name="capacity">The maximal count of items to be stored within /// the ring buffer.</param> public RingBuffer(int capacity) { // validate capacity if (capacity <= 0) throw new ArgumentException("Must be greater than zero", "capacity"); // set capacity and init the cache Capacity = capacity; _buffer = new T[capacity]; } /// <summary> /// the internal buffer /// </summary> T[] _buffer; /// <summary> /// The all-over position within the ring buffer. The position /// increases continously by adding new items to the buffer. This /// value is needed to calculate the current relative position within the /// buffer. /// </summary> int _position; /// <summary> /// The current version of the buffer, this is required for a correct /// exception handling while enumerating over the items of the buffer. /// </summary> long _version; /// <summary> /// Gets or sets an item for a specified position within the ring buffer. /// </summary> /// <param name="index">The position to get or set an item.</param> /// <returns>The fond item at the specified position within the ring buffer. /// </returns> /// <exception cref="IndexOutOfRangeException"></exception> public T this[int index] { get { // validate the index if (index < 0 || index >= Count) throw new IndexOutOfRangeException(); // calculate the relative position within the rolling base array int index2 = (_position - Count + index) % Capacity; return _buffer[index2]; } set { Insert(index, value); } } /// <summary> /// Gets the maximal count of items within the ring buffer. /// </summary> public int Capacity { get; private set; } /// <summary> /// Get the current count of items within the ring buffer. /// </summary> public int Count { get; private set; } /// <summary> /// Adds a new item to the buffer. /// </summary> /// <param name="item">The item to be added to the buffer.</param> public void Add(T item) { // avoid an arithmetic overflow if (_position == int.MaxValue) _position = _position%Capacity; // add a new item to the current relative position within the // buffer and increase the position _buffer[_position++ % Capacity] = item; // increase the count if capacity is not yet reached if (Count < Capacity) Count++; // buffer changed; next version _version++; } /// <summary> /// Clears the whole buffer and releases all referenced objects /// currently stored within the buffer. /// </summary> public void Clear() { for (int i = 0; i < Count; i++) _buffer[i] = default(T); _position = 0; Count = 0; _version++; } /// <summary> /// Determines if a specified item is currently present within /// the buffer. /// </summary> /// <param name="item">The item to search for within the current /// buffer.</param> /// <returns>True if the specified item is currently present within /// the buffer; otherwise false.</returns> public bool Contains(T item) { int index = IndexOf(item); return index != -1; } /// <summary> /// Copies the current items within the buffer to a specified array. /// </summary> /// <param name="array">The target array to copy the items of /// the buffer to.</param> /// <param name="arrayIndex">The start position witihn the target /// array to start copying.</param> public void CopyTo(T[] array, int arrayIndex) { for (int i = 0; i < Count; i++) { array[i + arrayIndex] = _buffer[(_position - Count + i) % Capacity]; } } /// <summary> /// Gets an enumerator over the current items within the buffer. /// </summary> /// <returns>An enumerator over the current items within the buffer. /// </returns> public IEnumerator<T> GetEnumerator() { long version = _version; for (int i = 0; i < Count; i++) { if (version != _version) throw new InvalidOperationException("Collection changed"); yield return this[i]; } } /// <summary> /// Gets the position of a specied item within the ring buffer. /// </summary> /// <param name="item">The item to get the current position for.</param> /// <returns>The zero based index of the found item within the /// buffer. If the item was not present within the buffer, this /// method returns -1.</returns> public int IndexOf(T item) { // loop over the current count of items for (int i = 0; i < Count; i++) { // get the item at the relative position within the internal array T item2 = _buffer[(_position - Count + i) % Capacity]; // if both items are null, return true if (null == item && null == item2) return i; // if equal return the position if (item != null && item.Equals(item2)) return i; } // nothing found return -1; } /// <summary> /// Inserts an item at a specified position into the buffer. /// </summary> /// <param name="index">The position within the buffer to add /// the new item.</param> /// <param name="item">The new item to be added to the buffer.</param> /// <exception cref="IndexOutOfRangeException"></exception> /// <remarks> /// If the specified index is equal to the current count of items /// within the buffer, the specified item will be added. /// /// <b>Warning</b> /// Frequent usage of this method might become a bad idea if you are /// working with a large buffer capacity. The insertion of an item /// at a specified position within the buffer causes causes all present /// items below the specified position to be moved one position. /// </remarks> public void Insert(int index, T item) { // validate index if (index < 0 || index > Count) throw new IndexOutOfRangeException(); // add if index equals to count if (index == Count) { Add(item); return; } // get the maximal count of items to be moved int count = Math.Min(Count, Capacity - 1) - index; // get the relative position of the new item within the buffer int index2 = (_position - Count + index) % Capacity; // move all items below the specified position for (int i = index2 + count; i > index2; i--) { int to = i % Capacity; int from = (i - 1) % Capacity; _buffer[to] = _buffer[from]; } // set the new item _buffer[index2] = item; // adjust storage information if (Count < Capacity) { Count++; _position++; } // buffer changed; next version _version++; } /// <summary> /// Removes a specified item from the current buffer. /// </summary> /// <param name="item">The item to be removed.</param> /// <returns>True if the specified item was successfully removed /// from the buffer; otherwise false.</returns> /// <remarks> /// <b>Warning</b> /// Frequent usage of this method might become a bad idea if you are /// working with a large buffer capacity. The removing of an item /// requires a scan of the buffer to get the position of the specified /// item. If the item was found, the deletion requires a move of all /// items stored abouve the found position. /// </remarks> public bool Remove(T item) { // find the position of the specified item int index = IndexOf(item); // item was not found; return false if (index == -1) return false; // remove the item at the specified position RemoveAt(index); return true; } /// <summary> /// Removes an item at a specified position within the buffer. /// </summary> /// <param name="index">The position of the item to be removed.</param> /// <exception cref="IndexOutOfRangeException"></exception> /// <remarks> /// <b>Warning</b> /// Frequent usage of this method might become a bad idea if you are /// working with a large buffer capacity. The deletion requires a move /// of all items stored abouve the found position. /// </remarks> public void RemoveAt(int index) { // validate the index if (index < 0 || index >= Count) throw new IndexOutOfRangeException(); // move all items above the specified position one step // closer to zeri for (int i = index; i < Count - 1; i++) { // get the next relative target position of the item int to = (_position - Count + i) % Capacity; // get the next relative source position of the item int from = (_position - Count + i + 1) % Capacity; // move the item _buffer[to] = _buffer[from]; } // get the relative position of the last item, which becomes empty // after deletion and set the item as empty int last = (_position - 1) % Capacity; _buffer[last] = default(T); // adjust storage information _position--; Count--; // buffer changed; next version _version++; } /// <summary> /// Gets if the buffer is read-only. This method always returns false. /// </summary> bool ICollection<T>.IsReadOnly { get { return false; } } /// <summary> /// See generic implementation of <see cref="GetEnumerator"/>. /// </summary> /// <returns>See generic implementation of <see cref="GetEnumerator"/>. /// </returns> IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } }
You can download the source file and the unit tests here:
RingBuffer.cs
RingBufferTests.cs
Very helpful, thank you very much for your efforts!
ReplyDeleteNot bad as a starting point. I have to add array inserts. Thanks.
ReplyDeleteVery nice! a good Base!
ReplyDeletebut try:
public void CopyTo(T[] pArray, int pIndex)
{
var lSize = pArray.Length;
for (var i = 0; i <= Count; i++)
pArray[(i + pIndex) % lSize] = _buffer[(_position - Count + i) % Capacity];
}
the class should also implement IDisposable an try to call dispose if items are overwritten or deleted.
@DaWesti
ReplyDeleteFirst, thanks for the CopyTo method.
For the IDisposable, I'm always careful with disposing items within a collection. You are very correct, in case of a ring buffer this feels like the correct solution. However, I guess I'd at least add a bool property like "AutoDispose" or an event/callback to let the user of the ring buffer decide what to do with removed items.
Thanks for the feedback.
Flo
Awesome work - exactly what I was looking for. Thank you for sharing :-)
ReplyDeleteHi Joachim
ReplyDeleteGlad that you found what you've been looking for :-). Thanks for your feedback!
Flo
thank you! I needed this one, but what happends when _position overflows? it seems that _position will incriment continuously by adding function Add(T item)?
ReplyDeleteHi E2K
ReplyDeleteGood point, thanks!
I updated the Add(T item) method. Now an arithmetic overflow can only happen if your buffers capacity is equal to int.MaxValue. If this is given in your case, change the types from Int32 to Int64 - what should be enough in all cases.
Flo
What's about the licence? Is it free to use? You should add this to the code above.
ReplyDeleteHi Felix
ReplyDeleteNo special licenses. You can use it for whatever you want. For sure, no guarantees too.
Flo
Thank you Flo.
ReplyDeleteSeems very clean anyway.
Additionally i implemented INotifyCollectionChanged which helps a lot when working with bindings.
Felix
How can use this with images in a page flipper book.
ReplyDeleteHi Shelby
DeleteDepends in hat you man.
If you just want to store you images in memory I'd suggest Tor use an array instead of a ringbuffer.
If you don't want to keep all images in memory I'd use two buffers. One for backward one for forward navigation. But keep in mind to dispose Thema removed images.
Cheers
-Flo
// add 105 items to a 10 items buffer
ReplyDeleteCome on, 3-5 elements should be enough for most unit tests. This would reduce the complexity of the tests while maintaining their range. It will also remove the need for loops. Currently the tests are not easy to follow. I would prefer to read this:
ring.Add(0);
ring.Add(1);
ring.Add(2);
Assert.AreEqual(3, ring[3]);
By the way, you should flip the expected and actual values in the asserts.
This code will throw an IndexOutOfRangeException if _position ever reaches int.MaxValue.
ReplyDeleteThis will happen because for the first time _position is reduced to something smaller than the Count value. Which means in these 2 lines here:
int index2 = (_position - Count + index) % Capacity;
return _buffer[index2];
You'll in all likelihood get a negative number and use it to access the _buffer.
This error is thanks to the modulus operator returning the results in the sign of the dividend and not the divisor. Whereas for example, Excel returns the results in the same sign as the divisor.
ReplyDeleteTo fix your code you could add Capacity onto index2 when it is negative, it will bring the results back around and make them correct.
Of course this will add a conditional branch but the branch predictor should just skip it every time because of how rarely it will be entered. Though don't trust me, I don't know much about hardware.
On second thought you could also simply change the code that avoids arithmetic overflow (currently on line 84) to this:
if (_position == int.MaxValue)
_position = _position%Capacity + Capacity;
This will ensure _position will always be larger or equal to the count property.
Note: The Iterator Block you are using for GetEnumerator does auto generate an enumerator that contains a Reset method that throws per default.
ReplyDeleteYour IEnumerator is therefore not usable for DataVisualization.Charting.Chart as it will call Reset which will throw
I have found one Problem in your Clear-Function.
ReplyDeleteAfter you add more Elements than Capacity, delete one or more Element and now you say Clear(), not all Element delete from Buffer. For Example an Unit-Test to check the Problem:
[code]
// Arrange
var list = new CircularBuffer(5);
for (int i = 0; i < 7; ++i )
list.Add(i);
list.Remove(4);
list.Remove(6);
// Act
list.Clear();
// Assert
Assert.AreEqual(0, list.Count);
Assert.AreEqual(0, (int)list.CallField("_position"));
CollectionAssert.AreEqual(new int[] { 0, 0, 0, 0, 0 }, (int[])list.CallField("_buffer")); // <- At this point buffer has the value: "0, 0, 0, 3, 5"
[/code]
So the Clear()-Function musst be changed to:
for (int i = 0; i < Capacity; i++) _buffer[i] = default(T);
or better to:
for (int i = 0; i < Count; i++) _buffer[(_position - Count + i)] = default(T);
The reason you did not find another implementation is because System.Queue is a ring buffer.
ReplyDeleteIt is useful to learn how to set and reset a error.Thank you author for posting this kind of error.
ReplyDeletehttp://www.wikitechy.com/fix-error/flush-the-print-buffer-in-tsql
Both are really good.
Cheers,
Venkat