Comments: Authenticated sender is From: "Alaric B. Williams" To: Eli Zaretskii Date: Sun, 22 Dec 1996 21:58:16 +0000 MIME-Version: 1.0 Content-type: text/plain; charset=US-ASCII Content-transfer-encoding: 7BIT Subject: Re: windows <-> cwsdpmi Reply-to: alaric AT abwillms DOT demon DOT co DOT uk CC: djgpp AT delorie DOT com Message-ID: <851364688.618879.0@abwillms.demon.co.uk> On 22 Dec 96 at 9:33, Eli Zaretskii wrote: > On Thu, 19 Dec 1996, Alaric B. Williams wrote: > > > an implementation of garbage collection that can be turned on at > compile time would be nice, too... > > I don't see how a garbage collecting could be built into a > general-purpose memory allocator of a C library. Since in C, every > pointer is just an address of a memory chunk, how would you relocate data > (to compact used memory) without breaking C code? IMHO, there's no > simple way to even know which pointers are unused and can be freed. > Maybe in C++, but not in C. Do I miss something? Yup, but sadly I don't have the URL for it anymore :-) Conservative GC can be used in C. It works like so: The search for accessed blocks starts with the registers, the stack, and the data segment. These are always considered "live"; to start off with, all malloced data is not considered live. For every block being searched, consider each 32 bit word. If the value is an address within a malloced block - found by walking the heap - then mark that block live and search it, unless it was live already, in which case we bottom out. Then free all non-live memory blocks. Tada! It's called conservative GC because if anything - maybe not even a pointer - seems to refer to a block, it stays. Therefore, some blocks hang around longer than they need to. But we've got to be real sure in a non-typesafe C program. ABW -- Governments are merely protection rackets with good images. Alaric B. Williams Internet : alaric AT abwillms DOT demon DOT co DOT uk http://www.abwillms.demon.co.uk/