Proper way to input a dynamically-allocated string

[Michel Rouzic]

I know it must sound like a newbie question, but I never really had to
bother with that before, and I didn't even find an answer in the c.l.c
FAQ

I'd like to know what's the really proper way for input a string in an
array of char that's dynamically allocated. I mean, I wish not to see
any such things as char mystring[100]; I don't want to see any number
(if possible) I just want to declare something like char *mystring; and
then I don't know how allocate it with just as many chars (with the
space for the \0 of course) as you get from stdin.

I'd really like to know once for all what's the smartest way of
inputing strings from stdin and storing them in a way so they take just
the needed space and I don't want to see any number such as 100 or
10,000 or even 4,294,967,296 in my code. Any way it can be done?

[Dag-Erling Smørgrav]

Re: Proper way to input a dynamically-allocated string

"Michel Rouzic" <Michel0528@yah oo.fr> writes:[color=blue]
> I'd like to know what's the really proper way for input a string in an
> array of char that's dynamically allocated. I mean, I wish not to see
> any such things as char mystring[100]; I don't want to see any number
> (if possible) I just want to declare something like char *mystring; and
> then I don't know how allocate it with just as many chars (with the
> space for the \0 of course) as you get from stdin.[/color]

One common idiom is the following:

#include <stdio.h>
#include <stdlib.h>

void *
frealloc(void *ptr, size_t sz)
{
void *tmp;

if ((tmp = realloc(ptr, sz)) != NULL)
return (tmp);
free(ptr);
return (NULL);
}

char *
getline(FILE *f)
{
char *str = NULL;
size_t sz = 0;
int ch;

for (size_t len = 0; ; ++len) {
ch = fgetc(f);
if (ch == EOF && !len)
return (NULL);
if (len == sz)
str = frealloc(str, sz = sz * 2 + 1);
if (ch == EOF || ch == '\n') {
str[len] = '\0';
return (str);
} else {
str[len] = ch;
}
}
}

However, on average, about 25% of the allocated memory will be wasted.
You can fix that by replacing

return (str);
with
return (frealloc(str, len + 1));

but you may still end up losing quite a bit to heap fragmentation,
depending on how good your system's malloc() implementation is.

DES
--
Dag-Erling Smørgrav - des@des.no

[Eric Sosman]

Re: Proper way to input a dynamically-allocated string

Michel Rouzic wrote:
[color=blue]
> I know it must sound like a newbie question, but I never really had to
> bother with that before, and I didn't even find an answer in the c.l.c
> FAQ
>
> I'd like to know what's the really proper way for input a string in an
> array of char that's dynamically allocated. I mean, I wish not to see
> any such things as char mystring[100]; I don't want to see any number
> (if possible) I just want to declare something like char *mystring; and
> then I don't know how allocate it with just as many chars (with the
> space for the \0 of course) as you get from stdin.
>
> I'd really like to know once for all what's the smartest way of
> inputing strings from stdin and storing them in a way so they take just
> the needed space and I don't want to see any number such as 100 or
> 10,000 or even 4,294,967,296 in my code. Any way it can be done?[/color]

Let's suppose you're reading complete '\n'-terminated lines,
the way fgets() does but with no explicit length limit. You
could do something like this (pseudocode, no error checking):

buffer = <empty>
do {
expand buffer with realloc()
append next input character
} while (character wasn't '\n');
expand buffer with realloc()
append '\0'

For efficiency's sake you'd probably want to avoid quite
so many trips in and out of the memory allocator, so a refinement
would be to start with a roomier buffer and expand by more than
one character at a time if necessary. (My own function for doing
this -- everybody writes one eventually -- begins with 100 characters
and adds half the buffer's current size each time it needs to expand:
100, 150, 225, ...)

Once you've read the entire line you can, if you like, realloc()
the buffer one final time to trim it to the exact size. I find
that's seldom worth the bother: your program is probably going to
process the line and free() or re-use the buffer pretty soon.

--
Eric Sosman
esosman@acm-dot-org.invalid

[slebetman@yahoo.com]

Re: Proper way to input a dynamically-allocated string

Michel Rouzic wrote:[color=blue]
> I know it must sound like a newbie question, but I never really had to
> bother with that before, and I didn't even find an answer in the c.l.c
> FAQ
>
> I'd like to know what's the really proper way for input a string in an
> array of char that's dynamically allocated. I mean, I wish not to see
> any such things as char mystring[100]; I don't want to see any number
> (if possible) I just want to declare something like char *mystring; and
> then I don't know how allocate it with just as many chars (with the
> space for the \0 of course) as you get from stdin.
>
> I'd really like to know once for all what's the smartest way of
> inputing strings from stdin and storing them in a way so they take just
> the needed space and I don't want to see any number such as 100 or
> 10,000 or even 4,294,967,296 in my code. Any way it can be done?[/color]
[color=blue]
>From stdin is a bit of a problem. The usual answer is to use a buffer[/color]
to temporarily store the string:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define BUFFER_SIZE 100

