[GRASS-dev] storing pointers in CELL_TYPE maps?

[Glynn Clements]

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.

-- 
Glynn Clements <glynn at gclements.plus.com>