buffer

[Bill Cunningham]

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

 

[Richard Damon]

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.

 

[Bill Cunningham]

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

 

[henry eshbaugh]

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.

 

[Ian Collins]

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?

 

[Kaz Kylheku]

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

 

[Nick Keighley]

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

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

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]

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?

 

[henry eshbaugh]

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.

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 *blocks* of chars makes more sense. I've done it when
memory was very tight and it worked quite well.

Either one works.

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

 

[Ian Collins]

Please don't snip attributions, it's rude.

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.


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.

 

[Nick Keighley]

Please don't snip attributions, it's rude.




Since when did malloc stop being used for dynamic allocation?








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]

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.

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

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.

Either one works.

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

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"

 

[Keith Thompson]

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.

 

[Charles Richmond]

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

 

[Malcolm McLean]

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.