[squeak-dev] The Trunk: Collections-ar.138.mcz

Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ar.138.mcz

==================== Summary ====================

Name: Collections-ar.138
Author: ar
Time: 29 September 2009, 9:53:28 am
UUID: 8eeaf535-25df-3346-aa33-59540513b74b
Ancestors: Collections-nice.136, Collections-ul.137

Merging Collections-ul.137:

- prepare for a new #grow and #rehash implementation for Set and its subclasses (except MethodDictionary). Add #noCheckNoGrowFillFrom:, #scanForEmptySlotFor: and #growTo: to these classes.
- fix: adding Objects with the usual 12-bit #identityHash to a KeyedIdentitySet became O(n^2) when the set size reached 4096 (#scanFor:).
- other minor changes (#scanFor:, #keysDo:)

=============== Diff against Collections-nice.136 ===============

Item was changed:
  ----- Method: Set>>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 zero if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements."
- | element start finish |
- finish := array size.
- start := (anObject hash \\ finish) + 1.
-
- "Search from (hash mod size) to the end."
- start to: finish do:
- [:index | ((element := array at: index) == nil or: [element = anObject])
- ifTrue: [^ index ]].
-
- "Search from 1 to where we started."
- 1 to: start-1 do:
- [:index | ((element := array at: index) == nil or: [element = anObject])
- ifTrue: [^ index ]].
 
+ | element start |
+ start := (anObject hash \\ array size) + 1.
+
+ "Search from (hash mod size) to the end."
+ start to: array size do: [ :index |
+ ((element := array at: index) == nil or: [ element = anObject ])
+ ifTrue: [ ^index ] ].
+
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ ((element := array at: index) == nil or: [ element = anObject ])
+ ifTrue: [ ^index ] ].
+
+ ^0  "No match AND no empty slot"!
- ^ 0  "No match AND no empty slot"!

Item was added:
+ ----- Method: IdentitySet>>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."
+
+ | finish hash start |
+ (finish := array size) > 4096
+ ifTrue: [ hash := anObject identityHash * (finish // 4096) ]
+ ifFalse: [ hash := anObject identityHash ].
+ start := hash \\ finish + 1.
+ "Search from (hash mod size) to the end."
+ start to: finish do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ self error: 'There is no free space in this collection!!'!

Item was added:
+ ----- 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 scanForEmptySlotFor: (keyBlock value: object))
+ put: object ] ]!

Item was added:
+ ----- 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."
+
+ | finish hash start |
+ (finish := array size) > 4096
+ ifTrue: [ hash := anObject identityHash * (finish // 4096) ]
+ ifFalse: [ hash := anObject identityHash ].
+ start := hash \\ finish + 1.
+ "Search from (hash mod size) to the end."
+ start to: finish do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ self error: 'There is no free space in this collection!!'!

Item was added:
+ ----- 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 scanForEmptySlotFor: object)
+ put: object.
+ tally := tally + 1 ] ]!

Item was added:
+ ----- Method: WeakSet>>scanForEmptySlotFor: (in category 'private') -----
+ scanForEmptySlotFor: anObject
+ "Scan the key array for the first slot containing an empty slot (indicated by flag or a nil). Answer the index of that slot. This method will be overridden in various subclasses that have different interpretations for matching elements."
+
+ | start element |
+ start := anObject hash \\ array size + 1.
+ "Search from (hash mod size) to the end."
+ start to: array size do: [ :index |
+ ((element := array at: index) == flag or: [ element == nil ]) ifTrue: [ ^index ] ].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ ((element := array at: index) == flag or: [ element == nil ]) ifTrue: [ ^index ] ].
+ self error: 'There is no free space in this collection!!'!

Item was added:
+ ----- 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 scanForEmptySlotFor: object)
+ put: object ] ]!

Item was added:
+ ----- 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 scanForEmptySlotFor: object key)
+ put: object ] ]!

Item was added:
+ ----- 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."
+
+ | finish hash start |
+ (finish := array size) > 4096
+ ifTrue: [ hash := anObject identityHash * (finish // 4096) ]
+ ifFalse: [ hash := anObject identityHash ].
+ start := hash \\ finish + 1.
+ "Search from (hash mod size) to the end."
+ start to: finish do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ self error: 'There is no free space in this collection!!'!

Item was added:
+ ----- 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 scanForEmptySlotFor: association key)
+ put: association.
+ tally := tally + 1 ] ]!

Item was changed:
  ----- Method: PluggableDictionary>>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 zero if no slot
+ is found. This  method will be overridden in various subclasses that have different
+ interpretations for matching elements."
+
+ | element start |
- "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 zero if no slot is found. This  method will be
- overridden  
- in various subclasses that have different interpretations for matching
-  
- elements."
- | element start finish |
  start := (hashBlock ifNil: [anObject hash]
  ifNotNil: [hashBlock value: anObject])
  \\ array size + 1.
- finish := array size.
  "Search from (hash mod size) to the end."
