DaniWeb Forum Index > Software Development > C

C RSS

dynamic memory allocation in a struct

Thread Solved

•

Join Date: Sep 2008

Posts: 5

Reputation: nezhad is an unknown quantity at this point

Solved Threads: 0

nezhad

Offline

Newbie Poster

dynamic memory allocation in a struct

Sep 22nd, 2008

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.

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
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.
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

•

Join Date: Sep 2004

Posts: 7,603

Reputation: Narue has a reputation beyond repute

Solved Threads: 713

Narue

Offline

Code Goddess

Re: dynamic memory allocation in a struct

Sep 22nd, 2008

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:

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
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.
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.

I'm here to prove you wrong.

•

Join Date: Sep 2008

Posts: 5

Reputation: nezhad is an unknown quantity at this point

Solved Threads: 0

nezhad

Offline

Newbie Poster

Re: dynamic memory allocation in a struct

Sep 22nd, 2008

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

•

Join Date: Sep 2004

Posts: 7,603

Reputation: Narue has a reputation beyond repute

Solved Threads: 713

Narue

Offline

Code Goddess

Re: dynamic memory allocation in a struct

Sep 22nd, 2008

>Basically, there will be no difference.
Only if you ignore the fact that you can re-size a dynamic array.

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.

I'm here to prove you wrong.

•

Join Date: Sep 2008

Posts: 5

Reputation: nezhad is an unknown quantity at this point

Solved Threads: 0

nezhad

Offline

Newbie Poster

Re: dynamic memory allocation in a struct

Sep 22nd, 2008

•

Originally Posted by 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:
Help with Code Tags

c Syntax (Toggle Plain Text)
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.
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:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
node_routing_info.paths = (path_info *) malloc (600 * sizeof(path_info));
node_routing_info	global_routing_info[30];
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

•

Join Date: Sep 2004

Posts: 7,603

Reputation: Narue has a reputation beyond repute

Solved Threads: 713

Narue

Offline

Code Goddess

Re: dynamic memory allocation in a struct

Sep 22nd, 2008

>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:

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
node_routing_info global_routing_info[30];
 
for ( i = 0; i < 30; i++ ) {
  global_routing_info[i].paths = malloc ( 600 * sizeof ( path_info ) );
 
  /* ... */
}
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.

I'm here to prove you wrong.

•

Join Date: Sep 2008

Posts: 5

Reputation: nezhad is an unknown quantity at this point

Solved Threads: 0

nezhad

Offline

Newbie Poster

Re: dynamic memory allocation in a struct

Sep 23rd, 2008

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.

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
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++;
}
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

Last edited by Ancient Dragon; Sep 24th, 2008 at 1:51 am. Reason: corrected code tags

•

Join Date: Oct 2007

Posts: 305

Reputation: stilllearning has a spectacular aura about

Solved Threads: 43

stilllearning stilllearning is offline

Offline

Posting Whiz

Re: dynamic memory allocation in a struct

Sep 24th, 2008

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;

Last edited by stilllearning; Sep 24th, 2008 at 12:40 am.

•

Join Date: Sep 2008

Posts: 3

Reputation: TooMpa is an unknown quantity at this point

Solved Threads: 1

TooMpa

Offline

Newbie Poster

Re: dynamic memory allocation in a struct

Sep 24th, 2008

do you want to make a tree with paths?

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

•

Join Date: Sep 2008

Posts: 5

Reputation: nezhad is an unknown quantity at this point

Solved Threads: 0

nezhad

Offline

Newbie Poster

Re: dynamic memory allocation in a struct

#10

Sep 24th, 2008

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