Circular Buffer Question

Working with implementing a circular buffer for a producer/consumer deal.
Have not done one in a while. The following seems to work. However, I
remember and have seen other implementation that make the buffer 1 more then
the needed capacity so that a full buffer and an empty buffer can be
differentiated. However this implementation does not do that (i.e. the
capacity and the buffer size is the same.) I assume the following does not
need the extra buffer element because I am always tracking "used" (where the
other implementation would not do that as you could calculate that with the
readPos/writePos markers.) Just wondering if this imp. will somehow break
down for certain things or what the pros or cons are between the two
implementations (this seems a bit more straight forward)? TIA

//no locking yet.
public class CircularBuffer
{
private object[] buffer;
public int readPos;
public int writePos;
public int used;
public int size;

public CircularBuffer(int size)
{
this.size = size;
buffer = new object[size];
readPos = 0;
writePos = 0;
used = 0;
}
public void Put(object o)
{
if (IsFull())
throw new ApplicationException("Buffer is Full.");
buffer[writePos] = o;
writePos = (writePos + 1) % size;
used++;
}
public object Get()
{
if (IsEmpty())
throw new ApplicationException("Buffer is Empty.");
object o = buffer[readPos];
readPos = (readPos + 1) % size;
used--;
return o;
}
public bool IsFull()
{
return (used == size);
}
public bool IsEmpty()
{
return (used == 0);
}
public int Free
{
get { return size - used; }
}
} // End Class

--
William Stacey

re: Circular Buffer Question

Hi William,

I think it is the same with the circular queue in data structure.
There is 2 ways of implement the circular queue:
1. Use tail, head pointer and empty flag.
initial value: tail=head=0
empty mode: tail=head and empty=true;
full mode: tail=head and empty=false;

2. Give up the empty flag, but you must let one momery cell
not use.
Initial value: tail=head=0
empty mode: tail=head
full mode: (tail+1)%SIZE=head

For you sample code, it is the same with the first implement, but
it changes empty flag for used flag.

For multi-threading application, you should be careful of the share
variables: tail, head, empty.
You should use some mutex mechanism to protect them.

Hope this helps,
Best regards,
Jeffrey Tan
Microsoft Online Partner Support
Get Secure! - www.microsoft.com/security
This posting is provided "as is" with no warranties and confers no rights.

--------------------
| From: "William Stacey" <staceyw@mvps.org>
| Subject: Circular Buffer Question
| Date: Mon, 29 Sep 2003 11:26:40 -0400
| Lines: 65
| X-Priority: 3
| X-MSMail-Priority: Normal
| X-Newsreader: Microsoft Outlook Express 6.00.3790.0
| X-MimeOLE: Produced By Microsoft MimeOLE V6.00.3790.0
| Message-ID: <eRSmr4phDHA.1796@TK2MSFTNGP10.phx.gbl>
| Newsgroups: microsoft.public.dotnet.languages.csharp
| NNTP-Posting-Host: 66.188.59.114.bay.mi.chartermi.net 66.188.59.114
| Path: cpmsftngxa06.phx.gbl!TK2MSFTNGP08.phx.gbl!TK2MSFTN GP10.phx.gbl
| Xref: cpmsftngxa06.phx.gbl microsoft.public.dotnet.languages.csharp:188005
| X-Tomcat-NG: microsoft.public.dotnet.languages.csharp
|
| Working with implementing a circular buffer for a producer/consumer deal.
| Have not done one in a while. The following seems to work. However, I
| remember and have seen other implementation that make the buffer 1 more
then
| the needed capacity so that a full buffer and an empty buffer can be
| differentiated. However this implementation does not do that (i.e. the
| capacity and the buffer size is the same.) I assume the following does
not
| need the extra buffer element because I am always tracking "used" (where
the
| other implementation would not do that as you could calculate that with
the
| readPos/writePos markers.) Just wondering if this imp. will somehow break
| down for certain things or what the pros or cons are between the two
| implementations (this seems a bit more straight forward)? TIA
|
| //no locking yet.
| public class CircularBuffer
| {
| private object[] buffer;
| public int readPos;
| public int writePos;
| public int used;
| public int size;
|
| public CircularBuffer(int size)
| {
| this.size = size;
| buffer = new object[size];
| readPos = 0;
| writePos = 0;
| used = 0;
| }
| public void Put(object o)
| {
| if (IsFull())
| throw new ApplicationException("Buffer is Full.");
| buffer[writePos] = o;
| writePos = (writePos + 1) % size;
| used++;
| }
| public object Get()
| {
| if (IsEmpty())
| throw new ApplicationException("Buffer is Empty.");
| object o = buffer[readPos];
| readPos = (readPos + 1) % size;
| used--;
| return o;
| }
| public bool IsFull()
| {
| return (used == size);
| }
| public bool IsEmpty()
| {
| return (used == 0);
| }
| public int Free
| {
| get { return size - used; }
| }
| } // End Class
|
| --
| William Stacey
|
|
|
|

re: Circular Buffer Question

> For multi-threading application, you should be careful of the share[color=blue]
> variables: tail, head, empty.
> You should use some mutex mechanism to protect them.[/color]

Thank you Jeffery. I did run into this issue in a marathon debug session
today. Although I was locking the puts and gets and the other vars, I ran
into one of those strange sync issues that don't happen every time you run
it. When I put the last buffer in the cBuffer, that worked fine. However,
from the producer code, you can't tell it that this is the last byte[] until
after the Put() (I guess ya could if you put another sync wrapper) I set an
"InputComplete" flag in the cbuffer class right after the last "Put". Well,
luck has it that every once in a while a thread switch happens right after
the consumer tests for Empty and waits on a pulse from producer and did not
pick up the fact that the producer set the "InputComplete" flag. Short
story is I worked this out by sending a null in the stream to indicate a
stream done condition which simplifies the logic a bit. Many things to
watch out for to sync data structures. Anyway, a hard one to find and
diagnose - thanks for the help!

--
William Stacey, DNS MVP