2009/11/13 Andreas Raab <andreas.raab at gmx.de>:
> Hi -
>
> I just noticed a subtle bug in Set>>fixCollisionsFrom: namely here:
>
> [ (element := self keyAt: (index := index \\ array size + 1)) == nil ]
> whileFalse: [...].
>
> The problem is that the usage of #keyAt: is incorrect here for Set
> subclasses (i.e., Dictionary). We don't want to stop when the *key* is nil
> (which can happen in Dictionaries) but rather when the *set entry* is nil.
> To illustrate the problem, here is the test that I just put into trunk:
>
> testNilHashCollision
>        "Ensures that fixCollisionsFrom: does the right thing in the presence
> of a nil key"
>        | dict key |
>        dict := Dictionary new.
>        key := nil hash. "any key with same hash as nil"
>        dict at: key put: 1.
>        dict at: nil put: 2.
>        self assert: (dict includesKey: nil).
>        dict removeKey: key.
>        self assert: (dict includesKey: nil).
>
> I'm not sure if this is an old problem or got broken recently (there were
> various changes for faster sets etc).
>

Aye, i finally got what it means :)
Here the fix (i suppose).

fixCollisionsFrom: start
	"The element at start has been removed and replaced by nil.
	This method moves forward from there, relocating any entries
	that had been placed below due to collisions with this one."

	| element index |
	index := start.
	[ (element := array at: (index := index \\ array size + 1)) == nil ]
whileFalse: [
		| newIndex |
		(newIndex := self scanFor: ( self keyOfElement: element ) = index ifFalse: [
			self swap: index with: newIndex ] ]

where:

Set >> keyOfElement: elem
  ^ elem

and

Dictionary >> keyOfElement: elem
  ^ elem key

and we can get rid of #keyAt:


> Cheers,
>  - Andreas
>
>



-- 
Best regards,
Igor Stasenko AKA sig.