[Gc] Re: Weak hash tables and cycles

Ludovic Courtès ludo at gnu.org
Tue Nov 4 00:50:52 PST 2008


Hi,

"Bruce Hoult" <bruce at hoult.org> writes:

> On Tue, Nov 4, 2008 at 11:30 AM, Ludovic Courtès <ludo at gnu.org> wrote:
>> Hi,
>>
>> Is it possible to implement a weak-key hash table that can deal with
>> cycles using disappearing links?
>>
>> I'm in particular concerned with the following corner case: K is a key
>> in a weak-key hash table, V is its associated value, and V references K.
>> This leads to the following object graph, where the dotted arrow denotes
>> a disappearing link:
>>
>>  .---.      .---.
>>  | K |<-----| V |
>>  `---'      `---'
>>    ^          ^
>>    :          |
>>    :          |
>>  .--------------.
>>  |   weak-key   |
>>  |  hash table  |
>>  `--------------'
>>
>> Neither K nor V can become unreachable in such a case, even if none of
>> them is referenced elsewhere.
>
> But surely this is the behaviour you want, as otherwise you would use
> a  hash table where both keys and values are weak.

This is not necessarily the desired behavior when V is the only
reference to K.

Under Guile's current GC, which is "weak hash table aware", K becomes
unreachable when V is the only reference to it.  To achieve this, the GC
marks values of weak-key hash tables only once it has determined which
keys are reachable.

Thanks,
Ludovic.



More information about the Gc mailing list