int main () {
char buffer[BUFFER_SIZE];
char *inputString = NULL;
size_t inLen = 0;

while (fgets(buffer, BUFFER_SIZE, stdin) != NULL) {
inLen += strlen(buffer);
if (inputString == NULL) {
inputString = malloc(inLen);
inputString[0] = '\0';
} else {
inputString = realloc(inputSt ring, inLen);
}
if (inputString == NULL) {
/* malloc or realloc failed */
exit(-1);
}
strcat(inputStr ing, buffer);
/* check for newline */
if(inputString[inLen-1] == '\n') {

/* process input here */

/* then remember to free inputString */
free(inputStrin g);
inputString = NULL;
}
}
}

[Michel Rouzic]

Re: Proper way to input a dynamically-allocated string


Eric Sosman wrote:[color=blue]
> Michel Rouzic wrote:
>[color=green]
> > I know it must sound like a newbie question, but I never really had to
> > bother with that before, and I didn't even find an answer in the c.l.c
> > FAQ
> >
> > I'd like to know what's the really proper way for input a string in an
> > array of char that's dynamically allocated. I mean, I wish not to see
> > any such things as char mystring[100]; I don't want to see any number
> > (if possible) I just want to declare something like char *mystring; and
> > then I don't know how allocate it with just as many chars (with the
> > space for the \0 of course) as you get from stdin.
> >
> > I'd really like to know once for all what's the smartest way of
> > inputing strings from stdin and storing them in a way so they take just
> > the needed space and I don't want to see any number such as 100 or
> > 10,000 or even 4,294,967,296 in my code. Any way it can be done?[/color]
>
> Let's suppose you're reading complete '\n'-terminated lines,
> the way fgets() does but with no explicit length limit. You
> could do something like this (pseudocode, no error checking):
>
> buffer = <empty>
> do {
> expand buffer with realloc()
> append next input character
> } while (character wasn't '\n');
> expand buffer with realloc()
> append '\0'
>
> For efficiency's sake you'd probably want to avoid quite
> so many trips in and out of the memory allocator, so a refinement
> would be to start with a roomier buffer and expand by more than
> one character at a time if necessary. (My own function for doing
> this -- everybody writes one eventually -- begins with 100 characters
> and adds half the buffer's current size each time it needs to expand:
> 100, 150, 225, ...)
>
> Once you've read the entire line you can, if you like, realloc()
> the buffer one final time to trim it to the exact size. I find
> that's seldom worth the bother: your program is probably going to
> process the line and free() or re-use the buffer pretty soon.[/color]

That's the method I like the best. I wouldn't bother with make larger
buffers anyways, would make things too complicated, and things don't
have to be sooo efficient when it comes to inputting strings, what
matters the most is the result. i think I made your idea work pretty
good, tell me if you think yous potted anything wrong with it, I GDBed
it and the content of the memory looked fine

int i;
char *mystring;

i=0;
mystring=NULL;
do
{
mystring=reallo c(mystring, i+1);
mystring[i]=getchar();
i++;
}
while (mystring[i-1]!='\n');
mystring[i-1]='\0';

[Keith Thompson]

Re: Proper way to input a dynamically-allocated string

"Michel Rouzic" <Michel0528@yah oo.fr> writes:
[snip][color=blue]
> That's the method I like the best. I wouldn't bother with make larger
> buffers anyways, would make things too complicated, and things don't
> have to be sooo efficient when it comes to inputting strings, what
> matters the most is the result. i think I made your idea work pretty
> good, tell me if you think yous potted anything wrong with it, I GDBed
> it and the content of the memory looked fine
>
> int i;
> char *mystring;
>
> i=0;
> mystring=NULL;
> do
> {
> mystring=reallo c(mystring, i+1);
> mystring[i]=getchar();
> i++;
> }
> while (mystring[i-1]!='\n');
> mystring[i-1]='\0';[/color]

The speed of that code while reading input probably isn't going to be
much of an issue, but the multiple calls to realloc() might cause
excessive heap fragmentation, which could cause problems elsewhere in
your program. (The standard does use the term "heap", but you get the
idea.)

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Eric Sosman]