+ start to: array size do: [:index | ((element := array at: index) == nil or:
- start to: finish do: [:index | ((element := array at: index) == nil or:
- [equalBlock ifNil: [element key = anObject]
- ifNotNil: [equalBlock value: element key value: anObject]])
- ifTrue: [^ index]].
- "Search from 1 to where we started."
- 1 to: start - 1 do: [:index | ((element := array at: index) == nil or:
  [equalBlock ifNil: [element key = anObject]
  ifNotNil: [equalBlock value: element key value: anObject]])
  ifTrue: [^ index]].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [:index | ((element := array at: index) == nil or:
+ [equalBlock ifNil: [element key = anObject]
+ ifNotNil: [equalBlock value: element key value: anObject]])
+ ifTrue: [^ index]].
  ^ 0"No match AND no empty slot"!

Item was added:
+ ----- Method: Set>>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."
+
+ | start |
+ start := anObject hash \\ array size + 1.
+ "Search from (hash mod size) to the end."
+ start to: array size do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ self error: 'There is no free space in this collection!!'!

Item was changed:
  ----- Method: WeakKeyDictionary>>keysDo: (in category 'accessing') -----
  keysDo: aBlock
  "Evaluate aBlock for each of the receiver's keys."
+
+ self associationsDo: [ :association |
+ | key |
+ (key := association key) ifNotNil: [
+ aBlock value: key ] ].!
- self associationsDo: [:association |
- association key ifNotNil:[aBlock value: association key]].!

Item was added:
+ ----- 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 scanForEmptySlotFor: association key)
+ put: association.
+ tally := tally + 1 ] ]!

Item was changed:
  ----- Method: PluggableSet>>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 zero if no slot
+ is found. This  method will be overridden in various subclasses that have different interpretations for matching elements."
+ | element start |
+ start := (hashBlock
+ ifNil: [ anObject hash ]
+ ifNotNil: [ hashBlock value: anObject ]) \\ array size + 1.
- "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 zero if no slot is found. This  method will be
- overridden  
- in various subclasses that have different interpretations for matching
-  
- elements."
- | element start finish |
- start := (hashBlock ifNil: [anObject hash]
- ifNotNil: [hashBlock value: anObject])
- \\ array size + 1.
- finish := array size.
  "Search from (hash mod size) to the end."
+ start to: array size do: [:index | ((element := array at: index) == nil or:
- start to: finish do: [:index | ((element := array at: index) == nil or:
- [equalBlock ifNil: [element = anObject]
- ifNotNil: [equalBlock value: element value: anObject]])
- ifTrue: [^ index]].
- "Search from 1 to where we started."
- 1 to: start - 1 do: [:index | ((element := array at: index) == nil or:
  [equalBlock ifNil: [element = anObject]
  ifNotNil: [equalBlock value: element value: anObject]])
  ifTrue: [^ index]].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [:index | ((element := array at: index) == nil or:
+ [equalBlock ifNil: [element = anObject]
+ ifNotNil: [equalBlock value: element value: anObject]])
+ ifTrue: [^ index]].
  ^ 0"No match AND no empty slot"!

Item was added:
+ ----- 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."
+
+ | finish hash start |
+ (finish := array size) > 4096
+ ifTrue: [ hash := anObject identityHash * (finish // 4096) ]
+ ifFalse: [ hash := anObject identityHash ].
+ start := hash \\ finish + 1.
+ "Search from (hash mod size) to the end."
+ start to: finish do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ self error: 'There is no free space in this collection!!'!

Item was added:
+ ----- Method: PluggableDictionary>>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."
+
+ | start |
+ start := (hashBlock
+ ifNil: [ anObject hash ]
+ ifNotNil: [ hashBlock value: anObject ]) \\ array size + 1.
+ "Search from (hash mod size) to the end."
+ start to: array size do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ self error: 'There is no free space in this collection!!'!

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 zero if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements."
- "Same as super except change = to ==, and hash to identityHash"
-
- | element start finish |
- finish := array size.
- start := (anObject identityHash \\ finish) + 1.
-
 
+ | element hash start finish |
+ finish := array size.
+ finish > 4096
+ ifTrue: [ hash := anObject identityHash * (finish // 4096) ]
+ ifFalse: [ hash := anObject identityHash ].
+ start := hash \\ finish + 1.
+
  "Search from (hash mod size) to the end."
  start to: finish do:
  [:index | ((element := array at: index) == nil or: [(keyBlock value: element) == anObject])
  ifTrue: [^ index ]].
 
  "Search from 1 to where we started."
  1 to: start-1 do:
  [:index | ((element := array at: index) == nil or: [(keyBlock value: element) == anObject])
  ifTrue: [^ index ]].
 
  ^ 0  "No match AND no empty slot"!

Item was added:
+ ----- Method: PluggableSet>>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."
+
+ | start |
+ start := (hashBlock
+ ifNil: [ anObject hash ]
+ ifNotNil: [ hashBlock value: anObject ]) \\ array size + 1.
+ "Search from (hash mod size) to the end."
+ start to: array size do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ "Search from 1 to where we started."
+ 1 to: start - 1 do: [ :index |
+ (array at: index) ifNil: [ ^index ] ].
+ self error: 'There is no free space in this collection!!'!

Item was added:
+ ----- Method: Set>>growTo: (in category 'private') -----
+ growTo: anInteger
+ "Grow the elements array and reinsert the old elements"
+
+ | oldElements |
+ oldElements := array.
+ array := Array new: anInteger.
+ self noCheckNoGrowFillFrom: oldElements!