Dynamic Array

[Ronny Mandal]

Assume that you want to store n records in an array, and that the array can
hold all n elements, that is, it is declared int a[n].

And suddenlny in run-time, I need to store n+m items. Why cannot this be
done:

a[0] = e(0)
a[1] = e(1)
...
...
a[n] = e(n)

where e(i) is the i-th element
*(a+ (n+1) ) = e(the 1st element after n)
...
...
*(a+ (n+1) ) = e(the m-th element after n)

On the ocntrary, if I allocate an array with 0 elements a[0], C will let me
fill in approx 5 more values.

Is there a way to make the "index-table" of an array grow?
--

Thanks

Ronny Mandal
This e-mail and any attachment are confidential and may be privileged or
otherwise protected from disclosure. It is solely intended for the person(s)
named above. If you are not the intended recipient, any reading, use,
disclosure, copying or distribution of all or parts of this e-mail or
associated attachments is strictly prohibited. If you are not an intended
recipient, please notify the sender immediately by replying to this message
or by telephone and delete this e-mail and any attachments permanently from
your system.

[Walter Roberson]

In article <d3**********@readme.uio.no>,
Ronny Mandal <ro*****@math.uio.no> wrote:

Assume that you want to store n records in an array, and that the array can
hold all n elements, that is, it is declared int a[n]. And suddenlny in run-time, I need to store n+m items. Why cannot this be
done: *(a+ (n+1) ) = e(the 1st element after n)

