Ad:

C Discussion Thread
Marked Solved
Views: 3573

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Sep 22nd, 2008

dynamic memory allocation in a struct

Expand Post »

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.

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

Similar Threads

Memory Allocation of a Struct in C++
Help with function in C++
deleting dynamic memory in C++
Double-linked list in contiguous memory. in C
Dynamic Memory Allocation in C

nezhad

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Sep 2008

Permalink

Sep 22nd, 2008

Re: dynamic memory allocation in a struct

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:

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.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Sep 22nd, 2008

Re: dynamic memory allocation in a struct

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

nezhad

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Sep 2008

Permalink

Sep 22nd, 2008

Re: dynamic memory allocation in a struct

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

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Sep 22nd, 2008

Re: dynamic memory allocation in a struct

Click to Expand / Collapse Quote 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:
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:

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

nezhad

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Sep 2008

Permalink

Sep 22nd, 2008

Re: dynamic memory allocation in a struct

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

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.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Sep 23rd, 2008

Re: dynamic memory allocation in a struct

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.

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

nezhad

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Sep 2008

Permalink

Sep 24th, 2008

Re: dynamic memory allocation in a struct

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.

stilllearning

Reputation Points: 161

Solved Threads: 43

Posting Whiz

Offline

309 posts
since Oct 2007

Permalink

Sep 24th, 2008

Re: dynamic memory allocation in a struct

do you want to make a tree with paths?

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

TooMpa

Reputation Points: 10

Solved Threads: 1

Newbie Poster

Offline

7 posts
since Sep 2008

Permalink

Sep 24th, 2008

Re: dynamic memory allocation in a struct

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

nezhad

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Sep 2008

Page 1
2
Next

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: getimage and putimage funtions

Next Thread in C Forum Timeline: linked lists

DaniWeb Message

Cancel Changes

User Name
Password