buffer

Discussion in 'C Programming' started by Bill Cunningham, Oct 23, 2011.

  1. I am wanting to write a text reader involving fgetc and a loop but need
    to alloc memory of courses. At first I thought of malloc but would calloc
    have a better use for this. This function would also need to realloc and
    free memory. I've done this before but with a set buffer size and memory was
    wasted. int buff[5000]; for example. I need a buffer that would grow and
    then be freed. So how is calloc different than malloc. Also is valloc part
    of the standard? It shows up on the online man page.

    Bill
    Bill Cunningham, Oct 23, 2011
    #1
    1. Advertising

  2. On 10/23/11 4:58 PM, Bill Cunningham wrote:
    > I am wanting to write a text reader involving fgetc and a loop but need
    > to alloc memory of courses. At first I thought of malloc but would calloc
    > have a better use for this. This function would also need to realloc and
    > free memory. I've done this before but with a set buffer size and memory was
    > wasted. int buff[5000]; for example. I need a buffer that would grow and
    > then be freed. So how is calloc different than malloc. Also is valloc part
    > of the standard? It shows up on the online man page.
    >
    > Bill
    >
    >


    the difference between malloc and calloc is that calloc will clear the
    allocated region, and the size it allocates is based on the product of
    its two parameters. Unless you need one of these, calloc doesn't buy you
    anything. Since you are going to use realloc to grow the buffer, the
    clearing is probably not that useful as realloc won't clear the new memory.

    valloc() is not part of the c standard.
    Richard Damon, Oct 23, 2011
    #2
    1. Advertising

  3. Richard Damon wrote:

    > the difference between malloc and calloc is that calloc will clear the
    > allocated region, and the size it allocates is based on the product of
    > its two parameters. Unless you need one of these, calloc doesn't buy
    > you anything. Since you are going to use realloc to grow the buffer,
    > the clearing is probably not that useful as realloc won't clear the
    > new memory.
    > valloc() is not part of the c standard.


    Thanks I didn't quite understand that man pages description of calloc.

    Bill
    Bill Cunningham, Oct 24, 2011
    #3
  4. On Oct 23, 4:58 pm, "Bill Cunningham" <> wrote:

    > I need a buffer that would grow and then be freed.


    The most efficient way of doing this, rather than VLAs on the stack or
    multiple calls to malloc(), calloc() and free() is to use a linked
    list. It can grow and shrink dynamically on a node-by-node basis, and
    can be manipulated freely. They're simple to write and much easier to
    use.
    henry eshbaugh, Oct 26, 2011
    #4
  5. Bill Cunningham

    Ian Collins Guest

    On 10/27/11 10:58 AM, henry eshbaugh wrote:
    > On Oct 23, 4:58 pm, "Bill Cunningham"<> wrote:
    >
    >> I need a buffer that would grow and then be freed.

    >
    > The most efficient way of doing this, rather than VLAs on the stack or
    > multiple calls to malloc(), calloc() and free() is to use a linked
    > list. It can grow and shrink dynamically on a node-by-node basis, and
    > can be manipulated freely. They're simple to write and much easier to
    > use.


    A linked list of characters, you jest?

    How do you propose growing a linked list without dynamic allocation?

    --
    Ian Collins
    Ian Collins, Oct 27, 2011
    #5
  6. Bill Cunningham

    Kaz Kylheku Guest

    On 2011-10-27, Ian Collins <> wrote:
    > On 10/27/11 10:58 AM, henry eshbaugh wrote:
    >> On Oct 23, 4:58 pm, "Bill Cunningham"<> wrote:
    >>
    >>> I need a buffer that would grow and then be freed.

    >>
    >> The most efficient way of doing this, rather than VLAs on the stack or
    >> multiple calls to malloc(), calloc() and free() is to use a linked
    >> list. It can grow and shrink dynamically on a node-by-node basis, and
    >> can be manipulated freely. They're simple to write and much easier to
    >> use.

    >
    > A linked list of characters, you jest?


    Been there, done that.

    Recently.

    $ gdb ./txr
    GNU gdb (Ubuntu/Linaro 7.2-1ubuntu11) 7.2
    [ ... ]
    (gdb) b build_filter_from_list
    Breakpoint 1 at 0x428ee8: file filter.c, line 177.
    (gdb) r -c '@(deffilter f ("aaaaaab" "aaaaaac" "aaaaaad" "e"))'
    Starting program: /kaz-disk/home/kaz/txr/txr -c '@(deffilter f ("aaaaaab" "aaaaaac" "aaaaaad" "e"))'

    Breakpoint 1, build_filter_from_list (list=0x7ffff7fb20d8) at filter.c:177
    177 val trie = make_trie();
    (gdb) n
    180 for (iter = list; iter; iter = cdr(iter)) {
    (gdb) n
    181 val tuple = reverse(car(iter));
    (gdb) n
    182 mapcar(curry_123_2(func_n3(trie_add), trie, first(tuple)), rest(tuple));
    (gdb) n
    180 for (iter = list; iter; iter = cdr(iter)) {
    (gdb) n
    185 trie_compress(&trie);
    (gdb) p d(trie)
    #<hash: 0x8aa980>
    $1 = void
    (gdb) n
    186 return trie;
    (gdb) p d(trie)
    ('a' 'a' 'a' 'a' 'a' 'a' . #<hash: 0x8adbc0>)
    $2 = void
    (gdb) p (typeof(trie))
    $3 = (obj_t *) 0x7ffff7fe6cb8
    (gdb) p d(typeof(trie))
    cons
    $4 = void
    (gdb) p d(typeof(car(trie)))
    chr
    Kaz Kylheku, Oct 27, 2011
    #6
  7. On Oct 27, 2:50 am, Ian Collins <> wrote:
    > On 10/27/11 10:58 AM, henry eshbaugh wrote:
    > > On Oct 23, 4:58 pm, "Bill Cunningham"<>  wrote:


    > >> I need a buffer that would grow and then be freed.

    >
    > > The most efficient way of doing this, rather than VLAs on the stack or
    > > multiple calls to malloc(), calloc() and free() is to use a linked
    > > list. It can grow and shrink dynamically on a node-by-node basis,


    the *nodes* change size dynamically or just the list?

    > > and
    > > can be manipulated freely. They're simple to write


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

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

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

    > How do you propose growing a linked list without dynamic allocation?


    fixed number of blocks "allocated" at start up. Could be a giant
    array.

    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
    Nick Keighley, Oct 27, 2011
    #7
  8. On Oct 27, 3:44 am, Kaz Kylheku <> wrote:
    > On 2011-10-27, Ian Collins <> wrote:
    >
    > > On 10/27/11 10:58 AM, henry eshbaugh wrote:
    > >> On Oct 23, 4:58 pm, "Bill Cunningham"<>  wrote:

    >
    > >>> I need a buffer that would grow and then be freed.

    >
    > >> The most efficient way of doing this, rather than VLAs on the stack or
    > >> multiple calls to malloc(), calloc() and free() is to use a linked
    > >> list. It can grow and shrink dynamically on a node-by-node basis, and
    > >> can be manipulated freely. They're simple to write and much easier to
    > >> use.

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

    >
    > Been there, done that.
    >
    > Recently.
    >
    > $ gdb ./txr
    > GNU gdb (Ubuntu/Linaro 7.2-1ubuntu11) 7.2
    > [ ... ]
    > (gdb) b build_filter_from_list
    > Breakpoint 1 at 0x428ee8: file filter.c, line 177.
    > (gdb) r -c '@(deffilter f ("aaaaaab" "aaaaaac" "aaaaaad" "e"))'
    > Starting program: /kaz-disk/home/kaz/txr/txr -c '@(deffilter f ("aaaaaab""aaaaaac" "aaaaaad" "e"))'
    >
    > Breakpoint 1, build_filter_from_list (list=0x7ffff7fb20d8) at filter.c:177
    > 177       val trie = make_trie();
    > (gdb) n
    > 180       for (iter = list; iter; iter = cdr(iter)) {
    > (gdb) n
    > 181         val tuple = reverse(car(iter));
    > (gdb) n
    > 182         mapcar(curry_123_2(func_n3(trie_add), trie, first(tuple)), rest(tuple));
    > (gdb) n
    > 180       for (iter = list; iter; iter = cdr(iter)) {
    > (gdb) n
    > 185       trie_compress(&trie);
    > (gdb) p d(trie)
    > #<hash: 0x8aa980>
    > $1 = void
    > (gdb) n
    > 186       return trie;
    > (gdb) p d(trie)
    > ('a' 'a' 'a' 'a' 'a' 'a' . #<hash: 0x8adbc0>)
    > $2 = void
    > (gdb) p (typeof(trie))
    > $3 = (obj_t *) 0x7ffff7fe6cb8
    > (gdb) p d(typeof(trie))
    > cons
    > $4 = void
    > (gdb) p d(typeof(car(trie)))
    > chr


    is this an example of such a system or did the cat tread on your
    keyboard?
    Nick Keighley, Oct 27, 2011
    #8
  9. > the *nodes* change size dynamically or just the list?

    The list, of course.

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

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

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

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

    > > 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);
    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...)
    henry eshbaugh, Oct 29, 2011
    #9
  10. Bill Cunningham

    Ian Collins Guest

    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.

    --
    Ian Collins
    Ian Collins, Oct 29, 2011
    #10
  11. On Oct 29, 4:01 am, Ian Collins <> 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.
    Nick Keighley, Oct 29, 2011
    #11
  12. On Oct 29, 12:27 am, henry eshbaugh <> 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"
    Nick Keighley, Oct 29, 2011
    #12
  13. Nick Keighley <> 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.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Oct 29, 2011
    #13
  14. "Keith Thompson" <> wrote in message
    news:...
    > Nick Keighley <> 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)
    > <http://www.ghoti.net/~kst>
    > "We must do something. This is something. Therefore, we must do this."
    > -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Charles Richmond, Oct 30, 2011
    #14
  15. On Oct 29, 4:59 pm, Nick Keighley <>
    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
    Malcolm McLean, Oct 30, 2011
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Max

    buffer port

    Max, Sep 22, 2003, in forum: VHDL
    Replies:
    1
    Views:
    1,694
    Egbert Molenkamp
    Sep 22, 2003
  2. Raja
    Replies:
    12
    Views:
    24,379
    John Harrison
    Jun 21, 2004
  3. Replies:
    2
    Views:
    601
    sergejusz
    Mar 26, 2007
  4. Neal Becker

    buffer creates only read-only buffer?

    Neal Becker, Jan 8, 2009, in forum: Python
    Replies:
    0
    Views:
    409
    Neal Becker
    Jan 8, 2009
  5. xingye
    Replies:
    9
    Views:
    269
    Michael Lu
    Apr 19, 2004
Loading...

Share This Page