Because when you declare int a[n] (presuming that n has
been #define'd with a constant value) then you are telling
C to reserve -exactly- n locations to store integers, and
you are telling C that it is fine to store whatever it needs to
in the location after that.

If you want *anything* in C to be dynamically sized, then you
must use malloc() or alloc() or the equivilent. Each malloc()
request will grant the amount of storage that you requested
in the call, and you can't store beyond that without undefined
behaviour. However, malloc() allows you to pass in a size
at run-time rather than the fixed sizes that C requires at -compile-
time for [] arrays.

If you are using dynamic memory as an array, and you find you
need more locations in the array, then you can use realloc()
to ask that more storage be made available. realloc() will
not necessarily extend the array "in place": instead, if necessary,
it will create a new object with the larger size, copy the
contents of the old object to the new one, and return the address
of the new one. Which is fine unless you happened to have been
taking pointers to the old object before, because those pointers
might not be valid anymore...

If you need the effect of dynamic arrays and you need the location
of any one element not to change after you allocate it and you
need to be able to grow the array, then you need to use a techique
such as linked lists or binary trees, or 2-3 trees, or tries; or
you could find one of the several pre-written "sparse array"
implementations and use them without worrying about what's under
the hood.
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers

[Daniel Cer]

You might want to have a look at realloc().

If you have an array 'a' that was already allocated using malloc,
realloc() allows you to dynamically resize the amount of memory
allocated to 'a' (i.e. in this case, effectively resizing the array).
For example, assume that 'a' was allocated using the following code:

int *a;

if (!(a = malloc(sizeof(int)*N))) {
/* some out of memory error handling code */
}

You could then operate on 'a' in the same manner you would use if 'a'
was allocated on the stack using "int a[N];". e.g.:

/* some random code using the just allocated array */
for (i = 0; i < N; i++) { a[i] = i; }

Then if you later need to resize 'a' so that it has M elements you could
use the following:

if (!(a = realloc(a, sizeof(int)*M))) {
/* some out of memory error handling code */
}

After calling realloc, you would then be free to use indices in the
range of 0..(M-1).

/* some more random code using the just reallocated array*/
for (i = N; i < M; i++) { a[i] = i; }

Hope that helps

-Dan
Ronny Mandal wrote:

Assume that you want to store n records in an array, and that the array can
hold all n elements, that is, it is declared int a[n].

And suddenlny in run-time, I need to store n+m items. Why cannot this be
done:

a[0] = e(0)
a[1] = e(1)
...
...
a[n] = e(n)

where e(i) is the i-th element
*(a+ (n+1) ) = e(the 1st element after n)
...
...
*(a+ (n+1) ) = e(the m-th element after n)

On the ocntrary, if I allocate an array with 0 elements a[0], C will let me
fill in approx 5 more values.

Is there a way to make the "index-table" of an array grow?

[Jack Klein]

On Sun, 17 Apr 2005 19:22:02 +0200, "Ronny Mandal"
<ro*****@math.uio.no> wrote in comp.lang.c:

Assume that you want to store n records in an array, and that the array can
hold all n elements, that is, it is declared int a[n].

And suddenlny in run-time, I need to store n+m items. Why cannot this be
done:

a[0] = e(0)
a[1] = e(1)
..
..
a[n] = e(n)

where e(i) is the i-th element
*(a+ (n+1) ) = e(the 1st element after n)
..
..
*(a+ (n+1) ) = e(the m-th element after n)

On the ocntrary, if I allocate an array with 0 elements a[0], C will let me

If your compiler compiles a program defining an array of [0] elements,
it is not a C compiler. At least not the way you are invoking it.
You may think it is compiling C, but in fact it is compiling a C-like
language with its own non-standard extensions.

It is a constraint violation for an array to be defined with a size of
less than 1 element, and a real C compiler must issue a diagnostic for
this.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

[Ronny Mandal]

Thanks, your solution really worked, except that realloc() is a void*
function, the program crashed when I tried to assign its "output" to a,
which was the original array.

RM.

[Mark McIntyre]

On Mon, 18 Apr 2005 23:17:27 +0200, in comp.lang.c , "Ronny Mandal"
<ro*****@math.uio.no> wrote:

Thanks, your solution really worked, except that realloc() is a void*
function,
This isn't going to cause any problems
the program crashed when I tried to assign its "output" to a,
which was the original array.

if a was a real array (as oppose to a pointer to something), you can't
assign to them. You've snipped too much context to be sure tho.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

[Chris Croughton]

On Mon, 18 Apr 2005 23:17:27 +0200, Ronny Mandal
<ro*****@math.uio.no> wrote:

Thanks, your solution really worked, except that realloc() is a void*
function, the program crashed when I tried to assign its "output" to a,
which was the original array.

The output of realloc should always be assigned to a temporary variable
which can be tested, because if it fails (insufficient memory for
instance) the original memory will still be allocated and need to be
freed. Something like

{
void *anew = realloc(a, size);
if (anew)
{
a = anew;
}
else
{
/* some error handling */
}
}

That way you can also put in traces to see what the values are before
assigning them.

How do you know that your program crashed when you tried to assign,
could it have crashed in realloc? It's best to post your code (as small
as possible which produces the problem) so we can see what you are
doing.

Chris C

[Daniel Cer]

Good advise. However, I think "always" is a little strong.

For example, in the case of a small command line utility, running out of
memory is pretty much "game over", where by the only thing left to do is
print out an "out of memory" error message and then exit the program.
So, in this case, it's not totally unreasonable to have code like the
following:

if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(OUT_OF_MEM_ERROR_CODE);
}

However, for more substantial applications, e.g. something that acts as
a server, or most interactive applications, then, yeah, it's a good idea
to check the return value of 'realloc' before overwriting the original
value. That way, it's possible to gracefully recover from an operation
that would have exhausted available memory, rather than just exiting the
program.

-Dan
Chris Croughton wrote:

On Mon, 18 Apr 2005 23:17:27 +0200, Ronny Mandal
<ro*****@math.uio.no> wrote:

Thanks, your solution really worked, except that realloc() is a void*
function, the program crashed when I tried to assign its "output" to a,
which was the original array.

The output of realloc should always be assigned to a temporary variable
which can be tested, because if it fails (insufficient memory for
instance) the original memory will still be allocated and need to be
freed. Something like

