Nicolas Cellier uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-nice.728.mcz
==================== Summary ====================
Name: Collections-nice.728 Author: nice Time: 14 December 2016, 8:01:20.748497 pm UUID: fcb31400-a826-4642-8ad1-83c813998ba9 Ancestors: Collections-ul.727, Collections-nice.723
Merge Collections-nice.723 (WeakIdentityDictionary)
=============== Diff against Collections-ul.727 ===============
Item was changed: ----- Method: IdentityDictionary>>keyAtValue:ifAbsent: (in category 'accessing') ----- keyAtValue: value ifAbsent: exceptionBlock "Answer the key that is the external name for the argument, value. If there is none, answer the result of evaluating exceptionBlock."
+ ^self keyAtIdentityValue: value ifAbsent: exceptionBlock! - ^super keyAtIdentityValue: value ifAbsent: exceptionBlock!
Item was added: + IdentityDictionary subclass: #WeakIdentityDictionary + instanceVariableNames: 'vacuum' + classVariableNames: '' + poolDictionaries: '' + category: 'Collections-Weak'! + + !WeakIdentityDictionary commentStamp: 'nice 10/27/2016 20:00' prior: 0! + I am a WeakIdentityDictionary, that is a dictionary pointing weakly to its associations of key->value pairs. + I am especially usefull for handling undeclared bindings that will be naturally garbage collected without having to scan all the CompiledMethods. + + Instance variables: + vacuum <Object> a unique object used for marking empty slots + + Due to usage of WeakArray for my own storage, reclaimed slots will be nilled out. + I cannot consider a nil slot as empty because of garbage collection does not fix collisions. + Thus I need to differentiate empty slots (vacuum) from garbaged collected slots (nil). + + If I did not reclaim the nil slots and make them vacuum again, then my capacity would grow indefinitely. + My strategy to avoid such growth is to randomly cleanup the garbage collected slot encountered when scanning for a key. + It should mitigate the growth since this method is used when adding a new entry. + + Due to those not yet cleaned-up nil slots I might over-estimate my size. Don't take it too literally.!
Item was added: + ----- Method: WeakIdentityDictionary class>>arrayType (in category 'private') ----- + arrayType + ^ WeakArray!
Item was added: + ----- Method: WeakIdentityDictionary>>add: (in category 'accessing') ----- + add: anAssociation + + | index | + index := self scanFor: anAssociation key. + (array at: index) + ifNil: [ self atNewIndex: index put: anAssociation ] + ifNotNil: [ :element | + element == vacuum + ifTrue: [ self atNewIndex: index put: anAssociation ] + ifFalse: [ element value: anAssociation value ] ]. + ^anAssociation!
Item was added: + ----- Method: WeakIdentityDictionary>>associationAt:ifAbsent: (in category 'accessing') ----- + associationAt: key ifAbsent: aBlock + "Answer the association with the given key. + If key is not found, return the result of evaluating aBlock." + + ^((array at: (self scanFor: key)) + ifNil: [ aBlock value ] + ifNotNil: [:association | + association == vacuum + ifTrue: [ aBlock value ] + ifFalse: [ association ] ])!
Item was added: + ----- Method: WeakIdentityDictionary>>associationsDo: (in category 'enumerating') ----- + associationsDo: aBlock + "Evaluate aBlock for each of the receiver's elements (key/value + associations)." + + tally = 0 ifTrue: [ ^self]. + 1 to: array size do: [ :index | + (array at: index) ifNotNil: [ :element | + element == vacuum ifFalse: [ aBlock value: element ] ] ]!
Item was added: + ----- Method: WeakIdentityDictionary>>at:ifAbsent: (in category 'accessing') ----- + at: key ifAbsent: aBlock + "Answer the value associated with the key or, if key isn't found, + answer the result of evaluating aBlock." + + ^((array at: (self scanFor: key)) + ifNil: [ aBlock ] + ifNotNil: [:association | + association == vacuum + ifTrue: [ aBlock ] + ifFalse: [ association ] ]) value "Blocks and Associations expect #value"!
Item was added: + ----- Method: WeakIdentityDictionary>>at:ifPresent:ifAbsentPut: (in category 'accessing') ----- + at: key ifPresent: oneArgBlock ifAbsentPut: absentBlock + "Lookup the given key in the receiver. If it is present, answer the value of + evaluating oneArgBlock with the value associated with the key. Otherwise + add the value of absentBlock under the key, and answer that value." + + | index value | + index := self scanFor: key. + (array at: index) ifNotNil: + [:element| + element == vacuum ifFalse: [^oneArgBlock value: element value] ]. + value := absentBlock value. + self atNewIndex: index put: (self associationClass key: key value: value). + ^value!
Item was added: + ----- Method: WeakIdentityDictionary>>at:put: (in category 'accessing') ----- + at: key put: anObject + "Set the value at key to be anObject. If key is not found, create a + new entry for key and set is value to anObject. Answer anObject." + + | index | + index := self scanFor: key. + (array at: index) + ifNil: + ["it's possible to get here if the association just died" + self atNewIndex: index put: (self associationClass key: key value: anObject) ] + ifNotNil: [ :association | + association == vacuum + ifTrue: [ self atNewIndex: index put: (self associationClass key: key value: anObject) ] + ifFalse: [association value: anObject ] ]. + ^anObject!
Item was added: + ----- Method: WeakIdentityDictionary>>cleanupIndex: (in category 'private') ----- + cleanupIndex: anInteger + array at: anInteger put: vacuum. + tally := tally - 1. + self fixCollisionsFrom: anInteger.!
Item was added: + ----- Method: WeakIdentityDictionary>>fixCollisionsFrom: (in category 'private') ----- + fixCollisionsFrom: start + "The element at start has been removed and replaced by vacuum. + 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)) == vacuum ] whileFalse: [ + element + ifNil: + [ "The binding at this slot was reclaimed - finish the cleanup" + array at: index put: vacuum. + tally := tally - 1 ] + ifNotNil: + [| newIndex | + (newIndex := self scanWithoutGarbagingFor: element key) = index ifFalse: [ + array + at: newIndex put: element; + at: index put: vacuum ] ] ]!
Item was added: + ----- Method: WeakIdentityDictionary>>growTo: (in category 'private') ----- + growTo: anInteger + "Grow the elements array and reinsert the old elements" + + | oldElements | + oldElements := array. + array := self class arrayType new: anInteger withAll: vacuum. + self noCheckNoGrowFillFrom: oldElements!
Item was added: + ----- Method: WeakIdentityDictionary>>includesKey: (in category 'testing') ----- + includesKey: key + "Answer whether the receiver has a key equal to the argument, key." + + ^(array at: (self scanFor: key)) + ifNil: + ["it just has been reclaimed" + false] + ifNotNil: [:element | element ~~ vacuum]!
Item was added: + ----- Method: WeakIdentityDictionary>>initialize: (in category 'private') ----- + initialize: n + vacuum := Object new. + array := self class arrayType new: n withAll: vacuum. + tally := 0!
Item was added: + ----- Method: WeakIdentityDictionary>>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 | + (anArray at: index) ifNotNil: [ :association | + association == vacuum + ifFalse: [array + at: (self scanForEmptySlotFor: association key) + put: association ] ] ]!
Item was added: + ----- Method: WeakIdentityDictionary>>postCopy (in category 'copying') ----- + postCopy + "Beware: do share the bindings, so changing a binding value in the copy will also change it in the original. + Copying the bindings would not make sense: we hold weakly on them, so they would die at first garbage collection." + + | oldVacuum | + super postCopy. + oldVacuum := vacuum. + vacuum := Object new. + array := array collect: [ :association | + association ifNotNil: [ + association == oldVacuum + ifTrue: [ vacuum ] + ifFalse: [ association ] ] ]!
Item was added: + ----- Method: WeakIdentityDictionary>>removeKey:ifAbsent: (in category 'removing') ----- + removeKey: key ifAbsent: aBlock + "Remove key (and its associated value) from the receiver. If key is not in + the receiver, answer the result of evaluating aBlock. Otherwise, answer + the value externally named by key." + + | index association | + index := self scanFor: key. + (association := (array at: index)) == vacuum ifTrue: [ ^aBlock value ]. + self cleanupIndex: index. + ^association value!
Item was added: + ----- Method: WeakIdentityDictionary>>scanFor: (in category 'private') ----- + scanFor: anObject + "Scan the array for the first slot containing either + - a vacuum object indicating an empty slot + - or a binding whose key matches anObject. + Answer the index of that slot or raise an error if no slot is found. + When garbage collected slots are encountered, perform a clean-up." + + | index start rescan | + [ + rescan := false. + index := start := anObject scaledIdentityHash \ array size + 1. + [ + (array at: index) + ifNil: + ["Object at this slot has been garbage collected. + A rescan is necessary because fixing collisions + might have moved the target before current index." + self cleanupIndex: index. + rescan := true] + ifNotNil: + [:element | (element == vacuum or: [ element key == anObject ]) + ifTrue: [ ^index ]. + (index := index \ array size + 1) = start ] ] whileFalse. + rescan ] whileTrue. + self errorNoFreeSpace!
Item was added: + ----- Method: WeakIdentityDictionary>>scanForEmptySlotFor: (in category 'private') ----- + scanForEmptySlotFor: anObject + "Scan the array for the first empty slot marked by vacuum object. + Answer the index of that slot or raise an error if no slot is found. + Ignore the slots that have been garbage collected (those containing nil)." + + | index start | + index := start := anObject scaledIdentityHash \ array size + 1. + [ + (array at: index) + ifNotNil: + [:element | element == vacuum ifTrue: [ ^index ] ]. + (index := index \ array size + 1) = start ] whileFalse. + self errorNoFreeSpace!
Item was added: + ----- Method: WeakIdentityDictionary>>scanWithoutGarbagingFor: (in category 'private') ----- + scanWithoutGarbagingFor: anObject + "Scan the array for the first slot containing either + - a vacuum object indicating an empty slot + - or a binding whose key matches anObject. + Answer the index of that slot or raise an error if no slot is found. + Ignore the slots that have been garbage collected (those containing nil)" + + | index start | + index := start := anObject scaledIdentityHash \ array size + 1. + [ + (array at: index) + ifNotNil: + [:element | (element == vacuum or: [ element key == anObject ]) + ifTrue: [ ^index ] ]. + (index := index \ array size + 1) = start ] whileFalse. + self errorNoFreeSpace!
Item was changed: + ----- Method: WeakSet class>>arrayType (in category 'private') ----- - ----- Method: WeakSet class>>arrayType (in category 'as yet unclassified') ----- arrayType
^WeakArray!