Xref: utzoo comp.unix.questions:27903 comp.lang.c:35081
Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!clyde.concordia.ca!ccu.umanitoba.ca!salomon
From: salomon@ccu.umanitoba.ca (Dan Salomon)
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: <1991Jan7.161216.29729@ccu.umanitoba.ca>
Date: 7 Jan 91 16:12:16 GMT
References: <1991Jan7.034619.4449@portia.Stanford.EDU>
Distribution: comp
Organization: University of Manitoba, Winnipeg, Canada
Lines: 41

In article <1991Jan7.034619.4449@portia.Stanford.EDU> fangchin@portia.Stanford.EDU (Chin Fang) writes:
>
> The problem I had (and still having) was how to keep the program's
> memory consumption almost constant.  From what I understand, if my
> malloc(3C) and free3(C) work correctly, as long as I make sure that
> a sequence of malloced memory blocks are freed in EXACTLY the reverse 
> order, my program's memory consumption would stay constant no matter
> how many iterations it goes thru.  This has been my guideline in my
> coding.  By the way, I always do C programming on UNIX machines.  

What you can do is add an extra pointer to the binary tree nodes
to form a linked list that records the order of allocation.

Ptr-to-Head-of-Allocation-List
    |
    |
    V
-------------------------------------------------------
| Data  |  left-subtree | right-subtree | new-pointer |
-------------------------------------------------------
                                                  |
						  |
						  V
			             To node allocated just 
				     before this one.

Every time you allocate a tree node, also add it to the FRONT of the
linked list recording allocations.  Thus the linked list will
be in order of most recent allocation first, oldest allocation last.
As a result it is easy to free the nodes from front to back.

Note that each node is in two data structures simultaneously,
the tree data structure, and the allocation data structure.
Since the data structures are accessed through different
pointers, they do not interfere with each other.

-- 

Dan Salomon -- salomon@ccu.UManitoba.CA
               Dept. of Computer Science / University of Manitoba
	       Winnipeg, Manitoba, Canada  R3T 2N2 / (204) 275-6682