dynamic memory allocation in a struct

[nezhad]

Hello;
I have 2 questions:
1- I know you can allocate memory to an array dinamically in C and C++. But, can this be done if the array is part of a structure?
2- Can the size of a dynamic array automatically grow up to a maximum or do you have to increase it when needed yourself?

This is my exact problem:
I want to have a table of a fixed number of rows like 30. These are for example nodes in a comupter network. Now, for each node, I want to keep track of the paths that it can be on. These would be in a column of the table named "paths". Each node may have hundreds of paths. So, I want to define the table as a struct and the "paths" as a big array. However, one node may end up with 300 paths and another with 2000 paths. I don't know this in advance.
Moreover, For each path, I need to keep track of the nodes that it passes through. So, each path is also defined as an array of a length let's say 10.
Below, I have specified how I am doing it now. But obviously, for large values I get an stack overflow error.

typedef struct	//A row of the global routing table 
	{
        int                     node;
	int			no_paths;
	path_info	     paths[600];	//Plan for 600 paths per node. 
	}node_routing_info;

typedef struct	
	{
	int			path_id;
	int			length;		
	int			prev_hops[10];	     //maximum 10 hops per path
	}path_info;

node_routing_info	global_routing_info[30];	//no_elem= no_nodes.

P.S: If this cannot be done with structs, how can I do it with multi-dimentional arrays?

Your help is greatly appreciated.
Thanks
Ali

[Narue]

1) Yes, you can allocate memory to a pointer regardless of it's level of indirection.
2) When you dynamically allocate memory, it's totally under your control. That means you must allocate enough memory, you must make sure it's resized properly, and you must make sure it's properly released when you're done.

>This is my exact problem
Yes, describing what you want is generally more productive.

>path_info paths[600];
If you want to use heap memory, you should make this a pointer and use malloc/calloc/realloc/free to maintain it:

typedef struct	//A row of the global routing table 
	{
        int                     node;
	int			no_paths;
	path_info	     *paths;
	}node_routing_info;

typedef struct	
	{
	int			path_id;
	int			length;		
	int			prev_hops[10];	     //maximum 10 hops per path
	}path_info;

node_routing_info	global_routing_info[30];	//no_elem= no_nodes.

If you have fixed values, a static array is fine. If you have an unknown number of values, or a maximum limit, dynamic arrays can often save you lots of space. You might also consider dynamically allocating prev_hops since it represents "up to N" hops and there might be a great many path_info objects. Since those objects will be on the heap, the stack overflow issue isn't as much of an issue, but you're still be using up memory and potentially affecting your performance.

[nezhad]

Thanks Narue;
But my problem is that I can't predict how many paths a node will have. Even if I define paths as a pointer to type path_info, I will have to allocate a certain amount of memory to it which means it will be the same for every node. So, I will have to allocate the maximum possible number of paths to each node. Basically, there will be no difference. But I guess the difference between allocating memory on the heap or on the stack prevents an stack overflow problem in your solution. I will try it.
And, yes. If I find the solution I will apply it to prev_hops too.
Ali

[Narue]

>Basically, there will be no difference.
Only if you ignore the fact that you can re-size a dynamic array. :icon_rolleyes: Start with a very small initial size and grow it by increments as you add paths. Or allocate the maximum possible size and once you've gotten all of the paths, shrink the size down to fit the actual number. Just because you don't know the number of paths before you fill the array doesn't mean you can't save space once you do know.

[nezhad]

1) Yes, you can allocate memory to a pointer regardless of it's level of indirection.
2) When you dynamically allocate memory, it's totally under your control. That means you must allocate enough memory, you must make sure it's resized properly, and you must make sure it's properly released when you're done.

>This is my exact problem
Yes, describing what you want is generally more productive.

>path_info paths[600];
If you want to use heap memory, you should make this a pointer and use malloc/calloc/realloc/free to maintain it:

typedef struct	//A row of the global routing table 
	{
        int                     node;
	int			no_paths;
	path_info	     *paths;
	}node_routing_info;

typedef struct	
	{
	int			path_id;
	int			length;		
	int			prev_hops[10];	     //maximum 10 hops per path
	}path_info;

node_routing_info	global_routing_info[30];	//no_elem= no_nodes.

If you have fixed values, a static array is fine. If you have an unknown number of values, or a maximum limit, dynamic arrays can often save you lots of space. You might also consider dynamically allocating prev_hops since it represents "up to N" hops and there might be a great many path_info objects. Since those objects will be on the heap, the stack overflow issue isn't as much of an issue, but you're still be using up memory and potentially affecting your performance.

How do I allocate memory for the paths pointer anyways? It is inside a struct. For example, in order to reserve memory for 600 paths per node, do I say:

