Some time ago I started to write a well designed library of useful algorithms in C. As long as I needed more stuff, I simply added pieces.
Today I'm pretty bored, so I'd like to add an implementation for circular buffers. Since however I don't really need it (it's just for fun), I'm wondering which is the most useful semantics for a circular buffer.
For instance:
[list]
[*] Is it worthy to write a primitive which applies a function on every availabe element from the oldest to the most recent?
[*] What if the buffer is full and I want to insert a new element? Should I overwrite the oldest one or should I make the request fail instead?
[/list]
Which are, in general, the kind of functionalities you'll prefer?
If by buffer you mean an array of bytes, then all that one would need to do is access it like this buff[index%length], where index is inputted, and length may be part of the structure holding the pointer to the buffer.
If you mean something else by "circular buffer", you're going to have to define it. Is it a linked list, a stack or queue or something else? All these have specific names and different behaviours and implementations. Decide exactly what semantics you want.
>>3
Yes, by circular buffer I mean a lightweight fixed-length array of void *. So you think about something like
void * ValueAt (Buffer *buf, int idx)
{
return buf->data[idx % buf->size];
}
in which the user simply needs to manage one incremental integer?
>>4
There's no point in using noko on a board which is so slow...
Name:
Anonymous2011-01-06 10:30
[*] Is it worthy to write a primitive which applies a function on every availabe element from the oldest to the most recent?
You are speaking of the Visitor pattern. Visitors are useful, but in C, you'd have to do this using function pointers, and the overhead of calling a function through indirection is slow. C doesn't lend itself to this type of thing very well. So I probably wouldn't bother. Instead, I'd implement some C99 inline functions to quickly allow someone to iterate over the values and pop values out of the circular buffer.
[*] What if the buffer is full and I want to insert a new element? Should I overwrite the oldest one or should I make the request fail instead?
You can implement both.
// pushes the value pointed to by value forcefully overwriting old values.
void cbuffer_push(cbuffer_t *cb, void* value);
// pushes a value into the buffer if space is available. returns 1 if successful, 0 if no space is available
int cbuffer_try_push(cbuffer_t *cb, void* value);
Name:
Anonymous2011-01-06 10:44
>>5
I'd also store the index of the head and tail nodes in the data structure. Leaving that for the user of the data structure is making it more difficult for your users, making their code more error-prone. Should look something like this:
>>6
Wouldn't it be best if he just used a linked list if all he wanted was to push/pop elements? No overwriting needed there, and requests won't fail, unless you run out of RAM.
cbuf_t *cbuf_new(int length) {
cbuf_t *buf = malloc(sizeof(buf));
buf->buffer = malloc(sizeof(int)*length);
buf->length = length;
return buf;
}
int cbuf_at(cbuf_t *buf, int i) { //
return (i>=buf->length)?(i-buf->length):i;
int cbuf_ref(cbuf_t *BUFFA, int index) {
return BUFFA->buffer[cbuf_at(index)];
}
void cbuf_set(cbuf_t *BUFFA, int index, int val) {
BUFFA->buffer[cbuf_at(index)] = val;
}
void cbuf_destroy(cbuf_t *buf) {
free(buf->buffer);
free(buf);
}
Name:
Anonymous2011-01-06 10:57
>>9
Sometimes you need something quick and without memory allocation. By example, in real timing memory allocation can be an issue, because of the time unpredictability.
Name:
Anonymous2011-01-06 11:00
>>8
Well, calling a function once isn't a problem. Having to call a function for each node in the data structure is. CPU has to perform a branch, create a stack frame, etc. You might be end up causing a cache miss on a each function call. Much faster to do:
for (size_t i = 0, end = cbuffer_size(cb); i < end; ++i) {
void *value = cbuffer_at(pos);
// do something with value
}
Since they're inline functions, they get inlined, and you don't have any call overhead per node in the circular buffer.
>>9
Then it wouldn't be called a circular buffer then, would it?
Name:
Anonymous2011-01-06 11:03
>>13
Sorry, should be:
for (size_t i = 0, end = cbuffer_size(cb); i < end; ++i) {
void *value = cbuffer_at(cb, i);
// do something with value
}
Name:
Anonymous2011-01-06 11:06
>>11
People who still use ints for addressing memory offsets should be shot on sight. Also, that code leaves it up to the user of the data structure to manage head and tail indices. Shitty code.
Name:
Anonymous2011-01-06 11:12
>>13>>14
Oh, you definitely have a point! I'll take this advice!
Name:
Anonymous2011-01-06 11:14
>>15
Yeah, about that I agree on how good and more clear is having a clean API, but is there any guy so dumb to mess with someone else's data structs?
Name:
Anonymous2011-01-06 11:31
>>15
People who use unsigned ints such as size_t for anything except bitwise operations, but including addressing memory offsets, should be hunted down and murdered.