Pointers, structs and memory allocations

[Christian F]

Hi, I'm a C-newbie and I would like to know if I am doing something
wrong in the code below. It is working, but I'm afraid it might not be
correct because I don't really understand everything of it. There are
lots of pointers and pointers to pointers which makes me confused.

First my typedef:

typedef struct
{
double re;
double im;
} cplx;

What I need to do first is to allocate memory to hold N pointers to
cplx. I do it with this statement (correct or not?):

cplx **data = (cplx **)malloc(sizeof(cplx *) * N);
if(!data) { /* malloc failed */ ... }

Next I need to malloc space for each struct in the list and fill it
with data. This is what I do (correct or not?):

for(i = 0; i < N; i++)
{
data[i] = (cplx *)malloc(sizeof(cplx));
data[i]->re = i; /* fill with testdata */
data[i]->im = N - i - 1; /* fill with testdata */
}

Then I will call a rearrange-function to rearrange the _pointers_ and
_not_ the data in the array. The function looks like this:

void rearrange(cplx **data, int n_elements)
{
cplx *tmp;
int i;

/* reverse the data */
for(i = 0; i < (n_elements / 2); i++)
{
tmp = data[i];
data[i] = data[n_elements - i - 1];
data[n_elements - i - 1] = tmp;
}
}

I call this function from main() the following way (correct or not?):

rearrange(data, N);

And finally clean up the memory (correct or not?):

for(i = 0; i < N; i++)
free(data[i]);

free(**data);

Finally, is this the right approach if you got a large list of structs
to be rearranged? I guess it's much faster swapping pointers than
swapping the entire data in the structs?

[Nils Petter Vaskinn]

On Tue, 11 Nov 2003 05:28:31 -0800, Christian F wrote:

typedef struct
{
double re;
double im;
} cplx;
cplx **data = (cplx **)malloc(sizeof(cplx *) * N); if(!data) { /* malloc
failed */ ... }
Don't cast malloc. It can hide errors, if you've included stdlib.h the
casting is unnesseary.

for(i = 0; i < N; i++)
{
data[i] = (cplx *)malloc(sizeof(cplx));
Again don't cast malloc.
data[i]->re = i; /* fill with testdata */ data[i]->im = N - i - 1; /*
fill with testdata */
}
And finally clean up the memory (correct or not?):

for(i = 0; i < N; i++)
free(data[i]);
Correct.

free(**data);
Not! use:
free(data);

Finally, is this the right approach if you got a large list of structs
to be rearranged? I guess it's much faster swapping pointers than
swapping the entire data in the structs?

Probably yes, if the goal is speed.

Otoh this requires sizeof(cplx*) * N
bytes of extra memory. If N is suficciently large that may be what pushes
your program over the edge to using swap space, resulting in lower overall
speed.
But for most cases the size of the pointerarray would be overshadowed by
the size of the struct so I wouldn't worry about it. But if you vere
reversing an array of ints the pointer array would be a waste.

--
NPV

"the large print giveth, and the small print taketh away"
Tom Waits - Step right up

[Nils Petter Vaskinn]

On Tue, 11 Nov 2003 14:04:06 +0000, Nils Petter Vaskinn wrote:

On Tue, 11 Nov 2003 05:28:31 -0800, Christian F wrote:

Finally, is this the right approach if you got a large list of structs
to be rearranged? I guess it's much faster swapping pointers than
swapping the entire data in the structs?

Probably yes, if the goal is speed.

Just struck me:

For an array of pointers you do N mallocs and 2N copy operations on
pointers.

For an arrray of structs you do 1 malloc (sizeof(cplx)*N) and 2N copy
operations on the struct data.

In this case it all comes down to the speed of your malloc implementation
vs the speed of the copy operations.

Another alternative:

cplx *realData = malloc(sizeof(cplx)*N);
cplx **data = malloc(sizeof(cplx*)*N);

for(int i=0; i<N; ++i) {
data[i] = realData + i;
}

This gives 2 malloc operations and 3N copy operations on pointers.
The way to know which is faster is to profile all three.

--
NPV

"the large print giveth, and the small print taketh away"
Tom Waits - Step right up

[Zoran Cutura]

Christian F <kh***@telia.com> wrote:

Hi, I'm a C-newbie and I would like to know if I am doing something
wrong in the code below. It is working, but I'm afraid it might not be
correct because I don't really understand everything of it. There are
lots of pointers and pointers to pointers which makes me confused.

First my typedef:

typedef struct
{
double re;
double im;
} cplx;
Though the above is syntactically correct, IMHO it brings you no good.
Hiding structs behind typedefs is only a good idea if the struct needs
to be camouflaged somehow. That is, programs use an abstract type they
do not have to know in depth (like for example the type FILE).

It is arguable that a complex-type should be abstracted to the user, but
on the other hand it should not for the part of the program that works
with the contents of such a struct.

I usually stick to the conservative

struct cplx {...};

..

What I need to do first is to allocate memory to hold N pointers to
cplx. I do it with this statement (correct or not?):

cplx **data = (cplx **)malloc(sizeof(cplx *) * N);
Casting malloc is a no no, especially in this newsgroup. If you have the
appropriate prototype for malloc in place, there is no need to cast its
return value at all. malloc returns a generic pointer, which can be
converted without a cast to any other object pointer type. So if you are
getting diagnostic messages from you compiler, that is rather due to
failure to include tha correct header file (stdlib.h), that to a missing
cast.

Some people argue that in C++ you'ld need cast mallocs return value, but
who would ever want to compile a C program with a C++ compiler? And if
one is programming in C++, why would one use malloc at all? ...

Also I recommend to apply sizeof to an object rather than a type, so
when you change the type of data, there will be no need to change the
malloc call:

struct cplx **data = malloc(sizeof *data * N);

Btw, if N is meant to be constant, I don't see the need to use malloc
at all, but I think this is going to be a parameter of some kind.

if(!data) { /* malloc failed */ ... }

Next I need to malloc space for each struct in the list and fill it
with data. This is what I do (correct or not?):

for(i = 0; i < N; i++)
{
data[i] = (cplx *)malloc(sizeof(cplx));
As explained above:
data[i] = malloc(sizeof *data[i]);
data[i]->re = i; /* fill with testdata */
data[i]->im = N - i - 1; /* fill with testdata */
}

Then I will call a rearrange-function to rearrange the _pointers_ and
_not_ the data in the array. The function looks like this:

void rearrange(cplx **data, int n_elements)
{
cplx *tmp;
int i;

/* reverse the data */
for(i = 0; i < (n_elements / 2); i++)
{
tmp = data[i];
data[i] = data[n_elements - i - 1];
data[n_elements - i - 1] = tmp;
}
}

I call this function from main() the following way (correct or not?):

rearrange(data, N);

And finally clean up the memory (correct or not?):

for(i = 0; i < N; i++)
free(data[i]);
That is ok!

free(**data);
But this one is not. Guess why!

free(data);

Finally, is this the right approach if you got a large list of structs
to be rearranged? I guess it's much faster swapping pointers than
swapping the entire data in the structs?

It depends one the size of the list. It is probably the right approach
for lists that are pretty short (like less than say 1000 elements). At
some point you may recognize that there need to be better ways of doing,
but that is another story... which is better discussed elsewhere.
--
Z (Zo**********@daimlerchrysler.com)
"LISP is worth learning for the profound enlightenment experience
you will have when you finally get it; that experience will make you
a better programmer for the rest of your days." -- Eric S. Raymond