Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Buffers

Reply
Thread Tools

Buffers

 
 
jacob navia
Guest
Posts: n/a
 
      02-02-2011
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?

 
Reply With Quote
 
 
 
 
ImpalerCore
Guest
Posts: n/a
 
      02-03-2011
On Feb 2, 4:45*pm, jacob navia <(E-Mail Removed)> 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.
 
Reply With Quote
 
 
 
 
jacob navia
Guest
Posts: n/a
 
      02-03-2011
Le 03/02/11 16:08, ImpalerCore a écrit :
> On Feb 2, 4:45 pm, jacob navia<(E-Mail Removed)> 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
 
Reply With Quote
 
James Waldby
Guest
Posts: n/a
 
      02-03-2011
On Thu, 03 Feb 2011 07:08:19 -0800, ImpalerCore wrote:
> On Feb 2, 4:45Â*pm, jacob navia <(E-Mail Removed)> 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
 
Reply With Quote
 
ImpalerCore
Guest
Posts: n/a
 
      02-03-2011
On Feb 3, 2:28*pm, jacob navia <(E-Mail Removed)> wrote:
> Le 03/02/11 16:08, ImpalerCore a crit :
>
>
>
> > On Feb 2, 4:45 pm, jacob navia<(E-Mail Removed)> *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.
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      02-03-2011
On 02/ 4/11 10:09 AM, ImpalerCore wrote:
> On Feb 3, 2:28 pm, jacob navia<(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modeling switches without bi-directional buffers easwarsr@gmail.com VHDL 2 07-30-2005 11:40 PM
Delay with buffers ratep2001 VHDL 3 02-28-2005 09:56 PM
Question about Header Buffers root Cisco 0 10-12-2004 05:14 PM
Designing MUX with tri sate buffers in xilinx virtex II FPGA Oleg VHDL 4 04-06-2004 02:55 PM
Ingress buffers on 4000 series oversubscribed gigabit line cards Peter Yardley Cisco 2 11-14-2003 11:41 AM



Advertisments