Dynamic 2D array

[I wish]

I found someone wrote this code

int **array2, nrows, ncolumns, i;

scanf( "%d %d", &nrows, &ncolumns );

array2 = malloc(nrows*sizeof(int *) + nrows*ncolumns*sizeof(int));
for(i = 0; i < nrows; i++ )
array2 = (int *)array2 + nrows + i * ncolumns;

This can decrease malloc times to just once.

It it legal? I think the code assume the sizeof( int ) is equal to

sizeof( int * ), then the code may not be portable.

--
|
___
(-_-)
<| |>---------------------------------- ShepJeng.twbbs.org -------------
/ cherry.cs.nccu.edu.tw

 

[Peter Nilsson]

I found someone wrote this code

int **array2, nrows, ncolumns, i;

scanf( "%d %d", &nrows, &ncolumns );

array2 = malloc(nrows*sizeof(int *) + nrows*ncolumns*sizeof(int));
for(i = 0; i < nrows; i++ )
array2 = (int *)array2 + nrows + i * ncolumns;

This can decrease malloc times to just once.

It it legal?

It's not strictly conforming no.

I think the code assume the sizeof( int ) is equal to
sizeof( int * ), then the code may not be portable.

It assumes that sizeof(int) divides sizeof(int *). Fortunately you can take care of this
by adding any necessary padding...

size_t iz = sizeof(int); /* int size */
size_t r = ncolumns * iz; /* row of int size */
size_t p = nrows * sizeof(int *); /* row pointer table size */
size_t np = (p + iz - 1) / iz * iz; /* normalised table size */
size_t m = nrows * r; /* matrix size */

void *v = malloc(np + m); /* allocate table (+ padding) + matrix */
int **a = v;

if (a)
for (i = 0; i < nrows; i++)
a = (int *) ( (char *) v + np + i * r );

You can be more rigorous avoiding overflow of size_t values, but that's basically it.

 

[Prawit Chaivong]

I found someone wrote this code

int **array2, nrows, ncolumns, i;

scanf( "%d %d", &nrows, &ncolumns );

array2 = malloc(nrows*sizeof(int *) + nrows*ncolumns*sizeof(int));
for(i = 0; i < nrows; i++ )
array2 = (int *)array2 + nrows + i * ncolumns;

This can decrease malloc times to just once.

It it legal? I think the code assume the sizeof( int ) is equal to

sizeof( int * ), then the code may not be portable.

I don't know whether it's legal or not. But what gonna happen if your
program want to adjust amount of column. And I think it much more
expensive to reallocate the whole array if it's huge array. Or you may
say, Let change array2 to pointed to next column and so on (in case
of remove some column). The column that you ignored would be unused
anyway (at lease until you free your array2).

Moreover if you want to add new column. What you gonna do.
Thinking twice before do that.

Regards,
Prawit Chaivong

 

[Joe Wright]

I found someone wrote this code

int **array2, nrows, ncolumns, i;

scanf( "%d %d", &nrows, &ncolumns );

array2 = malloc(nrows*sizeof(int *) + nrows*ncolumns*sizeof(int));
for(i = 0; i < nrows; i++ )
array2 = (int *)array2 + nrows + i * ncolumns;

This can decrease malloc times to just once.

It it legal? I think the code assume the sizeof( int ) is equal to

sizeof( int * ), then the code may not be portable.

I have done something like this before and it worked for me. The
assumption that it makes is about alignment. It assumes that the
address (array2 + nrows) is suitably aligned for int. It is on my
machines and probably yours but the Standard is quiet on the subject
and portability is not assured.

 

[Anirudh]

I found someone wrote this code

int **array2, nrows, ncolumns, i;

scanf( "%d %d", &nrows, &ncolumns );

array2 = malloc(nrows*sizeof(int *) + nrows*ncolumns*sizeof(int));
for(i = 0; i < nrows; i++ )
array2 = (int *)array2 + nrows + i * ncolumns;

This can decrease malloc times to just once.

It it legal?

It's not strictly conforming no.

I think the code assume the sizeof( int ) is equal to
sizeof( int * ), then the code may not be portable.

It assumes that sizeof(int) divides sizeof(int *). Fortunately you can take care of this
by adding any necessary padding...

size_t iz = sizeof(int); /* int size */
size_t r = ncolumns * iz; /* row of int size */
size_t p = nrows * sizeof(int *); /* row pointer table size */
size_t np = (p + iz - 1) / iz * iz; /* normalised table size */
size_t m = nrows * r; /* matrix size */

void *v = malloc(np + m); /* allocate table (+ padding) + matrix */
int **a = v;

if (a)
for (i = 0; i < nrows; i++)
a = (int *) ( (char *) v + np + i * r );

You can be more rigorous avoiding overflow of size_t values, but that's basically it.

I understand the problem that could be caused because sizeof(int)
not being equal to sizeof(int*), but I did not understand your
solution. I tried it out on a toy example: Assume sizeof(int) = 3
units(bytes), sizeof(int*) = 2 units; you want an array of size 2x2.
Then, iz = 3; r = 6; p = 4; np = 0 (integer part); m = 12.
So you are allocating 12 bytes totally (m + np)...while you need
atleast 12 (= 3 * 4) + 4 ( for the two int* s) in reality...is this
reasoning wrong?
In the post by I wish, the method he'd suggested would work with
the following scheme:

for(i = 0; i < nrows; i++ )
array2 = (int *)array2 + nrows + i * ncolumns;

Instead of the above line, write
array2 = (int*)(array2 + nrows) + i * ncolumns;

Please correct...


thanks,
Anirudh

 

[Peter Nilsson]

"Peter Nilsson" <[email protected]> wrote in message

size_t iz = sizeof(int); /* int size */
size_t r = ncolumns * iz; /* row of int size */
size_t p = nrows * sizeof(int *); /* row pointer table size */
size_t np = (p + iz - 1) / iz * iz; /* normalised table size */
size_t m = nrows * r; /* matrix size */

void *v = malloc(np + m); /* allocate table (+ padding) + matrix */
int **a = v;

if (a)
for (i = 0; i < nrows; i++)
a = (int *) ( (char *) v + np + i * r );

I understand the problem that could be caused because sizeof(int)
not being equal to sizeof(int*), but I did not understand your
solution. I tried it out on a toy example: Assume sizeof(int) = 3
units(bytes), sizeof(int*) = 2 units; you want an array of size 2x2.
Then, iz = 3; r = 6; p = 4; np = 0 (integer part); m = 12.

Almost; np will be...

(p + iz - 1) / iz * iz
(4 + 3 - 1) / 3 * 3
6 / 3 * 3
2 * 3
6

So you are allocating 12 bytes totally (m + np)...

Nope, I'm allocating 18 bytes: 4 for the pointers, 12 for matrix elements and 2 extra
bytes of padding between them.

 

[Anirudh]

Almost; np will be...

(p + iz - 1) / iz * iz
(4 + 3 - 1) / 3 * 3
6 / 3 * 3
2 * 3
6

Silly me. :-(


Anirudh