Circular Buffer

[ejleiss]

Hi, Could anybody show me some sample code of a circular buffer with start and end pointers?
I understand the basic idea of a circular buffer but don't quite know how to implement it in code.

Thank you!

 

[IanRyder]

Hi,

I have never come across the term "Circular Buffer" but I am interested to learn what this may mean so if you can explain the concept in detail I will see if I can come up with something to demonstrate your concept.

If this is beyond my experience then I will let you know and then leave it to one of the Experts on this site who may be able to provide you with an appropriate answer.

Cheers,

Ian

 

[ejleiss]

Thank you for the reply. I guess it is sometimes called a "ring buffer"... The concept would be a buffer that is connected end to end where in my case I would use it to display a stream of incoming data where the earlier data is not as important as the latest data coming in. Hope that explanation was sufficient enough.

 

[IanRyder]

Hi,

Based on the explanation of your concept please see the code below. Create a new form, add a button, a textbox with multiline set to true and a timer control with interval being 1000 and set enabled being true. Then replace the code behind with the below code.

Public Class Form1
  Private CircularBuffer As New List(Of String)
 
  Private Sub Timer1_Tick(sender As System.Object, e As System.EventArgs) Handles Timer1.Tick
    CircularBuffer.Insert(0, CreateRandomString)
  End Sub
 
  Private Function CreateRandomString() As String
    Const Range As Integer = 50
    Const StartValue As Integer = 32
 
    Dim counter As Integer
    Dim StringBuffer As String = Nothing
    Randomize()
    For counter = 1 To 20
      Dim RandomChar = Convert.ToInt32((Rnd() * Range) + StartValue)
      StringBuffer += Chr(RandomChar)
    Next
    Return StringBuffer
  End Function
 
  Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
    CheckCircularBufferInfo()
  End Sub
 
  Private Sub CheckCircularBufferInfo()
    TextBox1.Clear()
    For Each ReceivedString In CircularBuffer
      TextBox1.Text += ReceivedString & vbCrLf
    Next
    CircularBuffer.Clear()
  End Sub
End Class

Run the app, wait a few seconds and then click the button and as you will see, the timer is simulating some data coming into the application and then being stored in a List. However, when storing to the list the string is stored at the top of the list since its newer data. When you therefore click the button this then processes the list in the newest order it was received.

Does that simulate the Circular Buffer that you are after?

Hope that helps and let me know if I have misunderstood the concept.

Cheers,

Ian

 

[ejleiss]

I don't think this is quite the same as what I am looking for. Say you are receiving a steady stream of serial port data. I would like to take about 100 bytes and store them in an array that I would then like to display in a chart. I only want to display about 50 points at a time, however it needs to look like the data is streaming onto the chart in real time. So, I would like to look at my 100 data point array, take the first 50 points and plot them, (all while the new data is coming in then i would have to shift the pointer to look at the oldest data and keep plotting all while the new data is being added to the array. Sorry if I am not explaining this correctly.

 

[IanRyder]

It seems to me that you have contradicted yourself a bit since if I look at this as a continuous stream coming in, concatenated to the end an existing string then you must be taking the first bytes in the string to be plotted? i.e. first in, last out to be plotted?

Here is an example of what I mean, using a timer again as the data being received:-

Public Class Form1
  Private BufferString As String
 
  Private Sub Timer1_Tick(sender As System.Object, e As System.EventArgs) Handles Timer1.Tick
    BufferString += CreateRandomString()
  End Sub
 
  Private Function CreateRandomString() As String
    Const Range As Integer = 50
    Const StartValue As Integer = 32
 
    Dim counter As Integer
    Dim StringBuffer As String = Nothing
    Randomize()
    For counter = 1 To 20
      Dim RandomChar = Convert.ToInt32((Rnd() * Range) + StartValue)
      StringBuffer += Chr(RandomChar)
    Next
    Return StringBuffer
  End Function
 
  Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
    If BufferString.Length >= 50 Then
      Dim MyCharsToProcess As Char() = BufferString.Substring(0, 50).ToCharArray
      ProcessChars(MyCharsToProcess)
      BufferString = BufferString.Substring(50, BufferString.Length - 50)
    End If
  End Sub
 
  Private Sub ProcessChars(CharArray() As Char)
    'plot the chart here 
  End Sub
End Class

Is that any better?

Good Luck.

Ian

 

[Herman]

A ring buffer is a buffer with loss on overflow. A simple example of a ring buffer could be used where you would need a moving average of a number of value. Let's say you have an integer coming in a stream every second, and you want to calculate an average of the values over 1 minute. So you design a circular buffer with 60 indexes, and as every new integer arrives you add it to the end of the buffer. When the 61st integer arrives, the buffer is full, but that hardly matters. You add the new value, and the first value that was originally added is lost.

I *think* (someone correct me here) that the implementation in .Net is Queue(Of T), but I never had to use it. This kind of buffer is used extensively at low-level in embedded programs, but I never had a major need for them in .Net, because mostly everywhere I would need it it's already abstracted for me by the framework.

EDIT: After checking, a Queue(Of T) is very close to a ring buffer, but the difference is it does not dequeue old items automatically, by default it grows with the amount of data you put in it. It could certainly be adapted though. It seems .Net does not contain an implementation for a ring buffer. Others have done some though, here is one: http://www.codeproject.com/Articles/2880/Circular-Buffer . Apparently you cannot derive from generic collections except from the base type, which kind of screws the plan to inherit from Queue. However someone wrapped around it to do just what you want here: http://www.codeproject.com/Articles/31816/LimitedQueue . It's in C# but it shouldn't be too hard to convert.