{
void *anew = realloc(a, size);
if (anew)
{
a = anew;
}
else
{
/* some error handling */
}
}

That way you can also put in traces to see what the values are before
assigning them.

How do you know that your program crashed when you tried to assign,
could it have crashed in realloc? It's best to post your code (as small
as possible which produces the problem) so we can see what you are
doing.

Chris C

[Chris Croughton]

On Wed, 20 Apr 2005 12:56:54 -0600, Daniel Cer
<Da********@gmail.com> wrote:

(Post re-ordered so that it makes sense, please don't top-post!)

Chris Croughton wrote:

The output of realloc should always be assigned to a temporary variable
which can be tested, because if it fails (insufficient memory for
instance) the original memory will still be allocated and need to be
freed. Something like

{
void *anew = realloc(a, size);
if (anew)
{
a = anew;
}
else
{
/* some error handling */
}
}

That way you can also put in traces to see what the values are before
assigning them.
Good advise. However, I think "always" is a little strong.

What have I said before about absolute generalisations? Something like
"they're always wrong"? <g>
For example, in the case of a small command line utility, running out of
memory is pretty much "game over", where by the only thing left to do is
print out an "out of memory" error message and then exit the program.
Yup.
So, in this case, it's not totally unreasonable to have code like the
following:

if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(OUT_OF_MEM_ERROR_CODE);
}
Although you can't guarantee that the fprintf will even work (it might
need to allocate a buffer). But yes, in many cases with simple
command-line utilities the only thing you can do is to give up, try to
display some message and exit.

Although even there I would want to free the existing memory first, to
give fprintf a better chance of succeeding:

{
void *anew = realloc(a, size);
if (!anew)
{
free(a);
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(OUT_OF_MEM_ERROR_CODE);
}
a = anew;
/* ... */
}

Incidentally, two things:

It is not necessary to cast the result of realloc(). Doing so often
masks an error like not including a header.

There are only two defined values for the exit() function, anything
else is non-portable.
However, for more substantial applications, e.g. something that acts as
a server, or most interactive applications, then, yeah, it's a good idea
to check the return value of 'realloc' before overwriting the original
value. That way, it's possible to gracefully recover from an operation
that would have exhausted available memory, rather than just exiting the
program.

As I indicate, it is anyway, or at least to make it more likely that the
error message gets out.

Chris C

[Daniel Cer]

>>So, in this case, it's not totally unreasonable to have code like the

following:

if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(OUT_OF_MEM_ERROR_CODE);
}

Although you can't guarantee that the fprintf will even work (it might
need to allocate a buffer). But yes, in many cases with simple
command-line utilities the only thing you can do is to give up, try to
display some message and exit.

Although even there I would want to free the existing memory first, to
give fprintf a better chance of succeeding:

{
void *anew = realloc(a, size);
if (!anew)
{
free(a);
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(OUT_OF_MEM_ERROR_CODE);
}
a = anew;
/* ... */
}

Yeah, but I would point out that with code like (1), using realloc,
you're not really any worse off than with code like (2), using the more
standard malloc idiom:

(1)

if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

(2)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

In both cases, if you're afraid of fprintf() not having enough memory to
do it's job, then, of course, the thing to do is to free up some memory
before making the call. But, 'a' might just point to a particularly
miniscule chuck of memory, so freeing it alone might not be too helpful.

With that in mind, technically, shouldn't each of the above be changed
to something more like the following?

(3)

if (!(new_a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
free(a);
/* some code free()-ing anything else we can get * /
/* access to, e.g. */
free(some_big_array);
/* and */
fclose(some_file_handle);
fclose(some_other_file_handle);
....

fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
} new_a = a;

(4)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
/* some code free()-ing anything else we can get * /
/* access to, e.g. */
free(some_big_array);
/* and */
fclose(some_file_handle);
fclose(some_other_file_handle);
....

fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

Incidentally, two things:

It is not necessary to cast the result of realloc(). Doing so often
masks an error like not including a header.
Unless, you're planning on moving any of the source code to C++ at some
point. In which case, the compiler will generate an error like "cannot
convert `void *' to `int *' in assignment".

There are only two defined values for the exit() function, anything
else is non-portable.

Non-portable to non Unix-like systems. :)

