Re: hash tables and GC

[Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>]

> Date: Fri, 22 Jul 88 10:00:21 PDT
> From: John Rose <jrose@com.sun>

> Sometimes that's "OK", sometimes not.  For example, if a hash table is
> being used as a relational database (with a primary key indexed by the
> hash table), you probably don't want tuples therein to be GC-able.

True.  There are cases where the "independent reference" is in the
user's head.  Some value has been associated with a string key, say,
and it should remain in case the user types it again.  So, I'm not
whether "weak retention" makes sense for EQUAL tables; but perhaps
it does nonetheless.

> Therefore, it's wise not to present them as hash tables.

I don't mind calling them something else.

> Similarly, if hash table keys are being used to store information,
> as well as merely access it, they shouldn't be GC-ed.

The question is whether you have any way of getting that key object.
If nothing has a pointer to X, there's no way to know X exists much
less that it's in some table.  (I'm thinking EQ here.)

> Putting weak links to keys in hash tables would make the EQUAL semantics
> I proposed impossible, since an isomorphism test depends strongly
> on MAPHASH.  (Or, before EQUAL is applied to test for isomorphism,
> normalize the two tables by performing a full GC! :@)

I'm willing to have "EQUAL uncertainty" for "weak tables" if it's
decided that EQUAL traverses such things at all.

> Weak pointers are probably more useful than EQUAL isomorphism tests,
> but a reliable MAPHASH also seems indispensible.  Sounds to me
> like weakly-linked keys want to be another option to
> MAKE-HASH-TABLE.

Just so.  I did not want all tables to be that way, just for it to
possible to have some that were.

Cheers,
Jeff

Jeff Dalton,                      JANET: J.Dalton@uk.ac.ed             
AI Applications Institute,        ARPA:  J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University.             UUCP:  ...!ukc!ed.ac.uk!J.Dalton