Dynamically growing an array (pointer question)

[Fabian Wauthier]

Hi list,

I am trying to dynamically grow a 2 dimensional array (Atom ***Screen) of
pointers to a struct Atom (i.e. the head of a linked list). I am not
sure if this is the right way to do it:

/* Allocate 1st dimension */

if((Screen = (Atom ***) malloc(sizeof(Atom **) * Width)) == NULL)
perrexit("malloc");

/* Allocate 2nd dimension */

for(i = 0; i < Width; i++)
if((Screen = (Atom **) malloc(sizeof(Atom *) * Height)) == NULL)
perrexit("malloc");

/* Set Screen all NULL initially */

for(i = 0; i < Width; i++)
for(j = 0; j < Height; j++)
Screen[j] = NULL; /* Can I do this? */

Can I then access Screen using normal Array subscript notation?

I keep getting strange behaviour in another part of the program, and
I'm not sure if this is the problem.

I hope this wasn't to verbose.

Thanks for any pointers.

Fabian

 

[Jens.Toerring]

I am trying to dynamically grow a 2 dimensional array (Atom ***Screen) of
pointers to a struct Atom (i.e. the head of a linked list). I am not
sure if this is the right way to do it:

/* Allocate 1st dimension */

if((Screen = (Atom ***) malloc(sizeof(Atom **) * Width)) == NULL)
perrexit("malloc");

/* Allocate 2nd dimension */

for(i = 0; i < Width; i++)
if((Screen = (Atom **) malloc(sizeof(Atom *) * Height)) == NULL)
perrexit("malloc");

/* Set Screen all NULL initially */

for(i = 0; i < Width; i++)
for(j = 0; j < Height; j++)
Screen[j] = NULL; /* Can I do this? */

Can I then access Screen using normal Array subscript notation?

I keep getting strange behaviour in another part of the program, and
I'm not sure if this is the problem.

I guess you know that you don't have a real 2-dimensional array here,
you're "faking" one by having an array of pointers, each pointing to
an array of Atom structure pointers and use that with the declaration

SOME_TPYE **a;

the expression "a[j]" is evaluated as "*(*(a+i)+j)" to be able to
empoy the normal array subscript notation for something that isn't a
2-dimensional C array. So you won't, for example, be able to use the
sizeof operator on that "array" and get the same results as with a
real array. And you won't be able to use functions written for use
with a real 2-dimensional C array of Atom pointers (they'd expect an
Atom** and not an Atom***). But as long as you keep that in mind your
use of 'Screen' with the notation for 2-dimensional arrays looks ok.

BTW, you can save a lot of calls of malloc() (and later of free()) if
you allocate the whole set of Atom pointers a once like this:

if ( ( *Screen = malloc( Width * Height * sizeof **Screen ) ) == NULL )
perrexit( "malloc" );

for ( i = 1; i < Width; i++ )
Screen[ i ] = Screen [ i - 1 ] + Height;

Regards, Jens

 

[Leor Zolman]

BTW, you can save a lot of calls of malloc() (and later of free()) if
you allocate the whole set of Atom pointers a once like this:

if ( ( *Screen = malloc( Width * Height * sizeof **Screen ) ) == NULL )
perrexit( "malloc" );

If the OP has defined Screen as he indicated, via:
Atom ***Screen;
then, at the very least, I do not think you want that asterisk in front of
'Screen' up there.

After your single malloc, you've got a pointer (Screen) to a 2D matrix of
atom pointers; you no longer have the situation where Screen points to the
first element of an "array of arrays of atom pointers" as in the OP's
scenario, so whatever you're doing down below, I don't see how it can be
healthy:

for ( i = 1; i < Width; i++ )
Screen[ i ] = Screen [ i - 1 ] + Height;

Regards, Jens

Since the OP mentioned he wants to "dynamically grow" the array, rather
than just dynamically /allocating/ it, he'd need the array of pointer to
arrays in order to, say, grow the Height but not the Width. I have no
idea if that's what he really wants to do or not, but it's another thing
that would be difficult with the "one malloc fits all" approach rather
than allocating the columns piecemeal as he did.
-leor

 

[Jens.Toerring]

If the OP has defined Screen as he indicated, via:
Atom ***Screen;
then, at the very least, I do not think you want that asterisk in front of
'Screen' up there.

After your single malloc, you've got a pointer (Screen) to a 2D matrix of
atom pointers; you no longer have the situation where Screen points to the
first element of an "array of arrays of atom pointers" as in the OP's
scenario, so whatever you're doing down below, I don't see how it can be
healthy:

for ( i = 1; i < Width; i++ )
Screen[ i ] = Screen [ i - 1 ] + Height;

Sorry, I meant the OP to keep the first allocation of the array of
pointers to Atom pointers:

if ( ( Screen = malloc( Width * sizeof *Screen ) ) == NULL )
perrexit( "malloc" );

and only then to allocate memory for the arrays of Atom pointers all at
once, initializing Screen[0] (aka *Screen) with that pointer and finally
setting up the rest of the pointers, making them point into that memory
region.

Since the OP mentioned he wants to "dynamically grow" the array, rather
than just dynamically /allocating/ it, he'd need the array of pointer to
arrays in order to, say, grow the Height but not the Width. I have no
idea if that's what he really wants to do or not, but it's another thing
that would be difficult with the "one malloc fits all" approach rather
than allocating the columns piecemeal as he did.

That's correct, of course. I made the mistake of interpreting "dynami-
cally grow" to mean allocate dynamically (as opposed to creating a true
2-dimensional array with fixed sizes). If the OP really wants to be able
to change the sizes dynamically afterwards there's obviously no way
around allocating each array of pointers to Atom pointers of size
'Height' individually. Sorry for the confusion and thanks for pointing
that out.
Regards, Jens

 

[Al Bowers]

Hi list,

I am trying to dynamically grow a 2 dimensional array (Atom ***Screen) of
pointers to a struct Atom (i.e. the head of a linked list). I am not
sure if this is the right way to do it:

/* Allocate 1st dimension */

if((Screen = (Atom ***) malloc(sizeof(Atom **) * Width)) == NULL)
perrexit("malloc");

/* Allocate 2nd dimension */

for(i = 0; i < Width; i++)
if((Screen = (Atom **) malloc(sizeof(Atom *) * Height)) == NULL)
perrexit("malloc");

/* Set Screen all NULL initially */

for(i = 0; i < Width; i++)
for(j = 0; j < Height; j++)
Screen[j] = NULL; /* Can I do this? */

Can I then access Screen using normal Array subscript notation?

I keep getting strange behaviour in another part of the program, and
I'm not sure if this is the problem.

The faq offers various methods of creating the 2d array at:
http://www.eskimo.com/~scs/C-faq/q6.16.html

The allocations and assignments look ok here for an initial
allocation. Perhaps the source of the strange behavior is
somewhere else. Dynamic growing, reallocating, deallocating this 2d
array of pointers to linked lists can be tricky.

Function ReallocScreen below and the datatype Screen is one
way you may approach this code.

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

typedef struct Atom
{
unsigned value;
struct Atom *next;
} Atom;

typedef struct Screen
{
Atom ***screen;
unsigned Width;
unsigned Height;
} Screen;
/* Prototypes */
int AddLINK( Screen *p,unsigned Welement, unsigned Helement,
unsigned value);
void PrintLINK(Screen *p, unsigned Welement, unsigned Helement);
void FreeLINK(Atom **p);
void FreeScreen(Screen *p);
int ReallocScreen(Screen *p, unsigned Width, unsigned Height);

int main(void)
{
Screen my = {NULL};

if(ReallocScreen(&my, 5,6)) /* 5x6 array of Atom pointers */
{
puts("Allocated an [5][6] array of pointers");
AddLINK(&my, 0, 0, 52);
AddLINK(&my, 0, 0,100);
AddLINK(&my,1, 0,200);
AddLINK(&my, 1, 0,300);
PrintLINK(&my,0,0);
PrintLINK(&my,1,0);
}
if(ReallocScreen(&my,1,1))
{
puts("\nReallocated the array[1][1] to check "
"if values changed\n");
PrintLINK(&my,0,0);
PrintLINK(&my,1,0);
puts("Element [1][0] and linked list has been deallocated");
}
FreeScreen(&my);
return 0;
}

int AddLINK( Screen *p,unsigned Welement, unsigned Helement,
unsigned value)
{
Atom *tmp;

if(Welement > p->Width || Helement > p->Height ||
(tmp = malloc(sizeof *tmp)) == NULL) return 0;
tmp->value = value;
tmp->next = p->screen[Welement][Helement];
p->screen[Welement][Helement] = tmp;
return 1;
}

void PrintLINK(Screen *p, unsigned Welement, unsigned Helement)
{
Atom *tmp;

if(Welement < p->Width && Helement < p->Height)
{
tmp = p->screen[Welement][Helement];
printf("Screen[%u][%u]: ",Welement,Helement);
for( ; tmp; tmp = tmp->next)
printf("%u -> ",tmp->value);
puts("NULL(End of Linked List)");
}
return;
}

void FreeLINK(Atom **p)
{
Atom *tmp;

for( ; *p; *p = tmp)
{
tmp = (*p)->next;
free(*p);
}
return;
}

void FreeScreen(Screen *p)
{
unsigned i,j;

for(i = 0;i < p->Width; i++)
for(j = 0; j < p->Height; j++)
FreeLINK(&p->screen[j]);
if(p->screen)
{
free(p->screen[0]);
free(p->screen);
}
p->screen = NULL;
p->Height = p->Width = 0;
return;
}

