Tracy R Reed wrote:
> Wade Curry wrote:
>>> I understand what all of those datastructures are except the
>>> circular buffer. What is it? More importantly, what kinds of
>>> things is it good for?
>
> Isn't it just a linked list with one end linked to the other?
>
A circular (or ring) buffer is usually done simpler. Earliest uses were,
I believe, for things like serial buffers in interrupt routines. That
was my first need, at least.
There is a producer that only does put(), and a consumer that only does
get(). Tests for full and empty are required; no need to walk any lists
or inspect the buffer.
Without considering strategy requirements that may be applied on empty
or full, I hereby submit some sample code -- no pizza required, even.
/* circbuf.c
* 2006.09.30jgs
*
* example assumes put/get occur in units of USIZ
* somehow allocate and initialize a buffer
* that can hold UTOT units
* (probably not static, as shown)
*
* NOTE: traditional problem distinguishing between full and empty
* is simplified (avoided) by requiring a one-unit "hole"
* that is, the max content is UTOT-1; buffer never really full
*
*******************************************************************/
typedef enum {false, true} bool;
// FIXME (as req'd)
#define USIZ 1
#define UTOT 10
typedef struct unit_st {
unsigned char item[USIZ];
} UNIT;
UNIT buf[UTOT];
#define BFIRST (&buf[0])
#define BLAST (&buf[UTOT-1])
UNIT* pNextGet = BFIRST;
UNIT* pLastPut = BLAST;
#define pNextPut (pLastPut < BLAST ? 1+pLastPut : BFIRST)
int
uAvail()
{
int ua = pNextPut - pNextGet;
return ua >= 0 ? ua : ua + UTOT;
}
#define isEmpty() (pNextPut == pNextGet)
int
uSpace()
{
int us= pNextGet - pNextPut -1;
return us >= 0 ? us : us + UTOT;
}
#define isFull() (0 == uSpace())
/* Note/Assert:
* producer only diddles pLastPut
* consumer only diddles pNextGet
*/
bool
uGet(UNIT* getdest)
{
if (isEmpty())
return false;
else
*getdest = *pNextGet++;
if (pNextGet > BLAST)
pNextGet = BFIRST;
return true;
}
bool
uPut(const UNIT* putsrc)
{
if (isFull())
return false;
else
pLastPut = pNextPut;
*pLastPut = *putsrc;
return true;
}
/***********/
/* TESTING */
/***********/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define DBG 1
#if DBG
# define dbg(...) fprintf (stderr, __VA_ARGS__)
#else
# define dbg
#endif
int main(int ac, char* av[])
{
#include <assert.h>
UNIT x,y;
unsigned char i;
int j;
assert(true == isEmpty());
assert(0 == uAvail());
assert(false == isFull());
assert(9 == uSpace());
assert(false == uGet(&x));
for (i='0'; i<'9'; i++){
x.item[0] = i;
assert(true == uPut(&x));
}
assert(false == isEmpty());
assert(9 == uAvail());
assert(true == isFull());
assert(0 == uSpace());
assert(false == uPut(&x));
assert(pNextPut == BLAST);
for (i='0'; i<'9'; i++){
assert(true == uGet(&x));
assert(x.item[0] == i);
}
assert(pNextGet == BLAST);
assert(0 == uAvail());
assert(9 == uSpace());
x.item[0] = 'Z';
for (j=0; j<97*UTOT; j++){
assert(true == uPut(&x));
assert(true == uGet(&y));
}
dbg("buf=%p..%p get=%p last=%p put=%p\n",
BFIRST,BLAST, pNextGet,pLastPut,pNextPut);
dbg("uspace returns %d\n", uSpace());
assert(pNextGet == BLAST);
assert(0 == uAvail());
assert(9 == uSpace());
return 0;
}
/*===eof===*/
Regards,
..jim
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-list
