Wade Curry wrote:
Andrew Lentvorski([EMAIL PROTECTED])@Fri, Sep 29, 2006 at 06:19:33PM -0700:
Stewart Stremler wrote:
I used to have a directory full of simple C data structures --
singly-linked list, doubly-linked list, hashtable, binary tree,
etc. -- but I seem to have lost that directory.
Circular buffer is what I was looking for.
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?
Circular buffer - also called a circular array, ring array, or ring buffer.
It's basically an in-place FIFO. You can, however, normally address
things by position in O(1) just like an array. You have to keep track
of the start and the end to insure that you don't overflow/underflow.
You also have to keep track of empty (or full) so that you know whether
your buffer is full or empty when start == end. End can be less than
start; it just means that your data wraps around the end of the buffer.
It is similar to thinking about how many hours is it from 10PM to 2AM
(modular arithmetic).
The problem with a normal FIFO is that it either A) requires a lot of
copying or you run out of memory (array backed) or B) requires list
pointers to avoid the insertion/deletion copying (but adds a lot to your
memory requirements for small objects).
Normally such things are used in producer/consumer systems when moving
data between processes running at different rates but you don't want to
recopy all the data multiple times.
In this instance, the consumer is the sound system on a Nintendo DS. It
consumes 4 bytes from the circular buffer every 45.35 microseconds and
places them on the speakers. The producer is the Tremor Ogg Vorbis
codec. It is taking compressed Vorbis data at approximately 64kbps
(that's bits--not bytes) and decoding that into 4 bytes of 16-bit PCM
data and placing that onto the circular buffer. The rate at which it
produces the PCM data is *far* from constant depending upon how
effective the compression is.
The system has to make sure not to place too much data in the buffer
(thus, overwriting the currently playing sound data ... not good) or to
let the sound system run out of data to consume (normally, because the
producer is blocked for some reason).
There is no point in copying data because the PCM data is
write-once/read-once and then has no further use.
When used for audio decompression like this, the structure is often
called a jitter buffer (especially in voice over IP).
-a
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-list
