[plt-scheme] Red black trees in PLT Scheme

On Fri, Jul 24, 2009 at 3:11 AM, Noel Welsh<noelwelsh at gmail.com> wrote:
> On Fri, Jul 24, 2009 at 5:52 AM, Andrew
> Reilly<andrew-scheme at areilly.bpc-users.org> wrote:
>
>> What I wonder, though, is: will this work at all?  Is the
>> eq-hash-code of a struct stable across garbage collections?  I
>> had assumed that eq-hash-code was somehow derived from the
>> memory address of the argument object, but the 3m version of
>> PLT uses a copying collector, I believe, so object locations can
>> change over time.  That could result in the "order" in my r-b
>> tree becoming wrong (and searches failing) over time.
>
> I believe that the GC maintains a table mapping objects to hash codes,
> and this is updated whenever an object is moved. I don't recall where
> I got this idea from, so it might be PLT doesn't work this way and I'm
> thinking of a different language implementation.

PLT stores eq hash codes in extra bits in the GC metadata (how many
depends on your platform).  The codes are stable -- they don't change
as GC happens, though they are not guaranteed unique.

PLT's immutable hash tables are, in fact, implemented as red-black
trees over hash codes.

--Carl