node_routing_info.paths = (path_info *) malloc (600 * sizeof(path_info));
node_routing_info	global_routing_info[30];

Besides, should I put global_routing_info on the heap too? What happens if I don't?
Ali

[Narue]

>How do I allocate memory for the paths pointer anyways? It is inside a struct.
It doesn't matter that it's in a struct. As long as the struct objects are created, you can do whatever you want:

node_routing_info global_routing_info[30];

for ( i = 0; i < 30; i++ ) {
  global_routing_info[i].paths = malloc ( 600 * sizeof ( path_info ) );

  /* ... */
}

>Besides, should I put global_routing_info on the heap too?
I don't see any reason why you should at this point.

>What happens if I don't?
You'll have 30 node_routing_info objects on the stack. Since paths is now a pointer, that's not nearly the hit that you had before, so it shouldn't be an issue.

[nezhad]

Narue;
I would like to thank you first for your help. After that, I hope you won't find my next question stupid. Basically, I'd like to know what is wrong with the following code? global_routing_info[30] is global and visible to every thing.

typedef struct
{
int path_id;
int length;
int prev_hops[10]; //maximum 10 hops per path
}path_info;

typedef struct //A row of the global routing table
{
int node;
int no_paths;
//path_info paths[600]; //Plan for 600 paths per node.
path_info *paths
}node_routing_info;

main()
{
node_routing_info global_routing_info[30]; //no_elem= no_nodes.

int i, a_path_id;
for (i=0; i< 30 ; i++)
{
global_routing_info[i].no_paths = 0;
global_routing_info[i].paths = (path_info *) malloc ( sizeof ( path_info ) );
}

AddPath(local_id, neigh_id, local_path_id);

a_path_id = global_routing_info[22].paths[120]->path_id;
for (i=0; i<30; i++)
free (global_routing_info[i].paths);
}

void AddPath (int local_node, int neighbor, int path)
{
int no_paths;

no_paths = global_routing_info[neighbor].no_paths;

global_routing_info[neighbor].paths = (path_info *) realloc (global_routing_info[neighbor].paths, (no_paths +1)* sizeof(path_info));

global_routing_info[neighbor].paths[no_paths]->path_id = path;
global_routing_info[neighbor].no_paths++;
}

I am allocating memory for the 'paths' field of the global_routing_info structure on the heap. This area of memory would contain path_info for many paths per node. Now, I have problem accessing or referring to the elements of 'paths', such as path_id. I get this compile error:
"left hand side has type struct. Use . instead of ->"

Thanks again
Ali

[stilllearning]

To access an element of the array "paths", you need to use the notation . not ->

so its
global_routing_info[neighbor].paths[no_paths].path_id = path;

[TooMpa]

do you want to make a tree with paths?

and I would lock memory with malloc to use *path...

[nezhad]

Dear Stilllearning and TooMpa;
paths is a pointer to a memory location that I am allocating using malloc. However, this area of memory is supposed to hold an array of a struct type. This struct describes a path having a path_id, a length, ...
My problem is referring to each element of this array of structs and then accessing its path_id, ....
So, paths is not actually an array but a pointer to an array. Makes sense?
Ali

[stilllearning]

paths is a pointer, as per your definition.

path_info *paths

When you do

global_routing_info.paths = (path_info *) malloc ( sizeof ( path_info ) );

You now have an array of paths.

In order to access an element of path using the array notation [], you need to use the . not the ->

So its
global_routing_info[neighbor].paths[no_paths].path_id = path;

not

global_routing_info[neighbor].paths[no_paths]->path_id = path;

[nataraja833]

following this thread i wrote the following code

int main () {
    INST **top_inst_list ;
    int i,j;
    char string_name[100];
    printf("Enter number of insts in design\n") ;
    scanf("%d",&i);
    printf("Number of instance %d \n",i);
    top_inst_list = (INST **)malloc(sizeof(INST*)*i) ;

    printf ("hi %f \n",top_inst_list);
//  if (top_inst_list == NULL ) {
//      
//      printf ("memory allocation error bye bye \n");
//      exit(0);
//  }
    for ( j = 0; j < i;  j++ ) {
        top_inst_list[j] = (INST *)malloc(sizeof(INST));
        top_inst_list[j]->name = (char *)malloc (sizeof(char) * 10);
        top_inst_list[j]->cell->name = (char *)malloc (sizeof(char) * 5);
    }

##############

the last two lines are giving me segmentation fault can anyone tell me what is wrong with this ??

[nataraja833]

typedef i have created

typedef struct {
    char *name; 
} CELL;


typedef struct {
    CELL *cell;
    char *name;
} INST ;