Re: Proper way to input a dynamically-allocated string

Michel Rouzic wrote:[color=blue]
> Eric Sosman wrote:
>[color=green]
>>Michel Rouzic wrote:
>>
>>[color=darkred]
>>>I know it must sound like a newbie question, but I never really had to
>>>bother with that before, and I didn't even find an answer in the c.l.c
>>>FAQ
>>>
>>>I'd like to know what's the really proper way for input a string in an
>>>array of char that's dynamically allocated. I mean, I wish not to see
>>>any such things as char mystring[100]; I don't want to see any number
>>>(if possible) I just want to declare something like char *mystring; and
>>>then I don't know how allocate it with just as many chars (with the
>>>space for the \0 of course) as you get from stdin.
>>>
>>>I'd really like to know once for all what's the smartest way of
>>>inputing strings from stdin and storing them in a way so they take just
>>>the needed space and I don't want to see any number such as 100 or
>>>10,000 or even 4,294,967,296 in my code. Any way it can be done?[/color]
>>
>> Let's suppose you're reading complete '\n'-terminated lines,
>>the way fgets() does but with no explicit length limit. You
>>could do something like this (pseudocode, no error checking):
>>
>> buffer = <empty>
>> do {
>> expand buffer with realloc()
>> append next input character
>> } while (character wasn't '\n');
>> expand buffer with realloc()
>> append '\0'
>>
>> For efficiency's sake you'd probably want to avoid quite
>>so many trips in and out of the memory allocator, so a refinement
>>would be to start with a roomier buffer and expand by more than
>>one character at a time if necessary. (My own function for doing
>>this -- everybody writes one eventually -- begins with 100 characters
>>and adds half the buffer's current size each time it needs to expand:
>>100, 150, 225, ...)
>>
>> Once you've read the entire line you can, if you like, realloc()
>>the buffer one final time to trim it to the exact size. I find
>>that's seldom worth the bother: your program is probably going to
>>process the line and free() or re-use the buffer pretty soon.[/color]
>
>
> That's the method I like the best. I wouldn't bother with make larger
> buffers anyways, would make things too complicated, and things don't
> have to be sooo efficient when it comes to inputting strings, what
> matters the most is the result. i think I made your idea work pretty
> good, tell me if you think yous potted anything wrong with it, I GDBed
> it and the content of the memory looked fine
>
> int i;
> char *mystring;
>
> i=0;
> mystring=NULL;
> do
> {
> mystring=reallo c(mystring, i+1);
> mystring[i]=getchar();
> i++;
> }
> while (mystring[i-1]!='\n');
> mystring[i-1]='\0';[/color]

That's the general idea. As written, though, it's not
very robust: it's oblivious to realloc() failures and to
end-of-file or errors on the standard input. Pay attention
to the Sixth Commandment at

http://www.lysator.liu.se/c/ten-commandments.html

Other observations: `int' should probably be `size_t',
and see Keith Thompson's response for one of the reasons a
character-at-a-time expansion may not work well. ("Others
will occur to your thought." -- Gandalf)

--
Eric Sosman
esosman@acm-dot-org.invalid

[Michel Rouzic]

Re: Proper way to input a dynamically-allocated string


Keith Thompson wrote:[color=blue]
> "Michel Rouzic" <Michel0528@yah oo.fr> writes:
> [snip][color=green]
> > That's the method I like the best. I wouldn't bother with make larger
> > buffers anyways, would make things too complicated, and things don't
> > have to be sooo efficient when it comes to inputting strings, what
> > matters the most is the result. i think I made your idea work pretty
> > good, tell me if you think yous potted anything wrong with it, I GDBed
> > it and the content of the memory looked fine
> >
> > int i;
> > char *mystring;
> >
> > i=0;
> > mystring=NULL;
> > do
> > {
> > mystring=reallo c(mystring, i+1);
> > mystring[i]=getchar();
> > i++;
> > }
> > while (mystring[i-1]!='\n');
> > mystring[i-1]='\0';[/color]
>
> The speed of that code while reading input probably isn't going to be
> much of an issue, but the multiple calls to realloc() might cause
> excessive heap fragmentation, which could cause problems elsewhere in
> your program. (The standard does use the term "heap", but you get the
> idea.)[/color]

does it mean that the elements of my array won't be contigous?

[Michel Rouzic]

Re: Proper way to input a dynamically-allocated string


Eric Sosman wrote:[color=blue]
> Michel Rouzic wrote:[color=green]
> > Eric Sosman wrote:
> >[color=darkred]
> >>Michel Rouzic wrote:
> >>
> >>
> >>>I know it must sound like a newbie question, but I never really had to
> >>>bother with that before, and I didn't even find an answer in the c.l.c
> >>>FAQ
> >>>
> >>>I'd like to know what's the really proper way for input a string in an
> >>>array of char that's dynamically allocated. I mean, I wish not to see
> >>>any such things as char mystring[100]; I don't want to see any number
> >>>(if possible) I just want to declare something like char *mystring; and
> >>>then I don't know how allocate it with just as many chars (with the
> >>>space for the \0 of course) as you get from stdin.
> >>>
> >>>I'd really like to know once for all what's the smartest way of
> >>>inputing strings from stdin and storing them in a way so they take just
> >>>the needed space and I don't want to see any number such as 100 or
> >>>10,000 or even 4,294,967,296 in my code. Any way it can be done?
> >>
> >> Let's suppose you're reading complete '\n'-terminated lines,
> >>the way fgets() does but with no explicit length limit. You
> >>could do something like this (pseudocode, no error checking):
> >>
> >> buffer = <empty>
> >> do {
> >> expand buffer with realloc()
> >> append next input character
> >> } while (character wasn't '\n');
> >> expand buffer with realloc()
> >> append '\0'
> >>
> >> For efficiency's sake you'd probably want to avoid quite
> >>so many trips in and out of the memory allocator, so a refinement
> >>would be to start with a roomier buffer and expand by more than
> >>one character at a time if necessary. (My own function for doing
> >>this -- everybody writes one eventually -- begins with 100 characters
> >>and adds half the buffer's current size each time it needs to expand:
> >>100, 150, 225, ...)
> >>
> >> Once you've read the entire line you can, if you like, realloc()
> >>the buffer one final time to trim it to the exact size. I find
> >>that's seldom worth the bother: your program is probably going to
> >>process the line and free() or re-use the buffer pretty soon.[/color]
> >
> >
> > That's the method I like the best. I wouldn't bother with make larger
> > buffers anyways, would make things too complicated, and things don't
> > have to be sooo efficient when it comes to inputting strings, what
> > matters the most is the result. i think I made your idea work pretty
> > good, tell me if you think yous potted anything wrong with it, I GDBed
> > it and the content of the memory looked fine
> >
> > int i;
> > char *mystring;
> >
> > i=0;
> > mystring=NULL;
> > do
> > {
> > mystring=reallo c(mystring, i+1);
> > mystring[i]=getchar();
> > i++;
> > }
> > while (mystring[i-1]!='\n');
> > mystring[i-1]='\0';[/color]
>
> That's the general idea. As written, though, it's not
> very robust: it's oblivious to realloc() failures and to
> end-of-file or errors on the standard input. Pay attention
> to the Sixth Commandment[/color]


"If a function be advertised to return an error code in the event of
difficulties, thou shalt check for that code, yea, even though the
checks triple the size of thy code..."

ok, I guess I should do that but.... well... as it says, it makes the
code much longer and makes it harder to read and, well, I wouldn't know
what to do with an error anyways, I mean, if the return code ain't
right, i might display something like "the return code ain't right\n"
and don't know what I should do.

realloc() failures? never heard of that (maybe cuz im quite new to all
that), what can happen with it? how can you get an EOF or some error
from stdin?

you know, I care to know about why I should check for errors, and about
what can cause them and what I should do about it, but so far (and you
can understand that) I like to keep my code as simple as possible,
mostly that I consider that my program should work only as far as it is
used correctly (like, if a program is supposed to have a .wav file in
input, and the user put a .mp3 or anything else instead, I don't wanna
bother with doing stuff that will tell him "you need to input a .wav
file", i rather let him have a segmentation fault)

[Michel Rouzic]

Re: Proper way to input a dynamically-allocated string


Eric Sosman wrote:[color=blue]
> Other observations: `int' should probably be `size_t'[/color]

as for the size_t thing, well i could cast it for realloc, like this :
mystring=reallo c(mystring, (size_t) i+1); other than that, I think i
should leave it to int, unless it is ok to do iterations and refer to
some element of an array by a size_t, which i doubt

[Jordan Abel]

Re: Proper way to input a dynamically-allocated string

On 2005-12-09, Michel Rouzic <Michel0528@yah oo.fr> wrote:[color=blue]
>
> Eric Sosman wrote:[color=green]
>> Michel Rouzic wrote:[color=darkred]
>> > Eric Sosman wrote:
>> >
>> >>Michel Rouzic wrote:
>> >>
>> >>
>> >>>I know it must sound like a newbie question, but I never really had to
>> >>>bother with that before, and I didn't even find an answer in the c.l.c
>> >>>FAQ
>> >>>
>> >>>I'd like to know what's the really proper way for input a string in an
>> >>>array of char that's dynamically allocated. I mean, I wish not to see
>> >>>any such things as char mystring[100]; I don't want to see any number
>> >>>(if possible) I just want to declare something like char *mystring; and
>> >>>then I don't know how allocate it with just as many chars (with the
>> >>>space for the \0 of course) as you get from stdin.
>> >>>
>> >>>I'd really like to know once for all what's the smartest way of
>> >>>inputing strings from stdin and storing them in a way so they take just
>> >>>the needed space and I don't want to see any number such as 100 or
>> >>>10,000 or even 4,294,967,296 in my code. Any way it can be done?
>> >>
>> >> Let's suppose you're reading complete '\n'-terminated lines,
>> >>the way fgets() does but with no explicit length limit. You
>> >>could do something like this (pseudocode, no error checking):
>> >>
>> >> buffer = <empty>
>> >> do {
>> >> expand buffer with realloc()
>> >> append next input character
>> >> } while (character wasn't '\n');
>> >> expand buffer with realloc()
>> >> append '\0'
>> >>
>> >> For efficiency's sake you'd probably want to avoid quite
>> >>so many trips in and out of the memory allocator, so a refinement
>> >>would be to start with a roomier buffer and expand by more than
>> >>one character at a time if necessary. (My own function for doing
>> >>this -- everybody writes one eventually -- begins with 100 characters
>> >>and adds half the buffer's current size each time it needs to expand:
>> >>100, 150, 225, ...)
>> >>
>> >> Once you've read the entire line you can, if you like, realloc()
>> >>the buffer one final time to trim it to the exact size. I find
>> >>that's seldom worth the bother: your program is probably going to
>> >>process the line and free() or re-use the buffer pretty soon.
>> >
>> >
>> > That's the method I like the best. I wouldn't bother with make larger
>> > buffers anyways, would make things too complicated, and things don't
>> > have to be sooo efficient when it comes to inputting strings, what
>> > matters the most is the result. i think I made your idea work pretty
>> > good, tell me if you think yous potted anything wrong with it, I GDBed
>> > it and the content of the memory looked fine
>> >
>> > int i;
>> > char *mystring;
>> >
>> > i=0;
>> > mystring=NULL;
>> > do
>> > {
>> > mystring=reallo c(mystring, i+1);
>> > mystring[i]=getchar();
>> > i++;
>> > }
>> > while (mystring[i-1]!='\n');
>> > mystring[i-1]='\0';[/color]
>>
>> That's the general idea. As written, though, it's not
>> very robust: it's oblivious to realloc() failures and to
>> end-of-file or errors on the standard input. Pay attention
>> to the Sixth Commandment[/color]
>
>
> "If a function be advertised to return an error code in the event of
> difficulties, thou shalt check for that code, yea, even though the
> checks triple the size of thy code..."[/color]

unless you _really_ don't care whether it succeeds or fails

what are you going to do if a printf fails? what if you just want to
continue?
[color=blue]
> realloc() failures? never heard of that (maybe cuz im quite new to all
> that), what can happen with it?[/color]

it returns a null pointer because it didn't find enough memory
[color=blue]
> how can you get an EOF or some error from stdin?[/color]

someone types the EOF character, or interrupts [sending a signal on read
can possibly cause a read to fail in addition to calling a signal
handler]
[color=blue]
> you know, I care to know about why I should check for errors, and about
> what can cause them and what I should do about it, but so far (and you
> can understand that) I like to keep my code as simple as possible,
> mostly that I consider that my program should work only as far as it is
> used correctly (like, if a program is supposed to have a .wav file in
> input, and the user put a .mp3 or anything else instead, I don't wanna
> bother with doing stuff that will tell him "you need to input a .wav
> file", i rather let him have a segmentation fault)[/color]

if you do something that can cause a segmentation fault, it could very
well cause worse.

[grayhag]

Re: Proper way to input a dynamically-allocated string

Eric Sosman wrote:
[color=blue]
> For efficiency's sake you'd probably want to avoid quite
> so many trips in and out of the memory allocator, so a refinement
> would be to start with a roomier buffer and expand by more than
> one character at a time if necessary. (My own function for doing
> this -- everybody writes one eventually -- begins with 100 characters
> and adds half the buffer's current size each time it needs to expand:
> 100, 150, 225, ...)
>[/color]

The way it was done in K&P Programming Practice,
where they started with a one char sized buffer
and doubled the size every time there was no space left.
I`s a good "golden middle" type idea, i think.

[Jordan Abel]

Re: Proper way to input a dynamically-allocated string

On 2005-12-10, grayhag <uelsh@yahoo.co m> wrote:[color=blue]
> Eric Sosman wrote:
>[color=green]
>> For efficiency's sake you'd probably want to avoid quite so many
>> trips in and out of the memory allocator, so a refinement would be to
>> start with a roomier buffer and expand by more than one character at
>> a time if necessary. (My own function for doing this -- everybody
>> writes one eventually -- begins with 100 characters and adds half the
>> buffer's current size each time it needs to expand: 100, 150, 225,
>> ...)
>>[/color]
>
> The way it was done in K&P Programming Practice, where they started
> with a one char sized buffer and doubled the size every time there was
> no space left. I`s a good "golden middle" type idea, i think.[/color]

doubling it each time actually reduces the worst-case complexity [of the
entire operation] from O(n^2) to O(n). I'm not sure what complexity you
end up with adding less than the full previous size. probably something
like nlogn or n^1.5

[Flash Gordon]

Re: Proper way to input a dynamically-allocated string

Michel Rouzic wrote:[color=blue]
> Eric Sosman wrote:[color=green]
>> Other observations: `int' should probably be `size_t'[/color]
>
> as for the size_t thing, well i could cast it for realloc, like this :
> mystring=reallo c(mystring, (size_t) i+1);[/color]

Why on earth would you think that? You *really* need to start working
through a decent text book.
[color=blue]
> other than that, I think i
> should leave it to int, unless it is ok to do iterations and refer to
> some element of an array by a size_t, which i doubt[/color]

Again, what on earth makes you think that? Of course you can use a
size_t variable for indexing in to an array.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

[Flash Gordon]

Re: Proper way to input a dynamically-allocated string

Michel Rouzic wrote:[color=blue]
> Keith Thompson wrote:[/color]

<snip>
[color=blue][color=green]
>> The speed of that code while reading input probably isn't going to be
>> much of an issue, but the multiple calls to realloc() might cause
>> excessive heap fragmentation, which could cause problems elsewhere in
>> your program. (The standard does use the term "heap", but you get the
>> idea.)[/color]
>
> does it mean that the elements of my array won't be contigous?[/color]

No, it means the free space in your heap will be fragmented. Any memory
block returned by *alloc is always contiguous.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.