Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > buffer

Reply
Thread Tools

buffer

 
 
Nick Keighley
Guest
Posts: n/a
 
      10-29-2011
On Oct 29, 4:01*am, Ian Collins <(E-Mail Removed)> wrote:
> Please don't snip attributions, it's rude.
>
> On 10/29/11 12:27 PM, henry eshbaugh wrote:
>
> *>> I wrote:
> >>> How do you propose growing a linked list without dynamic allocation?

>
> > void list_add_node(list_head_t *head, char c)
> > {
> > * * * * */* parse to end of node. can be done with reference to end
> > from list_head_t
> > * * * * * * or simple parsing logic. let's say node_t *current now
> > points to the
> > * * * * * * end of the list. */
> > * * * * */* ... */
> > * * * * *current->next = malloc(sizeof current->*next);

>
> Since when did malloc stop being used for dynamic allocation?
>
>
>
>
>
> > * * * * *current->next->next = NULL;
> > * * * * *current->next->value = c;
> > * * * * *return ;
> > }

>
> > Now, pass a char to it, and have your list expand.

>
> >> As I say, it works well on limited hardware but i can't really see the
> >> over whelming advantage over malloc/realloc on a modern system. I
> >> assume Bill isn't processing giga-bytes of data

>
> > The overhead of copying blocks of memory directly is much larger than
> > parsing to the end of a well-designed linked list. And I'd agree with
> > his initial approach if he was processing gigabytes of data. So, I'd
> > think that it would be easier to do something like this instead of
> > copying everything every time you want to append 1 char (something he
> > expects to be repeated a few thousand times...)

>
> But you don't copy everything every time you want to append 1 char. *You
> copy when the buffer fills.


and you use a number other than 1 when you expand the buffer. A common
practice is to use a multiplier perhaps up to some maximum.
 
Reply With Quote
 
 
 
 
Nick Keighley
Guest
Posts: n/a
 
      10-29-2011
On Oct 29, 12:27*am, henry eshbaugh <(E-Mail Removed)> wrote:

<snip>

> If you know of any data structures that can resize themselves, let me
> know. That would be pretty cool.


C++ vector which basically has something like realloc() underneath.
Trees, Stack, Queues. In other words most of 'em. That's because I
think a "data structure" is an abstraction.

> > amazing how many times I've debugged such things...

>
> I feel like it would be easier than to implement logic to copy arrays
> over and over again. Of course, I can always be wrong, but at least to
> me, a linked list would be easier.


I was just pointing out that implementing a linked list isn't entirely
trivial

> > > and much easier to use.

>
> > not really you have to be more careful not to drop off the end of the
> > block. Well designed primitives can mitigate this

>
> Just like you can drop off the end of any array. But at least you can
> return an error code.


yes but with blocks you can drop off the end in the middle of a
string.

> > > A linked list of characters, you jest?

>
> > a linked list of *blocks* of chars makes more sense. I've done it when
> > memory was very tight and it worked quite well.

>
> Either one works.


a linked list of characters would be odd. That's a 400% overhead on a
typical implementation.

<snip>

> > As I say, it works well on limited hardware but i can't really see the
> > over whelming advantage over malloc/realloc on a modern system. I
> > assume Bill isn't processing giga-bytes of data

>
> The overhead of copying blocks of memory directly is much larger than
> parsing to the end of a well-designed linked list.


notif you do your allocations in a sensible fashion. According to you
no-one should use C++ std::vector

> And I'd agree with
> his initial approach if he was processing gigabytes of data. So, I'd
> think that it would be easier to do something like this instead of
> copying everything every time you want to append 1 char (something he
> expects to be repeated a few thousand times...)


"Doctor it hurts when I do this!"
"Don't do that"

 
Reply With Quote
 
 
 
 
Keith Thompson
Guest
Posts: n/a
 
      10-29-2011
Nick Keighley <(E-Mail Removed)> writes:
[...]
> a linked list of characters would be odd. That's a 400% overhead on a
> typical implementation.

[...]

More likely 700% (or 1500% on a typical 64-bit system).

sizeof (struct node { char c; struct node *next; }) is likely to be
2 * sizeof (struct node *), with padding after c.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Charles Richmond
Guest
Posts: n/a
 
      10-30-2011
"Keith Thompson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Nick Keighley <(E-Mail Removed)> writes:
> [...]
>> a linked list of characters would be odd. That's a 400% overhead on a
>> typical implementation.

> [...]
>
> More likely 700% (or 1500% on a typical 64-bit system).
>
> sizeof (struct node { char c; struct node *next; }) is likely to be
> 2 * sizeof (struct node *), with padding after c.
>


No problem. Just call Intel and tell them we need more and faster
processors
on the next CPU chip...

> --
> Keith Thompson (The_Other_Keith) (E-Mail Removed)
> <http://www.ghoti.net/~kst>
> "We must do something. This is something. Therefore, we must do this."
> -- Antony Jay and Jonathan Lynn, "Yes Minister"


 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      10-30-2011
On Oct 29, 4:59*pm, Nick Keighley <(E-Mail Removed)>
wrote:
>
> a linked list of characters would be odd. That's a 400% overhead on a
> typical implementation.
>

A suffix tree has a huge overhead, but it allows for very fast
searching of strings.

--
Visit my website, lots of free games to download
http://www.malcolmmclean.site11.com/www

 
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
buffer creates only read-only buffer? Neal Becker Python 0 01-08-2009 01:58 AM
When using System.IO.FileStream, I write 8 bytes, then seek to the start of the file, does the 8 bytes get flushed on seek and the buffer become a readbuffer at that point instead of being a write buffer? DR ASP .Net 2 07-29-2008 09:50 AM
When using System.IO.FileStream, I write 8 bytes, then seek to the start of the file, does the 8 bytes get flushed on seek and the buffer become a readbuffer at that point instead of being a write buffer? DR ASP .Net Building Controls 0 07-29-2008 01:37 AM
convert M bit buffer to N bit buffer runcyclexcski@yahoo.com C++ 2 03-26-2007 09:43 AM
How to know the buffer size and increase buffer size in c++ Raja C++ 12 06-21-2004 06:21 PM



Advertisments