Xref: utzoo comp.unix.questions:27934 comp.lang.c:35102
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!motcid!mostek
From: mostek@motcid.UUCP (Frank B. Mostek)
Newsgroups: comp.unix.questions,comp.lang.c
Subject: Re: Memory allocation/deallocation for tree? Any good way?
Keywords: tree, cache, malloc, free, tree-deletion, memory consumption
Message-ID: <5522@beryl12.UUCP>
Date: 8 Jan 91 21:01:28 GMT
References: <1991Jan7.034619.4449@portia.Stanford.EDU>
Distribution: comp
Organization: Motorola Inc., Cellular Infrastructure Div., Arlington Heights, IL
Lines: 75

fangchin@portia.Stanford.EDU (Chin Fang) writes:

>Hi everyone,
> 
>...
>while (some conditions are true){

>    get raw data from somewhere;

>    form certain matrices and put them into nodes of a RB tree;

>    perform some FP ops, go to the tree first to see if required matrices
>    are available.  (They should, my algorithm guarantee this);

>    distory the tree and release all memory (in the right order);

>}

>exit program

>Given this situation, could someone give me some suggestions for 
>a better way of handling tree structure memory management? I don't
>think the order tracking list that I am using is a good enough one.
>and I believe there is still some memory leak somewhere as I can see
>from the output of ps(1) (SZ term was growing).

In one of my compilers I cleaned up allocated memory that was
transparent to the data structures. (Since the compiler was using
several different ones.)  I wrote a general memory allocation routine,
and inside this routine I built a linked list of allocated memory.
When I wanted to clean up, I simply checked for the type field, and
freed up all the memory in a tree, stack, etc...

In your case, you don't even have to keep track of the data structure.

I don't have the code handy, but its something like this:

struct alloced_mem {
  char* p;
  struct alloced_mem *next;
} mem_list;

void *allocate_memory(size)
unsigned size;
{
	char *p;

	p = malloc(size);
	if (p == null) err();

	/* Add node to alloced_mem list, Add to beginning of list */
	add_node_to_mem_list(p); /* Don't call allocate_memory! */
	return (void *)p;
}

Note: Cast the call to allocate_memory i.e:
tree = (struct tree*)allocate_memory(sizeof(struct tree));

Then to free it up:

void free_tree()
{
	while (mem_list != NULL)
	{
		free(mem_list);
		free(mem_list->p);
		mem_list = mem_list->next;
	}
}

This is kind of rough.  If you think this may help, I can dig up
the actual code and send it to you.

Frank Mostek - uunet!motcid!amethyst!mostek
Don't need no steenkin .signature file.