HashBits, a lazy way

Andres Valloud sqrmax at comcast.net
Sun Jul 13 21:55:43 UTC 2003


Hello.

> >That Object is the <flag> used by WeakSet to mark empty spaces. I
> >was a bit surprised to see nils as well. Hmm...
> As I understand things, which may be not at all, the nils are put
> there by the GC when an element of a WeakArray is garbage collected.
> The flag objects are put there by the Set implementation to make
> empty spaces, so that they can be distinguished from the nils.

That's right.  When WeakSet scans to find objects, it has to treat nils
as if they were objects too.  Only when it finds the flag it knows that
the object isn't there.  For example, let's say the weak array inside of
it originally had

	weak#(... x1 x2 x3 x4 x5 x6 x7 ...)

and all the objects from x1 through x7 had the same hash.  So if you did
weakSet includes: x7 it would find x7 like a regular set would.  But
since this is a weak array, things can go away.  Let's say x5 went
away.  Then you'd have

	weak#(... x1 x2 x3 x4 nil x6 x7 ...)

Finding nil while scanning doesn't mean [stop], it means [something went
away] but possibly there's more stuff behind it because you haven't
found a free spot marked by the flag object (or an object with a
different hash), so you have to continue.  Then you'd find x7.

Andres.



More information about the Squeak-dev mailing list