473,395 Members | 1,956 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,395 software developers and data experts.

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

Nov 15 '05 #1
2 6587

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" <st*****@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: <eR**************@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
|
|
|
|

Nov 15 '05 #2
> For multi-threading application, you should be careful of the share
variables: tail, head, empty.
You should use some mutex mechanism to protect them.


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

Nov 15 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: andy.dreistadt | last post by:
Hi all, I came across another problem that is probably pretty easy but, again, due to my rusty-ness with C, I'm a little stumped. I have a struct that looks like this: /* Instrument Data...
9
by: sunway | last post by:
i have written a small program, it turns out to be wrong, while(read()!=EOF){ read(); read(); read(); } so,when read==EOF,the next read() will read a -1, and the program will go infinitely.
7
by: toton | last post by:
Hi, I want a circular buffer or queue like container (queue with array implementation). Moreover I want random access over the elements. And addition at tail and remove from head need to be low...
2
by: marco.furlan | last post by:
Hi there, I have to write an optimized circular buffer to log events in C++. The elements are of type std::string. This should run under Linux on an ARM embedded system. I can dedicate to this...
9
by: thiago777 | last post by:
I have four methods(threads) in my application that must work syncronized sharing an 8 element circular buffer array. Each method should work in the data only after its previous thread had completed...
2
by: sharanap | last post by:
Implement a circular buffer of size 32 using an array inC, can anybody tel the answer, this que. asked to my friends in an interview
12
by: Sven | last post by:
Can someone point out source code for a safe circular buffer receiver transmitter? It's for sending and receiving bytes via RS232. Thanks in advance.
1
by: codedinC | last post by:
Is there a way to test to see if stdin is empty, or to see if there is data that has not been read from the buffer.
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.