Buffers

[jacob navia]

A container library must include the most common container:
buffers.

I have decided to provide two:

(1) An extensible linear buffer: You write into it, and if there is no
place the buffer resizes itself automatically.

(2) A circular buffer, designed to hold the last <n> items of a stream.
When the buffer is full the oldest item is overwritten with the new data.

OK, but I may have missed some.

What other kinds of buffers should be there?

 

[ImpalerCore]

A container library must include the most common container:
buffers.

I have decided to provide two:

(1) An extensible linear buffer: You write into it, and if there is no
place the buffer resizes itself automatically.

(2) A circular buffer, designed to hold the last <n> items of a stream.
When the buffer is full the oldest item is overwritten with the new data.

OK, but I may have missed some.

What other kinds of buffers should be there?

The only buffer that I've used before that is kind of unique is
referred to as a bipartite buffer. It's essentially a circular buffer
except that the elements can be variable sized. It basically
maintains a large buffer using a queue of block pointers (referenced
using a struct { void*, size_t }), and if it runs out of space, the
buffer will overwrite enough elements to make room for it.

queue
[ A, 3 bytes ]
[ B, 7 bytes ]
[ C, 3 bytes ]
[ D, 5 bytes ]

[ |.1.|...2...|.3.|..4..| ]
A B C D

The bipartite nature of it is that sometimes the elements form two
contiguous blocks within the buffer.

[|.6.|7| |..4..|....5....| ]

The main advantage over say maintaining an array of pointer elements
is that one can avoid calling malloc for each variable sized element,
but with the added complexity of maintaining a queue of block
pointers. I use it when having to process a live stream of data where
the individual messages are variable sized, i.e. data sent via strings
over a serial port. Sometimes in the embedded domain, one does not
have malloc available, so a bipartite buffer can be hardwired to
support a fixed buffer (the queue maintaining the elements in
bipartite buffer is fixed as well).

Not sure that this kind of buffer belongs in a generic container
library, as in my opinion it's a pretty specialized kind of buffer.
The tradeoff between its complexity and value is unclear.

Best regards,
John D.

 

[jacob navia]

Le 03/02/11 16:08, ImpalerCore a écrit :

A container library must include the most common container:
buffers.

I have decided to provide two:

(1) An extensible linear buffer: You write into it, and if there is no
place the buffer resizes itself automatically.

(2) A circular buffer, designed to hold the last<n> items of a stream.
When the buffer is full the oldest item is overwritten with the new data.

OK, but I may have missed some.

What other kinds of buffers should be there?

The only buffer that I've used before that is kind of unique is
referred to as a bipartite buffer. It's essentially a circular buffer
except that the elements can be variable sized. It basically
maintains a large buffer using a queue of block pointers (referenced
using a struct { void*, size_t }), and if it runs out of space, the
buffer will overwrite enough elements to make room for it.

queue
[ A, 3 bytes ]
[ B, 7 bytes ]
[ C, 3 bytes ]
[ D, 5 bytes ]

[ |.1.|...2...|.3.|..4..| ]
A B C D

The bipartite nature of it is that sometimes the elements form two
contiguous blocks within the buffer.

[|.6.|7| |..4..|....5....| ]

The main advantage over say maintaining an array of pointer elements
is that one can avoid calling malloc for each variable sized element,
but with the added complexity of maintaining a queue of block
pointers. I use it when having to process a live stream of data where
the individual messages are variable sized, i.e. data sent via strings
over a serial port. Sometimes in the embedded domain, one does not
have malloc available, so a bipartite buffer can be hardwired to
support a fixed buffer (the queue maintaining the elements in
bipartite buffer is fixed as well).

Not sure that this kind of buffer belongs in a generic container
library, as in my opinion it's a pretty specialized kind of buffer.
The tradeoff between its complexity and value is unclear.

Best regards,
John D.

Yes, variable sized items can be a problem, I started allowing for a
destructor function. The circular buffer will call the destructor
function when an item will be overwritten.

I will probaby introduce destructors in all containers shortly.

Thanks for uour very informative message

jacob

 

[James Waldby]

A container library must include [...buffers]
(1) An extensible linear buffer [...] resizes itself automatically.

(2) A circular buffer, designed to hold the last <n> items of a stream.

[...]
The only buffer that I've used before that is kind of unique is referred
to as a bipartite buffer. It's essentially a circular buffer except
that the elements can be variable sized. It basically maintains a large
buffer using a queue of block pointers (referenced using a struct {
void*, size_t }), and if it runs out of space, the buffer will overwrite
enough elements to make room for it. [snip examples]
The main advantage over say maintaining an array of pointer elements is
that one can avoid calling malloc for each variable sized element, but
with the added complexity of maintaining a queue of block pointers. I
use it when having to process a live stream of data where the individual
messages are variable sized, i.e. [...]

Not sure that this kind of buffer belongs in a generic container
library, as in my opinion it's a pretty specialized kind of buffer. The
tradeoff between its complexity and value is unclear.

....

Your struct { void*, size_t } is equivalent to struct iovec (see sys/uio.h
on linux systems), which is used with i/o like you mention. POSIX
functions readv and writev read and write multiple buffers per a vector
of struct iovec's.

 

[ImpalerCore]

Le 03/02/11 16:08, ImpalerCore a crit :

The only buffer that I've used before that is kind of unique is
referred to as a bipartite buffer.  It's essentially a circular buffer
except that the elements can be variable sized.  It basically
maintains a large buffer using a queue of block pointers (referenced
using a struct { void*, size_t }), and if it runs out of space, the
buffer will overwrite enough elements to make room for it.

queue
[ A, 3 bytes ]
[ B, 7 bytes ]
[ C, 3 bytes ]
[ D, 5 bytes ]

[   |.1.|...2...|.3.|..4..|           ]
     A   B       C   D

The bipartite nature of it is that sometimes the elements form two
contiguous blocks within the buffer.

[|.6.|7|            |..4..|....5....| ]

The main advantage over say maintaining an array of pointer elements
is that one can avoid calling malloc for each variable sized element,
but with the added complexity of maintaining a queue of block
pointers.  I use it when having to process a live stream of data where
the individual messages are variable sized, i.e. data sent via strings
over a serial port.  Sometimes in the embedded domain, one does not
have malloc available, so a bipartite buffer can be hardwired to
support a fixed buffer (the queue maintaining the elements in
bipartite buffer is fixed as well).

Not sure that this kind of buffer belongs in a generic container
library, as in my opinion it's a pretty specialized kind of buffer.
The tradeoff between its complexity and value is unclear.

Best regards,
John D.

Yes, variable sized items can be a problem, I started allowing for a
destructor function. The circular buffer will call the destructor
function when an item will be overwritten.

I will probaby introduce destructors in all containers shortly.

I believe that destructors are definitely beneficial, particularly
when managing containers of pointers. Rather than coding a loop to
free each element individually, a container 'free' with a destructor
wraps that kind of loop nicely.

The main issue is how to communicate the destructor function. In the
STL, destroying a list has the advantage of implicitly calling the
destructor of each element, something that's not available to us in
C. In C, you can free the allocated elements in a container, but you
also have to provide some method to execute the destructor manually.

The two options are through the container function API, or as a
function pointer in the container struct itself (or thirdly, code it
manually using a loop). I actually use both. For containers with
distributed nodes, like linked lists or trees, I pass a destructor
function as a function parameter to its free function. I don't want
to add the overhead of a function pointer to each node (you may feel
differently if your nodes are fatter). On the other hand, for
containers whose storage is in a central location, like a resizable
array, I like a function pointer member in its struct.

These are the rules of thumb that I have used, and I feel pretty
comfortable with it. Of course some people just prefer to manually
destruct their elements using a looping mechanism, which I have no
problem with as long as they assume the maintenance burden.

Best regards,
John D.

 

[Ian Collins]

I believe that destructors are definitely beneficial, particularly
when managing containers of pointers. Rather than coding a loop to
free each element individually, a container 'free' with a destructor
wraps that kind of loop nicely.

The main issue is how to communicate the destructor function. In the
STL, destroying a list has the advantage of implicitly calling the
destructor of each element, something that's not available to us in
C. In C, you can free the allocated elements in a container, but you
also have to provide some method to execute the destructor manually.

The two options are through the container function API, or as a
function pointer in the container struct itself (or thirdly, code it
manually using a loop). I actually use both. For containers with
distributed nodes, like linked lists or trees, I pass a destructor
function as a function parameter to its free function. I don't want
to add the overhead of a function pointer to each node (you may feel
differently if your nodes are fatter). On the other hand, for
containers whose storage is in a central location, like a resizable
array, I like a function pointer member in its struct.

I'm having trouble parsing that...

For a homogeneous container of type T, I'd just pass a destructor
function for T to the container. For a heterogeneous container, each
element would have to have its own.