Circular Buffer

Hi /prog/

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?

>>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
}

Where cbuffer_value_at is just:

inline size_t cbuffer_size(cbuffer_t *cb) {
    return (cb->head > cb->tail) ? (cb->size - cb->head + cb->tail) : (cb->tail - cb->head);
}

inline void *cbuffer_at(cbuffer_t *cb, size_t offset) {
    assert(cb->offset < cbuffer_size(cb));
    return cb->data[(offset + cb->head) % cb->size];
}

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?