Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.233.mcz
==================== Summary ====================
Name: Collections-ul.233
Author: ul
Time: 1 December 2009, 4:36:35 am
UUID: b5e9b392-4055-0e45-8a29-1eff47faa883
Ancestors: Collections-ul.232
Part 2 of WeakIdentityKeyDictionary hash change.
=============== Diff against Collections-ul.232 ===============
Item was changed:
----- Method: WeakIdentityKeyDictionary>>scanFor: (in category 'private') -----
scanFor: anObject
"Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements."
| index start |
- CollectionRehashingUtility quickRehashBecause: #weakIdentityKeyDictionaryScanForChanged.
index := start := anObject scaledIdentityHash \\ array size + 1.
[
| element |
((element := array at: index) == nil or: [ element key == anObject ])
ifTrue: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Item was changed:
Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.232.mcz
==================== Summary ====================
Name: Collections-ul.232
Author: ul
Time: 1 December 2009, 4:35:49 am
UUID: 775f15c4-da80-9b4a-bf1c-a909ad305387
Ancestors: Collections-ul.231
Part 1 of WeakIdentityKeyDictionary hash change.
Also removed previous preamble.
=============== Diff against Collections-ul.231 ===============
Item was changed:
----- Method: WeakIdentityKeyDictionary>>scanFor: (in category 'private') -----
scanFor: anObject
"Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements."
+ | index start |
+ CollectionRehashingUtility quickRehashBecause: #weakIdentityKeyDictionaryScanForChanged.
+ index := start := anObject scaledIdentityHash \\ array size + 1.
- | index start hash |
- array size >= 8192
- ifTrue: [ hash := anObject identityHash * (array size // 4096) ]
- ifFalse: [ hash := anObject identityHash ].
- index := start := hash \\ array size + 1.
[
| element |
((element := array at: index) == nil or: [ element key == anObject ])
ifTrue: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Item was changed:
Item was changed:
----- Method: WeakIdentityKeyDictionary>>scanForEmptySlotFor: (in category 'private') -----
scanForEmptySlotFor: anObject
"Scan the key array for the first slot containing an empty slot (indicated by a nil). Answer the index of that slot. This method will be overridden in various subclasses that have different interpretations for matching elements."
+ | index start |
+ index := start := anObject scaledIdentityHash \\ array size + 1.
- | index start hash |
- array size >= 8192
- ifTrue: [ hash := anObject identityHash * (array size // 4096) ]
- ifFalse: [ hash := anObject identityHash ].
- index := start := hash \\ array size + 1.
[
(array at: index) ifNil: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.231.mcz
==================== Summary ====================
Name: Collections-ul.231
Author: ul
Time: 1 December 2009, 4:33:38 am
UUID: 475eb0bf-076a-384b-8b7d-b7695f145442
Ancestors: Collections-ul.230
Part 2 of KeyedIdentitySet hash change.
=============== Diff against Collections-ul.230 ===============
Item was changed:
Item was changed:
----- Method: KeyedIdentitySet>>scanFor: (in category 'private') -----
scanFor: anObject
"Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements."
| index start |
- CollectionRehashingUtility quickRehashBecause: #keyedIdentitySetScanForChanged.
index := start := anObject scaledIdentityHash \\ array size + 1.
[
| element |
((element := array at: index) == nil or: [ (keyBlock value: element) == anObject ])
ifTrue: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.230.mcz
==================== Summary ====================
Name: Collections-ul.230
Author: ul
Time: 1 December 2009, 4:32:14 am
UUID: 9130582b-780e-8f4d-9daa-ca90b6b15da3
Ancestors: Collections-ul.229
Part 1 of KeyedIdentitySet hash change.
Also removed previous preamble.
=============== Diff against Collections-ul.229 ===============
Item was changed:
----- Method: KeyedIdentitySet>>scanForEmptySlotFor: (in category 'private') -----
scanForEmptySlotFor: anObject
"Scan the key array for the first slot containing an empty slot (indicated by a nil). Answer the index of that slot. This method will be overridden in various subclasses that have different interpretations for matching elements."
+ | index start |
+ index := start := anObject scaledIdentityHash \\ array size + 1.
- | index start hash |
- array size >= 8192
- ifTrue: [ hash := anObject identityHash * (array size // 4096) ]
- ifFalse: [ hash := anObject identityHash ].
- index := start := hash \\ array size + 1.
[
(array at: index) ifNil: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Item was changed:
Item was changed:
----- Method: KeyedIdentitySet>>scanFor: (in category 'private') -----
scanFor: anObject
"Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements."
+ | index start |
+ CollectionRehashingUtility quickRehashBecause: #keyedIdentitySetScanForChanged.
+ index := start := anObject scaledIdentityHash \\ array size + 1.
- | index start hash |
- array size >= 8192
- ifTrue: [ hash := anObject identityHash * (array size // 4096) ]
- ifFalse: [ hash := anObject identityHash ].
- index := start := hash \\ array size + 1.
[
| element |
((element := array at: index) == nil or: [ (keyBlock value: element) == anObject ])
ifTrue: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.229.mcz
==================== Summary ====================
Name: Collections-ul.229
Author: ul
Time: 1 December 2009, 4:29:44 am
UUID: 24338770-dc79-094d-9c95-97e9d65cfab4
Ancestors: Collections-ul.228
Part 2 of IdentityDictionary hash change.
=============== Diff against Collections-ul.228 ===============
Item was changed:
----- Method: IdentityDictionary>>scanFor: (in category 'private') -----
scanFor: anObject
"Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements."
+ | index start |
- | index start |
- CollectionRehashingUtility quickRehashBecause: #identityDictionaryScanForChanged.
index := start := anObject scaledIdentityHash \\ array size + 1.
[
| element |
((element := array at: index) == nil or: [ element key == anObject ])
ifTrue: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Item was added:
Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.228.mcz
==================== Summary ====================
Name: Collections-ul.228
Author: ul
Time: 1 December 2009, 4:28:09 am
UUID: f703f0eb-7da9-a44e-b2c4-ec682d060db8
Ancestors: Collections-ul.217
Part 1 of IdentityDictionary hash change.
Also removed previous postscript.
=============== Diff against Collections-ul.217 ===============
Item was changed:
----- Method: IdentityDictionary>>scanFor: (in category 'private') -----
scanFor: anObject
"Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements."
+ | index start |
+ CollectionRehashingUtility quickRehashBecause: #identityDictionaryScanForChanged.
+ index := start := anObject scaledIdentityHash \\ array size + 1.
- | index start hash |
- array size >= 8192
- ifTrue: [ hash := anObject identityHash * (array size // 4096) ]
- ifFalse: [ hash := anObject identityHash ].
- index := start := hash \\ array size + 1.
[
| element |
((element := array at: index) == nil or: [ element key == anObject ])
ifTrue: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Item was changed:
----- Method: IdentityDictionary>>scanForEmptySlotFor: (in category 'private') -----
scanForEmptySlotFor: anObject
"Scan the key array for the first slot containing an empty slot (indicated by a nil). Answer the index of that slot. This method will be overridden in various subclasses that have different interpretations for matching elements."
+ | index start |
+ index := start := anObject scaledIdentityHash \\ array size + 1.
- | index start hash |
- array size >= 8192
- ifTrue: [ hash := anObject identityHash * (array size // 4096) ]
- ifFalse: [ hash := anObject identityHash ].
- index := start := hash \\ array size + 1.
[
(array at: index) ifNil: [ ^index ].
(index := index \\ array size + 1) = start ] whileFalse.
self errorNoFreeSpace!
Item was changed:
Andreas Raab uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.314.mcz
==================== Summary ====================
Name: Kernel-ul.314
Author: ul
Time: 1 December 2009, 4:23:11 am
UUID: e293d76b-d182-a44c-b21f-1819da8fa9ec
Ancestors: Kernel-ul.313
Removed preamble.
=============== Diff against Kernel-ul.313 ===============
Andreas Raab uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.313.mcz
==================== Summary ====================
Name: Kernel-ul.313
Author: ul
Time: 1 December 2009, 4:22:35 am
UUID: 46ec2793-b46f-fa4c-9149-63e980f5625f
Ancestors: Kernel-ul.312
Part 2 of updating Object >> #hash.
=============== Diff against Kernel-ul.312 ===============
Item was changed:
----- Method: Object>>hash (in category 'comparing') -----
hash
"Answer a SmallInteger whose value is related to the receiver's identity.
May be overridden, and should be overridden in any classes that define = "
- CollectionRehashingUtility quickRehashBecause: #objectHashChanged.
^self scaledIdentityHash!
Andreas Raab uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.312.mcz
==================== Summary ====================
Name: Kernel-ul.312
Author: ul
Time: 1 December 2009, 4:19:45 am
UUID: 5b9007f4-b0f3-1e42-bf32-5a0efbeaae0f
Ancestors: Kernel-nice.307
Added #scaledIdentityHash.
Part 1 of updating Object >> hash.
=============== Diff against Kernel-nice.307 ===============
Item was added:
+ ----- Method: SmallInteger>>scaledIdentityHash (in category 'comparing') -----
+ scaledIdentityHash
+ "For identityHash values returned by primitive 75, answer
+ such values times 2^18. Otherwise, match the existing
+ identityHash implementation"
+
+ ^self!
Item was added:
+ ----- Method: ProtoObject>>scaledIdentityHash (in category 'comparing') -----
+ scaledIdentityHash
+ "For identityHash values returned by primitive 75, answer
+ such values times 2^18. Otherwise, match the existing
+ identityHash implementation"
+
+ ^self identityHash * 262144 "bitShift: 18"!
Item was changed:
----- Method: Object>>hash (in category 'comparing') -----
hash
"Answer a SmallInteger whose value is related to the receiver's identity.
May be overridden, and should be overridden in any classes that define = "
+ CollectionRehashingUtility quickRehashBecause: #objectHashChanged.
+ ^self scaledIdentityHash!
- ^ self identityHash!
Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.217.mcz
==================== Summary ====================
Name: Collections-ul.217
Author: ul
Time: 30 November 2009, 4:47:54 am
UUID: a67f6177-4f3f-bd41-af32-c1881c7f0e20
Ancestors: Collections-ul.216
Replace sends of #scanForEmptySlotFor: with #scanFor:. This enables atomic changes of the hash implementation.
=============== Diff against Collections-dtl.214 ===============
Item was added:
+ ----- Method: CollectionRehashingUtility>>rehashAllSets (in category 'private - rehashing') -----
+ rehashAllSets
+
+ HashedCollection rehashAll!
Item was added:
+ ----- Method: CollectionRehashingUtility class>>rehashBecause: (in category 'rehashing') -----
+ rehashBecause: aSymbol
+
+ self new rehashBecause: aSymbol!
Item was changed:
----- Method: KeyedSet>>noCheckNoGrowFillFrom: (in category 'private') -----
noCheckNoGrowFillFrom: anArray
"Add the elements of anArray except nils to me assuming that I don't contain any of them, they are unique and I have more free space than they require."
1 to: anArray size do: [ :index |
| object |
(object := anArray at: index) ifNotNil: [
array
+ at: (self scanFor: (keyBlock value: object))
- at: (self scanForEmptySlotFor: (keyBlock value: object))
put: object ] ]!
Item was added:
+ ----- Method: CollectionRehashingUtility>>changes (in category 'private - accessing') -----
+ changes
+
+ ^changes!
Item was added:
+ ----- Method: CollectionRehashingUtility>>quickRehashAllSets (in category 'private - rehashing') -----
+ quickRehashAllSets
+
+ HashedCollection withAllSubclassesDo:
+ [:class |
+ class = MethodDictionary ifFalse:
+ [class allInstances do: [:each | each rehash]]
+ ]!
Item was added:
+ ----- Method: CollectionRehashingUtility class>>new (in category 'instance creation') -----
+ new
+
+ self current notNil ifTrue: [^self current].
+ self current: super new initialize.
+ ^self current!
Item was changed:
----- Method: WeakSet>>noCheckNoGrowFillFrom: (in category 'private') -----
noCheckNoGrowFillFrom: anArray
"Add the elements of anArray except nils and flag to me assuming that I don't contain any of them, they are unique and I have more free space than they require."
tally := 0.
1 to: anArray size do: [ :index |
| object |
((object := anArray at: index) == flag or: [
object == nil ]) ifFalse: [
array
+ at: (self scanFor: object)
- at: (self scanForEmptySlotFor: object)
put: object.
tally := tally + 1 ] ]!
Item was changed:
----- Method: Set>>noCheckNoGrowFillFrom: (in category 'private') -----
noCheckNoGrowFillFrom: anArray
"Add the elements of anArray except nils to me assuming that I don't contain any of them, they are unique and I have more free space than they require."
1 to: anArray size do: [ :index |
| object |
(object := anArray at: index) ifNotNil: [
array
+ at: (self scanFor: object)
- at: (self scanForEmptySlotFor: object)
put: object ] ]!
Item was changed:
----- Method: Dictionary>>noCheckNoGrowFillFrom: (in category 'private') -----
noCheckNoGrowFillFrom: anArray
"Add the elements of anArray except nils to me assuming that I don't contain any of them, they are unique and I have more free space than they require."
1 to: anArray size do: [ :index |
| object |
(object := anArray at: index) ifNotNil: [
array
+ at: (self scanFor: object key)
- at: (self scanForEmptySlotFor: object key)
put: object ] ]!
Item was changed:
----- Method: WeakKeyDictionary>>noCheckNoGrowFillFrom: (in category 'private') -----
noCheckNoGrowFillFrom: anArray
"Add the elements of anArray except nils and flag to me assuming that I don't contain any of them, they are unique and I have more free space than they require."
tally := 0.
1 to: anArray size do:[ :i |
| association |
(association := anArray at: i) ifNotNil: [
array
+ at: (self scanFor: association key)
- at: (self scanForEmptySlotFor: association key)
put: association.
tally := tally + 1 ] ]!
Item was added:
+ ----- Method: CollectionRehashingUtility>>quickRehashBecause: (in category 'rehashing') -----
+ quickRehashBecause: aSymbol
+
+ (self changes includes: aSymbol) ifTrue: [^self].
+ self changes add: aSymbol.
+ self quickRehashAllSets!
Item was added:
+ ----- Method: CollectionRehashingUtility class>>current: (in category 'private - accessing') -----
+ current: anInstance
+
+ current := anInstance!
Item was changed:
----- Method: WeakSet>>do: (in category 'public') -----
do: aBlock
- | each |
tally = 0 ifTrue: [^self].
+ array do: [ :each |
+ (each == nil or: [each == flag])
+ ifFalse: [ aBlock value: each ] ]!
- 1 to: array size do:
- [:index |
- ((each := array at: index) == nil or: [each == flag])
- ifFalse: [aBlock value: each]
- ]!
Item was changed:
----- Method: WeakKeyDictionary>>finalizeValues: (in category 'finalization') -----
finalizeValues: finiObjects
"Remove all associations with key == nil and value is in finiObjects.
This method is folded with #rehash for efficiency."
| oldArray |
oldArray := array.
array := Array new: oldArray size.
tally := 0.
1 to: array size do:[ :i |
| association |
(association := oldArray at: i) ifNotNil: [
| key |
((key := association key) == nil and: [ "Don't let the key go away"
finiObjects includes: association value ])
ifFalse: [
array
+ at: (self scanFor: key)
- at: (self scanForEmptySlotFor: key)
put: association.
tally := tally + 1 ] ] ]!
Item was changed:
Item was added:
+ ----- Method: CollectionRehashingUtility>>rehashBecause: (in category 'rehashing') -----
+ rehashBecause: aSymbol
+
+ (self changes includes: aSymbol) ifTrue: [^self].
+ self changes add: aSymbol.
+ self rehashAllSets.
+ self rehashSymbolTable!
Item was changed:
----- Method: WeakKeyToCollectionDictionary>>noCheckNoGrowFillFrom: (in category 'as yet unclassified') -----
noCheckNoGrowFillFrom: anArray
"Add the elements of anArray except nils and associations with empty collections (or with only nils) to me assuming that I don't contain any of them, they are unique and I have more free space than they require."
tally := 0.
1 to: anArray size do:[ :i |
| association cleanedValue |
((association := anArray at: i) == nil or: [
(cleanedValue := association value copyWithout: nil) isEmpty ])
ifFalse: [
association value: cleanedValue.
array
+ at: (self scanFor: association key)
- at: (self scanForEmptySlotFor: association key)
put: association.
tally := tally + 1 ] ]!
Item was changed:
----- Method: Dictionary>>associationsDo: (in category 'enumerating') -----
associationsDo: aBlock
"Evaluate aBlock for each of the receiver's elements (key/value
associations)."
tally = 0 ifTrue: [ ^self].
+ array do: [ :each | each ifNotNil: [ aBlock value: each ] ]!
- 1 to: array size do: [ :index |
- | each |
- (each := array at: index)
- ifNotNil: [ aBlock value: each ] ]!
Item was added:
+ ----- Method: CollectionRehashingUtility class>>current (in category 'private - accessing') -----
+ current
+
+ ^current!
Item was added:
+ ----- Method: CollectionRehashingUtility>>initialize (in category 'private') -----
+ initialize
+
+ self changes: OrderedCollection new!
Item was added:
+ ----- Method: CollectionRehashingUtility>>rehashSymbolTable (in category 'private - rehashing') -----
+ rehashSymbolTable
+
+ Symbol rehash!
Item was changed:
----- Method: Set>>do: (in category 'enumerating') -----
do: aBlock
tally = 0 ifTrue: [ ^self ].
+ array do: [ :each | each ifNotNil: [ aBlock value: each ] ]!
- 1 to: array size do: [ :index |
- | each |
- (each := array at: index)
- ifNotNil: [ aBlock value: each ] ]!
Item was added:
+ Object subclass: #CollectionRehashingUtility
+ instanceVariableNames: 'changes'
+ classVariableNames: ''
+ poolDictionaries: ''
+ category: 'Collections-Unordered'!
+ CollectionRehashingUtility class
+ instanceVariableNames: 'current'!
Item was added:
+ ----- Method: CollectionRehashingUtility class>>quickRehashBecause: (in category 'rehashing') -----
+ quickRehashBecause: aSymbol
+
+ self new quickRehashBecause: aSymbol!
Item was added:
+ ----- Method: CollectionRehashingUtility>>changes: (in category 'private - accessing') -----
+ changes: aCollection
+ "aCollection must not be a hashed collection"
+
+ changes := aCollection!