pointers to multidimensional structs

[ajayicon]

Hi all,

I am not an expert in C..more of an algorithm developer.
One of my algorithm requires use of multidimensiona l struct.

for example something like:

struct cell{
int row;
int col;
int computation;
int super_step_row;
int super_step_col;
int super_step;
int division;
int processor;
int message ;
int valid_row;
};

the problem is when i define a multidimensiona l array for above struct as:

struct cell cell1[3000][3000]

the program worked fine for struct size less than [200][200]..but i need a size of 3000 to 40000...
there is no compile errors but when i run the pgm for higher dimensions i get buffer/stack overflow errors and pgm just hangs..

Is there any way to circumvent this...like using pointers or something??
i know little about allocating multidimensiona l arrays by using arrays of single dimension using pointers..
but am not able to apply that method here...
can somebody help me...your help is much appreciated..

Thanks

[gpraghuram]

Hi all,

I am not an expert in C..more of an algorithm developer.
One of my algorithm requires use of multidimensiona l struct.

for example something like:

struct cell{
int row;
int col;
int computation;
int super_step_row;
int super_step_col;
int super_step;
int division;
int processor;
int message ;
int valid_row;
};

the problem is when i define a multidimensiona l array for above struct as:

struct cell cell1[3000][3000]

the program worked fine for struct size less than [200][200]..but i need a size of 3000 to 40000...
there is no compile errors but when i run the pgm for higher dimensions i get buffer/stack overflow errors and pgm just hangs..

Is there any way to circumvent this...like using pointers or something??
i know little about allocating multidimensiona l arrays by using arrays of single dimension using pointers..
but am not able to apply that method here...
can somebody help me...your help is much appreciated..

Thanks

Why cant u declare somethink like this
struct cell **cell1; and then allocate memory to it dynamically.

Raghuram

[looker]

Hi all,

I am not an expert in C..more of an algorithm developer.
One of my algorithm requires use of multidimensiona l struct.

for example something like:

struct cell{
int row;
int col;
int computation;
int super_step_row;
int super_step_col;
int super_step;
int division;
int processor;
int message ;
int valid_row;
};

the problem is when i define a multidimensiona l array for above struct as:

struct cell cell1[3000][3000]

the program worked fine for struct size less than [200][200]..but i need a size of 3000 to 40000...
there is no compile errors but when i run the pgm for higher dimensions i get buffer/stack overflow errors and pgm just hangs..

Is there any way to circumvent this...like using pointers or something??
i know little about allocating multidimensiona l arrays by using arrays of single dimension using pointers..
but am not able to apply that method here...
can somebody help me...your help is much appreciated..

Thanks

Let review your algorithm first before we get on the new way!.
Your structure size is 40 bytes.
Your table is [3000][3000]
Total you confume 40 * 3000 * 3000 = 360, 000, 000 bytes = 343 MB
Imagine! your application just only launch then it allocates 342 MB in Memory! it must and you deserve a buffer over flow!.
becausse array is automatically allocated in memory when we declare it by defining it size. Furthermore, do you believe that your application needs to use all 343 MB all at once, i don't think so!. So why don't you use Single Link List ? because pointer allocates memory at only runtimes but you have to be VERY careful when using it because pointer is something we can not 100% control.

First of all, you better modify your structure.
You know how much int take from memory ? 4 byte = 32 bit right
so it can hold number from - 4294967296 to 4294967296. Let look at your structure..Do you think that the row id can be negative, impossible right ?
And one more thing, you choose int as type is more helpful for CPU because 32-bit CPU will read and write data 32 bit at a time. but i would suggest you to shorten it down a little bit because it much consume memory even though it does not need.
Let take example with the last element: valid_row
As long as i know, valid_row tell us that it is valid or invalid right ?....So there are only two available values right ? so why don't you choose boolean ?

I think it should work well as below:

typedef struct _sNodes {
Int node_id;
struct cell data;
struct cell * nextNode;
} tNodes, *Node_Ptr;

typedef struct _sNodeControlle r {
Node_Ptr head;
Node_Ptr tail;
Int number_of_node;
} tNodeController , *NodeController _Ptr;

[ajayicon]

first of all thanks for replying...

@looker

Thanks for pointing these out...i rewrote my code to reduce memory..as

