Memory allocation/deallocation for tree? Any good way?

[Doug Gwyn]

In article <21 at christmas.UUCP> rtm at island.uu.net (Richard Minner) writes:
>First an open question:
>	How common are allocators that don't coalesce properly?

Only one implemented by a nincompoop would have trouble with this,
which was an obvious requirement as far back as the first edition
of Knuth Vol. 1.

There is no way to guarantee that arena fragmentation will not
cause some allocation request to be impossible to satisfy even
though the aggregate amount of available free store exceeds the
amount requested.  If memory would always accessed via an extra
level of indirection (what Apple calls "handles"), then garbage
collection could compact the arena and solve this problem.
However, that is not the way that the malloc()/free() interface
was designed.