Re: Garbage Collection

[barmar@think.COM (Barry Margolin)]

In article <4050@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>A fundamental assumption
>> of manual deallocation is that when the allocator of a structure is
>> through with it, so is everyone else.  But when references to these
>> structures are passed around the references may be copied.  Unless you
>> want to require everyone to copy those structures you can't assume
>> that the allocator knows when it's safe to deallocate.
>
>     Sure I can, provided the lost art of documentation is practiced
>     from time to time...  (Gee, I sure hope I don't ever have to 
>     program with YOUR colleagues...)

I had a feeling you'd say that.  Unfortunately, at the time, I
couldn't think of a better example.  Here's one (I hope):

There are several programs running in a common address space.  Call
them COMMAND_PROCESSOR, COMPILER, and EDITOR.  There is a global data
structure, COMPILER_WARNINGS; the operations on this database include
adding warnings, selecting warnings based on various criteria, and
deleting selected warnings from the database.  COMPILER adds warnings,
as one would expect.  EDITOR has operations that make use of the data
in COMPILER_WARNINGS; for instance, you can display the warnings for
the current file and have the editor position you to the appropriate
source line.  And COMMAND_PROCESSOR has a command to clear out
COMPILER_WARNINGS (which selects all warnings and then deletes them).

The natural way to implement the COMPILER_WARNINGS database is as an
array or list of pointers to warning structures.  The ADD operation
copies the pointer it's given, and is documented so that the caller
knows not to try to deallocate the object it added.  SELECT simply
returns newly allocated pointers to the selected warnings.  DELETE
objviously should deallocate the pointer and remove it from
COMPILER_WARNINGS, but what about pointer.all?

If someone has called SELECT and it has returned a pointer to a
particular warning, DELETE should not deallocate pointer.all, because
there is another handle to it.  EDITOR should be permitted to continue
to display and manipulate selected warnings even if they've since been
deleted from the global database.

Reference counts can be used to make this work.  Every time a warning
is selected, its reference count can be incremented, and it can be
decremented when it is DELETEd, and DELETE can deallocate pointer.all
when it drops below 0.  Callers of SELECT are required to DELETE all
the selected warnings when they are done with them.  There would also
need to be a different DELETE operation to specify that it should be
removed from the COMPILER_WARNINGS database, to be used by the
COMMAND_PROCESSOR command.  But I don't think this is what you are
advocating.

Can this be solved with only documentation?  Or is this an ugly
example that only a Lisp afficionado would think is clean?

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar