Design Patterns Series 19 - Circular Buffer Pattern

Circular Buffer Pattern :

Circular Buffer is perfect when one part of your code stores data and another part reads that data asynchronously. Makes very efficient use of memory.

A Circular Buffer is a memory allocation scheme where memory is reused when an index, incremented modulo the buffer size, writes over a previously used location. A Circular Buffer makes bounded queue when separate indices are used for inserting and removing data. The queue can be safely shared between threads (or processors) without further synchronization so long as one processor en-queues data and the other de-queues it.

You store data items in the various locations in a ring buffer and keep track of reading and writing operations  by labeling one location the Head and one the Tail.

When you store an item in the Circular Buffer you store the item at the tail location, and the tail advances to the next location.
When you read an item, you read the item at the current head location, and the head advances to the next position.

By writing to the tail and reading from the head, two streams can store and read data from the same circular buffer at the same time. The following code sets up an array holding the number of items you pass to the constructor.
public class CircularBuffer
{
    private String[] Buffer { get; set; }
    private Int32 Head { get; set; }
    private Int32 Tail { get; set; }

    public CircularBuffer(Int32 itemsCount)
    {
        Buffer = new String[itemsCount];
        Head = 0;
        Tail = 0;
    }
    .
    .
    .
}
The Store() method stores an item and advances the tail.
public Boolean Store(String data)
{
    if (!BufferIsFull)
    {
        Buffer[Tail] = data;
        Tail++;
        if (Tail == Buffer.Length)
        {
            Tail = 0;
        }
        return true;
    }
    return false;
}
private Boolean BufferIsFull
{
    get
    {
        if (Tail + 1 == Head)
        {
            return true;
        }
        if ((Tail == Buffer.Length - 1) && Head == 0)
        {
            return true;
        }
        return false;
    }
}
And the Read() method reads the item at the head location, and advances the head.
public String Read()
{
    if (Head != Tail)
    {
        String data = Buffer[Head];
        Head++;
        if (Head == Buffer.Length)
        {
            Head = 0;
        }
        return data;
    }
    return String.Empty;
}
Now you implemented the Circular Buffer and to test it you just want to create an instance of CircularBuffer class and call Store() and Read() methods many times in random order.
var buffer = new CircularBuffer(5);
Console.WriteLine("Stroing : Item0");
buffer.Store("Item0");
Console.WriteLine("Reading : {0}", buffer.Read());
Console.WriteLine("Stroing : Item1");
buffer.Store("Item1");
Console.WriteLine("Stroing : Item2");
buffer.Store("Item2");
Console.WriteLine("Reading : {0}", buffer.Read());
Console.WriteLine("Stroing : Item3");
buffer.Store("Item3");
Console.WriteLine("Reading : {0}", buffer.Read());
Console.WriteLine("Stroing : Item4");
buffer.Store("Item4");
Console.WriteLine("Reading : {0}", buffer.Read());
Console.WriteLine("Reading : {0}", buffer.Read());
Console.WriteLine("Stroing : Item5");
buffer.Store("Item5");
Console.WriteLine("Stroing : Item6");
buffer.Store("Item6");
Console.WriteLine("Reading : {0}", buffer.Read());
Console.WriteLine("Reading : {0}", buffer.Read());
Note we passed 5 as an argument of the constructor and stored 7 items that means we stored two items more than the capacity of our buffer but actually we overwrote the first two items. So the out put will become:
Stroing : Item0
Reading : Item0
Stroing : Item1
Stroing : Item2
Reading : Item1
Stroing : Item3
Reading : Item2
Stroing : Item4
Reading : Item3
Reading : Item4
Stroing : Item5
Stroing : Item6
Reading : Item5
Reading : Item6

you can download the full source code here

Comments

Popular posts from this blog

Android : How to change progress bar color at runtime programmatically?

How to fire RowCommand event of nested GridView?

ASP.Net MVC : Conditional Validation using ValidationAttribute