Also, on many Unix based/like systems, you can make use of the
standardized error codes in sysexits.h. But, since many != all, this is
non-portable even between Unix like systems.

-Dan

[Chris Croughton]

On Wed, 20 Apr 2005 19:20:40 -0600, Daniel Cer
<Da********@gmail.com> wrote:

Yeah, but I would point out that with code like (1), using realloc,
you're not really any worse off than with code like (2), using the more
standard malloc idiom:

(1)

if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

(2)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

In both cases, if you're afraid of fprintf() not having enough memory to
do it's job, then, of course, the thing to do is to free up some memory
before making the call. But, 'a' might just point to a particularly
miniscule chuck of memory, so freeing it alone might not be too helpful.
It might or might not (it might not point to anything at all, of course,
passing a null pointer to realloc is valid).
With that in mind, technically, shouldn't each of the above be changed
to something more like the following?

(3)

if (!(new_a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
free(a);
/* some code free()-ing anything else we can get * /
/* access to, e.g. */
free(some_big_array);
/* and */
fclose(some_file_handle);
fclose(some_other_file_handle);
....

fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
} new_a = a;

ITYM a = new_a;

Yes, indeed, and I've known some programs which deliberately allocate a
large chunk of memory at the start just so that they can free it if they
do run out of memory later before they try to do tidying up.
(4)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
/* some code free()-ing anything else we can get * /
/* access to, e.g. */
free(some_big_array);
But in that case you won't be freeing a, and that might be the biggest
bit of memory you have.

Incidentally, two things:

It is not necessary to cast the result of realloc(). Doing so often
masks an error like not including a header.

Unless, you're planning on moving any of the source code to C++ at some
point. In which case, the compiler will generate an error like "cannot
convert `void *' to `int *' in assignment".

If you're using C++ you should be using new and delete instead of malloc
and free <g>.

There are only two defined values for the exit() function, anything
else is non-portable.

Non-portable to non Unix-like systems. :)

As I said, non-portable. Non-portable isn't necessarily bad, there are
many cases where it is necessary to use some non-portable features, but
it is best to keep such things in a few system-dependent modules so they
can be seen and changed easily in isolation.
Also, on many Unix based/like systems, you can make use of the
standardized error codes in sysexits.h. But, since many != all, this is
non-portable even between Unix like systems.

And since nothing running the program has access to those constants
(like a shell script) it can't depend on them either. Since they are
constants defined in a system implementation file, the documentation of
the program won't be able to say what they are either, so they are
pretty near useless. For instance, I can document a program as
returning:

0: success
1: user error
2: unable to open input
3: unable to create output

etc., and then use it in a script, but if it's

EX_USAGE user error
EX_NOINPUT unable to open input
EX_CANTCREAT unable to create output

etc. then I'd have to try to find syserror.h in some system include
directory and rewrite the script for each system (or even each compiler
version on the system, potentially). The only system I know where such
things worked was VMS, where return values are registered with the
system and everything uses the same mechanism (they also include
severity and program identification in the result). Unix is far too
anarchic for that sort of thing to work.

EXIT_SUCCESS and EXIT_FAILURE are the only values which are guaranteed
to be returned to the system at all on exit (and there's no guarantee
that the system will make those available to any other program, but if
you can't test for success by exit value in a system then it doesn't
matter what you return).

Chris C

[Keith Thompson]

Chris Croughton <ch***@keristor.net> writes:

On Wed, 20 Apr 2005 19:20:40 -0600, Daniel Cer
<Da********@gmail.com> wrote:

[...]

Also, on many Unix based/like systems, you can make use of the
standardized error codes in sysexits.h. But, since many != all, this is
non-portable even between Unix like systems.

