Very large array of structures

[Tom Reader]

I wonder if someone can help me with this C syntax question.

I've been using a two dimensional array of structures, allocated on
the stack, such as:

struct mystruct array[10][10];

array[0][0].structelement1 = 'a';
array[0][0].structelement2 = 'b';
array[0][1].structelement2 = 'c';
. etc.

This is working fine, until the array gets very large, eg.

struct mystruct array[1000][1000]; // or even bigger.

Even with everything else remaining the same, I am running into all
sorts of obsure problems that I didn't run into in the small version,
presumably due to stack overflows, and the related knock-on effects.
I've increased the stack size beyond what it should need to be, and
still get the same problems.

What I want to do is allocate the memory dynamically, so it can come
from the (heap? - main block of memory anyway!) instead of the stack.

Thinking that pointer syntax and array syntax were more or less
interchangeable, I hoped I could 'malloc' the memory necessary (x-size
* ysize * struct size), then reference the returned pointer as a 2D
array of structs.

So far, I've not managed to get the syntax right, and most of my books
and other references only talk about 1D arrays.

Can anyone help me on this, by showing an example like that above, but
using 'malloc'ed memory?

Thanks and advance,

Tom

Tom Reader t...@unix-manuals.com
Unix Manuals http://www.unix-manuals.com
Manuals, tutorials and reference materials for Unix

[Eric Sosman]

Tom Reader wrote:
>
> [...]

>
> So far, I've not managed to get the syntax right, and most of my books
> and other references only talk about 1D arrays.

The books only mention one-dimensional arrays because that's
really the only kind of array C supports. However, the elements
of a 1-D array can themselves be 1-D arrays, which permits you to
simulate multi-dimensional arrays.

> Can anyone help me on this, by showing an example like that above, but
> using 'malloc'ed memory?

A confession: I've been writing C for close to a quarter
century, and I am still uneasy in some corners of the language.
One of these dusty corners is the matter of multi-dimensional
arrays; I still have to stop and think carefully (and maybe even
consult a reference book) to decipher some array declarations.

I could, of course, suck in my gut, gird up my loins, and
dust out that corner once and for all -- for all its dinginess,
the corner isn't all *that* dusty. But I'm lazy and slothful,
not to mention cowardly, and C provides an easy mechanism for
avoiding all this unpleasantness: Use `typedef' and build up
your multi-dimensional array one level at a time.

In your case, you'd like to use malloc() and a pointer to
produce an effect similar to

struct mystruct array[M][N];

Here's the lazy coward's way to proceed:

typedef struct mystruct Row[N];
Row *array;
array = malloc(M * sizeof(*array));

Now (assuming malloc() succeeds), each of array[0] through
array[M-1] is a "Row", which is itself an array of N instances
of your struct. To set the `foobar' field of the last element
of the last row to 42, you could write

( (array[M-1]) [N-1] ).foobar = 42;

or more simply

array[M-1][N-1].foobar = 42;

Of course, I urge you not to follow my example: You *should*
be brave, studious, and diligent, and should learn how to do
this without the crutch of the `typedef'. On the other hand, it
never hurts to write your code in such a way that your intentions
are clear even to those less b.s.&d. than yourself.

--
Eric....@east.sun.com

[Mark Bessey]

Tom Reader <t...@unix-manuals.com> wrote in message
news:bfhr6tgr633la5bri...@4ax.com...

> I wonder if someone can help me with this C syntax question.
>
> I've been using a two dimensional array of structures, allocated on
> the stack, such as:

...snip typical 2D array declaration/manipulation...

> This is working fine, until the array gets very large, eg.
>
> struct mystruct array[1000][1000]; // or even bigger.
>
> Even with everything else remaining the same, I am running into all
> sorts of obsure problems that I didn't run into in the small version,
> presumably due to stack overflows, and the related knock-on effects.
> I've increased the stack size beyond what it should need to be, and
> still get the same problems.

For maximum portability, you shouldn't allocate large arrays on the stack.
What's "large" in this context? I'd say anything over a few hundred
characters in size.

> What I want to do is allocate the memory dynamically, so it can come
> from the (heap? - main block of memory anyway!) instead of the stack.

"heap" is the most commonly-used term. Not that Standard C says anything
about how the memory returned from malloc() is actually managed...

> Thinking that pointer syntax and array syntax were more or less
> interchangeable, I hoped I could 'malloc' the memory necessary (x-size
> * ysize * struct size), then reference the returned pointer as a 2D
> array of structs.

It can be done, it's just not trivially easy.

> So far, I've not managed to get the syntax right, and most of my books
> and other references only talk about 1D arrays.
>
> Can anyone help me on this, by showing an example like that above, but
> using 'malloc'ed memory?

Sure thing. What you want to do is something like this:

#include <stdlib.h>

struct mystruct {
char structelement1;
char structelement2;
};

int main (void) {
int rows = 100;
int columns = 100;

struct mystruct **array;
int x;
array = malloc(sizeof(*array) * rows);
for (x=0; x < rows; x ++) {
array[x]=malloc(sizeof(**array) * columns);
}

/* now do something with it... */
}

At the end of this, you should have an array of pointers to pointers to
mystruct, with each pointer initialized to point at an array of mystructs.
You can dereference a using the same syntax you used for the 2D array:

array[0][0].structelement1 = 'a';
array[0][0].structelement2 = 'b';

...etc...

Don't forget to check the calls to malloc(), to make sure they don't return
NULL. When you want to free the memory, you need to write a loop similar to
the one above to free() each element before freeing the array.

Hope this helped,

-Mark

[Tom Reader]

I've been programming C since about 10 years ago, but not much in the
last 2 or 3 years until now. Most of it has come back to me fairly
quickly, but I was having a nightmare with this!

Thanks for your help and solution.

Tom

>> Can anyone help me on this, by showing an example like that above, but
>> using 'malloc'ed memory?
>
> A confession: I've been writing C for close to a quarter
>century, and I am still uneasy in some corners of the language.
>One of these dusty corners is the matter of multi-dimensional
>arrays; I still have to stop and think carefully (and maybe even
>consult a reference book) to decipher some array declarations.
>

Tom Reader t...@unix-manuals.com

[Tom Reader]

It certainly did help - that's exactly what I wanted to do.

Thanks very much,

Tom

>>
>> Can anyone help me on this, by showing an example like that above, but
>> using 'malloc'ed memory?
>
>Sure thing. What you want to do is something like this:
>

<-snip->
>
>
>Hope this helped,
>
>-Mark