clearing (actually, freeing) entire memory

[Joe English]

kminor at ms.uky.edu (Kevin R. Minor) writes:
>I am attempting to implement an AVL tree.  I have the insertion
>and deletion routines.  I'm using pointers to access the nodes of
>the tree.
>
>Here's my question.  Is there a way to free up the entire memory
>without having to deallocate each node?  If I can free the entire tree
>structure in one step, it will dramatically save in run-time.  Either way,
>I'd like to know for my paper.

Don't malloc() each node individually; instead
allocate a big chunk of nodes and use them one
at a time.  When you want to destroy the tree,
just free the big chunks.

Something like this should do what you want:
(Note: I just typed this in, so test it before
you try it.)

/* Blocks of nodes are mallocked and stored in a linked list; 
   The function allocate_node() returns the next available node 
   in the current block.
*/

#define NODEBLOCKSIZE some_big_number

struct nodeblock {
	struct nodeblock *prevblock;	/* last block allocated */
	struct node *nextavail;			/* ptr. to next available AVL node */
	int nodesleft;					/* #nodes left in block */
	struct node block[NODEBLOCKSIZE];	/* actual storage */
};

static nodeblock *base = 0;

struct node *allocate_node()

{
	if (!base || !base->nodesleft) {
		/* need to get another block */

		struct nodeblock *old = base;

		base = malloc(sizeof(struct nodeblock));
		if (!base) return (struct node *)0;

		base->prevblock = old;
		base->nodesleft = NODEBLOCKSIZE;
		base->nextavail = base->block;
	}

	base->nodesleft--;
	return base->nextavail++;
}

void free_all_nodes()

{
	struct nodeblock *prev;

	while (base) {
		prev = base->prevblock;
		free(base);
		base = prev;
	}
}


You might want to maintain a free list of deleted
nodes too.  You save on malloc() overhead as well
with this approach.

Hope this helps,

--Joe English

  jeenglis at nunki.usc.edu