And since nothing running the program has access to those constants
(like a shell script) it can't depend on them either.

[snip]

The thing running the program could well be another C program that has
a "#include <sysexits.h>". Or it could be a script that invokes a
small C program to interpret the exit codes.

--
Keith Thompson (The_Other_Keith) ks***@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.

[Gregory Pietsch]

Ronny Mandal wrote:

Assume that you want to store n records in an array, and that the array can hold all n elements, that is, it is declared int a[n].

And suddenlny in run-time, I need to store n+m items. Why cannot this be done:

a[0] = e(0)
a[1] = e(1)
..
..
a[n] = e(n)

where e(i) is the i-th element
*(a+ (n+1) ) = e(the 1st element after n)
..
..
*(a+ (n+1) ) = e(the m-th element after n)

On the ocntrary, if I allocate an array with 0 elements a[0], C will let me fill in approx 5 more values.

Is there a way to make the "index-table" of an array grow?
Seems to me you need dynamic array code. Get FreeDOS edlin and borrow
it.

Gregory Pietsch


--

Thanks

Ronny Mandal
This e-mail and any attachment are confidential and may be privileged or otherwise protected from disclosure. It is solely intended for the person(s) named above. If you are not the intended recipient, any reading, use, disclosure, copying or distribution of all or parts of this e-mail or associated attachments is strictly prohibited. If you are not an intended recipient, please notify the sender immediately by replying to this message or by telephone and delete this e-mail and any attachments permanently from your system.

[Daniel Cer]

Daniel Cer wrote:

Yeah, but I would point out that with code like (1), using realloc,
you're not really any worse off than with code like (2), using the more
standard malloc idiom:

(1)

if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

(2)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

Sorry, to reply to my own post, but I noticed that for some bizarre
reason I used EXIT_SUCCESS instead of EXIT_FAILURE as the argument to
exit() when the system runs out of memory.

I'm actually semi-surprised nobody called me on that ;)

Anyhow, just in case anybody comes across this post later,all of the
"exit(EXIT_SUCCESSS);" statements should be changed to
"exit(EXIT_FAILURE);".

This goes for both for (1) & (2) above and (3) & (4) below.

-Dan
(3)

if (!(new_a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
free(a);
/* some code free()-ing anything else we can get * /
/* access to, e.g. */
free(some_big_array);
/* and */
fclose(some_file_handle);
fclose(some_other_file_handle);
....

fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
} new_a = a;

(4)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
/* some code free()-ing anything else we can get * /
/* access to, e.g. */
free(some_big_array);
/* and */
fclose(some_file_handle);
fclose(some_other_file_handle);
....

fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

[Daniel Cer]

Chris Croughton wrote:

(4)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
/* some code free()-ing anything else we can get * /
/* access to, e.g. */
free(some_big_array);

But in that case you won't be freeing a, and that might be the biggest
bit of memory you have.

The code in (4) was only suppose to contrast with (2), reproduced below.

(2)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_FAILURE);
}

That is, assuming no memory has been allocated for 'a' yet, how can
someone write code that will try to allocate some memory, such that if
not enough memory is available, then the program will exit and display
an "Out of memory" error message. Sorry, if my original message somehow
wasn't clear on that point. The code in (1) and (3) where given for the
case where 'a' actually points to something,.

Anyhow, for something like this, I've seen a fair amount code (prehaps
naively written code) that just looks something like (2). However, given
your point that if the program can't allocate any more memory, there
might not be enough memory for fprintf() to execute sucessfully, the
code in (4) was put forth as a more proper solution. That is, if
possible, a program should free other dynamically allocated memory
before making the call to fprintf().
-Dan

[CBFalconer]

Daniel Cer wrote:

.... snip ...
The code in (4) was only suppose to contrast with (2), reproduced below.

(2)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_FAILURE);
}

Which should be written (all casts are suspicious):

if (!(a = malloc(size * sizeof(*a)))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_FAILURE);
}

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson