Xref: utzoo comp.unix.questions:28010 comp.lang.c:35155
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!ames!haven!adm!smoke!gwyn
From: gwyn@smoke.brl.mil (Doug Gwyn)
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: <14823@smoke.brl.mil>
Date: 11 Jan 91 22:56:18 GMT
References: <1991Jan7.034619.4449@portia.Stanford.EDU> <21@christmas.UUCP>
Followup-To: comp.unix.questions
Organization: U.S. Army Ballistic Research Laboratory, APG, MD.
Lines: 16

In article <21@christmas.UUCP> rtm@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.