iyaowu / microcontroller-circular-buffer Goto Github PK

Microcontroller Circular Buffer

I looked everywhere for circular buffer implemenation suitable for a
microcontroller.  The key limitation is the absence of a malloc so the
circular buffer implementation would have to work with a statically
declared memory space.  Additionally, it would have to work with bytes
and nothing else.

I wrote this from scratch for my needs.

Included is cbufftest.c that does some simple test cases.  You can
also use it to see how to use it.

Taken from cbufftest.c:
---------------------------------------------------------------------
	long ret;
	unsigned char buff[12];
	unsigned char hey[21];
	cbuff_t c;

	cbuff_init(&c, buff, 12);

	cbuff_enqueue(&c, (unsigned char*)"Hello", 5);

	ret = cbuff_dequeue1(&c);

	ret = cbuff_dequeue(&c, hey, 20);
---------------------------------------------------------------------

Note that the size of the actual space declared need not be the same
size initialized.  You can certainly call cbuff_init with a size
less than that of the space it manages.  Really, there's nothing
stopping you from doing the following:

---------------------------------------------------------------------
	unsigned char buff[20];
	cbuff_t c, d;

	cbuff_init(&c, buff, 10);
	cbuff_init(&d, buff+10, 10);
---------------------------------------------------------------------


A quick note about the philosophy behind the cbuff_t struct.

typedef struct
{
	unsigned char *buff;

	int start;
	int end;

	int cnt;

	int remain;

	int size;
} cbuff_t;

The absolute minimum that is needed to manage a circular buffer is the
start and end index, but this leaves the ambiguity of full and empty.
(See the Wikipedia article for further explanation and a nice set of
SVG graphics I made to demonstrate the circular buffer.) So you
usually then need a flag indicating that state.  Instead of a flag, I
opted to put in the counter directly.  Additionally, I put in the
remain counter to avoid repeatedly computing how many bytes are free.
Absolutely this is redundant information but I see it as an extreme of
the space-time tradeoff: I am fine giving up the few extra bytes of
RAM to avoid repeated calculations.


Finally, a note about the optimization I have done.  This was
originally written for the ARM7TDMI architecture for the LPC 2138 chip
by NXP/Philips.  I reviewed several iterations of objdump(1) trying to
tweak some performance into the functions.  This optimization may be
unnecessary but it was fun doing it.  Further more, it may totally
flop optimally on anything but the ARM7TDMI and may not even be the
most optimal.