On Thu, 04 Sep 2003 19:34:06 -0400, Ben Collingsworth
<bd*************@cfl.rr.com> wrote:
Anyone have some efficient source code for implementing a ring buffer?
There are several ways to implement a ring-buffer, depending on
how easy you want to make the tests for buffer empty/full. The
usual way I do it (without optimisations) is:
static unsigned char ringbuffer[ 256 ];
static unsigned short getindex = 0;
static unsigned short putindex = 0;
static unsigned short buffersize = 0;
int putring( char c )
{
if ( buffersize >= sizeof ringbuffer )
return -1;
ringbuffer[ putindex ] = c;
putindex++;
if ( putindex >= sizeof ringbuffer )
putindex = 0;
buffersize++;
return 0;
}
int getring( void )
{
if ( !buffersize )
return -1;
{
char c;
buffersize--;
c = ringbuffer[ getindex ];
getindex++;
if ( getindex >= sizeof ringbuffer )
getindex = 0;
return c;
}
}
Now, to make it faster.
If the size of the ring buffer is always a power-of-two you can
use masking to make the index variables wrap-around. For example
the increment and test for wrap-around becomes:
putindex = ( putindex++ ) & 0xFF;
If you have suitable compiler-extensions then force the start
address of the ring buffer to an alignment that is the same
as its size. That is for a 256-byte buffer it should be
aligned on a 256-byte boundary.
The indexing can then be replaced by pointers:
static char *putpointer = ringbuffer;
*putpointer = c;
putpointer = ( putpointer++ ) & ~0xFF;
Also there are functional efficiencies to consider, for example
the put function could discard the existing buffer contents if
the buffer overflows, this saves a test.
However I find that in real life programming ring buffers
can be considerable more entertaining. For example:
You may be part of a multi-tasking system where the task that
gets is different from the task that puts. The shared index
variables and buffer need to be defined as volatile and there
most likely need to be some kind of semaphore protection.
You want to get/put from within an interrupt handler. Potential
barrel of laughs that one.
Finally you may want to 'block' (i.e. do a non-looping wait)
on buffer full (put) or buffer empty (get). This is non-trivial
to get right, especially when using interrupts.
Nick.