Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Buffers (http://www.velocityreviews.com/forums/t743013-buffers.html)

jacob navia 02-02-2011 09:45 PM

Buffers
 
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 02-03-2011 03:08 PM

Re: Buffers
 
On Feb 2, 4:45*pm, jacob navia <ja...@spamsink.net> wrote:
> 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 02-03-2011 07:28 PM

Re: Buffers
 
Le 03/02/11 16:08, ImpalerCore a écrit :
> On Feb 2, 4:45 pm, jacob navia<ja...@spamsink.net> wrote:
>> 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 02-03-2011 07:42 PM

Re: Buffers
 
On Thu, 03 Feb 2011 07:08:19 -0800, ImpalerCore wrote:
> On Feb 2, 4:45Â*pm, jacob navia <ja...@spamsink.net> wrote:
>> 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.

--
jiw

ImpalerCore 02-03-2011 09:09 PM

Re: Buffers
 
On Feb 3, 2:28*pm, jacob navia <ja...@spamsink.net> wrote:
> Le 03/02/11 16:08, ImpalerCore a crit :
>
>
>
> > On Feb 2, 4:45 pm, jacob navia<ja...@spamsink.net> *wrote:
> >> 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.


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 02-03-2011 10:14 PM

Re: Buffers
 
On 02/ 4/11 10:09 AM, ImpalerCore wrote:
> On Feb 3, 2:28 pm, jacob navia<ja...@spamsink.net> wrote:
>>
>> 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.


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.

--
Ian Collins


All times are GMT. The time now is 01:58 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.