struct cell
{
int row :2; //i need only from 0 t0 3000
int col :2;
int computation :2;
etc..
etc..
//and boolean for valid_row etc...(refer above code)
etc..
etc..
}

This brought down the memory size of struct to 4 bytes!!
can i bring down the struct size some more by using unsigned ints??
but its still high for [3000][3000] allocation right??or can we do something now with pointers??i need to have all the instances at a given time..so will be using all the memory at a given time :(

and frankly for my inexperience in C and linklists, I couldnot understand your last code snippets...coul d u explain more on what its doing??(anyway I have started reading more on linklists now..hope will be able to understand what u r trying to convey..)


@Raghuram..

Why cant u declare somethink like this
struct cell **cell1; and then allocate memory to it dynamically.

Raghuram

yes thats what i think i need...but how to do it??...
how do u pass the struct to functions for allocating??...


could u write me a sample code..on which i can build my own code...??atleas t i want an example to understand how it works..

i want something like how we allocate huge multidimensiona l arrays using pointers and arrays of single dimension...
is it possible in structs??

Thanks in advance...

[gpraghuram]

first of all thanks for replying...

@looker

Thanks for pointing these out...i rewrote my code to reduce memory..as

struct cell
{
int row :2; //i need only from 0 t0 3000
int col :2;
int computation :2;
etc..
etc..
//and boolean for valid_row etc...(refer above code)
etc..
etc..
}

This brought down the memory size of struct to 4 bytes!!
can i bring down the struct size some more by using unsigned ints??
but its still high for [3000][3000] allocation right??or can we do something now with pointers??i need to have all the instances at a given time..so will be using all the memory at a given time :(

and frankly for my inexperience in C and linklists, I couldnot understand your last code snippets...coul d u explain more on what its doing??(anyway I have started reading more on linklists now..hope will be able to understand what u r trying to convey..)


@Raghuram..

Why cant u declare somethink like this
struct cell **cell1; and then allocate memory to it dynamically.

Raghuram

yes thats what i think i need...but how to do it??...
how do u pass the struct to functions for allocating??...


could u write me a sample code..on which i can build my own code...??atleas t i want an example to understand how it works..

i want something like how we allocate huge multidimensiona l arrays using pointers and arrays of single dimension...
is it possible in structs??

Thanks in advance...

Let me give an example with sa small structure
[code=c]
typedef struct _test
{
int x;
char arr[10];
}Test;

Test **two_dim_str;

two_dim_str=(Te st**)malloc(siz eof(Test*)*10);
//I am assuming the first dimension and second dimension of 10.

for(lnVar=0;lnV ar<10;lnVar++)
{
two_dim_str[lnVar]=(Test*)malloc( sizeof(Test));
}

[/code]

Hope this helps....
If u need more info then post again.

Raghuram

[ajayicon]

@raghuram

thanks for posting that example..

now i have written below pgm ...plz check what is wrong in this...the o/p is not exactly what i expect

the code is:

main(){
int lnVar,i,j;
typedef struct _test{
int x ;
int y ;
int z ;
}Test;

Test **two_dim_str;
two_dim_str=(Te st**)malloc(siz eof(Test*)*10);
//I am assuming the first dimension and second dimension of 10.
for(lnVar=0;lnV ar<10;lnVar++)
{
two_dim_str[lnVar]=(Test*)malloc( sizeof(Test));
}

for(i=0;i<10;i+ +)
{ for(j=0;j<10;j+ +)
{
two_dim_str[i][j].x=i ;
two_dim_str[i][j].y=j ;
two_dim_str[i][j].z=i+j;
}
}

for(i=0;i<10;i+ +)
{ for(j=0;j<10;j+ +)
{
printf("%3d",tw o_dim_str[i][j].z);
}
printf("\n");
}
getchar();
}

the o/p i got was

0 1 1 2 2 3 3 4 4 5
1 2 2 3 3 4 4 5 6 6
2 3 3 4 4 5 5 6 6 7
...etc
etc..

but i wanted or expected o/p was

0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
4 5 6 7 8 9 10 11 12 13
5 6 7 8 9 10 11 12 13 14
etc..
etc.
ie each cell in above array should carry the value of i+j...

could u plz tell me what is wrong in my code??

Thanks

[ajayicon]

@raghuram

ok i got it!!..by some trial and error...
i think the allocation should be as:

typedef struct _test{
int x ;
int y ;
int z ;
}Test;

Test **two_dim_str;
two_dim_str=(Te st**)malloc(siz eof(Test*)*10);
two_dim_str[0]=(Test*)malloc( sizeof(Test) * 10 * 10);
//I am assuming the first dimension and second dimension of 10.
for(lnVar=0;lnV ar<10;lnVar++)
{
two_dim_str[lnVar]=two_dim_str[0]+lnVar*10;;
}

i think its based on array 2D allocation..

but my problem of buffer overflow still persists for dimensions > 1000

is there any way to overcome this overflow??

am using blood shed dev c++ and MS VS c++...

any tinkering that can allow me to assign [3000][3000] struct??

ur help is much appreciated...

Thanks...

[weaknessforcats]

OK so the struct Test has 3 ints making the size mostl likely 12 bytes. Then you have 3000x3000 of these things for a total of 108,000,000 bytes.

That should be fine.

Your 3000x3000 array is allocated by:
[code=c]
Test* array = (Test*)malloc(3 000 * 3000 * sizeof(Test));
[/code]

You can do this since C does not have multi-dimensional arrays. To make this allocaton look like a 3000x3000 array, just typecast the address returned by malloc() as the address of a Test[3000] array:
[code=c]
[code=c]
Test* array = (Test*)malloc(3 000 * 3000 * sizeof(Test));
Test (*Arr2D)[3000] = (Test(*)[3000])array;
[/code]

Now Arr2D is a 2D array of Test[3000] structs and array is still a one-dimensional array of 9000000 Test structs.

Read this:

First, there are only one-dimensional arrays in C or C++. The number of elements in put between brackets:
[code=c]
int array[5];
[/code]

That is an array of 5 elements each of which is an int.

[code=c]
int array[];
[/code]

won't compile. You need to declare the number of elements.

Second, this array:
[code=c]
int array[5][10];
[/code]

is still an array of 5 elements. Each element is an array of 10 int.

[code=c]
int array[5][10][15];
[/code]

is still an array of 5 elements. Each element is an array of 10 elements where each element is an array of 15 int.


[code=c]
int array[][10];
[/code]

won't compile. You need to declare the number of elements.

Third, the name of an array is the address of element 0
[code=c]
int array[5];
[/code]

Here array is the address of array[0]. Since array[0] is an int, array is the address of an int. You can assign the name array to an int*.

[code=c]
int array[5][10];
[/code]

Here array is the address of array[0]. Since array[0] is an array of 10 int, array is the address of an array of 10 int. You can assign the name array to a pointer to an array of 10 int:
[code=c]
int array[5][10];

int (*ptr)[10] = array;
[/code]

Fourth, when the number of elements is not known at compile time, you create the array dynamically:

[code=c]
int* array = new int[value];
int (*ptr)[10] = new int[value][10];
int (*ptr)[10][15] = new int[value][10][15];
[/code]

In each case value is the number of elements. Any other brackets only describe the elements.

Using an int** for an array of arrays is incorrect and produces wrong answers using pointer arithmetic. The compiler knows this so it won't compile this code:

[code=c]
int** ptr = new int[value][10]; //ERROR
[/code]

new returns the address of an array of 10 int and that isn't the same as an int**.

Likewise:
[code=c]
int*** ptr = new int[value][10][15]; //ERROR
[/code]

new returns the address of an array of 10 elements where each element is an array of 15 int and that isn't the same as an int***.

With the above in mind this array:
[code=cpp]
int array[10] = {0,1,2,3,4,5,6, 7,8,9};
[/code]
has a memory layout of

0 1 2 3 4 5 6 7 8 9

Wheras this array:
[code=cpp]
int array[5][2] = {0,1,2,3,4,5,6, 7,8,9};
[/code]
has a memory layout of

0 1 2 3 4 5 6 7 8 9

Kinda the same, right?

So if your disc file contains

0 1 2 3 4 5 6 7 8 9

Does it make a difference wheher you read into a one-dimensional array or a two-dimensional array? No.

Therefore, when you do your read use the address of array[0][0] and read as though you have a
one-dimensional array and the values will be in the correct locations.

[ajayicon]

@weaknessforcat s

thanks a lot for ur explanation there...
it is very informative....

am implementing those ideas now...

thanks again..