int ReallocScreen(Screen *p, unsigned Width, unsigned Height)
{
unsigned i,j;
Atom ***tmp;

tmp = malloc(Width * (sizeof *tmp));
if(!tmp) return 0;
tmp[0] = malloc(Width * Height * (sizeof **tmp));
if(!tmp[0])
{
free(tmp);
return 0;
}
for(i = 1; i < Width; i++)
tmp = tmp[0] + i * Height;
for(i = 0; i < Width; i++)
for(j = 0; j < Height;j++)
{
if(i < p->Width && j < p->Height)
tmp[j] = p->screen[j];
else
tmp[j] = NULL;
}
for( ; i < p->Width;i++)
for(j = 0 ; j < p->Height; j++)
FreeLINK(&p->screen[j]);
if(p->screen)
{
free(p->screen[0]);
free(p->screen);
}
p->screen = tmp;
p->Width = Width;
p->Height = Height;
return 1;
}

 

[Barry Schwarz]

Hi list,

I am trying to dynamically grow a 2 dimensional array (Atom ***Screen) of
pointers to a struct Atom (i.e. the head of a linked list). I am not
sure if this is the right way to do it:

/* Allocate 1st dimension */

if((Screen = (Atom ***) malloc(sizeof(Atom **) * Width)) == NULL)

Lose the cast. The only thing it does is prevent the compiler for
telling you that you forgot to include stdlib.h. You would like to
know if that is the case since your code would invoke undefined
behavior in C89.

If for some reason you ever decide to change the type of Atom, you
would have to update all the sizeof operands. For this reason, most
in this group recommend
if ((Screen = malloc(Width * sizeof *Screen)) = NULL)

perrexit("malloc");

/* Allocate 2nd dimension */

for(i = 0; i < Width; i++)
if((Screen = (Atom **) malloc(sizeof(Atom *) * Height)) == NULL)
perrexit("malloc");

Here it would be
if ((Screen = malloc(Height * sizeof *Screen)) == NULL)

/* Set Screen all NULL initially */

for(i = 0; i < Width; i++)
for(j = 0; j < Height; j++)
Screen[j] = NULL; /* Can I do this? */

Yes. Screen[j] is a pointer.

Can I then access Screen using normal Array subscript notation?

Yes, as long as you remember that Screen[j] is a pointer and not a
struct.

I keep getting strange behaviour in another part of the program, and
I'm not sure if this is the problem.

Without the code, it is like playing roulette. I bet the problem is
on line 42.


<<Remove the del for email>>

 

[Fabian Wauthier]

Hi list,

I am trying to dynamically grow a 2 dimensional array (Atom ***Screen) of
pointers to a struct Atom (i.e. the head of a linked list). I am not
sure if this is the right way to do it:

/* Allocate 1st dimension */

if((Screen = (Atom ***) malloc(sizeof(Atom **) * Width)) == NULL)

Lose the cast. The only thing it does is prevent the compiler for
telling you that you forgot to include stdlib.h. You would like to
know if that is the case since your code would invoke undefined
behavior in C89.

If for some reason you ever decide to change the type of Atom, you
would have to update all the sizeof operands. For this reason, most
in this group recommend
if ((Screen = malloc(Width * sizeof *Screen)) = NULL)

perrexit("malloc");

/* Allocate 2nd dimension */

for(i = 0; i < Width; i++)
if((Screen = (Atom **) malloc(sizeof(Atom *) * Height)) == NULL)
perrexit("malloc");

Here it would be
if ((Screen = malloc(Height * sizeof *Screen)) == NULL)

/* Set Screen all NULL initially */

for(i = 0; i < Width; i++)
for(j = 0; j < Height; j++)
Screen[j] = NULL; /* Can I do this? */

Yes. Screen[j] is a pointer.

Can I then access Screen using normal Array subscript notation?

Yes, as long as you remember that Screen[j] is a pointer and not a
struct.

Yes, I use this screen to hold a new ordering of Atoms (which I
allocated in a seperate step). On each run, the Screen array is
cleared and the atoms newly ordered into the Screen array as linked
lists.

Without the code, it is like playing roulette. I bet the problem is
on line 42.

Hi Barry and all,

Thanks everyone for your help, and pointers. I think I'll comment much
more code, and see what's left then.

Cheers,
Fabian

 

[Fabian Wauthier]

On 11 Apr 2004 20:51:36 +0100, Fabian Wauthier

[...]


Yes. Screen[j] is a pointer.

Can I then access Screen using normal Array subscript notation?

Yes, as long as you remember that Screen[j] is a pointer and not a
struct.

I actually used the Screen array only to hold an ordering of Atoms
(which I allocated and hold in a seperate array). I basically want to
check whether two Atoms share same x/y values (cast to int). Using the
Screen with x/y as indexes should work much faster than using two
nested for-loops.

There is in fact no real need for a totally dynamic 2d array (as I
probably implied). I just want to build one on startup.

So I guess Jens' solution could do the trick.

Without the code, it is like playing roulette. I bet the problem is
on line 42.

Thanks for all your help and pointers. I'll make the changes you
suggested comment much more code and see what happens.

Cheers, Fabian