Friday, January 8, 2010

Generic C# RingBuffer

Today I'll share an almost coding only blog entry.

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&lt;T&gt;"/> 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

19 comments:

  1. Very helpful, thank you very much for your efforts!

    ReplyDelete
  2. Not bad as a starting point. I have to add array inserts. Thanks.

    ReplyDelete
  3. Very nice! a good Base!
    but 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.

    ReplyDelete
  4. @DaWesti
    First, 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

    ReplyDelete
  5. Awesome work - exactly what I was looking for. Thank you for sharing :-)

    ReplyDelete
  6. Hi Joachim
    Glad that you found what you've been looking for :-). Thanks for your feedback!
    Flo

    ReplyDelete
  7. 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)?

    ReplyDelete
  8. Hi E2K
    Good 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

    ReplyDelete
  9. What's about the licence? Is it free to use? You should add this to the code above.

    ReplyDelete
  10. Hi Felix

    No special licenses. You can use it for whatever you want. For sure, no guarantees too.

    Flo

    ReplyDelete
  11. Thank you Flo.

    Seems very clean anyway.
    Additionally i implemented INotifyCollectionChanged which helps a lot when working with bindings.

    Felix

    ReplyDelete
  12. How can use this with images in a page flipper book.

    ReplyDelete
    Replies
    1. Hi Shelby

      Depends 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

      Delete
  13. // add 105 items to a 10 items buffer

    Come 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.

    ReplyDelete
  14. Orri Þór HólmarssonJune 9, 2013 at 6:03 AM

    This code will throw an IndexOutOfRangeException if _position ever reaches int.MaxValue.

    This 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.

    ReplyDelete
  15. Orri Þór HólmarssonJune 9, 2013 at 9:17 AM

    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.

    To 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.

    ReplyDelete
  16. Note: The Iterator Block you are using for GetEnumerator does auto generate an enumerator that contains a Reset method that throws per default.

    Your IEnumerator is therefore not usable for DataVisualization.Charting.Chart as it will call Reset which will throw

    ReplyDelete
  17. I have found one Problem in your Clear-Function.

    After 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);

    ReplyDelete
  18. The reason you did not find another implementation is because System.Queue is a ring buffer.

    ReplyDelete