[GRASS-dev] storing pointers in CELL_TYPE maps?

[Volker Wichmann]

Glynn Clements wrote:
> Volker Wichmann wrote:
> 
> > > If the list nodes are of fixed size, it's likely to be better to have
> > > a single array of nodes and uses indices to reference individual
> > > nodes.
> > 
> > that's my problem: I don't know the size of the array at compile time,
> > so I have to dynamically allocate memory. My idea was to use the GRASS
> > API to do that, but it seems I have to do this on my own. Or do you know
> > of another way?
> 
> For a variable-sized in-memory array, use G_realloc() to enlarge it as
> needed, e.g.:
> 
> 	#define SIZE_INCREMENT 50
> 	int num_nodes;
> 	int max_nodes;
> 	struct node *nodes;
> 
> 	int new_node(void)
> 	{
> 		int n = num_nodes++;
> 
> 		if (num_nodes >= max_nodes)
> 		{
> 			max_nodes += SIZE_INCREMENT;
> 			nodes = G_realloc(nodes, max_nodes * sizeof(struct node));
> 		}
> 
> 		return n;
> 	}
> 
> Bear in mind that G_realloc() may move the base of the array, so if
> you have any pointers to elements, e.g.:
> 
> 	struct node *node = &nodes[node_id];
> 
> those pointers cease to be valid after reallocation. Essentially,
> refer to nodes primarily using indices and keep the use of pointers to
> a minimum. In particular, don't store pointers to nodes within nodes.
> 
> If you need to be able to free list nodes for re-use, keep a linked
> list of free nodes and allocate from that before extending the arrary,
> e.g.:
> 
> 	struct node {
> 		int next;
> 		/* other fields */
> 	};
> 
> 	#define SIZE_INCREMENT 50
> 	int max_nodes;
> 	struct node *nodes;
> 	int free_list;
> 
> 	int new_node(void)
> 	{
> 		int n, i;
> 
> 		if (free_list > 0)
> 		{
> 			/* remove & return first node from free list */
> 			n = free_list;
> 			free_list = nodes[n].next;
> 		}
> 		else
> 		{
> 			/* enlarge array */
> 			n = max_nodes;
> 			max_nodes += SIZE_INCREMENT;
> 			nodes = G_realloc(nodes, max_nodes * sizeof(struct node));
> 			
> 			/* add unused nodes to free list */
> 			for (i = n + 1; i < max_nodes - 1; i++)
> 				nodes[i].next = i + 1;
> 			
> 			nodes[max_nodes - 1].next = 0;
> 
> 			free_list = n + 1;
> 		}
> 
> 		return n;
> 	}
> 
> 	void free_node(int n)
> 	{
> 		nodes[n].next = free_list;
> 		free_list = n;
> 	}
> 
> This is likely to be significantly more efficient than allocating
> individual list nodes with e.g. G_malloc(). Each malloc()ed block has
> a header and possibly padding, and having a large number of individual
> blocks can affect the time taken by malloc/free.
> 

Thanks a lot!!! I will give this a try,
Volker